Sudoku is a logic puzzle. You can try playing Sudoku yourself here: Play Sudoku Online. In this project, you are going to implement a C++ program which solves Sudoku puzzles for you. Below is brief description of Sudoku and its rules:

Sudoku is a logic puzzle. The objective is to fill a 9×9 grid with digits in such a way such that each column, each row, and each of the nine 3×3 grids that make up the larger 9×9 grid contains all of the digits from 1 to 9 exactly once.

Each Sudoku puzzle begins with some cells filled in. These numbers are chosen such that there is a unique solution to the Sudoku.

A typical Sudoku puzzle

And its solution

Since you are going to be writing a C++ program to solve Sudoku, here’s what the sample interaction would look like:

Enter the Sudoku grid (Use 0 for empty cells):
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
Solution:
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

Excited? We bet you are!

Backtracking

Before you start, let’s get a general sense of what approach you can take to make a Sudoku solver. The easiest approach to solve a Sudoku requires a technique called backtracking.

Backtracking is a method to solve problems that tries different solutions until finds a solution that “works”. Let’s see an example of backtracking on a simpler problem - the Eight Queens problem.

Eight Queens problem

The Eight Queen problem is — place eight chess queens on a 8×8 chess board so that no two queens attack each other. That is, no two queens are in the same row, column, or diagonal.

Here’s a description of the backtracking solution to the Eight Queen problem:

• Start with an empty board, and place queens one by one in different rows, starting from the top row.
• When we place a queen in a row, we check for clashes with already placed queens.
• If we are able to place the queen such that there is no clash, then we move on to placing the next queen.
• If we are not able to place this queen, then we backtrack. That is, we go to the previous stage, and position the previous queen at the next valid position.

Here’s what the solution looks like visually:

Animation using Backtracking to solve Eight Queens Problem.

Note that sometimes, this means we backtrack multiple positions up. This happens when you try to place the previous queen at the next valid position, but there are no more valid positions. So, you have to move the queen you placed before that one.

Here’s the pseudocode to solve the eight queens problem:

def place_next_queen()
    n = number of queens placed so far 
    if n == 8
        return "Success!"
    else
        for each possible column c
            if placing queen in (row n+1, column c) is valid
                place a queen in (row n+1, column c)
                if place_next_queen() == "Success!":
                    return "Success!"
                erase queen from (row n+1, column c)

The main part of the pseudocode is in the last 6 lines. It says, “try every possible column for placing the next queen one by one. If you find a solution with the current placing, stop. If you don’t, then try the next position.”

Sudoku using backtracking

Now that you understand how backtracking works on the eight queen problem, here’s the same concept being used for solving Sudoku.

The logic is the same, but we go cell by cell instead of row by row. That is, “try every possible number for the next empty cell. If you find a solution with the current number, stop. If you don’t, then try the next number.”

Implementing the Sudoku solver

If you don’t have C++ installed on your computer, you can do your work here: C++ Shell. Make sure you keep saving your work! Or, you can see C++ installation instructions here.

Okay, you are now ready to implement the Sudoku solver. Below, we have provided you some guidance to help you structure your code.

Step 1: Helper functions

Write three helper functions,

• bool isValid(int grid[N][N], int row, int col, int number) - checks whether or not it is valid to place number in the given position. That is, number should not appear in the row, column, or grid.
• bool findUnassignedLocation(int grid[N][N], int &row, int &col) - finds the first unassigned or empty cell in the sudoku grid. row and column are passed by reference
• void displayGrid(int grid[N][N]) - displays the grid

Make sure you keep testing each of the functions you write. Initialize grid to be the Sudoku given at the beginning of this project.

const int N = 9; 
int grid[N][N] = {
  {5,3,0,0,7,0,0,0,0},
  {6,0,0,1,9,5,0,0,0},
  {0,9,8,0,0,0,0,6,0},
  {8,0,0,0,6,0,0,0,3},
  {4,0,0,8,0,3,0,0,1},
  {7,0,0,0,2,0,0,0,6},
  {0,6,0,0,0,0,2,8,0},
  {0,0,0,4,1,9,0,0,5},
  {0,0,0,0,8,0,0,7,9},
}

Then call your functions and output their results to see if they are what you expect them to be.

Step 2: Main solver

Once you have all of the above helper functions, write the main solver which uses backtracking.

The pseudocode for this is very similar to the pseudocode for the eight queen problem. Try to get a sense of what the pseudocode for the Sudoku solver looks like.

Here are some tips:

• If there is no unassigned cell in the grid, then your solution in complete.
• Else, iterate over all numbers and check if it is valid to place the number. If it is not valid, don’t do anything. If it is valid, then place the number in the unassigned cell and continue solving by calling the solver function again.
• If the solver is successful, return that you were successful. If not, then erase the current number. As the iteration continues, other possible values will be tried.

This is a challenging exercise! Don’t loose heart if it takes time. If you get really stuck, take a peek at the solution below.

Testing your implementation

First, make sure your Sudoku solver works on the first Sudoku above.

Once that is done, you’re 90% there. But just to be sure, try a few more Sudoku’s as input and see if your program works! You can use the Play Sudoku Online website to find more Sudoku’s to solve.

It’s up to you whether you want to take input from the console or initialize the array directly in code.

Congratulations

This was a challenging project! You learn about backtracking, and used the concept and all your C++ skills to implement a Sudoku Solver! Great job!

Solution

Here’s the official solution to this project: C++ Solution: Sudoku Solver.