/* Main.java */public class Main{ public static void main(String[] args) { State s = new State(2, 2); State.WinnerResult r = s.winner(); java.util.Iterator<State> i = r.steps.iterator(); while (i.hasNext()) { System.out.println(i.next()); System.out.println("===================="); } if (r.winner > 0) System.out.println("A wins by " + r.winner); else if (r.winner == 0) System.out.println("Draw"); else System.out.println("B wins by " + (-r.winner)); }}/* State.java */import java.util.*;public class State implements Cloneable{ static Map<State,State> internTable = new HashMap<State,State>(); // 2x2 edge indices: // +6+9+ // 0 1 2 // +7+A+ // 3 4 5 // +8+B+ // ie across the rows for vertical edges, then down the columns for horizontal edges int width; int height; boolean[] edges; boolean playerBsTurn; public State(int width, int height) { this.width = width; this.height = height; edges = new boolean[width * (height + 1) + (width + 1) * height]; Arrays.fill(edges, false); playerBsTurn = false; } public State(int width, int height, boolean[] edges, boolean playerBsTurn) { this.width = width; this.height = height; if (edges.length != (width * (height + 1) + (width + 1) * height)) throw new IllegalArgumentException(); this.edges = edges.clone(); this.playerBsTurn = playerBsTurn; } public int hashCode() { return Arrays.hashCode(edges) ^ (width << 24) ^ (height << 16) ^ (playerBsTurn ? 194813 : 123108653); } public boolean equals(Object o) { if (!(o instanceof State)) return false; return ((State)o).width == width && ((State)o).height == height && Arrays.equals(((State)o).edges, edges); } public State intern() { // based on String.intern() // basically so that if we reach the same State through different paths, we have the same node // and winnerCache below is useful. State s = internTable.get(this); if (s != null) return s; internTable.put(this, this); return this; } public Object clone() { try { State s = (State)super.clone(); s.winnerCache = null; s.edges = edges.clone(); return s; } catch (CloneNotSupportedException e) { return null; } } public class AddEdgeReturn { State nextState; int scoreDifference; // relative extra score for player A - ie negative for player B } public AddEdgeReturn addEdge(int n) { int x, y, a, b; AddEdgeReturn ret = new AddEdgeReturn(); ret.nextState = (State)clone(); ret.nextState.edges[n] = true; ret.nextState.playerBsTurn = !playerBsTurn; // see if this edge adds any squares if (n < (width + 1) * height) { // the edge is vertical x = n % (width + 1); y = n / (width + 1); a = (x - 1) * (height + 1) + y + (width + 1) * height; b = x * (height + 1) + y + (width + 1) * height; if (x > 0) { if (edges[n - 1] && edges[a] && edges[a + 1]) { if (playerBsTurn) ret.scoreDifference--; else ret.scoreDifference++; ret.nextState.playerBsTurn = playerBsTurn; } } if (x < width) { if (edges[n + 1] && edges[b] && edges[b + 1]) { if (playerBsTurn) ret.scoreDifference--; else ret.scoreDifference++; ret.nextState.playerBsTurn = playerBsTurn; } } } else { // the edge is horizontal y = (n - (width + 1) * height) % (height + 1); x = (n - (width + 1) * height) / (height + 1); a = x + (y - 1) * (width + 1); b = x + y * (width + 1); if (y > 0) { if (edges[n - 1] && edges[a] && edges[a + 1]) { if (playerBsTurn) ret.scoreDifference--; else ret.scoreDifference++; ret.nextState.playerBsTurn = playerBsTurn; } } if (y < height) { if (edges[n + 1] && edges[b] && edges[b + 1]) { if (playerBsTurn) ret.scoreDifference--; else ret.scoreDifference++; ret.nextState.playerBsTurn = playerBsTurn; } } } ret.nextState = ret.nextState.intern(); return ret; } public String toString() { StringBuffer s = new StringBuffer(); for (int y = 0; y <= height; y++) { for (int x = 0; x < width; x++) { s.append('\u00B7'); if (edges[x * (height + 1) + y + (width + 1) * height]) s.append('-'); else s.append(' '); } s.append("\u00B7\n"); if (y < height) { for (int x = 0; x <= width; x++) { if (edges[x + y * (width + 1)]) s.append('|'); else s.append(' '); if (x != width) s.append(' '); } s.append('\n'); } } s.append(playerBsTurn ? 'B' : 'A').append(" to move"); return s.toString(); } // >0 if this is a win for A, 0 if it's a draw, <0 if it's a win for B // on player A's turn, >0 means any subnode is a >0, 0 means any subnode is a 0 (but none are >0), <0 means all subnodes are <0 - ie return the maximum // on player B's turn, vice-versa. // only consider what score we can earn from this point onward - this way we can cull duplicates based that differ only by the score to date. // unfortunately this means we cannot stop searching when we find a guaranteed win for the player, but instead search for the highest point difference. public static class WinnerResult { int winner; LinkedList<State> steps; } private WinnerResult winnerCache = null; public WinnerResult winner() { if (winnerCache != null) return winnerCache; winnerCache = new WinnerResult(); // is this a final node? If so, we know the result is a draw already - this is the terminator for the recursion int i; for (i = 0; i < edges.length; i++) if (!edges[i]) break; if (i >= edges.length) { // neither player can get any more points winnerCache.winner = 0; winnerCache.steps = new LinkedList<State>(); winnerCache.steps.addFirst(this); return winnerCache; } // assume a loser until we can better the situation winnerCache.winner = playerBsTurn ? 9999 : -9999; for (i = 0; i < edges.length; i++) { if (edges[i]) continue; AddEdgeReturn next = addEdge(i); WinnerResult ret = next.nextState.winner(); int tmp = ret.winner + next.scoreDifference; if (playerBsTurn) { if (tmp < winnerCache.winner) { winnerCache.winner = tmp; winnerCache.steps = ret.steps; } } else { if (tmp > winnerCache.winner) { winnerCache.winner = tmp; winnerCache.steps = ret.steps; } } } winnerCache.steps = (LinkedList<State>)winnerCache.steps.clone(); winnerCache.steps.addFirst(this); return winnerCache; }}