Return to Question

List of types defined and used throughout the program :

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.

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 :

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.

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.

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:

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.

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:

The SetPossibilityCount() function sums the 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. The GenerateWeightValues() function uses 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 instance of the same class.

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.