/* Copyright (C) 2002 J. M. Spivey */

import java.awt.*;

/* This uses Knuth's method of 'dancing links' to carry out an efficient 
backtracking search.  The method is based on the observation that the
assignments

    p.prev.next = p.next; p.next.prev = p.prev;

can be reversed by 

    p.prev.next = p.next.prev = p;

This is yet another former Oberon program, converted to Java for your
edification and delight! */

/** Solve the pentominoes problem.
 * 
 * The problem can be represented as an 'exact cover' problem: that of
 * finding a set of disjoint rows of a Boolean matrix that together
 * cover all of the columns.  Columns of the matrix correspond to
 * squares that must be covered or pieces that must be placed, and
 * each row corresponds to a move that places one piece over certain
 * squares.  The matrix is represented in sparse form, with both rows
 * and columns organised as doubly-linked lists. */
public class PentoSearch implements Runnable {
    private Column root;                // Root of the entire matrix
    private int nrows = 0, ncols = 0;   // Statistics
    
    private static final int MAX = 20;
    
    private Dimension bounds;
    private Square square[][] = new Square[MAX][MAX];
    private Piece piece[] = new Piece[128];
    private int nsquares = 0;
    private PentoWatcher watcher = null;
    private boolean cont;
    
    /** Return all squares of the board as an array of Point objects */
    public Point[] getSquares() {
        Point sq[] = new Point[nsquares];
        int k = 0;
        
        for (int x = 0; x < bounds.width; x++)
            for (int y = 0; y < bounds.height; y++)
                if (square[x][y] != null)
                    sq[k++] = new Point(x, y);
        
        if (k != nsquares) throw new RuntimeException();
        
        return sq;
    }
    
    public Dimension getBounds() {
        return new Dimension(bounds);
    }
    
    // These routines create the various kinds of object and link them into
    // the sparse matrix.
    
    /** Create a square on the board */
    private void makeSquare(int x, int y) {
        Square p = new Square();
        p.coords = new Point(x, y); p.size = 0;
        p.head = new Cell(); p.head.down = p.head.up = p.head;
        p.prev = root.prev; p.next = root;
        root.prev.next = p; root.prev = p;
        square[x][y] = p; ncols++; nsquares++;
    }
    
    /** Create a tile */
    private void makePiece(char name, Color color) {
        Piece p = new Piece();
        p.name = name; p.color = color; p.size = 0;
        p.head = new Cell(); p.head.down = p.head.up = p.head;
        p.prev = root.prev; p.next = root;
        root.prev.next = p; root.prev = p;
        piece[(int) name] = p; ncols++;
    }

    /** Create a placement of a tile */
    private void makeMove(char name, int xx[], int yy[], int n) {
        Column r = piece[(int) name];
        Cell p = new Cell(); p.left = p.right = p;
        p.up = r.head.up; p.down = r.head; 
        r.head.up.down = p; r.head.up = p;
        p.column = r; r.size++;
        
        for (int k = 0; k < n; k++) {
            r = square[xx[k]][yy[k]];
            Cell q = new Cell(); q.left = p; q.right = p.right;
            p.right.left = q; p.right = q;
            q.up = r.head.up; q.down = r.head;
            r.head.up.down = q; r.head.up = q;
            q.column = r; r.size++;
            p = q;
        }
        
        nrows++;
    }
    
    public static final String menu[] = 
        { "Rectangle 6 x 10", "Rectangle 5 x 12", "Rectangle 4 x 15",
          "Rectangle 3 x 20", "Parallelogram 6 x 10", "Parallelogram 10 x 6", 
          "Chessboard + square", "Chessboard - corners", "Ziggurat" };
    
    private static final int DONUT = 6;
    
