Log in

Abusing the depsolver for fun/Sudoku - James Antill

Aug. 24th, 2008

11:58 pm - Abusing the depsolver for fun/Sudoku

Previous Entry Share Next Entry

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.

Results are:


Date:August 26th, 2008 09:05 pm (UTC)


Please test with zypper too, rpms for zypper and friends can be found @ bugzilla.redhat.com.

the sat-solver backend in zypper should map directly to the sudoku problem?

(Reply) (Thread)