apache / hadoop-mapreduce / refs/heads/trunk / . / src / examples / org / apache / hadoop / examples / dancing / package.html

<html> | |

<!-- | |

Licensed to the Apache Software Foundation (ASF) under one or more | |

contributor license agreements. See the NOTICE file distributed with | |

this work for additional information regarding copyright ownership. | |

The ASF licenses this file to You under the Apache License, Version 2.0 | |

(the "License"); you may not use this file except in compliance with | |

the License. You may obtain a copy of the License at | |

http://www.apache.org/licenses/LICENSE-2.0 | |

Unless required by applicable law or agreed to in writing, software | |

distributed under the License is distributed on an "AS IS" BASIS, | |

WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |

See the License for the specific language governing permissions and | |

limitations under the License. | |

--> | |

<body> | |

This package is a distributed implementation of Knuth's <a | |

href="http://en.wikipedia.org/wiki/Dancing_Links">dancing links</a> | |

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 <b>true</b> value | |

in each column. | |

<p> | |

The package includes two example applications: a <a | |

href="http://en.wikipedia.org/wiki/Pentomino">pentomino</a> solver and | |

a sudoku solver. | |

<p> | |

The pentomino includes both a "normal" pentomino set and a one-sided | |

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 one-sided 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. | |

<p> | |

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. | |

<p> | |

Both applications have been added to the examples jar, so they can be | |

run as: | |

<pre> | |

bin/hadoop jar hadoop-*-examples.jar pentomino pent-outdir | |

bin/hadoop jar hadoop-*-examples.jar sudoku puzzle.txt | |

</pre> | |

<p> | |

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 | |

t-shirt. I had a lot of fun doing it. | |

</body> | |

</html> |