    /** Create the board as one of the menu of shapes */
    private void createBoard(int choice) {
        switch (choice) {
        case 0: case 1: case 2: case 3:
            // Various rectangles
            bounds = new Dimension(60/(6-choice), 6-choice);
            for (int x = 0; x < bounds.width; x++)
                for (int y = 0; y < bounds.height; y++)
                    makeSquare(x, y);
            break;
            
        case 4: case 5:
            // Rhombus shape
            bounds = (choice == 4 ? new Dimension(15, 6) : new Dimension(15, 10));
            for (int x = 0; x < 60/bounds.height; x++)
                for (int y = 0; y < bounds.height; y++)
                    makeSquare(x+y, bounds.height-y-1);
            break;
            
        case 6:
            // Chess board with hole -- let's allow the hole to move
            bounds = new Dimension(8, 8);
            for (int x = 0; x < 8; x++)
                 for (int y = 0; y < 8; y++)
                     makeSquare(x, y);
            break;
            
        case 7:
            // Blob -- 8 x 8 with missing corners
            bounds = new Dimension(8, 8);
            for (int x = 0; x < 8; x++)
                 for (int y = 0; y < 8; y++)
                     if (x > 0 && x < 7 || y > 0 && y < 7)
                         makeSquare(x, y);
            break;
            
        case 8:
            // Ziggurat -- upside down because the display is also inverted
            bounds = new Dimension(15, 8);
            for (int y = 0; y < 8; y++)
                for (int x = y; x < 15-y; x++)
                    if (y > 0 || x < 4 || x >= 6 && x < 9 || x >= 11)
                        makeSquare(x, 7-y);
            break;
        }
    }
    
    /** Test if a placement falls entirely on the board */
    private boolean feasible(int xx[], int yy[], int n) {
        for (int k = 0; k < n; k++)
            if (square[xx[k]][yy[k]] == null)
                return false;
        
        return true;
    }

    /** Create a piece and all its feasible placements */
    private void createPiece(char name, Color color, int rots, int refls, 
			     String layout) {
        makePiece(name, color);

        // Translate the piece description into coordinates
        int x = 0, y = 0, n = 0;
        int xmin = 0, xmax = 0, ymin = 0, ymax = 0; 
        int xx[] = new int[10], yy[] = new int[10];
        for (int k = 0; k < layout.length(); k++) {
            switch (layout.charAt(k)) {
            case 'x':                       // Fill a square
                xx[n] = x; yy[n] = y; n++;
                if (x > xmax) xmax = x;
                if (y > ymax) ymax = y;
                x++;
                break;
            case '.':                       // Skip a square
                x++;
                break;
            case '/':                       // Move to next row
                x = 0; y++;
                break;
            }
        }

        // Make |refls| reflections of the piece
        int uu[] = new int[10], vv[] = new int[10];
        for (int r = 0; r < refls; r++) {
            // Make |rots| rotations
            for (int m = 0; m < rots; m++) {
                // Create all feasible translations
                for (x = -xmin; x < bounds.width - xmax; x++) {
                    for (y = -ymin; y < bounds.height - ymax; y++) {
                        // Translate the coordinates
                        for (int k = 0; k < n; k++) {
                            uu[k] = xx[k] + x; vv[k] = yy[k] + y;
                        }

                        if (feasible(uu, vv, n))
                            makeMove(name, uu, vv, n);
                    }
                }
      
                // Rotate by 90 degrees
                for (int k = 0; k < n; k++) {
                    int z = xx[k]; xx[k] = (MAX-1) - yy[k]; yy[k] = z;
                }
                { int z = xmax; xmax = (MAX-1) - ymin; ymin = xmin;
                  xmin = (MAX-1) - ymax; ymax = z; }
            }

            // Reflect about vertical axis
            for (int k = 0; k < n; k++)
                xx[k] = (MAX-1) - xx[k];
            { int z = xmax; xmax = (MAX-1) - xmin; xmin = (MAX-1) - z; }
        }
    }

