In this post, we will learn how to solve the sudoku puzzle using the backtracking algorithm in C, C++, and Java.

What is Sudoku?

Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9.

Initially, we have a partially-filled grid, we need to fill the blanks cells abiding the rules to complete the sudoku puzzle.

The same number can not appear twice in the same row + column or in any of the nine 3×3 subregions/boxes of the grid.

Example:

Initial

sudoku uncomplete

Final

sudoku complete

So in order to solve sudoku using backtracking, we will follow the following approach.

  1. We will fill the cells column vise.
  2. Start from the first column. check if the current cell is empty or has 0. If NO then move to next cell of the same column or first row of the next column if you are at last cell (row==8) of the column (vertical).
  3. If the cell is empty or has 0 then start validating which number from 1 to 9 is valid for the particular cell. Once validated, move to next cell.
  4. If none of the numbers from 1 to 9 is valid for the current cell, then we need to backtrack and assign another valid value to the last updated cell. To acheive that we will return false because in the last recursive funcion stack the iteraion of ‘for loop’ continues if solve(row+1,col) or solve(0,col+1) is false. The process is repeated until we get another correct value for the previous cells.

That’s all we needed to do to implement the concept of backtracking since backtracking is implemented using recursion so our base condition will be

So, let’s solve sudoku using the backtracking algorithm in code.

Solution for sudoku using Backtraking in Java | C++

Java

C++

Output

output for sudoku program

If you have any doubts or suggestion then comment below.

Leave a Reply

Close Menu