Solving Sudoku using backtracking | faceprep

Solving Sudoku using backtracking | faceprep

Program to solve Sudoku using backtracking is discussed here.


Solving Sudoku Using Backtracking



Given a matrix of 9*9 incomplete sudoku (unassigned places are represented by 0). Check whether you can complete it. If so print the Sudoku or else, print “Np”.

Consider the given sudoku,


Solving Sudoku Using Backtracking


After solving,




Solving Sudoku Using Backtracking




Algorithm to solve Sudoku

  • Find row, col of a cell assigned with value = 0.
  • If there is no such row and column, return true
  • Repeat for digits from 0 to 9
  • a) If there is no conflict for digit at row, column, assign digit to row, column and recursively try to fill in rest of grid.
  • b) If recursion is successful, return true.
  • c) Else, remove the digit and try another digit.
  • If all digits have been tried and nothing worked, return false.




Code:

@@coding::1@@




Recommended Programs



Solving Sudoku Using Backtracking


c