source: proiecte/HadoopJUnit/hadoop-0.20.1/docs/api/org/apache/hadoop/examples/dancing/package-summary.html @ 120

Last change on this file since 120 was 120, checked in by (none), 14 years ago

Added the mail files for the Hadoop JUNit Project
  • Property svn:executable set to *
File size: 12.2 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2<!--NewPage-->
3<HTML>
4<HEAD>
5<!-- Generated by javadoc (build 1.6.0_07) on Tue Sep 01 20:56:59 UTC 2009 -->
6<TITLE>
7org.apache.hadoop.examples.dancing (Hadoop 0.20.1 API)
8</TITLE>
9
10<META NAME="date" CONTENT="2009-09-01">
11
12<LINK REL ="stylesheet" TYPE="text/css" HREF="../../../../../stylesheet.css" TITLE="Style">
13
14<SCRIPT type="text/javascript">
15function windowTitle()
16{
17    if (location.href.indexOf('is-external=true') == -1) {
18        parent.document.title="org.apache.hadoop.examples.dancing (Hadoop 0.20.1 API)";
19    }
20}
21</SCRIPT>
22<NOSCRIPT>
23</NOSCRIPT>
24
25</HEAD>
26
27<BODY BGCOLOR="white" onload="windowTitle();">
28<HR>
29
30
31<!-- ========= START OF TOP NAVBAR ======= -->
32<A NAME="navbar_top"><!-- --></A>
33<A HREF="#skip-navbar_top" title="Skip navigation links"></A>
34<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
35<TR>
36<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
37<A NAME="navbar_top_firstrow"><!-- --></A>
38<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
39  <TR ALIGN="center" VALIGN="top">
40  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A>&nbsp;</TD>
41  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Package</B></FONT>&nbsp;</TD>
42  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <FONT CLASS="NavBarFont1">Class</FONT>&nbsp;</TD>
43  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-use.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A>&nbsp;</TD>
44  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
45  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
46  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
47  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
48  </TR>
49</TABLE>
50</TD>
51<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
52</EM>
53</TD>
54</TR>
55
56<TR>
57<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
58&nbsp;<A HREF="../../../../../org/apache/hadoop/examples/package-summary.html"><B>PREV PACKAGE</B></A>&nbsp;
59&nbsp;<A HREF="../../../../../org/apache/hadoop/examples/terasort/package-summary.html"><B>NEXT PACKAGE</B></A></FONT></TD>
60<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
61  <A HREF="../../../../../index.html?org/apache/hadoop/examples/dancing/package-summary.html" target="_top"><B>FRAMES</B></A>  &nbsp;
62&nbsp;<A HREF="package-summary.html" target="_top"><B>NO FRAMES</B></A>  &nbsp;
63&nbsp;<SCRIPT type="text/javascript">
64  <!--
65  if(window==top) {
66    document.writeln('<A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>');
67  }
68  //-->
69</SCRIPT>
70<NOSCRIPT>
71  <A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>
72</NOSCRIPT>
73
74
75</FONT></TD>
76</TR>
77</TABLE>
78<A NAME="skip-navbar_top"></A>
79<!-- ========= END OF TOP NAVBAR ========= -->
80
81<HR>
82<H2>
83Package org.apache.hadoop.examples.dancing
84</H2>
85This package is a distributed implementation of Knuth's <a
86href="http://en.wikipedia.org/wiki/Dancing_Links">dancing links</a>
87algorithm that can run under Hadoop.
88<P>
89<B>See:</B>
90<BR>
91&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<A HREF="#package_description"><B>Description</B></A>
92<P>
93
94<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
95<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
96<TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2">
97<B>Interface Summary</B></FONT></TH>
98</TR>
99<TR BGCOLOR="white" CLASS="TableRowColor">
100<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/DancingLinks.SolutionAcceptor.html" title="interface in org.apache.hadoop.examples.dancing">DancingLinks.SolutionAcceptor&lt;ColumnName&gt;</A></B></TD>
101<TD>Applications should implement this to receive the solutions to their
102 problems.</TD>
103</TR>
104<TR BGCOLOR="white" CLASS="TableRowColor">
105<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Pentomino.ColumnName.html" title="interface in org.apache.hadoop.examples.dancing">Pentomino.ColumnName</A></B></TD>
106<TD>This interface just is a marker for what types I expect to get back
107 as column names.</TD>
108</TR>
109<TR BGCOLOR="white" CLASS="TableRowColor">
110<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Sudoku.ColumnName.html" title="interface in org.apache.hadoop.examples.dancing">Sudoku.ColumnName</A></B></TD>
111<TD>This interface is a marker class for the columns created for the
112 Sudoku solver.</TD>
113</TR>
114</TABLE>
115&nbsp;
116
117<P>
118
119<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
120<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
121<TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2">
122<B>Class Summary</B></FONT></TH>
123</TR>
124<TR BGCOLOR="white" CLASS="TableRowColor">
125<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/DancingLinks.html" title="class in org.apache.hadoop.examples.dancing">DancingLinks&lt;ColumnName&gt;</A></B></TD>
126<TD>A generic solver for tile laying problems using Knuth's dancing link
127 algorithm.</TD>
128</TR>
129<TR BGCOLOR="white" CLASS="TableRowColor">
130<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/DistributedPentomino.html" title="class in org.apache.hadoop.examples.dancing">DistributedPentomino</A></B></TD>
131<TD>Launch a distributed pentomino solver.</TD>
132</TR>
133<TR BGCOLOR="white" CLASS="TableRowColor">
134<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/DistributedPentomino.PentMap.html" title="class in org.apache.hadoop.examples.dancing">DistributedPentomino.PentMap</A></B></TD>
135<TD>Each map takes a line, which represents a prefix move and finds all of
136 the solutions that start with that prefix.</TD>
137</TR>
138<TR BGCOLOR="white" CLASS="TableRowColor">
139<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/OneSidedPentomino.html" title="class in org.apache.hadoop.examples.dancing">OneSidedPentomino</A></B></TD>
140<TD>Of the "normal" 12 pentominos, 6 of them have distinct shapes when flipped.</TD>
141</TR>
142<TR BGCOLOR="white" CLASS="TableRowColor">
143<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Pentomino.html" title="class in org.apache.hadoop.examples.dancing">Pentomino</A></B></TD>
144<TD>&nbsp;</TD>
145</TR>
146<TR BGCOLOR="white" CLASS="TableRowColor">
147<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Pentomino.Piece.html" title="class in org.apache.hadoop.examples.dancing">Pentomino.Piece</A></B></TD>
148<TD>Maintain information about a puzzle piece.</TD>
149</TR>
150<TR BGCOLOR="white" CLASS="TableRowColor">
151<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Sudoku.html" title="class in org.apache.hadoop.examples.dancing">Sudoku</A></B></TD>
152<TD>This class uses the dancing links algorithm from Knuth to solve sudoku
153 puzzles.</TD>
154</TR>
155</TABLE>
156&nbsp;
157
158<P>
159
160<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
161<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
162<TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2">
163<B>Enum Summary</B></FONT></TH>
164</TR>
165<TR BGCOLOR="white" CLASS="TableRowColor">
166<TD WIDTH="15%"><B><A HREF="../../../../../org/apache/hadoop/examples/dancing/Pentomino.SolutionCategory.html" title="enum in org.apache.hadoop.examples.dancing">Pentomino.SolutionCategory</A></B></TD>
167<TD>&nbsp;</TD>
168</TR>
169</TABLE>
170&nbsp;
171
172<P>
173<A NAME="package_description"><!-- --></A><H2>
174Package org.apache.hadoop.examples.dancing Description
175</H2>
176
177<P>
178This package is a distributed implementation of Knuth's <a
179href="http://en.wikipedia.org/wiki/Dancing_Links">dancing links</a>
180algorithm that can run under Hadoop. It is a generic model for
181problems, such as tile placement, where all of the valid choices can
182be represented as a large sparse boolean array where the goal is to
183pick a subset of the rows to end up with exactly 1 <b>true</b> value
184in each column.
185
186<p>
187
188The package includes two example applications: a <a
189href="http://en.wikipedia.org/wiki/Pentomino">pentomino</a> solver and
190a sudoku solver.
191
192<p>
193
194The pentomino includes both a "normal" pentomino set and a one-sided
195set where the tiles that are different when flipped are
196duplicated. The pentomino solver has a Hadoop driver application to
197launch it on a cluster. In Knuth's paper on dancing links, he
198describes trying and failing to solve the one-sided pentomino in a
1999x10 board. With the advances of computers and a cluster, it takes a
200small (12 node) hadoop cluster 9 hours to find all of the solutions
201that Knuth estimated would have taken him months.
202
203<p>
204
205The sudoku solver is so fast, I didn't bother making a distributed
206version. (All of the puzzles that I've tried, including a 42x42 have
207taken around a second to solve.) On the command line, give the solver
208a list of puzzle files to solve. Puzzle files have a line per a row
209and columns separated by spaces. The squares either have numbers or
210'?' to mean unknown.
211
212<p>
213
214Both applications have been added to the examples jar, so they can be
215run as:
216
217<pre>
218bin/hadoop jar hadoop-*-examples.jar pentomino pent-outdir
219bin/hadoop jar hadoop-*-examples.jar sudoku puzzle.txt
220</pre>
221
222<p>
223
224I (Owen) implemented the original version of the distributed pentomino
225solver for a Yahoo Hack day, where Yahoos get to work on a project of
226their own choosing for a day to make something cool. The following
227afternoon, everyone gets to show off their hacks and gets a free
228t-shirt. I had a lot of fun doing it.
229<P>
230
231<P>
232<DL>
233</DL>
234<HR>
235
236
237<!-- ======= START OF BOTTOM NAVBAR ====== -->
238<A NAME="navbar_bottom"><!-- --></A>
239<A HREF="#skip-navbar_bottom" title="Skip navigation links"></A>
240<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
241<TR>
242<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
243<A NAME="navbar_bottom_firstrow"><!-- --></A>
244<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
245  <TR ALIGN="center" VALIGN="top">
246  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A>&nbsp;</TD>
247  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Package</B></FONT>&nbsp;</TD>
248  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <FONT CLASS="NavBarFont1">Class</FONT>&nbsp;</TD>
249  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-use.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A>&nbsp;</TD>
250  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
251  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
252  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
253  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
254  </TR>
255</TABLE>
256</TD>
257<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
258</EM>
259</TD>
260</TR>
261
262<TR>
263<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
264&nbsp;<A HREF="../../../../../org/apache/hadoop/examples/package-summary.html"><B>PREV PACKAGE</B></A>&nbsp;
265&nbsp;<A HREF="../../../../../org/apache/hadoop/examples/terasort/package-summary.html"><B>NEXT PACKAGE</B></A></FONT></TD>
266<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
267  <A HREF="../../../../../index.html?org/apache/hadoop/examples/dancing/package-summary.html" target="_top"><B>FRAMES</B></A>  &nbsp;
268&nbsp;<A HREF="package-summary.html" target="_top"><B>NO FRAMES</B></A>  &nbsp;
269&nbsp;<SCRIPT type="text/javascript">
270  <!--
271  if(window==top) {
272    document.writeln('<A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>');
273  }
274  //-->
275</SCRIPT>
276<NOSCRIPT>
277  <A HREF="../../../../../allclasses-noframe.html"><B>All Classes</B></A>
278</NOSCRIPT>
279
280
281</FONT></TD>
282</TR>
283</TABLE>
284<A NAME="skip-navbar_bottom"></A>
285<!-- ======== END OF BOTTOM NAVBAR ======= -->
286
287<HR>
288Copyright &copy; 2009 The Apache Software Foundation
289</BODY>
290</HTML>
Note: See TracBrowser for help on using the repository browser.