10 Lessons About C++(2015)
Chapter 5: A Soduku Puzzle Solver
Sudoku is a logic puzzle in which you are given a 9×9 grid of numbers in the range 1 to 9. That grid is then further sub-divided into 9 lots of 3×3 sectors.
The rules are simple: in each row, column, and 3x3 sector, each one of the numbers 1-9 must appear. At the start of the puzzle, just enough of the grid’s elements are allocated to guarantee a single unique solution based on these rules. This chapter presents a C++ Grid class for both generating and solving a Soduku puzzle grid.
At the heart of the class is a recursive backtracking algorithm used to actually solve the puzzle. Each recursive call to the Solve function solves the puzzle one step at a time by assigning a feasible number to each empty cell. Before the number is assigned it is first checked for feasibility: we check if the number is not already present in the current row, in the current column and in the current 3x3 grid. If it is safe to do so, the number is assigned and we recursively check to see if this latest assignment has solved the solution or not. If a solution is still not found, we try the next number for the current empty Soduku cell. If none of the numbers 1-9 we have tried are successful then we return a false.
#include <vector>
#include <set>
#include <algorithm>
#include <ctime>
#include <iostream>
const int UNASSIGNED = 0;
const int N = 9;
class Grid
{
private:
std::vector<unsigned> grid;
std::set<unsigned> locations;
unsigned sizeSquared;
public:
Grid()
{
sizeSquared = N * N;
grid.resize( sizeSquared );
}
void Copy( unsigned matrix[N][N] )
{
for (int row = 0; row < N; ++row ) {
for ( int col = 0; col < N; ++col ) {
grid[ row + col * N ] = matrix[ row ][ col ];
}
}
}
void Print() const
{
for ( int row = 0; row < N; row++ ) {
for (int col = 0; col < N; col++)
std::cout << grid[ row + col * N ] << " ";
std::cout << std::endl;
}
std::cout << std::endl;
}
bool Solve()
{
int row, col;
if (!HasUnassignedLocations(row, col)) return true;
// consider digits 1 to 9
for ( int num = 1; num <= 9; num++ ) {
if ( IsFeasible( row, col, num ) ) {
grid[ row + col * N ] = num;
if (Solve())
{
return true;
}
// Try again
grid[ row + col * N ] = UNASSIGNED;
}
}
return false;
}
private:
bool HasUnassignedLocations( int &row, int &col )
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row + col * N] == UNASSIGNED)
return true;
return false;
}
bool IsFeasible(int row, int col, int num)
{
// Check if number not already placed in current row, col, 3x3 box
return !InRow(row, num) &&
!InColumn(col, num) &&
!In3x3Box(row - row%3 , col - col%3, num);
}
bool InRow(int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row + col * N] == num)
return true;
return false;
}
bool InColumn( int col, int num )
{
for (int row = 0; row < N; row++)
if (grid[row + col * N] == num)
return true;
return false;
}
bool In3x3Box( int boxStartRow, int boxStartCol, int num )
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
{
int rown = row+boxStartRow;
int coln = col+boxStartCol;
if (grid[rown + coln * N] == num)
return true;
}
return false;
}
};
int main()
{
Grid gr;
unsigned grid[N][N] = {{0, 7, 4, 3, 0, 2, 0, 0, 0},
{0, 0, 0, 0, 0, 5, 0, 4, 0},
{0, 0, 0, 6, 0, 7, 9, 0, 0},
{0, 5, 6, 0, 0, 0, 7, 9, 0},
{3, 0, 0, 0, 0, 0, 0, 0, 5},
{0, 2, 7, 0, 0, 0, 6, 8, 0},
{0, 0, 5, 7, 0, 1, 0, 0, 0},
{0, 1, 0, 2, 0, 0, 0, 0, 0},
{0, 0, 0, 4, 0, 8, 1, 6, 0}};
gr.Copy( grid );
std::cout << "Initial Puzzle:" << std::endl << std::endl;
gr.Print();
if ( true == gr.Solve() )
{
std::cout << "Solved Puzzle:" << std::endl << std::endl;
gr.Print();
}
else
{
std::cout << "No solution exists";
}
return 0;
}
Now here is the console output for the C++ implementation of the Sudoku puzzle solver. It prints the initial grid and the completely filled grid as outputs:
In this short master lesson, you have learned the intricacies of Sudoku puzzle programming as a practical application of the Grid class in C++.