Sudoku puzzle Solver

This article describes a solution written in c++ for solving a Sudoku puzzle, with the fastest time possible. At this point, I cannot claim this algorithm to be the "fastest" because I haven't compared it with other algorithms which might be better. This program uses a rule-based algorithm to solve a given puzzle. Even backtracking algorithm solves this problem in seconds; this is because of the simplicity of the problem. We may be encouraged to think that more the number of blank squares, longer it would take to finish the problem; this might be true for human players, but for puzzle solving algorithms, this need not always be true. We cannot exactly determine the runtime for solving a puzzle by just looking at the number of blank squares it has, because some blank squares have enough information that the number to be placed in it becomes obvious. But in most cases, Sudoku puzzle boards would have blank cells with a minimum of two possibilities.

Throughout this article, by "possibilities" I refer to the set of values that aren't present along the row, column and within the same 3X3 grid which contains the cell that's referred to. A rule in Sudoku puzzle game says that the there shouldn't be any repetition of numbers along each row, column and the subdivided 3X3 grids. This is same as saying that each row and column and the 3X3 sub-grid should contain all the values from one to nine. The possibilities in each cell can be computed by checking the row, column and the 3X3 sub-grid and eliminating the ones that are found. This leaves us with values that aren't entered yet, and which become valid possibilities for the cell.

For me, this program didn't work on the first go. I was wrong when I started with, I didn't know that a Sudoku problem will have cases where there wouldn't be any blank squares with just one possibility. I first thought that every Sudoku puzzle will be solvable in linear time, having at least one cell with exactly one possibility for each case. I quickly wrote a program that solves problems by checking for squares with just one possibility and inserting values into them. But unfortunately, it didn't work for all problems! That was when I realized that Sudoku puzzles have situations where there are blank cells having more than one possibilities. Now my next idea was using a backtracking algorithm to obtain the solution.

At first, I didn't believe that backtracking algorithm would work.  The reason to this was, if we have a board with 35 blank cells, with each cell having a minimum of two possibilities, then solving wouldn't be a linear-time operation. Even if we consider the minimum possibilities for each blank squares, which is 2, we would end up having (2^{35}) possibilities. At times, you have even five possibilities. This seems to be an even bigger value, now. This totally convinced me that using such an algorithm wouldn't work. But I was wrong. The simple reason to this is, placing a number in one blank square, in most cases, causes the number of possible values that can be inserted in the blank squares that are present in the same row and column and 3X3 cell to reduce by one. If the number of possibilities were itself two, then this reduces to one. So the possibilities won’t be (2^{35}) after all! Rather, as you keep inserting values into each cell, the "possibilities" for other blank cells would reduce by one or might even conclude (() i.e., make it explicitly clear what number should be inserted()). Finally, with an experiment conducted with a backtracking algorithm, one could clearly show that the problem doesn't always take long to solve (()unless it is specifically designed to be difficult to be solved by any brute-force algorithm()).

Basic idea for the Sudoku puzzle solver

The solution is split into two parts; the first one contains the implementation that involves analyzing the Sudoku board and screening out the possibilities for each cell. A set of weight values are defined and it determines which cell is to be chosen first for filling. The weight values are assigned in such a way that the cell with the maximum weight value has the least number of possibilities and is also surrounded by blank cells which have minimum possibilities (()i.e., along the row, the column and the 3X3 sub-grid()).   

Consider placing a number in a blank square (p(i, j)), then the sub-square is (p( [i / 3]X 3 + ki, [j/3]X3 + kj)), where (ki) and (kj)  varies from zero to 3. Also, consider the row and column to be represented as (p(k, j)) k varies from 0 to 8 and (p(i, k) )k varies from 0 to 8 respectively. Now, blank squares along (p(k, j))  and (p(i, k)) also get to rule-out a possibility; i.e., if the number placed in( p(i, j))  is v then the same value should not be present and cannot be inserted in any of the squares along  (p(k, j), p(i, k)) and (p( [i / 3]X 3 + ki, [j/3]X3 + kj)). Thus every blank square along (p(k, j)), (p(i, k)) and (p( [i / 3]X 3 + ki, [j/3]X3 + kj))  get to rule-out the possibility v (() note that [.] represents the greatest intiger()). If the “number of possibilities” in the blank squares along these group of cells contain the value v the number of possibilities reduces by one. If there were 2 possibilities, it becomes one. Once a cell has one possibility, it immediately gets filled. Thus, to ensure fast run-time, the square that’s surrounded by other blank squares that have less possibilities are chosen. So that they could conclude immediately, filling the subsequent squares faster. To do this, the following steps are involved:

