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:
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 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
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.
Obligations
- You have to write a report with the name “Report_HW1.pdf” explaining your HW (purpose, how did you solve it, what complexity you have, etc.) and which environment you used (Eclipse, NetBeans, for example). The person who reads your report can easily use the class you have written.
- Submissions should be in the form of a zip/rar. When extracted, the result should be a single folder with the name “Group_ID” (where ID is the number of your group which assigned for your cluster,
check https://docs.google.com/spreadsheets/d/173IvOMQZXzuKFR7w5oIu0rTovfEyTR DC_EsVz039Jlk/edit?usp=sharing%20 if you do not know )
