Sudoku puzzle solving algorithm that uses a rule-based approach to narrow the depth search

Question

I had written a Sudoku puzzle solver that accepts 9x9 puzzle boards, and completes them with the least possible time. Rather than purely depending on brute-force, my algorithm first attempts to fill in the squares that have an obvious solution. And for each square being filled this way, the amount of information increases (I.e.., more number of squares get filled which aids in filling in the remaining squares) which makes the further iteration process easier. Once this method fails (this happens if there isn't an obvious answer to fill-into any of the squares), the algorithm immediately switches over to brute-force search.

(Note, the source contains a few spelling mistakes, like the word recursive misspelled as Recrussive. Please ignore spelling errors. Anyway, it has been a while since I touched this code, and this was my first object oriented code written in C++).

The basic working (High level view)

1. The program first determines the set of all possible values that can be entered into every blank square in the puzzle board. The possibility set is determined by iterating through the row, column and the 3x3 block, and eliminating the set of numbers already present. The possibility-set is stored as a bit-filed value for each square.
2. Every blank square with a single possibility gets the number entered into it.
3. The algorithm is repeated from the first step again, until there isn't a square with just one possibility. If there aren't any blank squares left, the current board's state is returned as the result.
4. It chooses a blank square and enters a value into it. The process of choosing the blank square, out of all the available blank squares is guided by an analysis algorithm. The value entered into this blank square is chosen from all the possible values that can be entered into the square.
5. A recursive call to this function is initiated with a clone of the current board's state. Note that the current board state now contains the modification done to it at the 4th step (entering one of the possible values).
6. Steps 4 and 5 are carried over until all the possible values in each of the available blank squares are tested with, or until the puzzle gets solved.

Though this algorithm may seem to provide an alarmingly bad worse-time complexity, this algorithm almost never hits the worse time complexity regardless of the (legal) puzzle entered.

List of types defined and used throughout the program :

I. BoardGrid

typedef int BoardGrid[9][9];

Boardgrid type represents the puzzle board, encoded with the following convention:

1. The signed integer values from 1 to 9 represent the numbers 1 to 9 in the Sudoku puzzle board.
2. The value zero signifies a blank-box in the Sudoku puzzle board.

Therefore, this representation is the one that gets acquired from the user as a user-input.

---

II. PossibilitySet

typedef int possibilitySet[9][9];

possibilitySet type represents the set of all values that can/can't be filled in a square. This type is specifically defined for storing bit-fields for representing a set of values. This follows the following convention:

1. The value 0x0 represents a null-set.
2. The values starting from 0x1 << 0 to 0x1 << 9 represent the values 1 to 9 in the Sudoku board. For example, the bit-field value (0x1 << 5) | (0x1 << 7) represents the set of numbers: {5,7}. Therefore, unlike BoardGrid this stores multiple numbers in an integer field.
3. An object of this type is used for holding the possible list of values that can be inserted into a particular square.

The following defines bit-field values associated with each symbol accepted by the sudoku board puzzle:

enum POSSIB
    {
        // represents the values from 1 to 9
        // Here POS represents possibilities. 
        POS1 = 0x1,
        POS2 = 0x1<<1,
        POS3 = 0x1<<2,
        POS4 = 0x1<<3,
        POS5 = 0x1<<4,
        POS6 = 0x1<<5,
        POS7 = 0x1<<6,
        POS8 = 0x1<<7,
        POS9 = 0x1<<8,

        /// represents the set of all values.
        POS_ALL = POS1 | POS2 | POS3 | POS4 |
                  POS5 | POS6 | POS7 | POS8 |
                  POS9
};

---

III. InversePossibility

 typedef float InversePossibility[9][9];

This Sudoku puzzle solving algorithm follows a brute-force approach mixed with rule-based approach. To further improve performance, an extra analysis step is added, to determine which squares to be prioritized while choosing it to be filled. The priority value is inversely dependent on the number of possible values that can be filled into a particular square.

This InversePossibility value is used in computing the priority weight value of each of the blank square that is to be filled. This priority weight value helps in ordering which squares must be filled first.

---

IV. PriorityUnit:

struct PriorityUnit{ /// this is a structure that shows the location of the cell
                   /// along with it's priority.
     float PriorityValue;
     int x; int y; // represents the location of the element
};

This holds the priority value of each square in the puzzle board. This is used during the evaluation process, where each instance is sorted based on the PriorityValue. A detailed explanation will be provided in the later sections.

---

V. WeightQueue

class Compare{
public:
     bool operator () (PriorityUnit a, PriorityUnit b);
};

typedef std::priority_queue<PriorityUnit, std::deque<PriorityUnit>, Compare> WeightQueue;

This serves as the container containing the PriorityUnit.

Working of the Sudoku puzzle solver:

1. Rule-based search: This method involves identifying the set of blank squares that can be filled immediately with the available information. For each iteration, the amount of information increases, and eventually as each squares get filled, the puzzle board gets completed.

2. guided brute-force search: The evaluation algorithm, on a high level, is a brute-force algorithm which relies on an analysis method which prioritizes the blanks that are to be filled first. During each search iteration the rule-based search is called to complete the evaluation if the amount of information on the board is sufficient (as each depth first search iteration increases the amount of information on the board).

3. The analysis method that guides the depth first search: This assigns a weight value for each of the blank squares based on a measure which determines the influence of filling-in that square with a possible value.

The following is the header file, containing the primary functions that are used in the evaluation process:

#include "InverseCountSum.h"
#include "basicDeff.h"
class Sudoku
{
    // shows if there is a possibility for zero to be present in the possibilities variable
    bool ZeroPossibilities;

    BoardGrid Grid; // shows one sudoku board; (x, y) represents the position and the value
                    // field represents the value
        BoardGrid possibilities;
        BoardGrid possibilityCount;
        InversePossibility possibilityCountI; // inverse count (this serves as the exact inverse of the
                                          // possibilityCount.
        InvCount PossibCount;

                    /// only for debug purpose
                #ifdef DEBUG_TESTS
                        Weights weight_values; // holds the weights
                #endif // DEBUG_TESTS
    //BoardGrid possibilityCount;
    public:

                     PriorityUnit TempPUnit;

        Sudoku();
        Sudoku (BoardGrid grid);
        void SetGrid(BoardGrid grid);
        // this is the basic operation involved in converting the sudoku puzzle into a different sequence.
        void SwitchNumbers(int Value1, int Value2); // interchanges the values without making
                                                                // any mistakes by violating the fundamental rules
        bool ScreenPossibility(int pos_x, int pos_y); // screens the possibility of numbers that can fit.
        bool ScreenPossibilityL2(int pos_x, int pos_y);
        static bool CheckLegal(BoardGrid); // same as IsLegal(), but takes the board as the input
        bool IsLegal(); // checks if the current board is legal (or correctly follows the rules)
        static bool DeleteValue(int Value, int &field); // deletes the bit field (making it zero) which is at the position "value".
                                                        // "field" is a bit-vice set, holding the possibilities the cell can hold.
        void DeleteCommonElements(int Value_set, int& field );
        static int BitValue(int Value);
        BoardGrid* RetGrid();
        BoardGrid* RetPoss();
        static bool SinglePossibilityElement(int possib);
        static int NoOfElements(int value);
        bool Solve();

        void GeneratePossibilityCount();
        void GenerateInversePossibilityCount();
        void SetPossibilityCount();
        void GenerateWeightValues(InvCount& inv, WeightQueue& Q,  int pos_x, int pos_y);
        WeightQueue GenerateWeightValues();
        void reinitializepos();

        bool IsSolved();
        bool FullPossibility();

};

These are the definitions of the generator functions. This shows the vital functions involved in the analysis process (the process to determine the priority of selecting blank squares):

#include <iostream>
#include "Sudoku.h"
#include "InverseCountSum.h"
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;
}



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]);
                //std::cout<<":: "<<possibilityCountI[i][j]<<" ";
            }
}


