Solve and create 3x3 "scramble squares" puzzles using java.

ScrambleSqures.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

// create and solve 3x3 scramble square puzzles.
// tiles are squares, are arranged in 3x3 grid.
// each tile has 4 pictures, one per side.
// Each picture is either a "head" or "tail" (bottom or top half of picture)
// There are typically 4 pictures, represented by AaBbCcDd
// Each picture is represented by an upper and lower case letter.
// Goal is to match all pictures in all tiles that adjoin other tiles.
// Author Brad Lowe
public class ScrambleSqures {
    final static int DIM = 3;       // N by N puzzle. Only 3x3 supported.
    final static int MAX_TILES = DIM * DIM;

    enum Position {
        top, right, bottom, left
    }

    class Solver {
        boolean unsolved = true;
        Solver(Board input) {
            this.input = input;
        }

        final Board input;
        private final ArrayList<Board> solutions = new ArrayList<>();

        void addSolution(Board b) {
            solutions.add(new Board(b));
            System.out.println("Solved:");
            System.out.println(b.fullString());
        }

        List<Board> getSolutions() {
            return solutions;
        }

        public String toString() {
            String out = input.fullString();
            if (!unsolved) {
                out += "\ncontains " + getSolutions().size() + " solutions.";
                if (getSolutions().size() > 0) {
                    out += "\nSolution 1:\n" + getSolutions().get(0).fullString();
                }
            }
            return out;
        }

        public void solve() {
            solveRecursively(new Board());
            unsolved = false;
        }

        int firstFreeSpace(Board b) {
            for (int x = 0; x < b.tiles.length; x++)
                if (b.tiles[x] == null)
                    return x;
            return -1;
        }

        protected void solveRecursively(Board b) {
            final int pos = firstFreeSpace(b);
            assert (pos != -1);

            for (final Tile t : input.tiles) {
                if (b.contains(t))
                    continue;
                for (int r = 0; r < 4; r++) {
                    Tile rt = t.rotate(r);
                    if (checkPiece(b, rt, pos)) {
                        b.put(rt, pos);
                        int size = b.getSize();
                        if (size == MAX_TILES) {
                            addSolution(b);
                        } else {

                            solveRecursively(b);
                        }

                        assert (b.contains(rt));
                        Tile removed = b.clear(pos);
                        assert (removed.exactMatch(rt));
                    }
                }
            }
        }
    }


    class Tile {
        final String pieces;
        public final int index;

        Tile(String s, int index) {
            pieces = s;
            this.index = index;
            assert (s.length() == 4);
            assert (this.index >= 0 && this.index < MAX_TILES);
        }


        public Tile(Tile tile) {
            this(tile.pieces, tile.index);
        }

        public String toString() {
            return pieces;
        }

        Character get(Position p) {
            return pieces.charAt(p.ordinal());
        }

        Tile rotate(int i) {
            assert (i >= 0 && i <= 4);
            String s = "";
            for (int x = 0; x < 4; x++)
                s += pieces.charAt((x + i) % 4);
            Tile t = new Tile(s, index);
            return t;
        }

        Character top() {
            return get(Position.top);
        }

        Character bottom() {
            return get(Position.bottom);
        }

        Character left() {
            return get(Position.left);
        }

        Character right() {
            return get(Position.right);
        }

        public boolean equals(Object o) {
            assert (false);
            return ((Tile) o).index == this.index;
        }

        public boolean indexEquals(Object o) {
            return ((Tile) o).index == this.index;
        }

        public boolean exactMatch(Object o) {
            return ((Tile) o).pieces.equals(this.pieces);
        }
    }


    // return a puzzle to solve.
    // these are created by entering the squares, 4 pictures at a time in top,right,bottom,left order.
    // Assign each picture a letter (A-Z) and each picture a "top" or "bottom" (alternately left/right)
    // Top halves are Captial, Bottom halves are lower case, although it doesn't matter as long as you
    // are consistent.
    private Board init() {


        String puzzle[] = {"dwGf", "fdgW", "dwgW", "FfDW", "gwFD", "FgGd", "fWgd", "GDFw", "FdgW"};


        Board b = new Board(puzzle);
        // Board b = new Board("BacdbDCDCdBbbAcacdBaCbADAabdcDBabAcD");
        // Board b = new Board("bAcDcDBaAabdCdBbbDCDBacdbAcacdBaCbaD");

        return b;
    }


    public boolean isSolved(final Board b) {
        return isSolved(b, false).isEmpty();
    }

