// Modified output and added Timer() codeimport java.io.*;import java.util.*;public class penta{static final boolean DISPLAY_RESULTS = false;static final int CX = 5;static final int CY = 5;static final int N = 5;static final int SX = 10;static final int SY = 6;static class PAT{int x [] = new int [N];int y [] = new int [N];int sx, sy;int y0;PAT (String s){ int x, y, mx, n; int i; char c; x = y = mx = 0; n = 0; for (i = 0; i < s.length (); i++) { c = s.charAt (i); if (c == '/') { ++ y; if (x > mx) mx = x; x = 0; } else { if (c == '*') { this.x[n] = x; this.y[n] = y; ++n; } ++x; } } if (x > mx) mx = x; sx = mx; sy = y+1; if (n != N) throw new IllegalArgumentException (); normalize ();}PAT (PAT p, String rules){ int k, x, y, X, Y; sx = CX; sy = CY; for (k = 0; k < N; k++) { x = p.x[k]; y = p.y[k]; X = rules.charAt (1) == 'X' ? x : y; Y = rules.charAt (3) == 'X' ? x : y; if (rules.charAt (0) == '-') X = CX - X - 1; if (rules.charAt (2) == '-') Y = CY - Y - 1; this.x[k] = X; this.y[k] = Y; } normalize ();}final void put (int x0, int y0, char c){ int i; for (i = 0; i < N; i++) field [y0+y[i]][x0+x[i]] = c;}final boolean check (int x0, int y0){ int i; for (i = 0; i < N; i++) if (field [y0+y[i]][x0+x[i]] != 0) return false; return true;}public boolean equals (Object o){ int i, j; PAT q; if (! (o instanceof PAT)) return false; q = (PAT) o; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) if (x[i] == q.x[j] && y[i] == q.y[j]) break; if (j == N) return false; } return true;}void normalize (){ int xmin, xmax, ymin, ymax, i; xmin = CX; ymin = CY; xmax = ymax = -1; for (i = 0; i < N; i++) { if (x[i] < xmin) xmin = x[i]; if (x[i] > xmax) xmax = x[i]; if (y[i] < ymin) ymin = y[i]; if (y[i] > ymax) ymax = y[i]; } sx = xmax - xmin + 1; sy = ymax - ymin + 1; y0 = CY; for (i = 0; i < N; i++) { x[i] -= xmin; y[i] -= ymin; if (x[i] == 0 && y[i] < y0) y0 = y[i]; }}void print (PrintStream p, char c){ int i, j; char [] [] s = new char [N][N]; for (i = 0; i < N; i++) for (j = 0; j < N; j++) s [i][j] = ' '; for (i = 0; i < N; i++) s [y[i]][x[i]] = c; for (i = 0; i < N; i++) p.println (new String (s [i])); p.println ();}} // end of class PATstatic class FIG{PAT pats [] = new PAT [8];int n;char c;boolean used;static String rules [] = new String [] { "+X+Y", "-Y+X", "-X-Y", "+Y-X", "-X+Y", "-Y-X", "+X-Y", "+Y+X" };FIG (PAT p){ int i, j, k, x, y, X, Y; pats [0] = p; j = 1; for (i = 1; i < 8; i++) { pats [j] = new PAT (p, rules [i]); for (k = 0; k < j; k++) if (pats [k].equals (pats [j])) break; if (k == j) ++ j; } n = j;}FIG (String s){ this (new PAT (s.substring (1, s.length ()))); c = s.charAt (0);}void print (PrintStream s){ for (int i = 0; i < n; i++) pats [i].print (s, c);}} // end of FIG classstatic char [] [] field = new char [SY+2][SX+2];static char [] [] testfield = new char [SY+2][SX+2];static FIG [] figs = new FIG [20];static int nfigs;static String [] figdef = new String [] { "I*****", "L****/*", "Y****/.*", "V***/*/*", "P***/**", "U***/*.*", "T***/.*/.*", "N***/..**", "Z**/.*/.**", "R**/.**/.*", "W**/.**/..*", "X.*/***/.*" };static void makefigs (){ int i; for (i = 0; i < figdef.length; i++) figs [i] = new FIG (figdef [i]); nfigs = i;}/* --------------------------------------------------- */static int nsols = 0;static void disp (){ int y, x; ++nsols; if (!DISPLAY_RESULTS) return; System.out.println ("============== Solution #" + nsols + ": =============== "); for (y = 1; y <= SY; y++) { for (x = 1; x <= SX; x++) System.out.print (field [y][x]!=0 ? field [y][x] : '.'); System.out.println (); } System.out.println ();}static int xstart, ystart;static boolean find_hole (int x0){ int x, y, n; for (x = x0; x <= SX; x ++) for (y = 1; y <= SY; y++) if (field [y][x]==0) { xstart = x; ystart = y; return true; } return false;}static void try_put (PAT p, char c, int d, int x, int y){ int i; y -= p.y0; if (y < 1 || x + p.sx > SX+1 || y + p.sy > SY+1) return; if (! p.check (x, y)) return; p.put (x, y, c); if (d == 1) disp (); else deep (d-1, x); p.put (x, y, (char)0);}static void deep (int d, int x0){ int i, j, x, y; FIG ff; if (! find_hole (x0)) return; x = xstart; y = ystart; for (i = 0; i < nfigs; i++) { ff = figs [i]; if (!ff.used) { ff.used = true; for (j = 0; j < ff.n; j++) try_put (ff.pats [j], ff.c, d, x, y); ff.used = false; } }}static void search (){ int i, j; for (i = 0; i < nfigs; i++) figs [i].used = false; for (i = 0; i < SX+2; i++) field [0][i] = field [SY+1][i] = '*'; for (i = 0; i < SY+2; i++) field [i][0] = field [i][SX+1] = '*'; for (i = 0; i < nfigs; i++) { figs [i].used = true; for (j = 0; j < figs [i].n; j++) if (figs [i].pats [j].sx <= SX && figs [i].pats [j].sy <= SY) { //System.out.println ("" + i + "." + j); figs [i].pats [j].put (1, 1, figs [i].c); deep (nfigs-1, 1); figs [i].pats [j].put (1, 1, (char)0); } figs [i].used = false; }}/* --------------------------------------------------- */public static void main (String [] arg){ long start = System.currentTimeMillis(); //makefigs (); makefigs (); //long time1 = System.currentTimeMillis (); search (); //long time2 = System.currentTimeMillis (); //System.out.println ("time taken: " + (time2-time1) / 1000); System.out.print ("Solutions found: " + nsols + "; "); long end = System.currentTimeMillis(); System.out.println("Time: " + (end - start) + " ms"); }}