Summary: In this post, we will learn What Sudoku is and 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 are given a partially-filled grid like the following:

sudoku uncomplete

We need to fill the blanks cells such that the same number should not appear twice in the corresponding row + column and in any of the nine 3×3 subregions/boxes of the grid.

sudoku complete

Sudoku Solution using Backtracking Algorithm

We can easily solve sudoku using the backtracking approach as follows:

  1. We will fill the cells column vise.
  2. For every cell, we will check if it is empty (or has 0) or not.
  3. If the cell is empty, we will then check which number from 1 to 9 is valid for the particular cell and update the cell accordingly.
  4. If the current cell is not empty, we will move to the next cell of the same column or first row of the next column if at the last cell of the column.
  5. If none of the numbers from 1 to 9 is valid for the current cell, we will go back to the last updated cell and try with another valid value (i.e. backtrack).
  6. To achieve backtracking, we will return to the last recursive call by returning false check with the next value of the iteration of ‘for loop’. We again proceed to the next cell after updating the last cell with another valid value.

To implement backtracking, we will use recursion with the following base condition:

Here is the full implementation of the above discussed algorithm in Java and C++.

Java

C++

Output:

output for sudoku program

In this tutorial, we learned to solve Sudoku Puzzle programmatically using the backtracking algorithm in C++ and Java programming languages.

Leave a Reply