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
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.
check https://docs.google.com/spreadsheets/d/173IvOMQZXzuKFR7w5oIu0rTovfEyTR DC_EsVz039Jlk/edit?usp=sharing%20 if you do not know )
- All assignments will be checked via Moss (for more info https://theory.stanford.edu/~aiken/moss ). Therefore be honest and do your assignment with only your group.
- Add a 3×2 table in your report and explain contributions as a percent of each member of a group. Example :
| Dilara | Hercan | Halit Kaan |
| 35 % | 35 % | 30 % |