    public String isSolved(final Board b, boolean partial) {
        if (b == null)
            return "null board";

        for (int x = 0; x < MAX_TILES; x++) {
            Tile t = b.tiles[x];
            if (t == null) {
                if (!partial)
                    return "tile " + x + " null";

            } else {
                if (!checkPiece(b, t, x))
                    return "tile " + x + " failed";
            }
        }

        return "";
    }

    private Solver solve(final Board input) throws Exception {

        Solver s = new Solver(input);
        s.solve();
        return s;
    }

    class Board {
        private Tile tiles[] = new Tile[MAX_TILES];
        private boolean inUse[] = new boolean[MAX_TILES];
        private int size = 0; // number of tiles placed

        public Board() {
        }

        public Board(String[] tiles) {
            for (String s : tiles)
                put(new Tile(s, size), size);
        }

        public Board(String s) {
            String t = "";
            for (char c : s.toCharArray()) {
                if (!Character.isAlphabetic(c)) continue;
                t += c;
                if (t.length() == 4) {
                    put(new Tile(t, size), size);
                    t = "";
                }
            }

        }

        public Board(Board b) {
            for (int x = 0; x < tiles.length; x++) {
                this.tiles[x] = b.tiles[x] != null ? new Tile(b.tiles[x]) : null;
                this.inUse[x] = b.inUse[x];
            }
            this.size = b.size;
        }

        public Tile rotate(int pos, int amt) {
            this.tiles[pos] = this.tiles[pos].rotate(amt);
            return this.tiles[pos];
        }

        public String toString() {
            String out = "";
            for (int x = 0; x < tiles.length; x++) {
                Tile t = tiles[x];
                if (t == null)
                    out += "---";
                else
                    out += t.toString();
                if (x == 2 || x == 5)
                    out += "\n";
            }

            return out;
        }

        public String indexes() {
            String out = "";
            for (int x = 0; x < tiles.length; x++) {
                Tile t = tiles[x];
                if (t == null)
                    out += "-";
                else
                    out += t.index;
            }

            return out;
        }

        public String compact() {
            String out = "";
            for (Tile s : tiles)
                out += (s != null ? s.toString() : "----") + " ";
            return out.trim();
        }

        public String idxr() {
            String out = "";
            for (Tile s : tiles)
                out += (s != null ? ("" + s.index + "" + s.pieces.charAt(0)) : "--") + " ";
            return out.trim();
        }

        public String fullString() {
            String out = "";
            for (int y = 0; y < 3; y++) {
                for (int z = 0; z < 3; z++) {
                    for (int x = 0; x < 3; x++) {
                        Tile t = get(x, y);
                        String p = ".-.";
                        if (t != null) {
                            String indx = "" + t.index;
                            switch (z) {
                                case 0:
                                    p = " " + t.top() + " ";
                                    break;
                                case 1:
                                    p = (t.left() + indx + t.right());
                                    break;
                                case 2:
                                    p = " " + t.bottom() + " ";
                                    break;
                                default:
                                    assert (false);

                            }
                        }
                        out += p;
                    }
                    out += "\n";
                }
            }
            out += indexes();
            return out;
        }


        public Tile get(int x, int y) {
            if (x < 0 || x >= DIM)
                return null;
            if (y < 0 || y >= DIM)
                return null;
            return tiles[y * 3 + x];
        }

        boolean put(Tile t, int index) {
            assert (tiles[index] == null);
            assert (!contains(t));
            inUse[t.index] = true;
            tiles[index] = t;
            size++;
            assert (size <= MAX_TILES);
            return true;
        }


        public boolean contains(Tile t) {
            assert (t != null);
            if (t == null)
                return false;
            boolean result = inUse[t.index];
            return result;
        }

        public void clear() {
            for (int x = 0; x < tiles.length; x++)
                clear(x);
        }

        public Tile clear(int pos) {
            Tile t = tiles[pos];

            if (t != null) {
                assert (contains(t));
                assert (inUse[t.index]);
                inUse[t.index] = false;
                size--;
                assert (size >= 0);
                tiles[pos] = null;
                assert (!inUse[t.index]);
            }

            return t;
        }

        public Tile get(int pos) {
            if (pos < 0 || pos >= tiles.length)
                return null;
            return tiles[pos];
        }

        public int getSize() {
            return size;
        }
    }


    // see if two pieces match.
    // they match if they are the same letter but different case.
    // eg. a matches A and A matches a.
    public static boolean match(Character p1, Character p2) {
        if (p1 == null || p2 == null)
            return true;
        int delta = p1.charValue() - p2.charValue();
        if (delta == 32 || delta == -32)
            return true;
        return false;
    }


