home *** CD-ROM | disk | FTP | other *** search
/ BURKS 2 / BURKS_AUG97.ISO / BURKS / LANGUAGE / JAVA / NOTES / SOURCE / pentomin.jav < prev    next >
Text File  |  1996-12-20  |  15KB  |  398 lines
  1. // "LittlePentominosApplet"
  2. //
  3. // A pentomino consists of five squares attached along their edges.
  4. // There are exactly twelve possible pentominos that can be formed
  5. // in this way (not counting reflections and rotations).  Someone once
  6. // gave me a Pentominos puzzle where the goal was to place the 12
  7. // pentominos on an 8-by-8 board, leaving 4 blank squares in certain
  8. // previously decided positions.  This Java applet solves this puzzle
  9. // using a straightforward recursive backtracking procedure.
  10. //
  11. // This is a simple version of the applet that sets up and solves
  12. // randomly chosen boards.  If there is a mouseclick on the applet,
  13. // a new board is set up.  For a pentominos applet that gives more
  14. // user control, see my Java page at http://math.hws.edu/xJava
  15. //
  16. //
  17. // David Eck (eck@hws.edu)
  18.  
  19. import java.applet.Applet;
  20. import java.awt.*;
  21.  
  22. public class LittlePentominosApplet extends Applet implements Runnable {
  23.     
  24.     int board[];          // The 8-by-8 board is actually represented
  25.                           // conceptually as a 10-by-10 data structure
  26.                           // in which the cells along the border
  27.                           // are declared permanently "filled"
  28.                           // This simplifies testing whether a given
  29.                           // piece fits at a given position on the 
  30.                           // board.  Furthermore, this 10-by-10 board
  31.                           // is represented by a 1-dimensional array
  32.                           // in which the 10*i+j-th entry represents
  33.                           // row j and column i on the board.
  34.                                
  35.     PentominosBoardCanvas boardcanvas;  // for displaying the board on the screen
  36.                                
  37.     boolean used[];  //  used[i] tells whether piece # i is already on the board
  38.     
  39.     int numused;     // number of pieces currently on the board, from 0 to 12
  40.     
  41.     Thread gameThread = null;   // a thread to run the puzzle solving procedure
  42.                                 // (while the main applet thread handles the user interface)
  43.                                 
  44.     boolean done;  // used in play() to test whether the puzzle is solved (or aborted)
  45.     
  46.     boolean clicked;  // set to true when user clicks on the applet
  47.  
  48.     final int pieces[][] = {
  49.        { 1, 1,2,3,4 },         // This array represents everything the program
  50.        { 1, 10,20,30,40 },     // knows about the individual pentominos.  Each
  51.        { 2, 9,10,11,20 },      // row in the array represents a particular
  52.        { 3, 1,10,19,20 },      // pentomino in a particular orientation.  Different
  53.        { 3, 10,11,12,22 },     // orientations are obtained by rotating or flipping
  54.        { 3, 1,11,21,22 },      // the pentomino over.  Note that the program must
  55.        { 3, 8,9,10,18 },       // try each pentomino in each possible orientation,
  56.        { 4, 10,20,21,22 },     // but must be careful not to reuse a piece if
  57.        { 4, 1,2,10,20 },       // it has already been used on the board in a
  58.        { 4, 10,18,19,20 },     // different orientation.
  59.        { 4, 1,2,12,22 },       //     The pentominoes are numbered from 1 to 12.
  60.        { 5, 1,2,11,21 },       // The first number on each row here tells which pentomino
  61.        { 5, 8,9,10,20 },       // that line represents.  Note that there can be
  62.        { 5, 10,19,20,21 },     // up to 8 different rows for each pentomino.
  63.        { 5, 10,11,12,20 },     // some pentominos have fewer rows because they are
  64.        { 6, 10,11,21,22 },     // symmetric.  For example, the pentomino that looks
  65.        { 6, 9,10,18,19 },      // like:
  66.        { 6, 1,11,12,22 },      //           GGG
  67.        { 6, 1,9,10,19 },       //           G G
  68.        { 7, 1,2,10,12 },       //
  69.        { 7, 1,11,20,21 },      // can be rotated into three additional positions,
  70.        { 7, 2,10,11,12 },      // but flipping it over will give nothing new.
  71.        { 7, 1,10,20,21 },      // So, it has only 4 rows in the array.
  72.        { 8, 10,11,12,13 },     //     The four remaining entries in the array
  73.        { 8, 10,20,29,30 },     // describe the given piece in the given orientation,
  74.        { 8, 1,2,3,13 },        // in a way convenient for placing the piece into
  75.        { 8, 1,10,20,30 },      // the one-dimensional array that represents the
  76.        { 8, 1,11,21,31 },      // board.  As an example, consider the row
  77.        { 8, 1,2,3,10 },        //
  78.        { 8, 10,20,30,31 },     //           { 7, 1,2,10,19 }
  79.        { 8, 7,8,9,10 },        //
  80.        { 9, 1,8,9,10 },        // If this piece is placed on the board so that
  81.        { 9, 10,11,21,31 },     // its topmost/leftmost square fills position
  82.        { 9, 1,2,9,10 },        // p in the array, then the other four squares
  83.        { 9, 10,20,21,31 },     // will be at positions  p+1, p+2, p+10, and p+19.
  84.        { 9, 1,11,12,13 },      // To see whether the piece can be played at that
  85.        { 9, 10,19,20,29 },     // position, it suffices to check whether any of
  86.        { 9, 1,2,12,13 },       // these five squares are filled. 
  87.        { 9, 9,10,19,29 },      //     On the board, each piece will be shown
  88.        { 10, 8,9,10,11 },      // in its own color.
  89.        { 10, 9,10,20,30 },    
  90.        { 10, 1,2,3,11 },
  91.        { 10, 10,20,21,30 },
  92.        { 10, 1,2,3,12 },
  93.        { 10, 10,11,20,30 },
  94.        { 10, 9,10,11,12 },
  95.        { 10, 10,19,20,30 },
  96.        { 11, 9,10,11,21 },
  97.        { 11, 1,9,10,20 },
  98.        { 11, 10,11,12,21 },
  99.        { 11, 10,11,19,20 },
  100.        { 11, 8,9,10,19},
  101.        { 11, 1,11,12,21 },
  102.        { 11, 9,10,11,19 },
  103.        { 11, 9,10,20,21 },
  104.        { 12, 1,10,11,21 },
  105.        { 12, 1,2,10,11 },
  106.        { 12, 10,11,20,21 },
  107.        { 12, 1,9,10,11 },
  108.        { 12, 1,10,11,12 },
  109.        { 12, 9,10,19,20 },
  110.        { 12, 1,2,11,12 },
  111.        { 12, 1,10,11,20 }, 
  112.     };
  113.     
  114.     
  115.     public void init() {
  116.     
  117.         board = new int[100];
  118.         used = new boolean[13];
  119.     
  120.         setLayout(new BorderLayout());
  121.         boardcanvas = new PentominosBoardCanvas(board);  // for displaying the board
  122.         add("Center",boardcanvas);
  123.         
  124.     }
  125.     
  126.     public void start() {
  127.        gameThread = new Thread(this);
  128.        gameThread.start();
  129.     }
  130.     
  131.     public void stop() {
  132.        if (gameThread != null && gameThread.isAlive())
  133.           gameThread.stop();
  134.     }
  135.     
  136.     boolean putPiece(int p, int square) {  // try to place a piece on the board,
  137.                                            // return true if it fits
  138.         if (board[square] != 0)
  139.             return false;
  140.         for (int i = 1; i <= 4; i ++)
  141.             if (board[square + pieces[p][i]] != 0)  // one of the squares needed is already occupied
  142.                return false;
  143.         boardcanvas.playPiece(pieces[p],square);  // color in the squares to represent the piece
  144.         return true;
  145.     }
  146.     
  147.  
  148.     void play(int square) {   // recursive procedure that tries to solve the puzzle
  149.                               // parameter "square" is the number of the next empty
  150.                               // to be filled
  151.         for (int p=0; p<63; p++)
  152.            if (!done && (used[pieces[p][0]] == false) && putPiece(p,square)) {  // try piece p
  153.                used[pieces[p][0]] = true;
  154.                numused++;
  155.                if (getClicked()) {
  156.                   done = true;
  157.                   return;
  158.                }
  159.                else if (numused == 12) {  // puzzle is solved
  160.                   doDelay(5000);
  161.                   done = true;
  162.                   return;
  163.                }
  164.                else {
  165.                   doDelay(20);
  166.                   int nextSquare = square;
  167.                   while (board[nextSquare] != 0)  // find next empty square
  168.                      nextSquare++;
  169.                   play(nextSquare);  // and try to complete the solution
  170.                   if (done)
  171.                      return;
  172.                   boardcanvas.removePiece(pieces[p],square);  // backtrack
  173.                   numused--;
  174.                   used[pieces[p][0]] = false;
  175.                }
  176.            }
  177.     }
  178.     
  179.     void setUpRandomBoard() {
  180.         for (int i=0; i<100; i++) // fill in the border with -1's
  181.            board[i] = -1;
  182.         for (int i=1; i<9; i++)   // fill in the rest of the board with empty spaces (0's)
  183.           for (int j=1; j<9; j++)
  184.              board[j*10+i] = 0;
  185.         int x,y;
  186.         switch ((int)(5*Math.random())) {
  187.