Java domino tiling with recursion: second if block gets called with already updated values

Question

A rectangular grid m x n, should be filled with m*n/2 2x1 dominoes that can be placed horizontally or vertically. How many possible soluitons exist?

I'm trying to solve this problem with recursion (yes I know that this can easily be calculated with fibonacci).

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);
    placeHorizontally(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);
    placeVertically(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
}
private static void decideNextMove(int row, int col, int[][] rectangle) {
  if (rectangleIsFilled(rectangle)) {
    count = count.add(BigInteger.ONE);
  }
  else if(row == rectangle.length -1) {
    place(0, col+1, rectangle);
  }
  else{
    place(row+1, col, rectangle);
  }
}
private static BigInteger calculate(int m, int n) {
  int[][] rectangle = new int[m][n];
  place(0, 0, rectangle);
  return count;
}

The deepCopy() method just recreates the 2-dimensional array by iterating over the array and using Arrays.copyOf().

If I call calculate(2,2) it works correctly first by adding a dominio horizontally and changing the rectangle to [[1,1][0,0]]. It then goes to the next row in the same column (row=1, col=0) and places again a horizontal domino so the rectangle looks like [[1,1][1,1]]. It detects that the rectangle is filled and adds 1 to the count. It then continues by checking if a vertical domino can be placed at (row=1, col=0) with the allready filled array which obviously wont work. Then it falls back and checks if a vertical domino can be placed at (row=0, col=0) with the previous array [[1,1][0,0]] which also doesnt work. It then finishes.

What is confusing me is that the canBePlacedVertically if block in the place method gets called with the "new" parameters. In the example I expected it to call the method first with the [[1,1][0,0]] array and then with the [[0,0][0,0]] array. Can anyone see where my problem is? I'm guessing it has to do with the place where the array gets duplicated, but I'm not sure...

Thank you for your help

Here are the remaining methods If someone want's to try it for themselves:

  private static boolean rectangleIsFilled(int[][] rectangle) {
    for(int i = 0; i < rectangle.length; i++) {
      if(IntStream.of(rectangle[i]).sum() < rectangle[i].length) {
        return false;
      }
    }
    return true;
  }

  private static boolean canBePlacedHorizontally(int row, int col, int[][] rectangle) {
    // checks if given field is empty and not on the very right and that the field next to it is empty
    return col < rectangle[0].length -1 && rectangle[row][col] == 0 && rectangle[row][col+1] == 0;
  }

  private static boolean canBePlacedVertically(int row, int col, int[][] rectangle) {
    // checks if given field is empty and not on the bottom and that the field below it is empty
    return row < rectangle.length -1 && rectangle[row][col] == 0 && rectangle[row+1][col] == 0;
  }

  private static void placeHorizontally(int row, int col, int[][] rectangle) {
    rectangle[row][col] = 1;
    rectangle[row][col+1] = 1;
  }

  private static void placeVertically(int row, int col, int[][] rectangle) {
    rectangle[row][col] = 1;
    rectangle[row+1][col] = 1;
  }

  // https://stackoverflow.com/a/1564856
  private static int[][] deepCopy(int[][] original) {
    final int[][] result = new int[original.length][];
    for (int i = 0; i < original.length; i++) {
      result[i] = Arrays.copyOf(original[i], original[i].length);
    }
    return result;
  }
}

Did you try debugging into the method with your problematic inputs? You should be able to step through and figure out where your logic flaw is. — Roddy of the Frozen Peas, Sep 17 '18 at 20:23
yeah I tried that and with that I saw that the second if block uses the already updated values. But I don't get why — loelu, Sep 17 '18 at 20:25

score 2 · Accepted Answer · answered Sep 17 '18 at 20:33

Your problem is this method:

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    rectangle = deepCopy(rectangle);                  // A
    placeHorizontally(row, col, rectangle);           // B
    decideNextMove(row, col, rectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {   // C
    rectangle = deepCopy(rectangle);
    placeVertically(row, col, rectangle);
    decideNextMove(row, col, rectangle);
  }
}

While you correctly make a copy of the original rectangle in line A, you overwrite the reference to the original rectangle, thereby losing access to the original rectangle.

In line B you modify the copy of your rectangle.

In line C you work with the modified copy instead of the original rectangle.

To correct your code, you must not overwrite the reference to the original rectangle. That means that within the if statements you need a separate reference to the cloned rectangle:

private static void place(int row, int col, int[][] rectangle) {
  if (canBePlacedHorizontally(row, col, rectangle)) {
    int[][] testrectangle = deepCopy(rectangle);      // A
    placeHorizontally(row, col, testrectangle);       // B
    decideNextMove(row, col, testrectangle);
  }
  if (canBePlacedVertically(row, col, rectangle)) {   // C
    int[][] testrectangle = deepCopy(rectangle);
    placeVertically(row, col, testrectangle);
    decideNextMove(row, col, testrectangle);
  }
}

Java domino tiling with recursion: second if block gets called with already updated values

1 Answers1