Algorithm that analyses the Sudoku board and returns weight values for each blank cell,
and chooses the one with the highest weight value.

Algorithm 1: Finding the sum of all possibilities

Step 1: Obtain the puzzle board (p(i, j))
Step 2: compute the possibilities for each ((i, j))
Step 2.1: Initialize the 'possibilities board' of size (9\times 9) with each of its cell holding a bit-vice set which has all the possible numbers (() 1 to 9()) included in it,
Step 2.2: Now, search along the row, column and the 3X3 sub-square starting from
          ((i, j)) and eliminate each value that can be found across these cells, and thereby obtain the possibility set.
Step 2.3: carry over steps 2.1 and 2.2 for all ((i , j))
Step 3: Now sum up the number of possibilities across each row, column and the 3X3
        sub-square starting from ((i, j)) and place the value in another board
        (() (b_{sum}) of size 9X9 ()) for all ((i, j)).
Step 4: Return (b_{sum})

Algorithm 2: obtain the inverse

Step 1: Obtain (b_{sum}) from Algorithm 1.
Step 2: Initially another board (() (b_{inv}) which is an array of floating variables
        and it’s of size 9X9 ())
Step 3: for each ((i, j)), (b_{inv}(i, j)) (=) ( \frac{1}{b_{sum}(i, j)} )
Step 4: return (b_{inv})

Algorithm 3: obtain the inverse sum

Define another array variables (() of float datatype ()) of size 9X9 and like algorithm one,
sum up the inverse values (b_{inv}) rather than the number of possibilities and obtain the
(b_{invsum}) variable and return it.   

One might be prompted to believe that the inverse incorporated in the algorithm 2 to obtain the inverse sum might end-up storing zero. But that's not possible; because, every square that has a value in it would be counted as a cell with possibility one. 

Now let’s look into the code that actually incorporates these algorithms.

#ifndef INVERSECOUNT_H
#define INVERSECOUNT_H

#include "basicDeff.h"
#include <vector>
const int Row  = 0;
const int Col  = 1;
const int Cell = 2;

class InvCount
{

public:
    float Count[3][9];
    void SetValues(InversePossibility& a);
    float Reterive(int Type, int pos);
};

extern const int Row;
extern const int Col;
extern const int Cell;

#endif // INVERSECOUNT_H

Now let's see the definition:

#include <iostream>
#include "inverseCountSum.h"

void InvCount::SetValues(InversePossibility& a)
{
    int i,j, k;//, c = 0;
    for(i= 0; i <9; ++i)
    {
        Count[Row][i] = 0.0;
        for(j=0; j<9; ++j)
            {
                Count[Row][i] += a[i][j];
            }
    }

    for(i= 0; i <9; ++i)
    {
        Count[Col][i] = 0.0;
        for(j=0; j<9; ++j)
            {
                Count[Col][i] += a[j][i];
            }
    }

    for(k=0; k<9; ++k)
    {
        Count[Cell][k] = 0.0;
        for(i= (((int)(k/3)*3) ); i < (((int)(k/3)*3)) + 3; ++i)
            for(j= ((k*3) % 9); j < ((k*3) % 9) + 3; ++j)
            {
                Count[Cell][k] += a[i][j];
            }
       
    }
}

float InvCount::Reterive(int Type, int pos)
{
    //std::cout<<"  "<<Count[Row][pos]<<" ";
    switch (Type)
    {
    case Row:
        return Count[Row][pos];
        break;
    case Col:
        return Count[Col][pos];
        break;
    case Cell:
        return Count[Cell][pos];
        break;
    default:
        return 0; // do nothing
    }
}

