

PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 
See:
Description
Interface Summary  

DancingLinks.SolutionAcceptor<ColumnName>  Applications should implement this to receive the solutions to their problems. 
Pentomino.ColumnName  This interface just is a marker for what types I expect to get back as column names. 
Sudoku.ColumnName  This interface is a marker class for the columns created for the Sudoku solver. 
Class Summary  

DancingLinks<ColumnName>  A generic solver for tile laying problems using Knuth's dancing link algorithm. 
DistributedPentomino  Launch a distributed pentomino solver. 
DistributedPentomino.PentMap  Each map takes a line, which represents a prefix move and finds all of the solutions that start with that prefix. 
OneSidedPentomino  Of the "normal" 12 pentominos, 6 of them have distinct shapes when flipped. 
Pentomino  
Pentomino.Piece  Maintain information about a puzzle piece. 
Sudoku  This class uses the dancing links algorithm from Knuth to solve sudoku puzzles. 
Enum Summary  

Pentomino.SolutionCategory 
This package is a distributed implementation of Knuth's dancing links algorithm that can run under Hadoop. It is a generic model for problems, such as tile placement, where all of the valid choices can be represented as a large sparse boolean array where the goal is to pick a subset of the rows to end up with exactly 1 true value in each column.
The package includes two example applications: a pentomino solver and a sudoku solver.
The pentomino includes both a "normal" pentomino set and a onesided set where the tiles that are different when flipped are duplicated. The pentomino solver has a Hadoop driver application to launch it on a cluster. In Knuth's paper on dancing links, he describes trying and failing to solve the onesided pentomino in a 9x10 board. With the advances of computers and a cluster, it takes a small (12 node) hadoop cluster 9 hours to find all of the solutions that Knuth estimated would have taken him months.
The sudoku solver is so fast, I didn't bother making a distributed version. (All of the puzzles that I've tried, including a 42x42 have taken around a second to solve.) On the command line, give the solver a list of puzzle files to solve. Puzzle files have a line per a row and columns separated by spaces. The squares either have numbers or '?' to mean unknown.
Both applications have been added to the examples jar, so they can be run as:
bin/hadoop jar hadoopexamples*.jar pentomino pentoutdir bin/hadoop jar hadoopexamples*.jar sudoku puzzle.txt
I (Owen) implemented the original version of the distributed pentomino solver for a Yahoo Hack day, where Yahoos get to work on a project of their own choosing for a day to make something cool. The following afternoon, everyone gets to show off their hacks and gets a free tshirt. I had a lot of fun doing it.


PREV PACKAGE NEXT PACKAGE  FRAMES NO FRAMES 