Description
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:
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 3×3 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.
