org.apache.hadoop.examples.dancing
Class Pentomino

java.lang.Object
  org.apache.hadoop.examples.dancing.Pentomino

Direct Known Subclasses:

OneSidedPentomino

public class Pentomino
extends Object

Nested Class Summary

protected static interface	Pentomino.ColumnName This interface just is a marker for what types I expect to get back as column names.
protected static class	Pentomino.Piece Maintain information about a puzzle piece.
static class	Pentomino.SolutionCategory

Field Summary

protected static int[]	fourRotations Are all 4 rotations unique?
protected int	height
protected static int[]	oneRotation Is the piece fixed under rotation?
protected List<Pentomino.Piece>	pieces
protected static int[]	twoRotations Is the piece identical if rotated 180 degrees?
protected int	width

Constructor Summary

Pentomino()
Create the object without initialization.

Pentomino(int width, int height)
Create the model for a given pentomino set of pieces and board size.

Method Summary

Pentomino.SolutionCategory	getCategory(List<List<Pentomino.ColumnName>> names) Find whether the solution has the x in the upper left quadrant, the x-midline, the y-midline or in the center.
List<int[]>	getSplits(int depth) Generate a list of prefixes to a given depth
protected void	initializePieces() Fill in the pieces list.
static void	main(String[] args) Solve the 6x10 pentomino puzzle.
void	setPrinter(DancingLinks.SolutionAcceptor<Pentomino.ColumnName> printer) Set the printer for the puzzle.
int	solve() Find all of the solutions to the puzzle.
int	solve(int[] split) Find all of the solutions that start with the given prefix.
static String	stringifySolution(int width, int height, List<List<Pentomino.ColumnName>> solution) Convert a solution to the puzzle returned by the model into a string that represents the placement of the pieces onto the board.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

width

protected int width

height

protected int height

pieces

protected List<Pentomino.Piece> pieces

oneRotation

protected static final int[] oneRotation

Is the piece fixed under rotation?

twoRotations

protected static final int[] twoRotations

Is the piece identical if rotated 180 degrees?

fourRotations

protected static final int[] fourRotations

Are all 4 rotations unique?

Constructor Detail

Pentomino

public Pentomino(int width,
                 int height)

Create the model for a given pentomino set of pieces and board size.

Parameters:

width - the width of the board in squares

height - the height of the board in squares

Pentomino

public Pentomino()

Create the object without initialization.

Method Detail

stringifySolution

public static String stringifySolution(int width,
                                       int height,
                                       List<List<Pentomino.ColumnName>> solution)

Convert a solution to the puzzle returned by the model into a string that represents the placement of the pieces onto the board.

Parameters:

width - the width of the puzzle board

height - the height of the puzzle board

solution - the list of column names that were selected in the model

Returns:

a string representation of completed puzzle board

getCategory

public Pentomino.SolutionCategory getCategory(List<List<Pentomino.ColumnName>> names)

Find whether the solution has the x in the upper left quadrant, the x-midline, the y-midline or in the center.

Parameters:

names - the solution to check

Returns:

the catagory of the solution

initializePieces

protected void initializePieces()

Fill in the pieces list.

getSplits

public List<int[]> getSplits(int depth)

Generate a list of prefixes to a given depth

Parameters:

depth - the length of each prefix

Returns:

a list of arrays of ints, which are potential prefixes

solve

public int solve(int[] split)

Find all of the solutions that start with the given prefix. The printer is given each solution as it is found.

Parameters:

split - a list of row indexes that should be choosen for each row in order

Returns:

the number of solutions found

solve

public int solve()

Find all of the solutions to the puzzle.

Returns:

the number of solutions found

setPrinter

public void setPrinter(DancingLinks.SolutionAcceptor<Pentomino.ColumnName> printer)

Set the printer for the puzzle.

Parameters:

printer - A call-back object that is given each solution as it is found.

main

public static void main(String[] args)

Solve the 6x10 pentomino puzzle.