+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
2.7 KiB75 linesraw
1<html>
2
3<!--
4   Licensed to the Apache Software Foundation (ASF) under one or more
5   contributor license agreements.  See the NOTICE file distributed with
6   this work for additional information regarding copyright ownership.
7   The ASF licenses this file to You under the Apache License, Version 2.0
8   (the "License"); you may not use this file except in compliance with
9   the License.  You may obtain a copy of the License at
10
11       http://www.apache.org/licenses/LICENSE-2.0
12
13   Unless required by applicable law or agreed to in writing, software
14   distributed under the License is distributed on an "AS IS" BASIS,
15   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   See the License for the specific language governing permissions and
17   limitations under the License.
18-->
19
20<body>
21
22This package is a distributed implementation of Knuth's <a
23href="http://en.wikipedia.org/wiki/Dancing_Links">dancing links</a>
24algorithm that can run under Hadoop. It is a generic model for
25problems, such as tile placement, where all of the valid choices can
26be represented as a large sparse boolean array where the goal is to
27pick a subset of the rows to end up with exactly 1 <b>true</b> value
28in each column.
29
30<p>
31
32The package includes two example applications: a <a
33href="http://en.wikipedia.org/wiki/Pentomino">pentomino</a> solver and
34a sudoku solver. 
35
36<p>
37
38The pentomino includes both a "normal" pentomino set and a one-sided
39set where the tiles that are different when flipped are
40duplicated. The pentomino solver has a Hadoop driver application to
41launch it on a cluster. In Knuth's paper on dancing links, he
42describes trying and failing to solve the one-sided pentomino in a
439x10 board. With the advances of computers and a cluster, it takes a
44small (12 node) hadoop cluster 9 hours to find all of the solutions
45that Knuth estimated would have taken him months.
46
47<p>
48
49The sudoku solver is so fast, I didn't bother making a distributed
50version. (All of the puzzles that I've tried, including a 42x42 have
51taken around a second to solve.) On the command line, give the solver
52a list of puzzle files to solve. Puzzle files have a line per a row
53and columns separated by spaces. The squares either have numbers or
54'?' to mean unknown.
55
56<p>
57
58Both applications have been added to the examples jar, so they can be
59run as:
60
61<pre>
62bin/hadoop jar hadoop-*-examples.jar pentomino pent-outdir
63bin/hadoop jar hadoop-*-examples.jar sudoku puzzle.txt
64</pre>
65
66<p>
67
68I (Owen) implemented the original version of the distributed pentomino
69solver for a Yahoo Hack day, where Yahoos get to work on a project of
70their own choosing for a day to make something cool. The following
71afternoon, everyone gets to show off their hacks and gets a free
72t-shirt. I had a lot of fun doing it.
73
74</body>
75</html>