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.
(emphasis added)
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
blocks
):
- 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,
named
cellR.C-V where
R stands for
row,
C for
column, and
V for
value. Each of these packages represents writing the value
V in the cell (
R,
C). To describe the relationships of each
cell to the other cells in the problem, we can create several
virtual
packages:
- The virtual package
cellR.C represents the statement The cell
(R, C) has been filled in with some value.
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.
- The virtual package
blockR.C-V represents the statement A cell
in the block (R, C) has been filled in with the value V.
The block coordinates
are 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-V represents the statement A cell in
the row R has been filled in with the value V.
It will be
used to ensure that no two cells in any given row have the same
value.
- The virtual package
colC-V represents the statement A cell in
the column C has been filled in with the value V.
It will
be used to ensure that no two cells in any given column have the
same value.
Converting these requirements to package dependencies is quite
straightforward. For the package
cellR.C-V, in block row
BR and
block column
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
V=2:
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.
For instance,
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.
Proof-of-concept
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:
conflicts
,
which implements the conversion described above, and
depends
,
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.
Real-world evaluation
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
conflicts
reduction,
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.
(This is a more detailled and hopefully better structured explanation
of the topic of my Lightning Talk during Debconf)
With the ever growing number of packages in our archive we need
ever better methods to structure, sort, and search this collection.
While projects like debtags
try to improve the search in packages, my idea is about improving
the way the results are displayed.
There is one relation between packages that is currently never strongly
featured when presenting package meta-data:
the source ↔ binary relation.
Usually package managers operate either on binary packages
or source packages, but seldomly do they expose the fact that
one is generated from the other.
In the trivial case of one source package producing one binary
package there is probably nothing to gain. But there are a large
number of source packages where this isn't true (at the moment
about 29% of all the source packages in main build more than
one binary package, together producing about 61% of all binary packages).
I have the idea (which so far is nothing more) that if we could
present packages through their source packages that this could drastically
reduce the number of packages to choose from and make some common
search actions more effective.
This is not by any meaning a trivial task, though, since on the
other hand not all source packages necessarily produce binary packages
that have much to do with each other, and even for the ones that do,
the exact relationship between the binary packages can vary greatly.
Also some source packages are really belonging together but are split
to make maintenance easier (e.g. KDE and X.org). These splits might not
necessarily make any sense to an user.
Some ideas what to implement in terms of code to make it easier to
let the user benefit from the fact that multiple binaries have the
same source:
Computer security is generally defined as the following:
I’ve had little time in the four years I’ve lived in Roslindale to get involved in community volunteer efforts. My wife Rachele, however, has devoted several years to efforts such as the Roslindale Community Center, 
Some interesting two days have just passed. I took the airplane from
I tried 
What I liked
.
I, for one, like 
Since 2005, the talks at Debconf have been recorded on video, to be