java 数组递归

Question

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

问题是我不知道如何编码才能记住每个方块的位置。我可以让它完全填满棋盘一次，也许两次，但不能超过那个。我也知道我应该使用递归来解决这个问题。这是到目前为止我开始编写的代码。还有一个主要方法，我的初始偶/奇检查工作正常。这是我不知道的部分。

    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 板的平铺数量。

如果您只想计算有多少个，可以使用动态编程技术并且执行此操作更快。此外，将行数固定为 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);
    }
}

重点是：

    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 进行检查。

您需要从此解决方案中学习的一些内容是：

• 自行清理！这是修改可变共享数据的递归解决方案中非常常见的模式。您可以随意做您的事情，但将事情保留在您发现的地方，以便其他人可以做他们的事情。
• 找出探索搜索空间的系统方法。在这种情况下，多米诺骨牌被放置在 列主顺序，以其左上角为参考点。

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

---

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

---

更新！

这是 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 个相互递归函数，因此这应该具有教育意义。

Answer 2

实现此目的的一种方法是使用 CSP（约束满足问题）方法：

将网格中的每个单元格视为一个变量，具有 4 个可能的值（指示它所占用的多米诺骨牌部分）。有些任务显然是非法的。合法赋值也会将值赋给“相邻变量”。您的目标是为所有 3xN 变量分配合法值。

这里的递归可以帮助您轻松覆盖状态空间。在每次调用时，您尝试通过尝试所有 4 个选项来为下一个未签名的单元格分配一个值。每次成功分配后，您可以递归地调用相同的方法，然后撤消上次分配（这样您就不必克隆任何内容 - 网格数据的一份副本就足够了）。

- 编辑 -
如果你想有效地完成它，以便它在合理的时间内适用于 N 上的大值，你还必须考虑优化，以便放弃一些分配尝试。

Answer 3

这里有一些提示：

使用固定大小的板，您可以预先计算每个解决方案所采取的确切步骤数，因此终止标准很简单：您只需检查嵌套级别即可。

从一个角开始是一个好主意，因为这意味着您始终可以找到只能以两种不同方式（垂直或水平）覆盖的字段。

这意味着您的分支因子仅为 2，递归深度为 3*N/2，这可能足够小，您可以为每次调用克隆板的状态（通常您会从增量构造新状态）现有状态以节省空间，但这有点难以编程）。

在许多州，不止一个字段只允许两种可能性；通过选择下一个字段的巧妙策略，您可以确保永远不会通过两条不同的路径找到相同的解决方案，因此您甚至不必检查解决方案是否重复。

棋盘的状态必须记录哪些字段是空闲的、哪些字段被占用，而且还要记录哪些字段被同一个多米诺骨牌占用，因此 int 数组可以解决这个问题。