The above code defines the summation, where the possibilities are summed up across each rows, columns and the 3X3 sub square. If we create a recursive function which does the summation for each cell, then, we would nearly be doing (27\times 81) operations, where we would only have to do (81\times 2) operations. 

Next we have the part of the code that actually does the process of obtaining the summation for each cell, compute the inverse summation and finally generate the weight values.

void Sudoku::GeneratePossibilityCount() // this is to be called only after calling the
{                                       // screen possibility function for all (x,y) coordinates
    int i,j;
    for(i=0; i<9; ++i)
        for(j=0; j<9; ++j)
            possibilityCount[i][j] = NoOfElements(possibilities[i][j]);
}

void Sudoku::GenerateInversePossibilityCount() // this is to be called after the GeneratePossibilityCount() is called
{
    int i,j;
    for(i=0; i<9; ++i)
        for(j=0; j<9; ++j)
            {
                possibilityCountI[i][j] = (float)(1/(float)possibilityCount[i][j]);
            }
}

void Sudoku::GenerateWaightValues(InvCount& inv, WaightQueue& Q, int pos_x, int pos_y)
{
    GridLimits Lim;
    Lim.SetLimits(pos_x, pos_y);
    TempPUnit.PriorityValue = inv.Reterive(Row, pos_x - 1) +
        inv.Reterive(Col, pos_y - 1) +
        inv.Reterive(Cell, Lim.GridNo - 1)+
                                      10*possibilityCountI[pos_y-1][pos_x-1];
    TempPUnit.x = pos_x -1; // stored in C string indexing convention
    TempPUnit.y = pos_y -1;
    Q.push(TempPUnit);
}

// this one generates the weight values.
WaightQueue Sudoku::GenerateWaightValues()
{
    WaightQueue Q;
    int i,j;
    for(i=1; i<=9; ++i)
        for(j=1; j<=9; ++j)
        {
            if (Grid[i-1][j-1] == 0)
                GenerateWaightValues(PossibCount, Q, j, i);
        }
        return Q;
}

The following,

possibilityCount[i][j] = NoOfElements(possibilities[i][j]);

screens out the possibilities from the variable 'possibilities[i][j]'. This variable is a bit-vice set that holds the set of all possible values that can be placed in the position ((i, j)). This bit-vice array has each of its positions referring to a particular value. Bit value 1 in the (i^{th}) position refers to the value (i) being included in the set.

For your reference, the function 'NoOfElements()' is defined as:

int Sudoku::NoOfElements(int value)
{

    int tcount = 0;
    if( (value & POS1) != 0) ++tcount;
    if( (value & POS2) != 0) ++tcount;
    if( (value & POS3) != 0) ++tcount;
    if( (value & POS4) != 0) ++tcount;
    if( (value & POS5) != 0) ++tcount;
    if( (value & POS6) != 0) ++tcount;
    if( (value & POS7) != 0) ++tcount;
    if( (value & POS8) != 0) ++tcount;
    if( (value & POS9) != 0) ++tcount;
    return tcount;
}

This obviously checks and counts the number of possibilities. Now the next part aims at using a recursive algorithm to solve the problem in a way similar to the back propagation algorithm. The only difference is, the blank cells are chosen selectively based on the previously calculated weight values. The algorithm implementing this is depicted as follows:

Algorithm 4: implement the core calculation part

Step 1: Obtain the Sudoku board (p(i, j)).

Step 2: If the (p(i, j)) has no blank squares, and if the result is legal, then the program sets the 'result' as the board (p(i, j)) and returns false. 

Step 3: Set the weight values using the Sudoku board (p(i, j)), and thereby obtain (w(i, j)).

Step 4: Select the blank square with the maximum weight value                                                                

Step 5: Obtain the possible values that can be inserted there. Choose one either randomly or linearly and insert it into the blank square. It's necessary to have a log of what modification was done, to be able to reveres it in the future. 

Step 6: Now, pass on the new board in this module and call this function again. This recursive call causes this algorithm to be executed again, but with a newer modification of having a value in the initially blank square

