hadoop-mapreduce-project/hadoop-mapreduce-examples/src/main/java/org/apache/hadoop/examples/dancing/package.html - hadoop - Git at Google

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