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