java recursion on array

I have to create a program that finds all the possible ways of filling a square of size x by y. You place a block which takes up 2 spaces to completely fill.

The problem is I don't know how to code it to the point where you can remember the placements of each square. I can get it to where it fills the board completely once and maybe twice, but nothing past that. I also know that I'm supposed to use recursion to figure this out . Here is the code I started on so far. There is also a main method and I have the initial even/odd check working fine. This is the part I have no idea on.

    public void recurDomino(int row, int column) {
            if (Board[2][x - 1] != false) {

            } else if(Board[1][x-1]!=false)
            {

            }
      开发者_如何学Go      else {
                for (int n=0; n < x - 1; n++) {
                    Board[row][column] = true;
                    Board[row][column+1] = true;
                    column++;
                    counter++;
                } 
                recurDomino(1, 0);
                recurDomino(2, 0);

            }
        }

Thank you for any help you guys can give me. 


******************* EDIT ****************************************

I am a little confused still. I came up with this algorithm but I always get 2 for any value greater or equal to 2.

public boolean tryHorizontal(int row , int col){
        if( row < 0 || row >= array[0].length-1)
            return false;
        else
            return true;
    }

    public boolean tryVertical(int row, int col){
        if( col < 0 || col >= 2 )
            return false;
        else
            return true;
    }

    public boolean tryRowCol(int row, int col){
        if(this.tryHorizontal(row, col) && this.tryVertical(row, col)){
            return true;
        }
        else
            return false;
    }

    public int findWays(int row, int col){
        int n = 0;
        if( !this.tryRowCol(row, col))
            return 0;
        else
            n =+ 1 + this.findWays(row+1, col+1);

        return n;
    }

---

This recursive solution actually generates all the possible tiling of a general MxN board. It's more general than what your program requires, and therefore not optimized to just count the number of tiling of a 3xN board.

If you just want to count how many there are, you can use dynamic programming techniques and do this much faster. Also, having the number of rows fixed at 3 actually makes the problem considerably easier. Nonetheless, this general generative solution should be instructive.

public class Domino {
    final int N;
    final int M;
    final char[][] board;
    int count;

    static final char EMPTY = 0;

    Domino(int M, int N) {
        this.M = M;
        this.N = N;
        board = new char[M][N]; // all EMPTY
        this.count = 0;
        generate(0, 0);
        System.out.println(count);
    }

    void printBoard() {
        String result = "";
        for (char[] row : board) {
            result += new String(row) + "\n";
        }
        System.out.println(result);     
    }

    void generate(int r, int c) {
       //... see next code block
    }
    public static void main(String[] args) {
        new Domino(6, 6);
    }
}

So here's the meat and potatoes:

    void generate(int r, int c) {
        // find next empty spot in column-major order
        while (c < N && board[r][c] != EMPTY) {
            if (++r == M) {
                r = 0;
                c++;
            }
        }
        if (c == N) { // we're done!
            count++;
            printBoard();
            return;
        }
        if (c < N - 1) {
            board[r][c] = '<';
            board[r][c+1] = '>';
            generate(r, c);
            board[r][c] = EMPTY;
            board[r][c+1] = EMPTY;
        }
        if (r < M - 1 && board[r+1][c] == EMPTY) {
            board[r][c] = 'A';
            board[r+1][c] = 'V';
            generate(r, c);
            board[r][c] = EMPTY;
            board[r+1][c] = EMPTY;
        }
    }

This excerpt from the last few lines of the output gives an example of a generated board, and the final count.

//... omitted

AA<><>
VVAA<>
AAVV<>
VVAA<>
<>VVAA
<><>VV

//... omitted

6728

Note that 6728 checks out with OEIS A004003.

A few things that you need to learn from this solutions are:

• Clean-up after yourself! This is a very common pattern in recursive solution that modifies a mutable shared data. Feel free to do your thing, but then leave things as you found them, so others can do their thing.
• Figure out a systematic way to explore the search space. In this case, dominoes are placed in column-major order, with its top-left corner as the reference point.

So hopefully you can learn something from this and adapt the techniques for your homework. Good luck!

---

Tip: if you comment out the printBoard line, you can generate all ~13 million boards for 8x8 in reasonable time. It'll definitely be much faster to just compute the number without having to generate and count them one by one, though.

---

Update!

Here's a recursive generator for 3xN boards. It doesn't use a shared mutable array, it just uses immutable strings instead. It makes the logic simpler (no clean up since you didn't make a mess!) and the code more readable (where and how the pieces are placed is visible!).

Since we're fixed at 3 rows, the logic is more explicit if we just have 3 mutually recursive functions.

public class Domino3xN {
   static int count = 0;

   public static void main(String[] args) {
      addRow1(8, "", "", "");
      System.out.println(count);
   }

   static void addRow1(int N, String row1, String row2, String row3) {
      if (row1.length() == N && row2.length() == N && row3.length() == N) {
         count++; // found one!
         System.out.format("%s%n%s%n%s%n%n", row1, row2, row3);
         return;
      }
      if (row1.length() > row2.length()) { // not my turn!
         addRow2(N, row1, row2, row3);
         return;
      }
      if (row1.length() < N - 1)
         addRow2(N, row1 + "<>",
                    row2,
                    row3);
      if (row2.length() == row1.length())
         addRow3(N, row1 + "A",
                    row2 + "V",
                    row3);
   }
   static void addRow2(int N, String row1, String row2, String row3) {
      if (row2.length() > row3.length()) { // not my turn!
         addRow3(N, row1, row2, row3);
         return;
      }
      if (row2.length() < N - 1)
         addRow3(N, row1,
                    row2 + "<>",
                    row3);
      if (row3.length() == row2.length())
         addRow1(N, row1,
                    row2 + "A",
                    row3 + "V");
   }
   static void addRow3(int N, String row1, String row2, String row3) {
      if (row3.length() == row2.length()) { // not my turn!
         addRow1(N, row1, row2, row3);
         return;
      }
      if (row3.length() < N - 1)
         addRow1(N, row1,
                    row2,
                    row3 + "<>");
   }
}

You don't often see 3 mutually recursive functions like this, so this should be educational.

---

One way of doing it is with the CSP (Constraint Satisfaction Problem) approach:

Consider every cell in the grid to be a variable, with 4 possible values (indicating the part of the domino it takes). Some assignments are obviously illegal. Legal assignments assign values to a "neighboring variable" as well. Your goal is to assign all the 3xN variables with legal values.

The recursion here can help you cover the state space easily. On each invocation, you try to assign a value to the next unasigned cell, by trying all the 4 options. After each successfull assignment, you can call the same method recursively, and then undo your last assignment (this way you don't have to clone anything - one copy of the grid data is enough).

--EDIT-- If you want to do it efficiently so that it works for large values on N in reasonable time, you will also have to think about optimizations, in order to discard some assignment attempts.

---

Here are some hints:

With a fixed-size board you can precompute the exact number of steps that each solution takes, so the termination criterion is trivial: you just check the nesting level.

Starting from one corner is a good idea, because it means that you can always find a field that can only be covered in two different ways (vertically or horizontally).

That means that you have a branching factor of only 2, and a recursion depth of 3*N/2, which is probably small enough that you can just clone the sstate of the board for each call (ordinarily you would construct new states incrementally from existing states to save space, but that is a bit harder to program).

In many states here will be more than one field that allows only two possibilities; with a clever strategy for choosing the next field, you can ensure that you will never find the same solution via two different paths, so you don't even have to check the solutions for duplicates.

The state of the board must record which fields are free and which fields are occupied, but also which fields are occupied by the same domino, so an array of int could do the trick.