Almost everyone of you might have one or the other time stuck upon a SUDOKU. Here’s a simple C/C++ SUDOKU program that solves the hardest of the Sudoku puzzles in fraction of a second.
SUDOKU – THE GAME
A Sudoku in the most common form consists of a 9 x 9 grid of numbers. The grid is subdivided into 9 blocks of 3 x 3 size. Initially the grid is partially filled (with numbers from 1-9), your task is to complete the grid using numbers from 1-9 such that
- -no row/column contains a repeating digit
- -no sub block contains repeating digit
In short the digits 1-9 must occur in each row/column/sub block.
How to program or code SUDOKU solver in c/c++
The program makes use of BACKTRACKING.
You are required to enter the partially filled Sudoku in the following format
- -Each row represents a line.
- -Empty cells are denoted by a “.”
- -Non-empty cells are denoted by the digit they are filled with
The above code is self explanatory . Only thing worth noting here is the arrary game which represents the puzzle and the array xy which stores the x and y coordinates of the positions which are are already filled.
Solving the puzzle
The heart of the program is the solve() function
The function is first called as
0,0 indicate that we start with the top leftmost cell .
First an array of possible values (not present in row, column or sub-grid) for a cell is generated. Then we fill the cell with one of the possible values from the array and subsequently call the function recursively for for next cell. This procedure is repeated till either the puzzle is solved or the list of possible values for a particular cell is exhausted. In the latter scenario (indicated a return value of -1) the content of the preceeding cell is changed to the next possible value and the procedure is repeated again for the remaining cells.
Condition for successful completion
this condition when true indicates that puzzle has been solved , returns success code ie. 0
Seeding the possible values’ array
The above snippet creates a list of possible values in that particular cell. The temp array is initialized with numbers 1-9 and then the row , column and sub-grid containing the cell is checked . All numbers already present are zeroed out and thus only the possible values for that cell remain.
Finally we assign one value from the array to the cell and call the solve function for the next cell in sequence. The next cell coordinates are determined by the values I,J calculated earlier. A return value of -1 indicates incorrectly filled value and thus the content of the current cell are changed to the next possible value are the process repeated.
Here is the complete code