This post is completed by 2 users
|
Add to List |
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.
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