<img src="https://github.com/nilostolte/Sudoku/assets/80269251/ef41fe74-1b8b-415a-bab4-a65fd98ce03e" width="512" height="512"><br>

Sudoku

Simple 9x9 Sudoku brute force solver with intrinsic parallel candidate set processing using bits to represent digits in the [1, 9] range, and bitwise operations to test a candidate against the candidate set, all at once.

It can be upgraded for 16x16 or 25x25 grids.

The algorithm was implemented in Java, in C, as well as in Zig. The description below concerns the Java implementation, even though the C implementation is quite similar, but without classes. Zig implementation is similar to C's but faster and with an OOP style stack. In the Zig version many optimizations allowed to achieve a minimum running time of 0.7916 miliseconds for the same test grid run on my
Intel Core i7-2670QM @ 2.20GHz laptop:

<p align="center"> <img src="https://github.com/user-attachments/assets/ba6d2502-1c3b-4276-83cd-6f06a3476bcf" width="400"> </p>

The supplied Windows 64 executables for the C and Zig implementations can be used to solve arbitrary grids as described in the documentation.

Grid

This is the class containing the grid to be solved.

Input

The grid can be initialized using a 9x9 matrix of type char[][] or through a linear string containing all the elements, representating empty elements as 0 (or ' . ' in the C or Zig version), both given line by line. The char[][] is the unique input, however, and it must exist before being able to use any other input format. Even though the 9x9 matrix contains characters (it's a char[][]), the digits are not represented as ASCII or Unicode characters but rather as integers. In other words, the character '0' is actually represented by 0, and so forth.

In the string input format the string is just copied over the existing input char[][] matrix using the static function set. This string uses ASCII representation for the digits which are converted to integers by the function set.

An additional representation is possible, as illustrated in Main.java, by representing the charcater '0' with the character '.' in the string. In this case one adds .replace('.','0') at the end of the string as shown.

Both string input formats are common representations of Sudoku grids on the web.

Data Structures

The main data structure in Grid is matrix which is a 9x9 matrix in identical format as the input matrix for the grid. This is the matrix where the input matrix is copied to.

Auxiliary Data Structures

The main auxiliary data structures are the most interesting part of this class, besides the solver algorithm itself:

• lines - an array with 9 positions, each one, corresponding to a line in the grid, and functioning as a set where each bit represents a digit already present in that line.
• cols - an array with 9 positions, each one, corresponding to a column in the grid, and functioning as a set where each bit represents a digit already present in that column.
• cells - a 3x3 matrix, corresponding to a 3x3 cell that the grid is subdivided, with 9 positions, each one functioning as a set where each bit represents a digit already present in that cell.

Additional Auxiliary Data Structures

• stk - the stack to implement the backtracking algorithm. It uses an array of 81 positions. It uses the push and pop operators as shown in the algorithm below. The push operator not only stores the digit, its binary representation, the line and column (i and j) of the element inserted in a stack node (StkNode), "pushing" the node in the stack, but also inserts the digit in the internal matrix (matrix[i][j]) as well as its binary representation into the auxiliary data structures, thus, updating the candidate set of the new element inserted. The pop operation only removes the node from the stack, but the node is not garbage collected. It remains in the stack as an unused element. Nodes are lazily allocated, as null elements are found while pushing.
• cel - an array with 9 positions, each one is the inverse mapping of the indices in the lines and columns transformed into indices in the 3x3 matrix cells.

Representing a set of present digits with bits

All main auxiliary data structures use a common notation to represent a set of digits present in the line, column, or cell, accordingly. A bit is set to one at the position corresponding to a digit present in the set, or set to zero if it's position corresponds to a digit that is absent. By reversing the bits one gets the "candidate set" of digits that are still missing in the corresponding line, column or cell. For a better understanding of this candidate set scheme, please refer to the subsection explaining how digits are represented in binary.

Let's suppose a particular line, column or cell having the digits, 1, 3, 4 and 9. This set is then represented by the following binary number:

100001101 = 0x10D

• the first rightmost bit corresponds to the digit 1, and in this case it's present in the set already.
• the second bit on its left corresponds to the digit 2, and its clearly not present yet since its value is zero.
• bits three and four, corresponding to the digits 3 and 4, respectively, are clearly present, because they are both set to one.
• bits five, six, seven, and eight are all zeros, and thus, digits 5, 6, 7 and 8 are clearly absent in the set.
• bit 9 is 1. Therefore, the digit 9 is also present in the set.

Final Candidate Set

In order to obtain a candidate set for a given matrix[i][j] element of the grid one calculates:

lines[i] | cols[j] | cells[ cel[i] ][ cel[j] ] (1)

The expression in (1) gives a set where all bits containing zeros correspond to the available digits that are possible to be in matrix[i][j]. The candidate set is detected by the absent elements in the set, that is, all bits which are zero.

The interest in this notation is that the concatenation of all three sets is obtained by just using two bitwise or operations.

One can observe how cel inverse mapping works to access the corresponding cell in cells. First, i and j are used as indices in cel. cel[i] and cel[j] give the corresponding line and column in cells. Therefore, cells[cel[i]][cel[j]] corresponds to the cell where matrix[i][j] is contained.

Algorithm

    public void solve() {
        StkNode node;
        int digit = 1, code = 1, inserted;
        int i, j;
        char[] line = matrix[0];
        char c;
        i = j = 0;
        do {
            c = line[j];
            if (c == 0) {
                inserted = lines[i]|cols[j]|cells[cel[i]][cel[j]];
                for ( ; digit != 10 ; digit++, code <<= 1 ) {
                    if (( code & inserted ) == 0 ) {
                        push(i, j, code, digit);
                        digit = code = 1;
                        break;
                    }
                }
                if ( digit == 10 ) {            // no insertion -> backtrack to previous element
                    node = pop();               // pop previous inserted i, j, and digit
                    i = node.i;
                    j = node.j;
                    digit = node.digit;
                    code = node.code;
                    remove(node);               // remove digit from data structures
                    digit++; code <<= 1;        // let's try next digit;
                    line = matrix[i];           // maybe line has changed
                    continue;                   // short-circuit line by line logic
                }
            }
            if ( j == 8 ) {                     // line by line logic
                j = -1; i++;                    // last line element, advance to next line
                if (i < 9) line = matrix[i];    // update line from grid matrix
            }
            j++;                                // advance to next element in the line
        } while (i < 9);
    }

Binary Representation for Digits

In the binary representation, a digit is always a power of two, since it's a number with only one bit set to 1 at the position corresponding to the digit. The table below shows the correspondence between digits and their binary representation:

| Digit | Binary Representation | Hexadecimal | Decimal | | :---: | :-------------------: | :---------: | :-----: | | 0 | 000000000 | 0x000 | 0 | | 1 | 000000001 | 0x001 | 1 | | 2 | 000000010 | 0x002 | 2 | | 3 | 000000100 | 0x004 | 4 | | 4 | 000001000 | 0x008 | 8 | | 5 | 000010000 | 0x010 | 16 | | 6 | 000100000 | 0x020 | 32 | | 7 | 001000000 | 0x040 | 64 | | 8 | 010000000 | 0x080 | 128 | | 9 | 100000000 | 0x100 | 256 |

The binary representation as exposed in the table above is often called here as the "code" of the digit.

Implementation of Digit Retrieval in Candidate Set

As we can see the variable inserted contains the "candidate set" for a given matrix[i][j]. This algorithm is quite simple but it contains a major drawback. Since the digit is represented with a 1 bit in its corresponding position in variable code, and it accesses the candidate set in a sequential way,