PentominosSolver
// A pentomino consists of five squares attached along their edges.
// There are exactly twelve possible pentominos that can be formed
// in this way (not counting reflections and rotations). Someone once
// gave me a Pentominos puzzle where the goal was to place the 12
// pentominos on an 8-by-8 board, leaving 4 blank squares in certain
// previously decided positions. This java applet -- the first
// reasonably serious one I have written -- solves this puzzle using
// a recursive backtracking procedure.
//
// David Eck
// Deparment of Mathematics and Computer Science
// Hobart and William Smith Colleges
// Geneva, NY 14456
// Email: eck@hws.edu
//
// January 6, 1996
import java.applet.Applet;
import java.awt.*;
public class PentominosSolver extends Applet implements Runnable {
Button clearBttn, pauseBttn, goBttn, stepBttn;
Label message;
int board[]; // The 8-by-8 board is actually
// represented by a 10-by-10 data structure
// in which the cells along the border
// are declared permanently "filled"
// This simplifies testing whether a given
// piece fits at a given position on the
// board. Furthermore, this 10-by-10 board
// is represented by a 1-dimensional array
// in which the 10*i+j-th entry represents
// row j and column i on the board.
PentominosBoardCanvas boardcanvas; // for displaying the board on the screen
Graphics g = null; // a graphics context for the boardcanvas
boolean used[]; // used[i] tells whether piece # i is already on the board
int numused; // number of pieces currently on the board, from 0 to 12
Thread GameThread = null; // a thread to run the puzzle solving procedure
// (the main applet thread just does the user interface)
int squaresClicked = 0; // user starts by clicking on four squares; this is the
// number clicked so far. Squares are filled in in black.
// The puzzle is to fill in the remaining 60 squares with
// the 12 pentominos
boolean oneStepOnly = false; // this is set to true by the interface if the
// GameThread is supposed to stop after playing
// the next piece.
long lastYieldTime = 0; // last time Thread.yield() was called
final int pieces[][] = {
{ 1, 1,2,3,4 }, // This array represents everything the program
{ 1, 10,20,30,40 }, // knows about the individual pentominos. Each
{ 2, 9,10,11,20 }, // row in the array represents a particular
{ 3, 1,10,19,20 }, // pentomino in a particular orientation. Different
{ 3, 10,11,12,22 }, // orientations are obtained by rotating or flipping
{ 3, 1,11,21,22 }, // the pentomino over. Note that the program must
{ 3, 8,9,10,18 }, // try each pentomino in each possible orientation,
{ 4, 10,20,21,22 }, // but must be careful not to reuse a piece if
{ 4, 1,2,10,20 }, // it has already been used on the board in a
{ 4, 10,18,19,20 }, // different orientation.
{ 4, 1,2,12,22 }, // The pentominoes are numbered from 1 to 12.
{ 5, 1,2,11,21 }, // The first number on each row tells which pentomino
{ 5, 8,9,10,20 }, // that row represents. Note that there can be
{ 5, 10,19,20,21 }, // up to 8 different rows for each pentomino.
{ 5, 10,11,12,20 }, // some pentominos have fewer rows because they are
{ 6, 10,11,21,22 }, // symmetric. For example, the pentomino that looks
{ 6, 9,10,18,19 }, // like:
{ 6, 1,11,12,22 }, // GGG
{ 6, 1,9,10,19 }, // G G
{ 7, 1,2,10,12 }, //
{ 7, 1,11,20,21 }, // can be rotated into three additional positions,
{ 7, 2,10,11,12 }, // but flipping it over will give nothing new.
{ 7, 1,10,20,21 }, // So, it has only 4 entries in the array.
{ 8, 10,11,12,13 }, // The four remaining entries in the array
{ 8, 10,20,29,30 }, // describe the given piece in the given orientation,
{ 8, 1,2,3,13 }, // in a way convenient for placing the piece into
{ 8, 1,10,20,30 }, // the one-dimensional array that represents the
{ 8, 1,11,21,31 }, // board. As an example, consider the row
{ 8, 1,2,3,10 }, //
{ 8, 10,20,30,31 }, // { 7, 1,2,10,19 }
{ 8, 7,8,9,10 }, //
{ 9, 1,8,9,10 }, // If this piece is placed on the board so that
{ 9, 10,11,21,31 }, // its topmost/leftmost square fills position
{ 9, 1,2,9,10 }, // p in the array, then the other four squares
{ 9, 10,20,21,31 }, // will be at positions p+1, p+2, p+10, and p+19.
{ 9, 1,11,12,13 }, // To see whether the piece can be played at that
{ 9, 10,19,20,29 }, // position, it suffices to check whether any of
{ 9, 1,2,12,13 }, // these five squares are filled.
{ 9, 9,10,19,29 }, // On the board, each piece will be shown
{ 10, 8,9,10,11 }, // in its own color.
{ 10, 9,10,20,30 },
{ 10, 1,2,3,11 },
{ 10, 10,20,21,30 },
{ 10, 1,2,3,12 },
{ 10, 10,11,20,30 },
{ 10, 9,10,11,12 },
{ 10, 10,19,20,30 },
{ 11, 9,10,11,21 },
{ 11, 1,9,10,20 },
{ 11, 10,11,12,21 },
{ 11, 10,11,19,20 },
{ 11, 8,9,10,19},
{ 11, 1,11,12,21 },
{ 11, 9,10,11,19 },
{ 11, 9,10,20,21 },
{ 12, 1,10,11,21 },
{ 12, 1,2,10,11 },
{ 12, 10,11,20,21 },
{ 12, 1,9,10,11 },
{ 12, 1,10,11,12 },
{ 12, 9,10,19,20 },
{ 12, 1,2,11,12 },
{ 12, 1,10,11,20 },
};
public static void main(String args[]) { // more or less from "CardTest demo" example
Frame f = new Frame("Pentominos Solver");
PentominosSolver ps = new PentominosSolver();
ps.init();
ps.start();
f.add("Center",ps);
f.resize(250,300);
f.show();
}
public void init() {
board = new int[100];
used = new boolean[13];
Panel topPanel = new Panel(); // holds an informational message
Panel bottomPanel = new Panel(); // holds four control buttons
setLayout(new BorderLayout());
add("South", bottomPanel);
add("North", topPanel);
clearBttn = new Button("Clear"); // the control buttons
pauseBttn = new Button("Pause");
goBttn = new Button("Go");
stepBttn = new Button("Step");
bottomPanel.add(clearBttn);
bottomPanel.add(pauseBttn);
bottomPanel.add(goBttn);
bottomPanel.add(stepBttn);
message = new Label("Click Four Square"); // the message
topPanel.add(message);
boardcanvas = new PentominosBoardCanvas(board,this); // for displaying the board
add("Center",boardcanvas);
for (int i=0; i<100; i++) // fill in the border with -1's
board[i] = -1;
for (int i=1; i<9; i++) // fill in the rest of the board with empty spaces (0's)
for (int j=1; j<9; j++)
board[j*10+i] = 0;
stepBttn.disable();
goBttn.disable();
pauseBttn.disable();
}
boolean putPiece(int p, int square) { // try to place a piece on the board,
// return true if it fits
int name = pieces[p][0];
if (board[square] != 0)
return false;
for (int i = 1; i <= 4; i ++)
if (board[square + pieces[p][i]] != 0) // one of the squares needed is already occupied
return false;
boardcanvas.putSquare(g,name,square); // color in the squares to represent the piece
for (int i = 1; i <= 4; i++)
boardcanvas.putSquare(g,name,square+pieces[p][i]);
return true;
}
void removePiece(int p, int square) {
boardcanvas.clearSquare(g,square);
for (int i = 1; i <= 4; i++)
boardcanvas.clearSquare(g,square+pieces[p][i]);
}
void play(int square) { // recursive procedure that tries to solve the puzzle
// parameter "square" is the number of the next empty
// to be filled
for (int p=0; p<63; p++)
if ((used[pieces[p][0]] == false) && putPiece(p,square)) { // try piece p
used[pieces[p][0]] = true;
numused++;
if (numused == 12 || oneStepOnly) { // puzzle is solved or should be suspended
if (oneStepOnly)
oneStepOnly = false;
else {
stepBttn.enable();
goBttn.enable();
pauseBttn.disable();
}
GameThread.suspend();
}
else if (java.lang.System.currentTimeMillis() - lastYieldTime >= 100) {
Thread.yield();
lastYieldTime = java.lang.System.currentTimeMillis();
}
if (numused < 12) {
int nextSquare = square;
while (board[nextSquare] != 0) // find next empty square
nextSquare++;
play(nextSquare); // and try to complete the solution
}
removePiece(p,square); // backtrack
numused--;
used[pieces[p][0]] = false;
}
}
public void run() {
g = boardcanvas.getGraphics(); // run() procedure for GameThread;
message.setText("Solving..."); // try to solve the puzzle
for (int i=1; i<=12; i++)
used[i] = false;
numused = 0;
int square = 11;
while (board[square] == -1)
square++;
lastYieldTime = java.lang.System.currentTimeMillis();
play(square);
stepBttn.disable();
goBttn.disable();
pauseBttn.disable();
message.setText("No More Solutions");
}
void doClear() { // responce procedure for "Clear" button: restore initial state
if (GameThread != null) {
GameThread.stop();
GameThread = null;
g = null;
}
if (squaresClicked > 0) {
for (int i=0; i<100; i++) // fill in the border with -1's
board[i] = -1;
for (int i=1; i<9; i++) // fill in the rest of the board with empty spaces (0's)
for (int j=1; j<9; j++)
board[j*10+i] = 0;
boardcanvas.repaint();
squaresClicked = 0;
}
stepBttn.disable();
goBttn.disable();
pauseBttn.disable();
message.setText("Click Four Squares");
}
void doBoardClick(int square) { // respond to click on boardcanvas
// (called from PentominosBoardCanvas::mouseDown)
if (GameThread == null && squaresClicked < 4) {
if (board[square] == 0) { // fill in the clicked sqaure
squaresClicked++;
Graphics g1 = boardcanvas.getGraphics();
boardcanvas.blackenSquare(g1,square);
}
if (squaresClicked == 4) { // if four squares have been filled, start solving the puzzle
GameThread = new Thread(this);
int pri = GameThread.getPriority() - 1;
if (pri >= Thread.MIN_PRIORITY)
GameThread.setPriority(pri);
GameThread.start();
pauseBttn.enable();
}
}
}
void doPause() { // response procedure for Pause button
oneStepOnly = true; // tells GameThread to suspend itself
stepBttn.enable();
goBttn.enable();
pauseBttn.disable();
}
void doStep() { // response to Step button
oneStepOnly = true;
GameThread.resume();
}
void doGo() { // response to Go button
stepBttn.disable();
goBttn.disable();
pauseBttn.enable();
lastYieldTime = java.lang.System.currentTimeMillis();
GameThread.resume();
}
public boolean action(Event evt, Object arg) { // Check for clicks on buttons
if (evt.target instanceof Button) {
if ("Clear".equals(arg))
doClear();
else if ("Pause".equals(arg))
doPause();
else if ("Go".equals(arg))
doGo();
else if ("Step".equals(arg))
doStep();
return true;
}
else
return false;
}
} // end of class PentominosSolver
class PentominosBoardCanvas extends Panel { // implement the visible 8-by-8 playing board
int[] board; // The board data array, passed into the constructor and
// used throughout this class
PentominosSolver owner; // The applet, passed into constructor, and
// used in the mouseDown handler
Color pieceColor[]; // Array of colors to be used in displaying pieces
// pieceColor[0] is the color of an empty square,
// pieceColor[1] is the color for piece number 1, etc.
PentominosBoardCanvas(int[] theBoard, PentominosSolver theOwner) { // Constructor
board = theBoard;
owner = theOwner;
MakeColors(); // create and fill in pieceColor[] array
}
void MakeColors() {
pieceColor = new Color[13];
pieceColor[0] = Color.white;
pieceColor[1] = new Color(200,0,0);
pieceColor[2] = new Color(150,150,255);
pieceColor[3] = new Color(0,200,200);
pieceColor[4] = new Color(255,150,255);
pieceColor[5] = new Color(0,200,0);
pieceColor[6] = new Color(150,255,255);
pieceColor[7] = new Color(200,200,0);
pieceColor[8] = new Color(0,0,200);
pieceColor[9] = new Color(255,150,150);
pieceColor[10] = new Color(200,0,200);
pieceColor[11] = new Color(255,255,150);
pieceColor[12] = new Color(150,255,150);
}
public synchronized void paint(Graphics g) { // redraw the whole board
int w = size().width;
w = 8 * (w/8) + 1;
int h = size().height;
h = 8 * (h/8) + 1;
Color oldColor = g.getColor();
g.setColor(Color.black);
for (int i = 0; i <= 8; i++) {
int x = i * ((w - 1) / 8);
g.drawLine(x,0,x,h-1);
}
for (int i = 0; i <= 8; i++) {
int y = i * ((h - 1) / 8);
g.drawLine(0,y,w-1,y);
}
for (int i = 1; i <= 8; i++) {
int y = (i-1) * ((h-1) / 8);
for (int j = 1; j <= 8; j++) {
int x = (j-1) * ((w-1) / 8);
if (board[10*i + j] == -1)
g.setColor(Color.black);
else
g.setColor(pieceColor[board[10*i + j]]);
g.fillRect(x+1, y+1, (w-1) / 8 - 1, (h-1) / 8 - 1);
}
}
g.setColor(oldColor);
}
synchronized void putSquare(Graphics g, int name, int square) { // "name" gives the piece number
int w = size().width;
w = 8 * (w/8) + 1;
int h = size().height;
h = 8 * (h/8) + 1;
int x = ((square % 10)-1) * ((w-1)) / 8;
int y = ((square / 10)-1) * ((h-1)) / 8;
g.setColor(pieceColor[name]);
g.fillRect(x+1, y+1, (w-1)/8 - 1, (h-1)/8 - 1);
g.setColor(Color.black);
board[square] = name;
}
synchronized void clearSquare(Graphics g, int square) {
int w = size().width;
w = 8 * (w/8) + 1;
int h = size().height;
h = 8 * (h/8) + 1;
int x = ((square % 10)-1) * ((w-1)) / 8;
int y = ((square / 10)-1) * ((h-1)) / 8;
g.setColor(pieceColor[0]);
g.fillRect(x+1, y+1, (w-1)/8 - 1, (h-1)/8 - 1);
g.setColor(Color.black);
board[square] = 0;
}
synchronized void blackenSquare(Graphics g, int square) {
int w = size().width;
w = 8 * (w/8) + 1;
int h = size().height;
h = 8 * (h/8) + 1;
int x = ((square % 10)-1) * ((w-1)) / 8;
int y = ((square / 10)-1) * ((h-1)) / 8;
g.fillRect(x, y, (w-1)/8, (h-1)/8);
board[square] = -1;
}
public boolean mouseDown(Event evt, int x, int y) {
int w = size().width;
w = 8 * (w/8) + 1;
int h = size().height;
h = 8 * (h/8) + 1;
int row = (y / ((h-1)/8)) + 1;
int col = (x / ((w-1)/8)) + 1;
if (row > 0 && row < 9 && col > 0 && col < 9)
owner.doBoardClick(10*row + col);
return true;
}
public Dimension minimumSize() {
return new Dimension(160,160);
}
public Dimension preferredSize() {
return minimumSize();
}
}
New on the Java Boutique:
New Review:
Time Management Made Easy with the Quartz Enterprise Job Scheduler
Why not just use the Java timer API? This open source scheduling
API boasts simplicity, ease-of-integration, a well-rounded feature
set, and it's free!
New Applet:
Reverse Complement
Reverse Complement is a simple applet that converts DNA or RNA
sequences into three useful formats.
Elsewhere on internet.com:
WebDeveloper Java
Lots of Java information on webdeveloper.com
WDVL Java
Thorough Java resource at the Web Developer's Virtual Library.
ScriptSearch Java
Hundreds of free Java code files to download.
jGuru: Your View of the Java Universe
Customizable portal with online training, FAQs, regular news updates, and tutorials.
