Debian package-manager Sudoku

While poking around after my previous post, I found dburrows' posts on package management Sudoku and package management Sudoku 2. Burrows started with an offhand remark by someone else that one wouldn't want to have "a package management system that can solve Sudoku based on package dependency rules", took it as a challenge, and found a way to translate Sudoku puzzles automatically into package dependencies and solve them with the off-the-shelf package managers.

A little context: as the Debian linux FAQ describes, a package is a collection of files (code, configuration files, etc) needed to implement a set of related linux commands. Some packages need other packages to be installed as well, and some packages conflict, meaning that they cannot both be installed in the same system (installing one of them will cause the other one to break). The package manager resolves these issues and tries to find a set of packages to install that will include the ones you want and everything else they might need.

As Burrows second post describes, though both Sudoku and package dependency resolution are NP-complete constraint satisfaction type problems, they have different qualities leading to different solution techniques, so solving a Sudoku puzzle in this way is surprisingly slow (though maybe the bigger surprise is that it works at all). Anyway, the idea of testing the package management system by using these puzzles has already led to improvements that should speed it up for less artificial problems as well.

Comments: