By Sayma Naaz

Sudoku is a logic-based combinatorial number-placement puzzle. In this packet, the C++ programming language is used to solve the Sudoku game.

To solve the sudoku we use recursion with backtracking. Backtracking is a useful algorithm for solving the problem with recursion by building a solution incrementally. Generally, backtracking involves starting with a possible solution, and if it doesn’t work, you backtrack and try another solution until you find the correct one.

Backtracking is useful for the following three types of problems:

- Decision-making problems to find a suitable solution to a problem.
- The best solution to optimize the algorithm.
- Count problems to find a suitable solution.

To solve sudoku we use C++ programming. In the program in the main function, we initialize the sudoku matrix of size 9X9 and taking input from the sudoku matrix. To solve the sudoku we define a function named sudoku solver, in this function we recursively call the function to solve the sudoku and at every cell if a digit is correct to place or not, to check this we define a function named Can Place function, and in this function, we check if the digit has occurred in a row, column, or in 3X3 matrix(sub-matrix). If the Can Place function returns true and then the sudoku solver also returns true then we print the solved sudoku matrix as an output otherwise print “Sudoku cannot be solved”.And if at any point we are unable to place any digit then we backtrack and remove the previously filled digit and try any another digit at that place and moves ahead.

Submitted by Sayma Naaz (saymanaaz)

Download packets of source code on Coders Packet

## Comments