+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1< html > 2 3<!-- 4Licensed to the Apache Software Foundation (ASF) under one or more 5contributor license agreements. See the NOTICE file distributed with 6this work for additional information regarding copyright ownership. 7The 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 9the License. You may obtain a copy of the License at 10 11http://www.apache.org/licenses/LICENSE-2.0 12 13Unless required by applicable law or agreed to in writing, software 14distributed under the License is distributed on an "AS IS" BASIS, 15WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16See the License for the specific language governing permissions and 17limitations 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 >