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++).

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.
3. Each value in the 9x9 array of signed integers, represent a single square in the sudoku puzzle board.
4. the first array-index represents the board's row number and the second array-index represents the board's column number.

Therefore, this representation is the one that gets acquired from the user as a user-input. And is the most fundamental representation of the puzzle board.

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. The indexing is same as for BoardGrid. The first index (towards the left) represents the rows and the second index represents the board's column.
4. An object of this type is used for holding the possible list of values that can be inserted into a particular square.
5. To address a square, we may write p [row_number] [column_number], if p is an object of possibilitySet.

The following defines the list of all symbols, that's used throughout the program to represent bit-field values:

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 being filled during the brute-force trial and error process. 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 system 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() 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 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 locally calling the same member-function belonging to a different instance of the same class. This is helpful, in preserving the "state", when the functionality is quite complicated.

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-