import java.awt.*;
import java.applet.*;
import java.util.*;

public class Gominos extends Applet {

  private int atoms = 5;
  private byte ominos[][][];
  private Choice atomsMenu = new Choice();
  private Choice sizeMenu = new Choice();
  private Button startStop = new Button("Stop");
  private Button pauseRun = new Button("Pause");
  private Ominos om;

  public void init() {
    setBackground(Color.white);
    for (int i = 3; i < 8; i++)
      atomsMenu.addItem(i + "");
    atomsMenu.select(atoms-3);
    MakeSizeMenu();
    Panel menu = new Panel();
    menu.add(atomsMenu);
    menu.add(sizeMenu);
    menu.add(startStop);
    menu.add(pauseRun);
    om = new Ominos();
    setLayout(new BorderLayout());
    add("North",menu);
    add("Center",om);
  }

  private void MakeSizeMenu() { // figure out all X x Y's such that X,Y >= (atoms+2)/2
    sizeMenu.removeAll();
    GenOminos();
    int size = ominos.length * (ominos[0][0].length / 2);
    for (int i = (atoms+2)/2; i < (int)(Math.sqrt(size)+1); i++)
      if (size / i * i == size)
        sizeMenu.addItem(i + " x " + (size / i));
    sizeMenu.select(sizeMenu.countItems()-1);
    }
  
  public void start() {
    action(null,"Start"); // let 'er rip automatically
  }

  public void stop() {
    action(null,"Stop");
  }

  public String getAppletInfo() {
    return "Ominos v1.0";
  }
  
  public boolean action(Event evt, Object what) {
    String s = what.toString();
    if (s.equals("Pause")) {
      om.Suspend();
      pauseRun.setLabel("Run");
    } else if (s.equals("Run")) {
      om.Resume();
      pauseRun.setLabel("Pause");
    } else if (s.equals("Stop")) {
      om.Stop();
      pauseRun.disable();
      atomsMenu.enable();
      sizeMenu.enable();
      startStop.setLabel("Start");
    } else if (s.equals("Start")) {
      s = sizeMenu.getSelectedItem();
      int height = Integer.parseInt(s.substring(0,s.indexOf("x")-1));
      int width = Integer.parseInt(s.substring(s.indexOf("x")+2));
      om.Start(height,width,ominos);
             pauseRun.enable();
             pauseRun.setLabel("Pause");
      atomsMenu.disable();
      sizeMenu.disable();
      startStop.setLabel("Stop");
    } else if (s.indexOf("x") == -1) {
      atoms = Integer.parseInt(s);
      MakeSizeMenu();
    }
    return true;
  }

  private void Rotate(byte b[][]) { // rotate 90 degrees (clockwise)
    for (int i = 1; i < b.length/2+1; i++)
      for (int j = 1; j < b.length/2; j++) {
        byte t = b[i][j];
        b[i][j] = b[b.length-j-1][i];
        b[b.length-j-1][i] = b[b.length-i-1][b.length-j-1];
        b[b.length-i-1][b.length-j-1] = b[j][b.length-i-1];
        b[j][b.length-i-1] = t;
      }
  }

  private void Flip(byte b[][]) { // flip (vertically)
    for (int i = 1; i < b.length/2; i++) {
      byte t[] = b[i];
      b[i] = b[b.length-i-1];
      b[b.length-i-1] = t;
    }
  }

  private void Mirror(byte b[][]) { // mirror (horizontally)
    for (int i = 1; i < b.length-2; i++)
      for (int j = 1; j < b.length/2; j++) {
        byte t = b[i][j];
        b[i][j] = b[i][b.length-j-1];
        b[i][b.length-j-1] = t;
      }
  }

  private boolean Equals(byte a[], byte b[]) {
    for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return false;
    return true;
  }

  private void Compact(byte b[][]) {
    byte n[] = new byte[b[0].length];
    for (int i = 0; i < n.length; i++) n[i] = 0;
    while (Equals(b[1],n)) {
      for (int i = 1; i < b.length-1; i++) b[i] = b[i+1];
      b[b.length-2] = (byte [])n.clone();
    }
    a: while (true) {
      for (int i = 1; i < b.length-1; i++) if (b[i][1] != 0) break a;
      for (int i = 1; i < b.length-1; i++) {
        for (int j = 1; j < b.length-1; j++) b[i][j] = b[i][j+1];
        b[i][b.length-2] = 0;
      }
    }
  }

