Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Backtracking — SUDOKU Solver

SUDOKU Puz­zle : The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”, “regions”, or “sub-squares”) con­tains all of the dig­its from 1 to 9. The puz­zle set­ter pro­vides a par­tially com­pleted grid, which for a well-posed puz­zle has a unique solu­tion. (Source: Wiki — http://en.wikipedia.org/wiki/Sudoku)

SUDOKU Puzzle

SUDOKU Puz­zle

Approach:

Naive Approach:

The Naive way to solve it to is to gen­er­ate all pos­si­ble com­bi­na­tions of num­bers from 1 to 9 to fill the empty cells. Try every con­fig­u­ra­tion till the prob­lem is solved.

Bet­ter Approach — Backtracking:

Find empty cell, find int row, col number
  If there are no empty cells, return true, problem solved.
  For number  from 1 to 9
    a) If there if is safe for digit at cell[row][col]
        fill the cell[row][col]=number and recursively try fill in rest of 	grid
    b) If recursion successful, return true
    c) Else, undo the selection, cell[row][col]=0 and try another
  If all numbers are tried and solution not found, return false

Code:


Out­put:

 5 3 4  6 7 8  9 1 2 
 6 7 2  1 9 5  3 4 8 
 1 9 8  3 4 2  5 6 7 

 8 5 9  7 6 1  4 2 3 
 4 2 6  8 5 3  7 9 1 
 7 1 3  9 2 4  8 5 6 

 9 6 1  5 3 7  2 8 4 
 2 8 7  4 1 9  6 3 5 
 3 4 5  2 8 6  1 7 9 

Ref­er­ence : http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

You may also like...