Log in

August 24th, 2008 - 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).

Read more...Collapse )

Previous day (Calendar) Next day