More on sudokus

Not that I’m into doing sudokus, but it is a fun area for computer science to show that theory isn’t that far off from harmless applications in daily life.

About a year ago I wrote about solving sudokus with constraint programming, which some readers still found a bit too cumbersome. Santos-Garcia and Palomino had a go with it by rewriting rules to solve sudokus [1]. Note that even if you are number-averse, then the puzzle works equally fine with letters (sometimes called godoku or scramblets), colours, figurines and whatnot. Either way, solving the puzzle computationally is known to be NP-complete, and even with additional regional constraints the number of valid sudoku solution 9 x 9 grids is 6,670,903,752,021,072,963,960. So, niftier strategies to automatically solve a sudoku are welcome.

Santos-Garcia and Palomino used rewriting logic, which is a logic of concurrent change that can deal with states and highly nondeterministic concurrent computations. Then, the approach is to, first, represent sudokus as a set of objects where each object corresponds to a cell, and, second, use 8 local transition rules in a possibly concurrent system that can be applied concurrently to different fragments of this set of objects (see article for the formal specification).

Now, all this is specified and implemented in Maude [2], with implementation details in sections 4.1 and 4.2 of the article. With the Maude files for the specification to solve sudoku monsters (order 4), along with the complete specification of the sudoku solver, you can play with it yourself.

But, alas, it is a research article to see if it could be done with rewriting logic –which it can – and is not the fastest online software, as the authors note themselves, who mention [3] [4] and [5] that can do it faster. On the other hand, if you have time to solve sudokus, then you probably also have time to wait slightly longer for the solution if you haven’t found it already.

[1] Santos-Garcia, G. and Palomino, M. Solving Sudoku Puzzles with Rewriting Rules. Electronic Notes in Theoretical Computer Science, 2007, 176:79-93.
[2] Clavel, M., Duran, F.J., Eker, S., Lincoln, P., Marti-Oliet, N., Meseguer, J., and Talcott, C. Maude Manual (version 2.2). 2006.
[3] SuDoku Solver by Logic v1.4.
[4] Sudokulist. (step by step solver, with hints at each step)
[5] A Su Doku solver. (on sourceforge)

Advertisements

3 responses to “More on sudokus

  1. If you want to try out something new in sudoku, try shendoku, using the sudoku rules but playing two people, one against the other, like battleshipps. They have a free version to download at http://www.shendoku.com/sample.pdf . Anything else they are bringing out or they are working on you can find at http://www.shendoku.com or at they´r blog http://www.shendoku.blogspot.com . Have fun, I am. I specially like one slogan I heard about Shendoku: SUDOKU is like masturbation (on your own)…. SHENDOKU is like sex (it takes two).

  2. Pingback: Improbable Research » Blog Archive » 5524751496156892842531225600 on the road to Sudoku

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s