在C语言中实现分治三格图算法

Question

这是经典的分治算法问题。我们有一个大小为2^n * 2^n的棋盘，想要用L形方块填满它。我们知道棋盘上有一个方块不能被覆盖。这个问题也被称为三格图案问题（有点类似）。

问题

我的解决方案适用于n = 1和n = 2。但是当我想进一步推广解决方案（n > 2）时，我无法填满所有方块，其中一些包含错误的L形方块部分。

程序结构

输入

用户输入n和棋盘上缺失方块t的位置。

输出

我们打印填有“三格图案”的棋盘。我们为每个“三格图案”分配一个值。缺失的方块始终得到零值，每个“三格图案”都包含一个整数值（1、2、3……）。

解决方案

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int currBlockNum, int boardSize);

int main(void) {
    int n, m;

    do {
        printf("Give n > 0: ");
        scanf("%d", &n);
    } while (n <= 0);

    m = pow(2, n);

    int A[m][m];

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            A[i][j] = -1;
        }
    }

    int t_row, t_col;

    do {
        printf("Give missing square row coordinate: ");
        scanf("%d", &t_row);
        printf("Give missing square column coordinate: ");
        scanf("%d", &t_col);
    } while (t_row >= m || t_col >= m);

    A[t_row][t_col] = 0;

    recursiveSolve(m, A, 0, 0, t_row, t_col, 1, m);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
                printf("%2d ", A[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
    if (boardSize == 2) { // fill with L shaped block the area that is blank (no block exist).

        // check first which part of our board if filled up with  a block
        // and then paint the other.
        if (A[A_row][A_col] != -1) { // block exist at the top-left corner
            A[A_row+1][A_col]  = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner
            A[A_row][A_col+1] = currBlockNum; // paint the top-right corner

        } else if (A[A_row][A_col+1] != -1) { // block exist at the top-right corner
            A[A_row][A_col] = currBlockNum; // paint the top-left corner
            A[A_row+1][A_col] = currBlockNum; // paint the bottom-left corner
            A[A_row+1][A_col+1] = currBlockNum; // paint the bottom-right corner

        } else if (A[A_row+1][A_col] != -1) { // block exist at the bottom-left corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col+1] = currBlockNum;

        } else { // block exist at the bottom-right corner
            A[A_row][A_col] = currBlockNum;
            A[A_row][A_col+1] = currBlockNum;
            A[A_row+1][A_col] = currBlockNum;
        }

    } else {
        int A_halfSize = boardSize / 2;

        // the bellow calculations allow us to check which
        // sub-partition of our board includes the missing block,
        // as well as how we should paint the center L shaped block.
        int A_rowCenter = A_row + A_halfSize;
        int A_colCenter = A_col + A_halfSize;


        if (t_row < A_rowCenter) { // missing block in top half
            if (t_col < A_colCenter ) { // missing block is in top left half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            } else { // missing block is in top right half
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
            }

        } else { // missing block in bottom half
            if (t_col < A_colCenter ) { // missing block is in bottom left half
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
            } else { // missing block is in bottom right half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
            }
        }

        // solve each sub-partion recursively

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);

        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);

        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
    }
}

- user4108694

Answer 1

据我所见，策略是将L放置在3个不包含已占用方块的正方形中恰好占用一个方块的位置。

换句话说：

您将输入正方形分成4个正方形。 其中一个已经有一个占用的方块。 您放置L，以便另外3个正方形也恰好有一个占用的方块。 因此，现在您有4个正方形 - 所有正方形都恰好有一个占用的方块。 现在您可以在这四个正方形上运行函数。

现在，您可以独立处理每个正方形，因为每个正方形都恰好有一个占用的立方体。

那么，您的代码有什么问题呢？