  private boolean Compare(byte b[][], Vector v) {
    Enumeration e = v.elements();
    boolean rc = true;
    a: while (e.hasMoreElements()) {
      byte c[][] = ((byte[][])e.nextElement());
      for (int i = 1; i < b.length/2+1; i++)
        if (!Equals(b[i],c[i])) continue a;
      return false; 
    }
    return true; // do not match
  }

  private void AddOminos(byte[][] board, Vector nms) {
    byte c[];
    Compact(board);
    if (Compare(board,nms)) { // vector of boards NOT of x,y's!
      byte b[][] = new byte[board.length][board[0].length];
      for (int i = 0; i < board.length; i++) b[i] = (byte [])board[i].clone();
      nms.addElement((Object)b);
    }
  }

  private void GenOminos() {
    Vector oms = new Vector();
    oms.addElement((Object)new byte[2]);
    ((byte[])(oms.elementAt(0)))[0] = 0;
    ((byte[])(oms.elementAt(0)))[1] = 0; // at the begining the was ONE
    for (int at = 1; at < atoms; at++) { // loop through all dimensions
      Vector nms = new Vector(); // holds the next level
      for (int mn = 0; mn < oms.size(); mn++) { // loop down current ominos list
        byte board[][] = new byte[at*2+3][at*2+3]; // board to hold all ominos for this level
        for (int i = 0; i < board.length; i++)
          for (int j = 0; j < board[i].length; j++) board[i][j] = 0;
        for (int i = 0; i < ((byte[])oms.elementAt(mn)).length; i += 2)
          board[at+1+((byte[])oms.elementAt(mn))[i]][at+1+((byte[])oms.elementAt(mn))[i+1]] = 1;
        for (int i = 1; i < board.length-1; i++)
          for (int j = 1; j < board[i].length-1; j++)
            if ((board[i][j] == 0) && (board[i-1][j] == 1 || board[i+1][j] == 1 ||
                board[i][j-1] == 1 || board[i][j+1] == 1)) { // if this one is empty and one of it's neighbors is full
              byte b[][] = new byte[board.length][];
              for (int k = 0; k < board.length; k++) b[k] = (byte [])board[k].clone();
              b[i][j] = 1;
              Compact(b); if (Compare(b,nms)) {
                Flip(b); Compact(b); if (Compare(b,nms)) {
                  Rotate(b); Compact(b); if (Compare(b,nms)) {
                    Mirror(b); Compact(b); if (Compare(b,nms)) {
                      Rotate(b); Compact(b); if (Compare(b,nms)) {
                        Flip(b); Compact(b); if (Compare(b,nms)) {
                          Rotate(b); Compact(b); if (Compare(b,nms)) {
                            Mirror(b); Compact(b); if (Compare(b,nms)) {
                              nms.addElement((Object)b);
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
      }
      oms.removeAllElements();
      byte c[];
      for (int l = 0; l < nms.size(); l++) {
        byte b[][] = ((byte[][])nms.elementAt(l));
        oms.addElement((Object)(c = new byte[(at+1)*2]));
        int k = 0;
        for (int i = 1; i < at+2; i++)
          for (int j = 1; j < at+2; j++) {
            if (b[i][j] == 1) {
              c[k] = (byte)(i-1); k++;
              c[k] = (byte)(j-1); k++;
            }
          }
      }
    }
    ominos = new byte[oms.size()][][];
    byte board[][] = new byte[atoms*2+1][atoms*2+1]; // board to hold all ominos for this level
    for (int k = 0; k < ominos.length; k++) {
      byte b[] = ((byte [])oms.elementAt(k));
      for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[i].length; j++) board[i][j] = 0; // zap the board
      for (int i = 0; i < b.length; i += 2) board[atoms+b[i]][atoms+b[i+1]] = 1; // build it
      Vector nms = new Vector();
      AddOminos(board,nms);
      Flip(board); AddOminos(board,nms);
      Rotate(board); AddOminos(board,nms);
      Mirror(board); AddOminos(board,nms);
      Rotate(board); AddOminos(board,nms);
      Flip(board); AddOminos(board,nms);
      Rotate(board); AddOminos(board,nms);
      Mirror(board); AddOminos(board,nms);
      ominos[k] = new byte[nms.size()][];
      for (int l = 0; l < ominos[k].length; l++) {
        board = (byte [][])nms.elementAt(l);
        ominos[k][l] = new byte[atoms*2];
        int m = 0;
        for (int i = 1; i < atoms+1; i++)
          for (int j = 1; j < atoms+1; j++)
            if (board[i][j] == 1) {
              ominos[k][l][m] = (byte)(i-1); m++;
              ominos[k][l][m] = (byte)(j-1); m++;
            }
      }
    }
  }

}

class Ominos extends Canvas implements Runnable {

  private int[][] surround = {{-1,0},{0,-1},{1,0},{0,1}};
  private int[][] shifts;
  private Vector[] mlist;
  private BitSet[] blist;
  private short OS[] = new short[0];
  private Thread t;
  private int counter;
  private Color colors[] = new Color[0];
  private int atoms, molecules, size, height, width;
  private byte ominos[][][];

  public void Start(int height, int width, byte ominos[][][]) {
    atoms = ominos[0][0].length / 2;
    molecules = ominos.length;
    size = molecules * atoms;
    this.height = height;
    this.width = width;
    this.ominos = ominos;

    OS = new short[0]; // zap the last solution, if any
    mlist = new Vector[molecules];
    blist = new BitSet[molecules];
    for (int i = 0; i < molecules; i++) blist[i] = new BitSet(size+1);
    blist[0].set(size); // guard bit
    shifts = new int[size][surround.length];
//  System.out.println("atoms = " + atoms + ", molecules = " + molecules + ", size = " + size +
//    ", height = " + this.height + ", width = " + this.width);
    GenShift();
    for (int i = 0; i < molecules; i++) mlist[i] = new Vector();
    GenMolecule();
    colors = CreateColorCircle(molecules);
    counter = 0;
    repaint();
         t = new Thread(this);
    t.start();
  }
  
  public void Stop() {
    if (t != null) {
      t.stop();
      t = null;
    }
  }

  public void Suspend() {
    t.suspend();
  }
  
  public void Resume() {
    t.resume();
  }

  public void run() {
    Solve(0);
  }
  
  public synchronized void paint(Graphics g) {
    Dimension d = size();
    if (d.height == 0 || d.width == 0 || colors.length == 0) return;
    int hh = d.height / height, ww = d.width / width;
    if (hh < ww) ww = hh; else hh = ww;
    int ox = (d.width - (ww*width) - 1) / 2, oy = (d.height - (hh*height) - 1) / 2;
    g.translate(ox,oy);
    g.clearRect(0,0,width*ww,height*hh);
    g.setColor(Color.black);
    g.drawRect(0,0,width*ww+1,height*hh+1);
    if (OS.length == 0) {
           for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) {
        g.setColor(colors[(h*width+w) % colors.length]);
        g.fillRect(w*ww+1,h*hh+1,ww,hh);
      }
      return;
    }
       for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) {
      g.setColor(colors[OS[h*width+w]]); g.fillRect(w*ww+1,h*hh+1,ww,hh);
    }
    g.setColor(Color.black);
    for (int h = 0; h < height; h++) for (int w = 0; w < width; w++) {
      if ((h < (height-1)) && (OS[h*width+w] != OS[(h+1)*width+w]))
        g.drawLine(w*ww,(h+1)*hh,(w+1)*ww,(h+1)*hh);
      if ((w < (width-1)) && (OS[h*width+w] != OS[h*width+w+1]))
        g.drawLine((w+1)*ww,h*hh,(w+1)*ww,(h+1)*hh);
    }
  }

  private Color[] CreateColorCircle(int nPalSize) { // from an algorithm by J_Killingbeck@msn.com
    Color c[] = new Color[nPalSize];
    for (int n = 0; n < nPalSize; n++) {
      int nFactor = 768 * n / nPalSize;   // Assure that it runs 0 to 768
      if (nFactor >= 768) nFactor = nFactor - 768; // Adjust for color shift
      if (nFactor <= 256) c[n] = new Color(
        (int) ((double)255*(Math.sin(((double)nFactor/256)*Math.PI/2))),
        0,
        (int) ((double)255*(Math.cos(((double)nFactor/256) * Math.PI/2))) );
      else if ((nFactor > 256) && (nFactor <= 512)) c[n] = new Color(
        (int) ((double)255*(Math.cos(((double)(nFactor-256)/256)*Math.PI/2))),
        (int) ((double)255*(Math.sin(((double)(nFactor-256)/256)*Math.PI/2))),
        0 );
      else if (nFactor > 512) c[n] = new Color(
        0,
        (int) ((double)255*(Math.cos(((double)(nFactor-512)/256)*Math.PI/ 2))),
        (int) ((double)255*(Math.sin(((double)(nFactor-512)/256)*Math.PI/ 2))) );
    }
    return c;
   }
 
  private boolean Legal(int x,int y) {
    return ((x >= 0) & (x < width) & (y >= 0) & (y < height));
  }

  private void GenShift() {
    for (int h = 0; h < height; h++) {
      for (int w = 0; w < width; w++) {
        for (int s = 0; s < surround.length; s++) {
          if (Legal(w + surround[s][0],h + surround[s][1])) {
            shifts[width * h + w][s] = width * (h + surround[s][1]) +
              w + surround[s][0];
          } else {
            shifts[width * h + w][s] = size;
          }
        }
      }
    }
  }

  private int scount;
  private void CountSeg(int num,BitSet sboard) { // internal procedure for CheckSeg with shared vars (above)
    int shift;
    sboard.set(num); scount++;
    for (int s = 0; s < surround.length; s++) {
      shift = shifts[num][s];
      if (!sboard.get(shift)) CountSeg(shift,sboard);
    }
  }

  private boolean CheckSeg(BitSet board) {
    BitSet sboard = (BitSet)board.clone(); // create a local copy of this to play with
    sboard.set(size);
    for (int b = 0; b < size; b++) {
      if (!sboard.get(b)) {
        scount = 0;
        CountSeg(b,sboard);
        if (scount % atoms != 0) return false;
      }
    }
    return true;
  }

  private void GenMolecule() {
    for (int mn = 0; mn < molecules; mn++) {
      for (int j = 0; j < ominos[mn].length; j++)
        for (int h = 0; h < height; h++)
          loop: for (int w = 0; w < width; w++) {
            for (int a = 0; a < atoms * 2; a += 2)
              if (!Legal(w + ominos[mn][j][a],h + ominos[mn][j][a+1]))
                continue loop;
            BitSet mnew = new BitSet(size+1);
            for (int a = 0; a < atoms * 2; a += 2)
              mnew.set((h + ominos[mn][j][a+1]) * width + w + ominos[mn][j][a]);
            if (CheckSeg(mnew)) mlist[mn].addElement((Object)mnew);
          }
      }
  }
  
  private void PrintBoard(int mn) {
    short os[] = new short[size];
    short chars[] = new short[molecules];
    for (int i = 0; i < molecules; i++) chars[i] = (short)(i);
    for (int b = 0; b < size; b++) os[b] = 0;
    for (int i = mn; i > 0; i--)
      for (int b = 0; b < size; b++) if (blist[i].get(b)) os[b] = chars[i];
//  System.out.println(os);
    OS = (short [])os.clone();
    repaint();
  }

  private void Solve(int mn) {
//  PrintBoard(mn);
    BitSet emptySet = new BitSet(size+1);
    Enumeration mtrace = mlist[mn].elements();
    while (mtrace.hasMoreElements()) {
      BitSet board = (BitSet)blist[mn].clone(), mboard = (BitSet)mtrace.nextElement();
      board.and(mboard);
      if (emptySet.equals(board)) {
        board = (BitSet)blist[mn].clone();
        if (mn < (molecules-1)) {
          board.or(mboard);
          if (CheckSeg(board)) {
            board = (BitSet)blist[mn].clone();
            board.or(mboard);
            blist[mn+1] = board;
            Solve(mn+1);
          }
        } else {
          counter++;
//        System.out.print(counter + " ");
          PrintBoard(mn);
        }
      }
    }
  }
}