This post is completed by 2 users

  • 0
 Add to List
Hard

148. Solve Sudoku Puzzles with Backtracking

Given a sudoku problem or partially filled sudoku, write a program to solve the sudoku.

What is Sudoku: Sudoku is a puzzle where a partially completed grid is given and objective is to fill a 9×9 grid with digits with conditions below -

  • Each column contains all of the digits from 1 to 9 only once.
  • Each row contains all of the digits from 1 to 9 only once.
  • Each of the nine 3×3 sub-grid contains all of the digits from 1 to 9 only once.
SUDOKU Puzzle
SUDOKU Puzzle

Better 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
 

Output:

 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

Reference: http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

Related Problems: