DATA - Homework I - Recursive Functions  - Solved

Fill the table for the each given algorithm, is recursive is a good or bad solution?  (Just add a X) 

Copy/paste this table to your report and fill the blanks 

 
Good 
Bad 
Computing Fibonacci Sequence 
 
 
Towers of Hanoi (Search for it if you don’t know the problem) 
 
 
Computing factorial of a given number 
 
 
An autonomous robot 

looking for a way out of an 

unmapped maze 
 
 
In this homework, you are required to design a Sudoku-like game environment and program using a recursive approach.  Instead of integers, your app should run given keys:  

CNGBIM213 

 

Your program will work on the command line where the commands are given in one line as: (C for create and, S for solve) 

 

 

C :  Generates a 3x3 puzzle randomly, and prints out it on screen.  

 

Here is a some examples of a crated puzzle:  

 

 
C 
 
 
N 
 
 
 
 
 
 
 
 
 
1 
G 
 
 
 
 
 
B 
I 
 
 
C 
M 
C 
 
 
 
 
G 
 
 
 
 
 
 
 
 
 
 
2 
N 
 
 
3 
 
 
 
 
B 
 
M 
2 
 
I 
 
 
 
G 
 
 
B 
N 
 
 
 
M 
 
 
 
 
 
3 
 
2 
 
 
 
 

S : Solves the generated puzzle with a recursive brute force approach. 

 

I 
C 
2 
G 
2 
M 
B 
3 
1 
B 
3 
M 
C 
2 
1 
G 
N 
I 
N 
1 
G 
B 
I 
3 
2 
C 
M 
C 
N 
B 
2 
1 
G 
I 
M 
3 
1 
G 
I 
M 
3 
B 
C 
2 
N 
2 
M 
3 
N 
C 
I 
1 
B 
G 
M 
2 
1 
I 
B 
N 
3 
G 
C 
3 
B 
N 
1 
G 
C 
M 
I 
2 
G 
I 
C 
3 
M 
2 
N 
1 
B 
 

             

Hints 

In case you do not know the rules of Sudoku  

•        https://en.wikipedia.org/wiki/Sudoku 

This program should create and solve puzzles in a similar manner.  

•        In case you do not know what is the brute force approach https://en.wikipedia.org/wiki/Brute-force_search 

•        The purpose of this homework is to build a recursive search algorithm. Thus, you are free to utilize any proper data structure to store your puzzle e.g. a char array.  

•        Here is some solutions, you may adopt solutions on web, but explain how your code work in your report.

http://web.eecs.utk.edu/~bvanderz/cs140/Notes/Sudoku/ https://www.heimetli.ch/ffh/simplifiedsudoku.html 

However, you also need another function to build a Sudoku problem. Therefore, build two classes named:   

•        SudokuCreater

•        SudokuSolver

Also, build an interface to run such classes.

 There are several ways to build a puzzle. Such as  

•        First, you should assign a random variable in a cell, then keep it going until to reach enough number of hints to solve the rest  

•        Another method is to build a completed puzzle, then erase variables from cells until a minimum number of hint to solve the rest

•        or find your own way (and explain it in your report)

  

In this step, you might get clues from Sudoku builder sample codes from web searches.  

  

•        A generated puzzle can only have one (1) possible solution.
Dilara 
Hercan 
Halit Kaan 
 35 %  
35 % 
30 %