// "LittlePentominosApplet"
//
// 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.
//
// This is a simple version of the applet that sets up and solves
// randomly chosen boards.  If there is a mouseclick on the applet,
// a new board is set up.  For a pentominos applet that gives more
// user control, see my Java page at https://math.hws.edu/xJava
//
//
// David Eck (eck@hws.edu)

import java.applet.Applet;
import java.awt.*;

public class LittlePentominosApplet extends Applet implements Runnable {
    
    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)
                                
    boolean done;  // used in play() to test whether the puzzle is solved (or aborted)
    
    boolean clicked;  // set to true when user clicks on the applet

    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 void init() {
    
        board = new int[100];
        used = new boolean[13];
    
        setLayout(new BorderLayout());
        boardcanvas = new PentominosBoardCanvas(board);  // for displaying the board
        add("Center",boardcanvas);
        
    }
    
    public void start() {
       gameThread = new Thread(this);
       gameThread.start();
    }
    
    public void stop() {
       if (gameThread != null && gameThread.isAlive())
          gameThread.stop();
    }
    
    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 (!done && (used[pieces[p][0]] == false) && putPiece(p,square)) {  // try piece p
               used[pieces[p][0]] = true;
               numused++;
               if (getClicked()) {
                  done = true;
                  return;
               }
               else if (numused == 12) {  // puzzle is solved
                  doDelay(5000);
                  done = true;
                  return;
               }
               else {
                  doDelay(50);
                  int nextSquare = square;
                  while (board[nextSquare] != 0)  // find next empty square
                     nextSquare++;
                  play(nextSquare);  // and try to complete the solution
                  if (done)
                     return;
                  boardcanvas.removePiece(pieces[p],square);  // backtrack
                  numused--;
                  used[pieces[p][0]] = false;
               }
           }
    }
    
    void setUpRandomBoard() {
        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;
        int x,y;
        switch ((int)(5*Math.random())) {
           case 0:
              for (int i=0; i < 4; i ++) {
                 do {
                    x = 1 + (int)(8*Math.random());
                    y = 1 + (int)(8*Math.random());
                 } while (board[y*10+x] == -1);
                 board[y*10+x] = -1;
              }
           break;
           case 1:
           case 2:
              do {
                 x = 1 + (int)(8*Math.random());
                 y = 1 + (int)(8*Math.random());
              } while (y == 5 || x == 5);
              board[10*y+x] = -1;
              board[10*y+(9-x)] = -1;
              board[10*(9-y)+x] = -1;
              board[10*(9-y)+(9-x)] = -1;
           break;
           default:
              x = (int)(6*Math.random()) + 1;
              y = (int)((x)*Math.random()) + 1;
              board[y*10+x] = -1;
              board[y*10+x+1] = -1;
              board[y*10+x+10] = -1;
              board[y*10+x+11] = -1;
           break;
        }
        boardcanvas.repaint();
    }
    
    public void run() { 
       while (true) {
          do {
             setClicked(false);
             setUpRandomBoard();
             doDelay(1000);
          } while (getClicked());
          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
          done = false;
          setClicked(false);
          play(square);
       }
    }
    
    synchronized void doDelay(int milliseconds) {
       try {
          wait(milliseconds);
       }
       catch (InterruptedException e) {
       }
    }
    
    synchronized void setClicked(boolean clicked) {
       this.clicked = clicked;
       if (clicked)
          notify();
    }
    
    synchronized boolean getClicked() {
       return this.clicked;
    }
    
    public boolean mouseDown(Event evt, int x, int y) {
       setClicked(true);
       return true;
    }
    
    
}   // 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

    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) { // Constructor
       board = theBoard;
       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 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 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 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 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 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;
       Graphics g = getGraphics();
       g.fillRect(x, y, (w-1)/8, (h-1)/8);
       g.dispose();
       board[square] = -1;
    }
    
    public Dimension minimumSize() {
        return new Dimension(160,160);
    }

    public Dimension preferredSize() {
        return minimumSize();
    }
}