So apparently aptitude can solve Sudokus, now that's a surprising side effect of having an advanced SAT solver for dependencies.

Package Management Sudoku https://web.archive.org/web/20080823224640/http://algebraicthunk.net/~dburrows/blog/entry/package-management-sudoku/