Coders Packet

Solving a 9x9 sudoku using Backtracking in C++

By Shaik Ateeq ur Rahman

A 9x9 2D matrix is taken as an input and using backtracking with C++ we will give solved sudoku as output. If there is no solution for the matrix we will print The given sudoku can't be solved.

Given a 9x9 sudoku as a 2D matrix where empty spaces are filled with 0, we will try to solve the matrix by backtracking in C++. So, the brute force method will be to fill the cell containing 0 with an integer from 1-9 which is not present horizontally or vertically in that cell. After filling a cell, we move to the next cell recursively. Eventually, We will reach a cell where we cannot place any number from 1-9, then we will backtrack to the last cell in which we inserted a number, and we will change the number to the next digit that will fit in that cell.

First, the 2D matrix is passed to the function Sudokusolver.

Sudokusolver function first check few base cases the first base case is it checks if we are at the 8th row and 9th column to stop further backtracking. In another base case, we check if we are at the 9th column we move to the next row. After the base cases, we will traverse the matrix and if the cell contains a value greater than 0 we move to the next cell. If the cell contains a 0 value we will pass it to the function called "isPossible" which check and finds the possible number from 1-9 for that cell. If the number is not cant find a number to fit we change the previous number to 0 and repeat the process.

 

The isPossible function checks whether if a cell can be assigned a number. It basically checks if the assigning number is present in the particular cell's row and column or if the number is present in the 3*3 matrix.

After we reach the last cell we will print out the 2D matrix and 

Download project

Reviews Report

Submitted by Shaik Ateeq ur Rahman (ateeq)

Download packets of source code on Coders Packet