Update: There are more notes on how aptitude performs as a Sudoku solver here.
Russell Coker recently wrote a post entitled Ownership of the Local SE Linux Policy. This post has nothing to do with the substance of his post, which is a discussion of how distributions should configure SELinux by default. I know nothing about SELinux, but something that Russell said in passing caught my attention:
I am not aware of the Debian package dependencies (or those of any other distribution) being about to represent that the postfix package depends on selinux-policy-default-postfix if and only if the selinux-policy-default package is installed. Please note that I am not suggesting that we add support for such things, a package management system that can solve Sudoku based on package dependency rules is not something that I think would be useful or worth having.
As it happens, a little-known fact about the Debian packaging system is that you can, in fact, describe Sudoku puzzles in it!
Note for the impatient: If you want to skip all this talk and jump to the code, see debsudoku.py.
For those of you who, like me, are not Sudoku-heads, here's a quick
summary of the rules (for the common case of a game with 3
- The game is played by filling in a 9-by-9 grid with numbers between 1 and 9, inclusive. The board is divided into 9 3-by-3 blocks of grid cells in the obvious way.
- All the cells in a column must contain different numbers.
- All the cells in a row must contain different numbers.
- All the cells in a block must contain different numbers.
There are many ways that you could convert a Sudoku problem into a
Debian package archive, but here's a particularly simple one that is
close to my summary of the rules. Create 9 * 9 * 9 = 729 packages,
R stands for row,
C for column, and
V for value. Each of these packages represents writing the value
V in the cell (
C). To describe the relationships of each
cell to the other cells in the problem, we can create several virtual
The virtual package
cellR.Crepresents the statement
The cell (It will be used to ensure that only one value is placed in any particular cell, and to ensure that all the cells in the puzzle are filled in with something.
C) has been filled in with some value.
The virtual package
blockR.C-Vrepresents the statement
A cell in the block (The block
C) has been filled in with the value
coordinatesare the block-row and block-column containing the cell; for instance, the cell at (5, 8) is in block (2, 3). This package will be used to ensure that only one cell in a given block contains the same value.
The virtual package
rowR-Vrepresents the statement
A cell in the rowIt will be used to ensure that no two cells in any given row have the same value.
Rhas been filled in with the value
The virtual package
colC-Vrepresents the statement
A cell in the columnIt will be used to ensure that no two cells in any given column have the same value.
Chas been filled in with the value
Converting these requirements to package dependencies is quite
straightforward. For the package
cellR.C-V, in block row
BC, we add these lines to the package's definition:
Provides: cellR.C, blockBR.BC-V, rowR-V, colC-V Conflicts: cellR.C, blockBR.BC-V, rowR-V, colC-V
For instance, the cell at (5, 8) will get these provides/conflicts for
Provides: cell5.8, block2.3-2, row5-2, col8-2 Conflicts: cell5.8, block2.3-2, row5-2, col8-2
This relies on the fact that self-conflicts are ignored (see Debian Policy section 7.4).
To actually describe the puzzle we want to solve, we need to add another package that requires two things:
- Every cell contains a value.
- The cells that the problem fixes have their fixed values.
Package: puzzle Depends: cell1.1, cell1.2, ..., cell5.9-3, cell6.1, ....
if we want to require that the cell at (5, 9) contains the value 3.
As a proof-of-concept, I have written a hacky Python script, named
debsudoku.py, that can convert
ksudoku saved games into
Packages files suitable for use with
apt-get or aptitude. In fact, it has two modes:
which implements the conversion described above, and
which implements a different but logically equivalent conversion using
only Depends instead of Conflicts. To use the script, save a ksudoku
board without doing any work on it, then run
python debsudoku.py /path/to/the/ksudoku/board
I've only done minimal testing on this, so don't use it to fly airplanes (in fact, please don't use any Sudoku player to fly airplanes), but I did use it, in combination with aptitude, to solve a single ksudoku puzzle.
Interestingly, in a test with an easy puzzle generated by ksudoku,
aptitude was able to solve the puzzle in just a
few seconds when it was expressed with the
but failed to find a solution at all using
depends (I stopped
it after several minutes).
I think this is due to how the
depends reduction is performed.
Take rows: instead of generating conflicts between cells in a row, it
requires that each row contain every number between 1 and 9. The
problem with this is that aptitude's resolver functions poorly when
there are non-obvious conflicts in the dependency structure. It will
decide to try a combination of packages that can't be installed
together, but it won't realize it. As a result of this, it ends up
trying many possible combinations of packages. For instance, it might
try to place the number 3 in both (2, 5) and (5, 5). There is no
dependency outlawing this in the
depends reduction, so aptitude
will happily continue trying to resolve dependencies. Since it has
used 3 twice in the fifth column, it will not be able to find any way
to resolve all the dependencies that state that
all the numbers
between 1 and 9 appear in the 5th column, but it lacks the
higher-level reasoning that would allow it to break out; it will end
up trying many or most of the possible ways of filling cells in before
it gives up on the offending re-use of 3.
Luckily, real-world package archives (what the aptitude resolver is designed to run on) don't usually look like this.