Thursday, March 1, 2012

Doku: solve Sudoku-like puzzles with Ruby!

This week I published my first Ruby gem! It's called Doku and it can solve Sudoku-like puzzles quickly using the Dancing Links algorithm by Donald Knuth. Currently it can solve these types of puzzles:


It takes less than a second to solve Sudoku and Hexadoku puzzles.

Here is some example code:
require 'rubygems'
require 'doku'

puzzle = Doku::Sudoku.new <<END
...|..8|...
..7|.35|..9
5..|4.6|8..
---+---+---
...|..4|2..
4..|...|.37
8..|...|5..
---+---+---
.9.|.67|...
..3|...|1.5
...|...|..3
END

solution = puzzle.solve

puts solution.get(7,8)   # => 9
puts solution            # prints the solution in same format as above

Motivation

Back in July 2011, I saw this puzzle in Elektor magazine:



(That's an SVG image, so you can see it larger!)

This beast is called Hexamurai. It has 768 squares, which is 9.5 times larger than Sudoku. It is made by superimposing 5 Hexadoku (16×16 Sudoku) puzzles on top of eachother. One of the Hexadokus is in the center, and each of the other four is offset by 8 in some direction from the central puzzle.

When I looked at this puzzle I knew two things:
  1. Solving this puzzle is an awesome challenge.
  2. Solving this puzzle by hand is not fun and a waste of my time.

A simple, naive algorithm is not good enough to solve Hexamurai. I learned this the hard way; after my first algorithm languished for hours with no progress I had to abandon it.

It turns out that people have been solving Sudoku-like puzzles efficiently by reducing them to exact cover problems and then using the Dancing Links algorithm. If you're interested, I definitely recommend reading the PDF version of Knuth's paper. It's only 26 pages.

The exact cover problem for that particular Hexamurai consists of 3433 sets that contain 2872 different elements. With Doku, I was able to solve it in about 90 minutes!

That was back in August 2011. Since then, I have spent a lot of time refactoring, polishing, and adding useful features to every part of the gem.

Doku is general

Doku is designed to solve Sudoku-like puzzles. More precisely, it can solve any puzzle consisting of a set of glyphs (i.e. symbols), a set of squares, and a set of groups of squares. Additionally, the number of squares in each group must be equal to the number of glyphs. Given a partial assignment of glyphs to squares, Doku can figure out how to assign a glyph to every square such that no two squares in the same group are assigned the same glyph.

You can define your own puzzle class where the squares and glyphs are any type of Ruby object you want except nil. You are not forced to arrange your squares on a 2D grid: they can have any structure you want.

If you know of any interesting Sudoku-like puzzles that are not already supported by Doku, let me know in the comments and I'll probably implement a class for them!

Doku classes include batteries

Every puzzle class, including Sudoku, Hexadoku, and Hexamurai are well thought out and designed to be generally useful. Each of these classes inherits from a base class (Puzzle) which provides equality comparison, solution checking, and proper behavior for dup and clone. Each class includes a module (PuzzleOnGrid) that provides convenient methods for converting instances to strings and strings to instances (see the example code above).

Doku is elegant

Doku is meant to showcase beautiful Ruby code. Test-driven development was used at all times during the development of this gem. I have spent many hours reviewing the code, looking for ways to make it simpler, and refactoring it. Every class and public method is documented. Every method is short. There are no ugly hacks. All method names were chosen carefully. At every level, the power of the Ruby language is exploited to its fullest potential.

Learn more!


P.S. Here's the solution to that monstrous puzzle:

Posted by at
Labels:

1 comment:

Note: Only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)