    static boolean validPos(int i) {
        return i >= 0 && i < MAX_TILES;
    }

    static int getX(int pos) {
        assert (validPos(pos));
        return pos % DIM;
    }

    static int getY(int pos) {
        assert (validPos(pos));
        return pos / DIM;
    }


    // return true if tile can p can go on board a position pos.
    static boolean checkPiece(Board board, Tile tile, int pos) {

        int x = getX(pos);
        int y = getY(pos);

        Tile toLeft = board.get(x - 1, y);
        Tile toRight = board.get(x + 1, y);
        Tile onTop = board.get(x, y - 1);
        Tile below = board.get(x, y + 1);

        if (toLeft != null && !match(toLeft.right(), tile.left()))
            return false;
        if (toRight != null && !match(toRight.left(), tile.right()))
            return false;
        if (onTop != null && !match(onTop.bottom(), tile.top()))
            return false;
        if (below != null && !match(below.top(), tile.bottom()))
            return false;
        return true;
    }

    // some unit tests.
    public void tests() {
        assert (match('p', 'P'));
        assert (match('P', 'p'));
        assert (!match('P', 'P'));
        assert (!match('x', 'P'));
        assert (match(null, 'p'));
        assert (match('x', null));
        assert (inverse('x') == 'X');
        assert (inverse('Y') == 'y');

        Tile t = new Tile("ABCD", 0);
        assert (t.top() == 'A');
        assert (t.right() == 'B');
        assert (t.bottom() == 'C');
        assert (t.left() == 'D');
        Tile r[] = new Tile[4];
        for (int x = 0; x < 4; x++) r[x] = t.rotate(x);
        assert (r[0].pieces.equals("ABCD"));
        assert (r[1].pieces.equals("BCDA"));
        assert (r[2].pieces.equals("CDAB"));
        assert (r[3].pieces.equals("DABC"));
        assert (r[1].top() == 'B');
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {

            ScrambleSqures z = new ScrambleSqures();
            z.tests();

            if (true) {
                Board test = z.init();

                Solver result = z.solve(test);
                System.out.println(result);


                if (true) return;

                System.out.println("test:\n" + test.fullString());
                for (; ; ) {
                    z.shuffle(test, true);
                    Solver s = z.solve(test);
                    if (s != null) {
                        System.out.println("solu:\n" + s);
                        break;
                    }

                }


            }


        } catch (Throwable th) {
            th.printStackTrace();
        }
    }

    private static char inverse(char c) {
        if (Character.isLowerCase(c)) return Character.toUpperCase(c);
        if (Character.isUpperCase(c)) return Character.toLowerCase(c);
        assert (false);
        return c;
    }

    private char random() {
        int p = (int) (Math.random() * 4);
        p += 'a';

        Character c = new Character((char) p);
        p = (int) (Math.random() * 2);

        if (p == 1)
            c = Character.toUpperCase(c);
        return c;
    }

    // create a random puzzle.
    public Board create() {

        Board board = new Board();

        for (int pos = 0; pos < MAX_TILES; pos++) {
            int x = getX(pos);
            int y = getY(pos);

            Tile onTop = board.get(x, y - 1);
            Tile toRight = board.get(x + 1, y);
            Tile below = board.get(x, y + 1);
            Tile toLeft = board.get(x - 1, y);
            String tile = "";
            tile += (onTop != null ? inverse(onTop.bottom()) : random());
            tile += (toRight != null ? inverse(toRight.left()) : random());
            tile += (below != null ? inverse(below.top()) : random());
            tile += (toLeft != null ? inverse(toLeft.right()) : random());
            board.put(new Tile(tile, pos), pos);
        }

        System.out.println(board.fullString());
        int solved = checkBoard(board);
        if (solved != MAX_TILES)
            throw new IllegalArgumentException("fuck");
        return board;
    }

    public Board shuffle(Board board, boolean rotate) {
        Board out = new Board();

        List<Tile> list = Arrays.asList(board.tiles);
        Collections.shuffle(list);

        for (Tile t : list) {
            int amt = rotate ? ((int) (Math.random() * 4)) : 0;
            Tile r = t.rotate(amt);
            out.put(r, out.size);
        }
        return out;
    }

    static int checkBoard(Board board) {
        for (int pos = 0; pos < MAX_TILES; pos++) {
            if (!checkPiece(board, board.get(pos), pos))
                return pos;
        }
        return MAX_TILES;
    }
}