Return to Revisions

The key is to generalize like mad!

• Force your code to deal with any square puzzle.
• Strive to reuse the same code for rows and columns.

Additional tips:

• Make it object-oriented to reduce parameter-passing clutter.
• Use 0-based indexing for row and column numbers.
• Avoid ArrayList — your lists aren't going to grow. Arrays have tidier syntax and better performance.

// Use Arrays.binarySearch() like ArrayList.indexOf()
import static java.util.Arrays.binarySearch;

public class Puzzle {
    public static enum Axis { ROW, COL };

    private int[] state;
    private int side;

    public Puzzle(int[] state) {
        this.state = state;
        this.side = (int)Math.sqrt(state.length);
        if (side * side != state.length) {
            throw new IllegalArgumentException("Puzzle must be square");
        }
    }

    /**
     * Returns the squares of the puzzle for a specified row or column.
     *
     * @param rc row or col number (0-based)
     */
    private int[] tuple(Axis dir, int rc) {
        int[] result = new int[this.side];
        switch (dir) {
          case ROW:
            System.arraycopy(this.state, rc * this.side, result, 0, this.side);
            break;
          case COL:
            for (int i = 0, j = rc; i < this.side; i++, j += this.side) {
                result[i] = this.state[j];
            }
            break;
        }
        return result;
    }

    /**
     * Returns the squares of the puzzle of this size it it solved state
     * for a specified row or column.
     *
     * @param rc row or col number (0-based)
     */
    private int[] idealTuple(Axis dir, int rc) {
        int[] result = new int[this.side];
        switch (dir) {
          case ROW:
            for (int i = 0, j = rc * this.side + 1; i < this.side; i++, j++) {
                result[i] = (j < this.state.length) ? j : 0;
            }
            break;
          case COL:
            for (int i = 0, j = this.side + rc + 1; i < this.side; i++, j += this.side) {
                result[i] = (j < this.state.length) ? j : 0;
            }
            break;
        }
        return result;
    }

    /**
     * Count inversions (linear conflicts) for a row or column.
     */
    public int inversions(Axis dir, int rc) {
        int[] have = this.tuple(dir, rc);
        int[] want = this.idealTuple(dir, rc);
        int inversions = 0;

        // For each pair of squares, if both numbers are supposed to be in this
        // tuple, and neither is 0 (blank)...
        for (int i = 1, iPos; i < this.side; i++) {
            if (have[i] != 0 && 0 <= (iPos = binarySearch(want, have[i]))) {
                for (int j = 0, jPos; j < i; j++) {
                    if (have[j] != 0 && 0 <= (jPos = binarySearch(want, have[j]))) {
                        // ... and are inverted, count it as a conflict.
                        if ((have[i] < have[j]) != (i < j)) {
                            inversions++;
                        }
                    }
                }
            }
        }
        return inversions;
    }

    public static void main(String[] args) {
        Puzzle p = new Puzzle(new int[] {
            3, 2, 1,
            4, 7, 5,
            8, 6, 0
        });
        System.out.printf("Row %d inversions = %d\n", 0, p.inversions(Axis.ROW, 0));
        System.out.printf("Row %d inversions = %d\n", 1, p.inversions(Axis.ROW, 1));
        System.out.printf("Row %d inversions = %d\n", 2, p.inversions(Axis.ROW, 2));
        System.out.printf("Col %d inversions = %d\n", 0, p.inversions(Axis.COL, 0));
        System.out.printf("Col %d inversions = %d\n", 1, p.inversions(Axis.COL, 1));
        System.out.printf("Col %d inversions = %d\n", 2, p.inversions(Axis.COL, 2));
    }
}