数组上的java递归

Question

我必须创建一个程序来找到用 y 填充大小为 x 的正方形的所有可能方法。您放置一个占用 2 个空间的方 block 以完全填满。

问题是我不知道如何将它编码到可以记住每个方 block 的位置的程度。我可以让它完全填满整个板一次，也许两次，但仅此而已。我也知道我应该使用递归来解决这个问题。到目前为止，这是我开始使用的代码。还有一个主要方法，我的初始偶数/奇数检查工作正常。这是我不知道的部分。

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

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

            }
            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 ****************************************

我还是有点懵。我想出了这个算法，但对于大于或等于 2 的任何值，我总是得到 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;
    }

Answer 1

这个递归解决方案实际上生成一般MxN板的所有可能平铺。它比您的程序需要的更通用，因此没有优化为仅计算 3xN 板的平铺数量。

如果你只是想数有多少，你可以使用dynamic programming techniques并且更快。此外，将行数固定为 3 实际上可以使问题变得容易。尽管如此，这种通用的生成解决方案应该具有指导意义。

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);
    }
}

所以这是肉和土 bean :

    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;
        }
    }

输出最后几行的摘录给出了生成的棋盘示例和最终计数。

//... omitted

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

//... omitted

6728

请注意，6728 使用 OEIS A004003 checkout .

您需要从这个解决方案中学到的一些东西是:

• 自行清理!这是修改可变共享数据的递归解决方案中非常常见的模式。随意做您的事情，但是留下您发现的东西，以便其他人可以做他们的事情。
• 想出一种探索搜索空间的系统方法。在这种情况下，多米诺骨牌被放置在 column-major order 中。 , 以左上角为引用点。

因此，希望您能从中学到一些东西，并根据您的作业调整这些技巧。祝你好运!

---

提示:如果您注释掉 printBoard 行，您可以在合理的时间内为 8x8 生成所有约 1300 万 block 板。不过，只计算数字而不必一一生成和计数肯定会快得多。

---

更新!

这是一个用于 3xN 板的递归生成器。它不使用共享可变数组，而是使用不可变字符串。它使逻辑更简单(无需清理，因为您没有弄得一团糟!)并且代码更具可读性(片段的放置位置和方式可见!)。

因为我们固定在 3 行，所以如果我们只有 3 个相互递归的函数，逻辑会更明确。

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 + "<>");
   }
}

你不会经常看到像这样的 3 个相互递归的函数，所以这应该是有教育意义的。