| CodeTiger
| | Joined: 18 May 2006 | | Posts: 2 | | : | | Location: chennai |
Items |
|
 Posted: Thu May 18, 2006 1:40 pm Post subject: Solver Logic for sudoku mobile game developer |
 |
|
Solver Logic for sudoku mobile game developer
Writing Sudoku solver is not a great task, but when it comes to writing it for a mobile phone it is really hard to choose which algorithm to use. We were in a bad situation to decide whether to write 1000s of lines and reduce the CPU power conception, or to write the most compact code. Considering a mobile phone which commonly has just 100 -200 MHz CPU and 100 kb memory, we finally decided to code in hardest way to solve sudoku which most programmers do not prefer. “Solving Sudoku by logic”, it is very similar how a human thinks when solving sudoku. We have implemented 4 methods to solve any hard puzzle. Finally we decided to start this forum to share how we made it.
Prepare the Possibility grid: first step we have to do is create possibility grid of 9x9x9 array for Booleans which represents the possible no’s that can occur in each cell. The [0][0][0] Boolean represents the possibility of occurrence of number 1 in the cell[0][0]. This possibility grid can be generated with some simple steps. Fill all cells with all Booleans, true. Now for each value in the puzzle, remove the other possible Booleans in the corresponding cell in the possibility grid, i.e. the only possibility should be the no in the possibility grid.
Step 1: Now see each row if there is a particular number which occurs only once. Then the only possibility for that number to occur in the row is that cell. So you can remove the possibilities of the occurrence of this number the other columns. Do this column wise and each block (3x3)
Check if all the cells have only one possible value then you have successfully solved the puzzle. If not you will have to implement the next method.
Step 2: Now you have a better possibility grid. See if a particular row in the possibility grid has a number occurring only in a particular block. Then remove the possibility of that number in the other cells of the block. Repeat this for columns. See in a particular row of a block if any number occurs only in a particular row or column. If so, eliminate the possibility of occurrence of that number outside the block in that row or column. Follow step 1 every time you effectively use this step. This simplifies our possibility grid for a reasonable extend.
Check if all the cells have only one possible value then you have successfully solved the puzzle. If not you will have to implement the next method.
Step 3: see if a two numbers combination occurs only twice in a particular row and both numbers occur only in these two cells, and then these cells must contain only these two numbers. You can remove the other possibilities of occurrence of other numbers in these cells. Follow step 1, step 2 and again step 1 every time you effectively use this step.
Check if all the cells have only one possible value then you have successfully solved the puzzle. If not you will have to implement the next method.
Step 4: if the number of elements in the union of N cells in a row is equal to N, then you can remove the numbers in the union from all other cells in the row. The N can vary from 3 to 8. Apply this for columns and blocks also. Follow step 1, step 3, step 1, step 2, and step1 every time you effectively use this step.
Main loop: Now repeat these steps again and again until you get a unique solution. Most hard and Moderate puzzles are solved in the first loop itself, some complicated puzzles may have to go for further repeating all these steps.
The looping which is recommended at the end of each step is really effective on reducing CPU usage. If these inner looping is not used, the main loop has to go for more than 10 looping.
CodeTiger
Mobile Game Developer |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