问题在于您没有更新占用立方体的位置，而只是保持了原始位置。

    // top-right sub-partion
    recursiveSolve(m, A, A_row, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                             ^^^^^^^^^^^^
                                             May need update before calling

    // bottom-right sub-partion
    recursiveSolve(m, A, A_rowCenter, A_colCenter, t_row, t_col, ++currBlockNum, A_halfSize);
                                                    ^^^^^^^^^^^^
                                                    May need update before calling

    // bottom left sub-partition
    recursiveSolve(m, A, A_rowCenter, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                             ^^^^^^^^^^^^
                                             May need update before calling

    // top-left sub-partition
    recursiveSolve(m, A, A_row, A_col, t_row, t_col, ++currBlockNum, A_halfSize);
                                        ^^^^^^^^^^^^
                                        May need update before calling

对于其中的4个呼叫中的3个，您需要更新占用方块的位置。

有很多方法可以实现这一点。以下是一种方法：

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_col, int currBlockNum, int boardSize) {
    if (boardSize == 2) {

        // Keep your existing code unchanged here

    } else {
        int A_halfSize = boardSize / 2;

        // the bellow calculations allow us to check which
        // sub-partition of our board includes the missing block,
        // as well as how we should paint the center L shaped block.
        int A_rowCenter = A_row + A_halfSize;
        int A_colCenter = A_col + A_halfSize;

        // Calculate the position of the center cubes
        // as these will be the new occupied cub for
        // 3 of the 4 squares
        int TR_t_row = A_rowCenter - 1;
        int TR_t_col = A_colCenter;

        int BR_t_row = A_rowCenter;
        int BR_t_col = A_colCenter - 1;

        int BL_t_row = A_rowCenter - 1;
        int BL_t_col = A_colCenter;

        int TL_t_row = A_rowCenter - 1;
        int TL_t_col = A_colCenter - 1;



        if (t_row < A_rowCenter) { // missing block in top half
            if (t_col < A_colCenter ) { // missing block is in top left half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;

                TL_t_row = t_row;  // Roll back to 
                TL_t_col = t_col;  // original occupied cube

            } else { // missing block is in top right half
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter][A_colCenter] = currBlockNum;

                TR_t_row = t_row;  // Roll back
                TR_t_col = t_col;

            }

        } else { // missing block in bottom half
            if (t_col < A_colCenter ) { // missing block is in bottom left half
                A[A_rowCenter][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;

                BL_t_row = t_row;  // Roll back
                BL_t_col = t_col;

            } else { // missing block is in bottom right half
                A[A_rowCenter][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter-1] = currBlockNum;
                A[A_rowCenter-1][A_colCenter] = currBlockNum;

                BR_t_row = t_row;  // Roll back
                BR_t_col = t_col;

            }
        }

        // solve each sub-partion recursively

        // Use the 8 new variables for the recursive calls

        // top-right sub-partion
        recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, ++currBlockNum, A_halfSize);
                                             //  ^^^^^^^^^^^^^^^^^^

        // bottom-right sub-partion
        recursiveSolve(m, A, A_rowCenter, A_colCenter, BR_t_row, BR_t_col, ++currBlockNum, A_halfSize);
                                                   //  ^^^^^^^^^^^^^^^^^^

        // bottom left sub-partition
        recursiveSolve(m, A, A_rowCenter, A_col, BL_t_row, BL_t_col, ++currBlockNum, A_halfSize);
                                             //  ^^^^^^^^^^^^^^^^^^

        // top-left sub-partition
        recursiveSolve(m, A, A_row, A_col, TL_t_row, TL_t_col, ++currBlockNum, A_halfSize);
                                       //  ^^^^^^^^^^^^^^^^^^
    }
}

更新

如果您想避免将相同的数字用于多个 L，则应传递指向 currBlockNum 的指针。

更改原型 - 注意 int* currBlockNum：

void recursiveSolve(int m, int A[m][m], int A_row, int A_col, int t_row, int t_y, int* currBlockNum, int boardSize);

在主函数中执行：

int currBlockNum = 1;
recursiveSolve(m, A, 0, 0, t_row, t_col, &currBlockNum, m);
                                        ^^^
                                        Notice

在函数中更改所有你想要分配值的位置 - 例如：

A[A_row+1][A_col]  = *currBlockNum;
                    ^^^
                    Notice

每次递归调用函数时，首先要进行递增 - 如下所示：

并且每次递归调用函数时，首先要进行递增 - 如下所示：

    ++(*currBlockNum);
    recursiveSolve(m, A, A_row, A_colCenter, TR_t_row, TR_t_col, currBlockNum, A_halfSize);

- Support Ukraine

---

好的，我也这么认为，但是基于我的代码，这是否可能呢？我现在不想改变结构。 - user4108694

非常感谢。我理解了问题。我只是找不到与缺失的立方体位置相匹配的正确组合。 - user4108694

我相信我已经取得了进展。请检查我的更新。非常感谢！哦，刚看到我们想的一样！ - user4108694

请在所有四个递归函数上方添加++（* currBlockNum）; - user4108694

@GeorgeGkas - 我已经将那部分内容更加清晰明了。 - Support Ukraine