I've updated PADS, my Python algorithm implementation library, to include

• The condensation of a directed graph.


• A bit-parallel algorithm for testing reachability in a directed acyclic graph; after a linear number of bit-vector operations, one can test reachability between any pair of vertices in constant time.


• A 2-satisfiability solver that uses reachability in the condensation of an implication graph to determine which variables have values that are fixed to true or fixed to false in all solutions to a given 2SAT instance.


• An optional rule for my Sudoku solver that transforms the puzzle into a 2SAT instance with at least as many solutions, and uses the fixed variables of this instance to make inferences about the puzzle.

( Some details )

The new smarter Sudoku solver still needs to backtrack on some puzzles, but many fewer of them than before. Here's one that it still finds difficult:

 ----------------------------------- 
| .   .   . | 9   .   2 | .   .   . |
|           |           |           |
| 8   .   . | .   4   . | .   .   3 |
|           |           |           |
| .   4   . | 7   .   . | 1   .   . |
|-----------------------------------|
| .   .   6 | .   .   9 | .   .   1 |
|           |           |           |
| .   2   . | .   .   . | .   7   . |
|           |           |           |
| 5   .   . | 3   .   . | 4   .   . |
|-----------------------------------|
| .   .   7 | .   .   3 | .   6   . |
|           |           |           |
| 6   .   . | .   1   . | .   .   5 |
|           |           |           |
| .   .   . | 2   .   6 | .   .   . |
 ----------------------------------- 

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.

J. J. Hopfield, of neural net fame, just put out a new paper on associative memory and Sudoku. The Sudoku part involves constructing a (highly nonrandom) neural net that models a linear programming relaxation of the puzzle; as would perhaps be unsurprising to IPCO types, it works well on instances of moderate difficulty and only needs a small amount of branching even on quite hard instances. More intriguing to me in connection to Sudoku were some earlier examples (figures 1 and 2) of figures where the human visual system can find information quickly amid what seems a lot of noise, and where once found the signal seems to "pop" from the field; I sometimes get a similar "pop" feeling when I am solving Sudoku instances by hand, so (whether or not one believes that our eyes can solve arbitrary linear programs) he may be on a good track by using similar mechanisms to explain Sudoku solving and human visual memory.

Via meep: Snakes on a Sudoku. I'd say something about sharks and jumping but I think the metaphor is already quite mixed enough.

I just updated my PADS library to include some quick code for computing minimum spanning trees, via Kruskal's algorithm. Very simple given the prior existence in the library of union-find.

The same update also adds another case to the Sudoku solver's rectangle rule, that I found while trying to solve a "diabolic" puzzle in the LA Times last week. It didn't help solve that puzzle, but I want my program to be able to do anything I know to do by hand...

ETA: The impetus for me to implement this was a query from Mauro Cherobini, who is using minimum spanning trees to cluster spatial messaging data. Apparently the data set size is small enough that it's not necessary to go to an O(n log n) Delaunay triangulation based MST algorithm.

According to Ivars Petersen's MathTrek, tomorrow's episode of Numb3rs involves solving Sudoku puzzles, with a mention of counting how many possible puzzles there are. What this could have to do with antiterrorist investigation is a bit of a mystery to me... I haven't been watching the show (or, really, any TV since the Olympics ended) but it's amusing to see this sort of math get some attention. The show's producers also have a pdf classroom worksheet on Sudoku and latin squares.

Via WendSight (also seen on tdj): Sudoku solutions via X-ray diffraction phase reconstruction algorithms. Details unavailable on the press release, nor on Elser's home page... I'm guessing this is overhyped: it's an NP-hard problem, so it's unreasonable to claim that an efficient algorithm solves all instances. But I don't know whether the hype is in the implication that the algorithm is efficient, or the "all instances" part, and it's quite possible that whatever Elser has is a new and interesting solution technique.

My department's web site has added a new feature highlighting research topics from the faculty, with some kind of randomization so that you see different highlights each time you visit, and my sudoku research is one of the first three topics they're highlighting. It doesn't give a lot of detail, but it has a good brief discussion of the research issues I care about with a pointer to the paper for more information.

I finally tracked down the "triple threat in bilocal analysis" bug that was occasionally biting my Sudoku program. More for my own benefit than because I think anyone else might care, here's the explanation.

( Read more... )

Via Tyler H.: Hamster Sudoku. Or neon Sudoku. Or Cthulhu Sudoku. Or whatever other flickr keyword you prefer...

My recent post on Sudoku deductions using the knowledge that the solution is unique led me to re-think what complexity class puzzles like Sudoku should be classified under. Most sources including my own paper simply cite the puzzle as being NP-complete, as proven by Yato and Seta. But is it really? Complexity theory has ways of incorporating the knowledge that a puzzle has a unique solution, and they lead to complexity classes different from NP. It seems these classes, not NP, are the right level for describing the hardness of Sudoku puzzles.

( Read more... )

I had thought the "digit" rule of my Sudoku program was a non-backtracking equivalent of nishio. Turns out not.

( Read more... )

Just committed and uploaded a new version of PADS, where I greatly improved my Sudoku solver's ability to explain in English the deductions it makes. As part of this text generation capability, I needed to wrap lines of text to fit within a console window, and rather than doing it with the obvious (and perfectly adequate) greedy algorithm, I decided to make more work for myself by incorporating a more flexible and powerful TeX-like system (in Wrap.py) in which one assigns penalties to different possible lines in a paragraph depending on e.g. how much they fall short of the optimal target width, and searches for the partition of the paragraph into lines that minimizes the sum of the penalties.

( Read more... )

Just uploaded four newish papers to arxiv. They are:

• The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data (with Mike Goodrich and Jonathan Sun, from SoCG'05). Random sampling gives an efficient way of dynamizing quadtrees and performing approximate range queries with them.


• Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional Data Sets (with Lars Arge and Mike Goodrich, from PODC'05). Distributed versions of tries, skip quadtrees, trapezoidal decompositions, etc.


• Confluent Layered Drawings (with Mike Goodrich and Jeremy Meng, from Graph Drawing '04). A combination of our confluent drawing idea from GD'03 with Sugiyama style layered drawings. This is the paper that the leaning tower of Pisa logo (at right) for SoCG'05 came from.


• Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku. A combination of graph algorithms and rule-based puzzle solving heuristics. I still need to figure out where to send this, maybe another combinatorial games workshop of some sort?

I also heard this week that another confluent drawing paper with Goodrich, Meng, and myself has gotten into GD'05. Good news, because that means Jeremy has enough publications to put together a very coherent thesis. Will upload after responding to referee suggestions.

I figured it might be useful to collect the updates to different parts of my web existence in a single place, and easier to use livejournal than to roll my own. So here's the first one:

I just updated my Python algorithms library, PADS. Newly added are Sudoku.py, a command-line Sudoku puzzle solver/generator (type "python Sudoku.py -h" at a command line in the PADS directory for more information on how to use it), Repetitivity.py, analysis of paths in graphs that have no two equal consecutive edge labels (see forthcoming paper, used by Sudoku), and StrongConnectivity.py, DFS-based construction of strongly connected components in digraphs. I also added code to BipartiteMatching.py to find edges that can not participate in any perfect matching of a given graph (also used by Sudoku).

I thought the trick for finding unmatchable edges in bipartite graphs was cute; it was new to me, though probably familiar to matching specialists. Find a single perfect matching in the bipartite graph, orient the unmatched edges from one side of the bipartition to the other, and orient the matched edges in the opposite direction. The unmatchable edges are the unmatched ones that have endpoints in different strongly connected components of the resulting digraph.