// "Pentominos Puzzle Solver" // // 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 solves this puzzle // using a straightforward recursive backtracking procedure. // // Note: This will run as a standalone application as well as // as an applet. // // by: David J. Eck // Deparment of Mathematics and Computer Science // Hobart and William Smith Colleges // Geneva, NY 14456 // // Email: eck@hws.edu // // January 6, 1996 // Slightly revised: May 30, 1996 // // NOTE: YOU CAN DO ANYTHING YOU WANT WITH THIS CODE AND APPLET, AS // LONG AS YOU GIVE ME CREDIT FOR IT AND AS LONG AS YOU DON'T // TRY TO COPYRIGHT IT, PATENT IT, OR OTHERWISE RESTRICT ITS // USE YORUSELF. import java.awt.*; public class PentominosSolver extends java.applet.Applet implements Runnable { Button clearBttn, pauseBttn, goBttn, stepBttn; Choice speedSelect; int speed; Label message; // displayed above puzzleboard int board[]; // The 8-by-8 board is actually represented // conceptually as 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 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 // (while the main applet thread handles the user interface) int squaresClicked = 0; // user starts by clicking on four squares; this is the // number clicked so far. Clicked 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. This is used to implement both // the Pause button and the Step button. boolean stopped = false; // set to true when GameThread is suspended because // the pause button has been pressed or because a // a solution has been found. This is used in // the start() method to test for these situations. // (Netscape requires this because it sends a stop() // and a stop() to the applet whenever the browser // window is resized!!) long lastYieldTime = 0; // last time Thread.yield() was called // (I'm not sure this is a good idea, but I'm // trying to be polite by calling yield() regularly, // without calling it after every single move in // the game.) 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 here tells which pentomino { 5, 8,9,10,20 }, // that line 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 rows 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 argv[]) { // This "main" routine is provided so that Pentominos Solver can // be run as an application as well as an Applet. It is not used // at all when running as an Applet. The class KillableFrame is defined // below, in this file. This class is also not used by theis // Applet version. (Isn't it silly that I have to do this just // to get an application that can quit???) Frame f = new KillableFrame("Pentominos Solver"); PentominosSolver ps = new PentominosSolver(); ps.init(); f.add("Center",ps); f.resize(281,360); ps.start(); f.show(); } public void init() { board = new int[100]; used = new boolean[13]; Panel buttonPanel = new Panel(); // holds four control buttons Panel bottomPanel = new Panel(); // buttonPanel + speedSelect bottomPanel.setLayout(new BorderLayout()); setLayout(new BorderLayout()); add("South", bottomPanel); clearBttn = new Button("Clear"); // the control buttons pauseBttn = new Button("Pause"); goBttn = new Button("Go"); stepBttn = new Button("Step"); buttonPanel.add(clearBttn); buttonPanel.add(pauseBttn); buttonPanel.add(goBttn); buttonPanel.add(stepBttn); bottomPanel.add("North",buttonPanel); speedSelect = new Choice(); speedSelect.addItem("Fastest"); speedSelect.addItem("Fast"); speedSelect.addItem("Slow"); speedSelect.addItem("Slowest"); speedSelect.select("Fast"); speed = 2; Panel speedPanel = new Panel(); speedPanel.add(speedSelect); bottomPanel.add("South",speedPanel); message = new Label("Click Four Squares"); // the message // topPanel.add(message); message.setFont(new Font("TimesRoman", Font.BOLD, 14)); add("North", 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(); } public void start() { if (GameThread != null&& !stopped) { GameThread.resume(); } } public void stop() { if (GameThread != null) { GameThread.suspend(); } } boolean putPiece(int p, int square) { // try to place a piece on the board, // return true if it fits 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.playPiece(pieces[p],square); // color in the squares to represent the piece return true; } 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(); } stopped = true; GameThread.suspend(); stopped = false; } else if (speed > 1) { int sleepTime = (speed == 2) ? 10 : ((speed == 3) ? 100 : 1000); try { Thread.sleep(sleepTime); } catch (InterruptedException e) { } } else if (java.lang.System.currentTimeMillis() - lastYieldTime >= 100) { Thread.yield(); // Doesn't work as advertised??? 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 } boardcanvas.removePiece(pieces[p],square); // backtrack numused--; used[pieces[p][0]] = false; } } public void run() { // run() procedure for GameThread; // try to solve the puzzle message.setText("Solving..."); for (int i=1; i<=12; i++) used[i] = false; numused = 0; int square = 11; // reprsents the upper left corner of the board while (board[square] == -1) square++; // move past any filled squares, since Play(square) assumes the square is empty lastYieldTime = java.lang.System.currentTimeMillis(); play(square); stepBttn.disable(); goBttn.disable(); pauseBttn.disable(); message.setText("No More Solutions"); GameThread = null; } void doClear() { // responce procedure for "Clear" button: restore initial state if (GameThread != null) { GameThread.stop(); GameThread = 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++; boardcanvas.blackenSquare(square); } else { squaresClicked--; Graphics g = boardcanvas.getGraphics(); boardcanvas.clearSquare(g,square); g.dispose(); } if (squaresClicked == 4) { // if four squares have been filled, start solving the puzzle GameThread = new Thread(this); 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 or speedSelect 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 if (evt.target == speedSelect) { if ("Fastest".equals(arg)) speed = 1; else if ("Fast".equals(arg)) speed = 2; else if ("Slow".equals(arg)) speed = 3; else if ("Slowest".equals(arg)) speed = 4; 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); } // Note: The following methods are synchronized because when the // board is resized, the main applet thread might try to call paint // while the puzzle-solving thread is trying to place squares on the // Board. (I'm not sure this should really happen because the puzzle // thread is supposed to be running at a lower priority, but before // I added the synchronization, the screen would get corrupted when // I resized the board while the puzzle was in the process of being // solved.) public synchronized void paint(Graphics g) { // redraw the whole board int sw = (size().width - 1) / 8; int w = 8 * sw; int sh = (size().height - 1) / 8; int h = 8 * sh; Color oldColor = g.getColor(); g.setColor(Color.black); for (int i = 0; i <= 8; i++) { int x = i * sw; g.drawLine(x,0,x,h); } for (int i = 0; i <= 8; i++) { int y = i * sh; g.drawLine(0,y,w,y); } for (int i = 1; i <= 8; i++) { int y = (i-1) * sh; for (int j = 1; j <= 8; j++) { int x = (j-1) * sw; if (board[10*i + j] == -1) g.setColor(Color.black); else g.setColor(pieceColor[board[10*i + j]]); g.fillRect(x+1, y+1, sw-1, sh-1); } } g.setColor(oldColor); } synchronized void putSquare(Graphics g, int name, int square) { // "name" gives the piece number int sw = (size().width - 1) / 8; int sh = (size().height - 1) / 8; int x = ((square % 10)-1) * sw; int y = ((square / 10)-1) * sh; g.setColor(pieceColor[name]); g.fillRect(x+1, y+1, sw - 1, sh - 1); g.setColor(Color.black); board[square] = name; } synchronized void playPiece(int[] pieceData, int startSquare) { Graphics g = getGraphics(); putSquare(g,pieceData[0],startSquare); for (int i = 1; i < 5; i++) putSquare(g,pieceData[0],startSquare+pieceData[i]); g.dispose(); } synchronized void clearSquare(Graphics g, int square) { int sw = (size().width - 1) / 8; int sh = (size().height - 1) / 8; int x = ((square % 10)-1) * sw; int y = ((square / 10)-1) * sh; g.setColor(pieceColor[0]); g.fillRect(x+1, y+1, sw - 1, sh - 1); g.setColor(Color.black); board[square] = 0; } synchronized void removePiece(int[] pieceData, int startSquare) { Graphics g = getGraphics(); clearSquare(g,startSquare); for (int i = 1; i < 5; i++) clearSquare(g,startSquare+pieceData[i]); g.dispose(); } synchronized void blackenSquare(int square) { int sw = (size().width - 1) / 8; int sh = (size().height - 1) / 8; int x = ((square % 10)-1) * sw; int y = ((square / 10)-1) * sh; Graphics g = getGraphics(); g.fillRect(x, y, sw, sh); g.dispose(); board[square] = -1; } public boolean mouseDown(Event evt, int x, int y) { int sw = (size().width - 1) / 8; int sh = (size().height - 1) / 8; int row = (y / sh) + 1; int col = (x / sw) + 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(); } } class KillableFrame extends Frame { // this class is used only when PentominosSolver is run as a // standalone application rather than as an Applet. KillableFrame(String name) { super(name); } public boolean handleEvent(Event evt) { if (evt.id == Event.WINDOW_DESTROY) System.exit(0); return super.handleEvent(evt); } }