    /** Create the whole game */
    public PentoSearch(int choice) {
        root = new Column(); root.prev = root.next = root;
        createBoard(choice);

        createPiece('F', Color.black, 4, 2, "xx/.xx/.x");
        createPiece('I', Color.black, 2, 1, "xxxxx");
        createPiece('L', Color.blue, 4, 2, "xxxx/x");
        createPiece('N', Color.yellow, 4, 2, "xxx/..xx");
        createPiece('P', Color.red, 4, 2, "xxx/xx.");
        createPiece('T', Color.red, 4, 1, "xxx/.x/.x");
        createPiece('U', Color.lightGray, 4, 1, "xx/x/xx");
        createPiece('V', Color.green, 4, 1, "xxx/x/x");
        createPiece('W', Color.blue, 4, 1, "x/xx/.xx");
        createPiece('X', Color.green, 1, 1, ".x/xxx/.x");
        createPiece('Y', Color.yellow, 4, 2, "xxxx/.x");
        createPiece('Z', Color.lightGray, 2, 2, ".xx/.x/xx");
        if (choice == DONUT)
            createPiece('O', Color.white, 1, 1, "xx/xx");
    }

    int count;
    Cell choice[] = new Cell[20];
    
    private void solve(int level) {
        if (! cont) return;
        
        if (root.next == root) {
            count++;
            
            if (watcher != null) {
                watcher.solution(count);
                for (int k = 0; k < level; k++)
                    choice[k].watchRow(watcher);
                watcher.finish();
            }
            
            return;
        }
        
        // Find smallest column |col|
        Column col = root.next;
        for (Column c = col.next; c != root; c = c.next)
            if (c.size < col.size) col = c;
        
        if (col.size == 0) return;
        
        col.cover();
        
        // Try each row that intersects |col|
        for (Cell p = col.head.down; p != col.head; p = p.down) {
            choice[level] = p;
            
            // Cover other columns in row p
            for (Cell q = p.right; q != p; q = q.right)
                q.column.cover();
            
            solve(level+1);
            
            // Uncover other columns in row p
            for (Cell q = p.left; q != p; q = q.left)
                q.column.uncover();
        }
        
        col.uncover();
    }

    public void run() {
        count = 0;
        cont = true;
        solve(0);
        if (watcher != null) watcher.done();
    }
    
    public void kill() {
        cont = false;
    }
    
    public void addWatcher(PentoWatcher watcher) {
        this.watcher = watcher;
    }
}

class Cell {
    Cell up, down, left, right;
    Column column;

    public void printRow() {
        // Find the piece |r|
        Cell r = this;
        while (!(r.column instanceof Piece)) r = r.right;
        System.out.print(r.column);

        // Print each column that intersects the row
        for (Cell q = r.right; q != r; q = q.right)
            System.out.print(" " + q.column);
        
        // Print the position in the column
        int n = 0; 
        for (Cell q = this.column.head; q != this; q = q.down) n++;
        System.out.println("; # " + n + " of " + this.column.size +
                           " choices for " + this.column);
    }
    
    /** Show the move that corresponds to this row */
    public void watchRow(PentoWatcher watcher) {
        // Find the piece |r|
        Cell r = this;
        while (!(r.column instanceof Piece)) r = r.right;
        Piece p = (Piece) r.column;
        
        // Gather the squares that intersect the row
        Point a[] = new Point[10];
        int n = 0;
        for (Cell q = r.right; q != r; q = q.right)
            a[n++] = ((Square) q.column).coords;
        
        watcher.place(p.name, p.color, a, n);
    }
}
        
class Column {
    int size;
    Column prev, next;
    Cell head;

    /** Remove this column from the list of uncovered columns */
    public void cover() {
        this.prev.next = this.next; this.next.prev = this.prev;
        
        // Block each row that intersects p
        for (Cell q = this.head.down; q != this.head; q = q.down) {
            for (Cell r = q.right; r != q; r = r.right) {
                r.up.down = r.down; r.down.up = r.up;
                r.column.size--;
            }
        }
    }

    /** Restore this column to the list of uncovered columns */
    public void uncover() {
        this.prev.next = this.next.prev = this;
        
        // Unblock each row that intersects p
        for (Cell q = this.head.up; q != this.head; q = q.up) {
            for (Cell r = q.left; r != q; r = r.left) {
                r.up.down = r.down.up = r;
                r.column.size++;
            }
        }
    }
    
    public String toString() { return "root"; }
}

class Piece extends Column {
    char name;
    Color color;
    
    public String toString() { return String.valueOf(name); }
}

class Square extends Column {
    Point coords;
    
    public String toString() { return "(" + coords.x + "," + coords.y + ")"; }
}