Sudoku solver program: A challenge just for fun (2).

Related to the original post, I’m going to propose another way to solve a sudoku puzzle.

This program will try to find all the puzzle solutions in a more efficient way using a constraint oriented algorithm.

The basic idea and the source code dates from the year 2005, when the puzzle came into fashion.

The algorithm basis

The key factors are the uncertainty and the uniqueness constraints.

In a sudoku puzzle, we have 9×9 squares, each of them belonging to 3 uniqueness constraint groups: a row, a column and a 3×3 sub-grid. There are 3×9 restriction groups in total: 9 rows, 9 columns and 9 sub-grids.

Each square has a state: the digit set that can be fitted without violating the 3 uniqueness constraints, so the total table state will be the set of all the 81 individual states. Without any information, the initial state is the one with the maximum uncertainty: all the digits are possible in each square.

Furthermore, each square state gives us an uncertainty metric: the number of possible digits, so considering the uncertainty of all the squares, we can obtain a global uncertainty metric. Our strategy will be to reduce this uncertainty until reach the minimum state: the solution.

We have two ways to perform this reduction:

1. Using direct rules: given a correct state, we move to other correct states that have progressively less uncertainty. No errors are made in this one-way type of movements.
2. Using hypothesis: given a correct state, we make an assumption which takes us to another less uncertainty state that we suppose as correct . If we reach to an impossible state, we rule out the last hypothesis. These are the kind of rules considered in the original post.

Using the second kind rules in a standalone way involves a typical brute-force algorithm. But in this algorithm, combining the two types will allows us to reduce the space into which the hypothesis are made: the less the uncertainty is, the less assumptions we’ll need.

So the basic idea is to give priority to type 1 rules before making any hypothesis, but, how these rules are?.

The basic rule is: given a restriction group C, i.e., a set of 9 squares, let A the state of one of them (the set of possible digits of that square) and let B the set of squares of C with their state contained in A. If the cardinal of A (see cardinal number) is the same as the one of B, then the squares of C which aren’t contained in B (C\B) can’t contain in their states any element of A, so those elements can be removed from their states, and, consequently, the uncertainty is reduced.

In other words, if we want to distribute a set of N digits (A) among the squares of a restriction group (C), and there are exactly N squares (B) that accepts only digits from that set, my N digits necessarily have to be distributed among those N squares, and the other 9 – N (C\B) squares can’t receive any of them. A simple example: if a square of a row has its state fixed to one digit (no uncertainty), that digit can’t be placed on any of the 8 remaining squares of the same row.

One interesting thing is that when we reduce the uncertainty state of a square, we can trigger recursively a new reduction in their related squares, i.e., the other squares belonging to its restriction groups. This yields a notable global uncertainty reduction, given an initial information, without the necessity of making assumptions.

The algorithm is as follows:

1. We start from the maximum uncertainty state: a void table where all the digits (1..9) are possible in all the squares.
2. Use the initial table information to make type 1 reductions. If the puzzle is solved, we exit (many cases can be solved using only this technique).
3. Make a possible assumption over the next square with uncertainty. We have three possible results:
   • If the puzzle is solved, we exit.
   • If we arrive at an inconsistent state, the last hypothesis was incorrect and we try the next possible one over the same square.
   • Otherwise (the puzzle is not solved yet), we jump to the point 3.

The code

The program is written in C and has been tested under GNU Linux. More details about its usage and table format can be found in the README file.

The code is quite clear, so I’ll just give some guidelines to help its understanding:

• About the data model, the structures square_t and square_group_t models, respectively, a square and a restriction group. No more complex data structures are needed.
• As the square state is coded as a bit field (an unsigned short where the first 9 bits represent the possible digits), the following bitwise operations can be done:
  • An uncertainty reduction operation consists in removing a bit subset from a bit set: a = a and not(b) (the set b is removed from a).
  • A set inclusion can be detected checking the equality:  a or b == b? (is a contained in b?)
  • The number of considered digits (the number of set bits) can be computed with the built-in function __builtin_popcount.
  • The digit coded by a set of bits with only one set bit can be obtained with the built-in function __builtin_ffs, wich returns the first set bit index.
• The method uncertainty_reduction performs a type 1 rule over a square (the recursion enables to trigger other reductions in the related squares), and the method make_assumption performs a type 2 rule over a square.

Results

Whereas the original post presented us a simple algorithm where some basic AI techniques and general concepts were used, this algorithm uses a more specific and optimized approach, and therefore the performance is higher for common sudokus.

Links

• Sudoku solver source code