Abusing the depsolver for fun/Sudoku - James Antill
Aug. 24th, 2008
11:58 pm - Abusing the depsolver for fun/Sudoku
After seeing the article on sudoku in apt/dpkg, I naturally thought "I wonder how you can do that in rpm". The big differences (from what I read/understood of the article) being that rpm doesn't mind if two packages with the same virtual provide are installed at once where dpkg does (and their "game" relies on that).
The natural solution seemed to be to use provides and conflicts, although I didn't think of other forms for long before just trying to implement that one :). The basic premise is to have 9 * 9 * 9 packages, each providing cell_1.1.1 through cell_9.9.9 (which is the row, column and value) and cell_value_1.1 through cell_value_9.9 (just the row and column). Then require all 82 cell_values, with any specific cells. You then just add conflicts in each package obeying the rules for block, row and column. Simple.
I was pretty sure yum would fail at solving the sudoku puzzles, because it basically requires that when you get multiple answers to a provides question (what package provides cell_1.1) you need to repeatedly narrow it down based on future information. This is kind of on the longer term. road map for yum so that it'll get better results, in certain edge cases, for real packages in real repositories.
Read on for scripts/repos. and results (spoiler, yum does fail and smart succeeds).
I've made the scripts and repositories for the game and puzzles available. So it's as simple as possible to try it out.
The puzzle_complete_* packages are complete puzles (all 82 cells prefilled, and the "game" included). The puzzle_(medium|hard)_* packages are just random games I copied from gnome-sudoku on medium/hard setting. Note that you can't actually do the "install" as the packages don't exist in anything other than metadata, but that's probably a good thing.
yum-3.2.18 just picks some "random" values for the missing cells, and then complains about the resulting conflicts.
apt-0.5.15lorg3.94-3.fc9.x86_64 seems to decide a bunch of the cells are bad, and gives an "unmet dependencies" error.
smart-0:0.52-54.fc9.x86_64 solves the medium puzzles! And it hasn't given up on one of the non-guessing hard puzzles yet, although it's been over 20 minutes.
Update: smart solves hard_1 (no guessing required) and hard_2 (which requires guessing), taking only 3-4 minutes for hard_2 although hard_1 takes it just over 30 minutes. Interesting.