void Sudoku::GenerateWeightValues(InvCount& inv, WeightQueue& 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;
    TempPUnit.y = pos_y -1;
    Q.push(TempPUnit);
}

WeightQueue Sudoku::GenerateWeightValues()
{
    WeightQueue Q;
    int i,j;
    for(i=1; i<=9; ++i)
        for(j=1; j<=9; ++j)
        {
            if (Grid[i-1][j-1] == 0)
                GenerateWeightValues(PossibCount, Q, j, i);
        }
        return Q;
} 

The Solver class declaration:

class Solver
{
    WeightQueue Q;

public:
    Sudoku CurPuzzle;
    static Sudoku SudokuSolution;
    static bool IsSolutionSet;
    static int Count;
    static int GlobalPossibilities[9][9];
    static void initializeGP();
    void SetCurPuzzle(Sudoku P);
    bool RecrussiveSolve (); // this starts the main solution iteration process
};

The following shows the main evaluation operation's source:

bool Solver::RecrussiveSolve()
{
    PriorityUnit Unit;
    Solver solve;
    int temp_pos, temp;
    int i;
    int size;
    CurPuzzle.reinitializepos();
    while (CurPuzzle.Solve());

    if (CurPuzzle.FullPossibility())  return false;

    CurPuzzle.GeneratePossibilityCount();
    CurPuzzle.GenerateInversePossibilityCount();
    CurPuzzle.SetPossibilityCount();
    Q = CurPuzzle.GenerateWeightValues();
    if (CurPuzzle.IsSolved())
    {
        if (CurPuzzle.IsLegal() )
        {
            Solver::SudokuSolution = CurPuzzle;
            Solver::IsSolutionSet = true;
            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 Solver class's bool RecrussiveSolve() function solves the entire puzzle. Understanding the functioning of this function will be enough to understand the working of the algorithm.

The following,

  CurPuzzle.GeneratePossibilityCount();
  CurPuzzle.GenerateInversePossibilityCount();
  CurPuzzle.SetPossibilityCount();
  Q = CurPuzzle.GenerateWeightValues();

initializes the evaluation for the current iteration. The statement while (CurPuzzle.Solve()); called before these is the program's attempt to try and solve the problem purely based on the rule-based procedure, trying to eliminate the set of numbers that can be entered into each square. The CurPuzzle.Solve() function iterates through each bit-field trying to discover the possible elements (values) that can be entered into the blank box. The set of values are then stored as bit fields. This function runs in a loop because, an empty box getting filled by a value might help provide enough information to figure out the value in a different box. Therefore, until such a possibility is ruled-out the function iterates.

The above process configures the bit-fields, which would help the GeneratePossibilityCount() function to compute the number of possible elements that can be entered into each square. The next function, which relies on the result of the GeneratePossibilityCount() function, computes the GenerateInversePossibilityCount() which assigns a floating-point value to each square in the sudoku board following the expression (1/num_of_possibilities_for_that_square) and later the SetPossibilityCount() function is called followed by the GenerateWeightValues() function, which returns the list of all the empty cells, along with its associated priority value.

The SetPossibilityCount() function sums the number of possibilities across each row, each column and each 3x3 cell (the smaller boxes, which must also contain values from 1 to 9) and stores them in an array. The GenerateWeightValues() function returns a priority queue, sorted based on the priority value derived from the result provided by the other three functions.

The final depth-first search is computed by recursively calling the RecrussiveSolve() function, belonging to a locally declared instance of the Solver class. The solve.SetCurPuzzle(CurPuzzle); sets the puzzle board for the next recursive call. Recurrence is brought about by calling the same RecrussiveSolve() belonging to a local instance of the same class, declared within the RecrussiveSolve() function.

In what areas does my code need improvement? And how can I improve the design of my code and algorithm? I wrote this code intending it to be Object oriented. How object oriented is it? (I.e.., is there a better way to structure the same solution) And is there a better algorithm to solve this problem more easily?

For complete code, please refer this URL: https://github.com/sreramk/Sudoku-

Answer 1

I see a number of things that could help you improve your code.

Fix the formatting

The formatting of the code in general, and indenting in general, is inconsistent and makes it more difficult to read and understand the code. A consistent style helps the reader of the code.

Fix the spelling errors

Yes, I know you said "please ignore spelling errors" but such errors make the code harder to read and understand, and gives a poor impression of quality of the code.

Rethink your typedefs

There are a plethora of typedefs in this code that tend to obfuscate rather than simplify understanding of the code. For instance, these typedefs are not really helping much:

typedef int BoardGrid[9][9];
typedef int PossibilitySet[9][9];

In order to actually use them, we still need to know that their underlying structure is that of a 9x9 grid of int, so all this accomplishes is making the reader of the code look up yet another indirection.

Encapsulate class details

The Sudoku class exposes a great number of things that really should be private. The most egregious example is that RetGrid() and RetPoss return references to private data members. This means that any function calling these can alter the internal state of the object. That's a serious design error and must be fixed. The other aspect is to consider which are internal details and which are essential to the interface. The SwitchNumbers routine is never called (and wouldn't work anyway because all it does is swap the passed copies), so it should be eliminated from the interface. Likewise with ScreenPossibilityL2 which isn't even defined.

Simplify your class design

I found the code hard to read and the design difficult to follow because there are many classes and functions that don't seem to be well thought out. For example, the Sudoku class contains this public member:

PriorityUnit TempPUnit;

Why is a data member that is apparently intended to be temporary part of a class public interface? Why is the solver a separate class and not a method in the Sudoku class? Oh, wait, it's that, too. Very confusing.

Prefer integers to floating point numbers

On many machines, integer mathematics are far faster than floating point. Since your weighted values are simply the mathematical inverse of the number of possibilities per square, why not just use the former (which is always a small integer) rather than a floating point number? It would also simplify the code.

Eliminate parallel structures

In the Sudoku class, there are six different 9x9 structures, but they are largely redundant. I'd suggest instead that if you really want to hold all that data, a better way to do it would be to have a Square class and then create a single grid of those. It would simplify your code and make it much clearer.