Counting linear conflicts of the state of 8 puzzle for heuristic

Question

I need to find linear conflicts of 8 puzzle state, state is represented by int[9], goal state is {1,2,3,4,5,6,7,8,0}. A linear conflict would be if in a line two tiles that are supposed to be in that line are reversed.

For example, in goal state, the first row is 1,2,3 if in the state the first row is 2,1,3 then that is one linear conflict made by tiles 2 and 1.

My code works, but is way too long and awkward. Here it is:

public static int linearConflicts(int[] state) {
    ArrayList<Integer> row1 = new ArrayList<Integer>();
    ArrayList<Integer> row2 = new ArrayList<Integer>();
    ArrayList<Integer> row3 = new ArrayList<Integer>();
    ArrayList<Integer> column1 = new ArrayList<Integer>();
    ArrayList<Integer> column2 = new ArrayList<Integer>();
    ArrayList<Integer> column3 = new ArrayList<Integer>();
    int[] columnMarkers = new int[] { 0, 3, 6, 1, 4, 7, 2, 5, 8 };
    for (int i = 0; i < 9; i++) {
        if (i < 3) {
            row1.add(state[i]);
            column1.add(state[columnMarkers[i]]);
        } else if (i < 6) {
            row2.add(state[i]);
            column2.add(state[columnMarkers[i]]);
        } else {
            row3.add(state[i]);
            column3.add(state[columnMarkers[i]]);
        }
    }
    return row1Conflicts(row1) + row2Conflicts(row2) + row3Conflicts(row3)
            + column1Conflicts(column1) + column2Conflicts(column2)
            + column3Conflicts(column3);

}

public static int row1Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(1)) {
        if ((rowState.contains(2))
                && rowState.indexOf(1) > rowState.indexOf(2)) {
            conflicts++;
        }
        if ((rowState.contains(3))
                && rowState.indexOf(1) > rowState.indexOf(3)) {
            conflicts++;
        }

    }
    if (rowState.contains(2) && rowState.contains(3)
            && rowState.indexOf(2) > rowState.indexOf(3))
        conflicts++;
    return conflicts;
}

public static int row2Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(4)) {
        if ((rowState.contains(5))
                && rowState.indexOf(4) > rowState.indexOf(5)) {
            conflicts++;
        }
        if ((rowState.contains(6))
                && rowState.indexOf(4) > rowState.indexOf(6)) {
            conflicts++;
        }

    }
    if (rowState.contains(5) && rowState.contains(6)
            && rowState.indexOf(5) > rowState.indexOf(6))
        conflicts++;
    return conflicts;
}

public static int row3Conflicts(ArrayList<Integer> rowState) {
    int conflicts = 0;
    if (rowState.contains(7) && rowState.contains(8)
            && rowState.indexOf(7) > rowState.indexOf(8))
        conflicts++;
    return conflicts;
}

public static int column1Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(1)) {
        if ((columnState.contains(4))
                && columnState.indexOf(1) > columnState.indexOf(4)) {
            conflicts++;
        }
        if ((columnState.contains(7))
                && columnState.indexOf(1) > columnState.indexOf(7)) {
            conflicts++;
        }

    }
    if (columnState.contains(4) && columnState.contains(7)
            && columnState.indexOf(4) > columnState.indexOf(7))
        conflicts++;
    return conflicts;
}

public static int column2Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(2)) {
        if ((columnState.contains(5))
                && columnState.indexOf(2) > columnState.indexOf(5)) {
            conflicts++;
        }
        if ((columnState.contains(8))
                && columnState.indexOf(2) > columnState.indexOf(8)) {
            conflicts++;
        }

    }
    if (columnState.contains(5) && columnState.contains(8)
            && columnState.indexOf(5) > columnState.indexOf(8))
        conflicts++;
    return conflicts;
}

public static int column3Conflicts(ArrayList<Integer> columnState) {
    int conflicts = 0;
    if (columnState.contains(3) && columnState.contains(6)
            && columnState.indexOf(3) > columnState.indexOf(6))
        conflicts++;
    return conflicts;
}

Does anyone know how to do it shorter and less clumsy? If I keep doing methods like this, my code will be very hard to read.

Answer 1

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 as if it were in
     * its 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));
    }
}

Answer 2

I would have some tweaks how you could improve your code quality. Reading it from the top I would start adding a comment for your method linearConflict and mention that the array as the argument contains two dimensional matrix mapped into a 1D array. It is a short comment and then immediately you get the idea why the next variables are called columns and rows.

Another thing is I would avoid using i < 9 in for (i = 0; i < 9; i++). I know it is supposed to be 9 but in case it is not then you will get ArrayOutOfBound. I would say better would be to use i < state.lentgh or i < CONSTANT. The CONSTANT would be defined as static final in the class, but then I would suggest checking the length of the state array so that you know it will not be shorter - just more defensive style of programming.

The methods row1conflict, row2conflict,.... look exactly the same just the numbers inside the method are different. I would suggest have those numbers as the arguments and then you can have only one method. I would also make the numbers as constants in the class because the particular numbers does not change and then you can pass the constants in the method. This prevents you from running into a situation when you find out that you make a mistake in one method and since all the method are "the same" you have to correct it in multiple places.

So the signature could look:

public static int arrayConflicts(List<Integer> array, int number1, int number2,....)
//And then call it like this
arrayConflict(column1, NUMBER_1, NUMBER_2, NUMBER_3....)

I named the arguments number1 and number2 just for illustration but if you can come up with more descriptive name that would be better.

Another point as a type of variables use List instead of ArrayList. It gives you the freedom to change later on ArrayList for something else without refactoring all the types of the variables.