Sudoku Generator For Mobile
By Codetiger
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.

Sudoku Generator Algorithm:

Generating sudoku puzzle using low CPU power:
Puzzle generator completely depends on the solver technique in terms of efficiency. So we are half the way through. The generator logic is bit easy. Usually these are two common ways to generate Sudoku puzzle.

One: filling an empty grip partially with random numbers in random cells and trying to solve it, if there is a unique solution, the puzzle is ready. Else add another number and try solving. if this fails to produce unique solution puzzle try again with filling a different random numbers in random cells. This method is not suitable for mobile phones, coz this takes along time.

Two: take a filled solution grid and hide some cells now try solving it, if more than one solution is possible then hide more cells, if there is a unique solution then stop hiding more cells. This method is simple and faster but requires some code on generating filled solution grid. To generate a filled solution grid you have to use some matrix theorem rather than filling a grid by random numbers. This is the most deciding part of the methods we have used. We have crossed all major tasks now. Your code efficiency and CPU usage depends on this piece of code. I have tried two extremes of coding in this part which results to generation time of 10 mins and the simplest (the on I have implemented now) which takes at the max 3 seconds on a 35 MHz processor.