```package backtracking;

// résoudre le problème de Scott (pavage avec les pentaminos)

import java.util.HashSet;
import java.util.Set;

// les 8 isométries du carré
enum Iso { Id, Rot180, Hrefl, Vrefl, Rot90, Rot270, D1refl, D2refl }

class Tile {
final String name;
final boolean[][] pattern;
final int width, height;

public Tile(String name, boolean[][] pattern) {
super();
this.name = name;
this.pattern = pattern;
this.width = pattern.length;
this.height = pattern[0].length;
}

@Override
public boolean equals(Object obj) {
Tile that = (Tile)obj;
if (this.width != that.width || this.height != that.height)
return false;
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
if (this.pattern[x][y] != that.pattern[x][y])
return false;
return true ;
}

@Override
public int hashCode() {
int h = 31 * width + height;
for (int x = 0; x < width; x++)
for (int y = 0; y < height; y++)
h = 31 * h + (pattern[x][y] ? 17 : 42);
return h;
}

Set<Tile> iso() {
HashSet<Tile> s = new HashSet<>();
for (Iso iso: Iso.values()) {
int w = width, h = height;
switch (iso) {
case Id: case Rot180: case Hrefl: case Vrefl: break;
case Rot90: case Rot270: case D1refl: case D2refl: h = width; w = height; break;
}
boolean[][] pat = new boolean[w][h];
for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
switch (iso) {
case Id:     pat[x][y] = pattern[x][y]; break;
case Rot180: pat[x][y] = pattern[w-1-x][h-1-y]; break;
case Hrefl:  pat[x][y] = pattern[x][h-1-y]; break;
case Vrefl:  pat[x][y] = pattern[w-1-x][y]; break;
case Rot90:  pat[x][y] = pattern[h-1-y][x]; break;
case Rot270: pat[x][y] = pattern[y][w-1-x]; break;
case D1refl: pat[x][y] = pattern[y][x];     break;
case D2refl: pat[x][y] = pattern[h-1-y][w-1-x]; break;
}
}
return s;
}

}

public class ScottDLX {

private DLXNode[][] grid = new DLXNode[8][8];
private final Tile[] tiles = new Tile[] {
new Tile("I", new boolean[][] { { true ,true ,true ,true ,true  } }),
new Tile("V", new boolean[][] { { true ,true ,true  },
{ true ,false,false },
{ true ,false,false } }),
new Tile("Z", new boolean[][] { { false,true ,true  },
{ false,true ,false },
{ true ,true ,false } }),
new Tile("P", new boolean[][] { { true ,true ,true  },
{ true ,true ,false } }),
new Tile("N", new boolean[][] { { true ,true ,true ,false },
{ false,false,true ,true  } }),
new Tile("W", new boolean[][] { { false,true ,true  },
{ true ,true ,false },
{ true ,false,false } }),
new Tile("Y", new boolean[][] { { true ,true ,true ,true  },
{ false,true ,false,false } }),
new Tile("T", new boolean[][] { { true ,true ,true  },
{ false,true ,false },
{ false,true ,false } }),
new Tile("F", new boolean[][] { { false,true ,true  },
{ true ,true ,false },
{ false,true ,false } }),
new Tile("U", new boolean[][] { { true ,true ,true  },
{ true ,false,true  } }),
new Tile("L", new boolean[][] { { true ,true ,true ,true },
{ true ,false,false,false} }),
new Tile("X", new boolean[][] { { false,true ,false },
{ true ,true ,true  },
{ false,true ,false } }),
};
private DLXNode[] col = new DLXNode[12];

ScottDLX() {
for (int i = 0; i < 12; i++) {
DLXNode n = new DLXNode(tiles[i].name);
col[i] = n;
}
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++) {
if ((i == 3 || i == 4) && (j == 3 || j == 4)) continue;
cols.add(grid[i][j] = new DLXNode(i + ":" + j));
}
System.out.println(cols.size() + " colonnes");
int rows = 0;
for (int k = 0; k < 12; k++) {
Tile t0 = tiles[k];
System.err.print("pièce " + t0.name + ": ");
Set<Tile> s = t0.iso();
System.err.print(s.size() + " symétries");
DLXNode c = col[k];
int rows0 = rows;
for (Tile t: s) {
for (int i = 0; i < 8-t.width+1; i++)
L:for (int j = 0; j < 8-t.height+1; j++) {
for (int x = 0; x < t.width; x++)
for (int y = 0; y < t.height; y++)
if (t.pattern[x][y]) {
if (grid[i+x][j+y] == null) continue L;
}
rows++;
}
}
System.err.println(", " + (rows - rows0) + " placements");
}
System.out.println(rows + " lignes");
System.out.println(dl.count() + " solutions");
}

public static void main(String[] args) {
double start = System.currentTimeMillis();
new ScottDLX();
System.err.println((System.currentTimeMillis() - start)/1000 + " s");
}

}
```