The 9x9 sudoku

The Sudoku is a logic-based, combinatorial numberplacement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids contain all of the digits from 1 to 9. An additional constraint on the contents of individual regions is that the same single integer may not appear twice in the same 9×9 playing board row or column or in any of the nine 3×3 sub-regions of the 9×9 playing board.

The puzzle was popularized in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It became an international hit in 2005.

There a total of 6,670,903,752,021,072,936,960 possible permutations. This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and “brute force computation."

Major challenges faced

Challenges faced

Designing the Algorithm for the Sudoku solver and determining the best way to have the data stored in memory for quick access was a major challenge. To solve the sudoku, initially each box had possible values set. All single possible values were saved as the value of the cell then. This process was repeated after every computation.

Besides this, frequency of numbers in rows, columns and sub-boxes(3x3) were measured and single frequency values were set. If sudoku was not solved by now, guesses were made and each newly guessed sudoku was attempted to be solved. This was carried on until the complete sudoku was solved.

Another challenge then was accessing each sub-box individually, and to do so a 1-4-7 co-ordinate system was created where 1,4,7 represent the middle point of each 3x3 box.