Step 7: Now check if this module returns true or false. If it returns true, then it means that the result was successfully computed at one of the recursive calls, with the result already set. If it returns false, reverse the change done in Step 5 and insert another possibility and continue to execute the step 6 and 7 until all the possibilities are exhausted.

Step 8: Once all the possibilities are exhausted, it can be concluded that there is no solution for the board (p(i, j)) and false is returned.  

The code that executes the above algorithm is as follows:

#include <iostream>
#include "coreSolution.h"
#include "Sudoku.h"
#include "basicDeff.h"

Sudoku Solver::SudokuSolution;
bool Solver::IsSolutionSet = false;
int Solver::Count = 0;
int Solver::GlobalPossibilities[9][9];
void Solver::initializeGP()
{
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            GlobalPossibilities[i][j] = POS_ALL;
}
void Solver::SetCurPuzzle(Sudoku P)
{
    int i, j;
    for (i = 0; i < 9; ++i)
        for (j = 0; j < 9; ++j)
            (*CurPuzzle.RetGrid())[i][j] = (*P.RetGrid())[i][j];
}

bool Solver::RecrussiveSolve()
{
    PriorityUnit Unit;
    Solver solve;
    int temp_pos, temp;
    int i;
    int size;
    CurPuzzle.reinitializepos();
    while (CurPuzzle.Solve()); // tries to solve the puzzle using the linear search
    if (CurPuzzle.FullPossibility())  return false;

    CurPuzzle.GeneratePossibilityCount();
    CurPuzzle.GenerateInversePossibilityCount();
    CurPuzzle.SetPossibilityCount();
    Q = CurPuzzle.GenerateWaightValues(); // Q is a priority queue containing the weight values 
                                          // and the respective cell it points to. 
                                          // This automatically arranges the weight values in
                                          // acceding order.
    if (CurPuzzle.IsSolved())
    {
        if (CurPuzzle.IsLegal() )
        {
            Solver::SudokuSolution = CurPuzzle; // if the puzzle is solved, it sets a global scoped
                                                //variable, assigning it its final answer. 
            Solver::IsSolutionSet = true; // indicates that the solution is set successfully
            return true;
        }
        else
            return false;
    }

    solve.SetCurPuzzle(CurPuzzle);
        Unit = Q.top();
        temp_pos = (*CurPuzzle.RetPoss())[Unit.y][Unit.x];
        size = Sudoku::NoOfElements(temp_pos);
        for (i = 0; i < size; ++i)
            {
                            temp = (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = Sudoku::BitValue(temp_pos);
                            Sudoku::DeleteValue(temp, temp_pos);
                
                if (solve.RecrussiveSolve())
                    return true;
                solve.SetCurPuzzle(CurPuzzle);
            }
        (*solve.CurPuzzle.RetGrid())[Unit.y][Unit.x] = 0;
        Q.pop();
    return false;
}

The above program, does the 'recursive solve' procedure. 

Using this code

This code was compiled using g++ compiler and developed using code::blocks IDE. 

Future work

This program can be extended to support more analytical methods to study the nature of Sudoku puzzles. It is required for analyzing the mathematical structure and its behavior in various scenarios.  Observe the following line:

TempPUnit.PriorityValue = inv.Reterive(Row, pos_x - 1) +
       inv.Reterive(Col, pos_y - 1) +
       inv.Reterive(Cell, Lim.GridNo - 1)+
                                     10*possibilityCountI[pos_y-1][pos_x-1];

the value 10 was randomly chosen, even changing the sign form 10 to -10 may have impact on the solution; with a particular class of problems getting solved faster and the other class of problems being solved slower. Or if we place -3 instead of +10, we would totally be neglecting the possibilities in the cell to which these other values are added to. But by adding 10, we are giving at most preference to the number of possibilities in that particular cell rather than the neighboring cells. 

This 'retrieve' function retrieves the summation along x or y. This analytical part does not influence the correctness of the solution but has direct influence over the time of execution.

History

This article was first posted on 27-09-2015.