c - 在固定大小的矩阵表示中计算数独单元的邻居的最佳方法

Question

对于一项大学作业，我正在实现一个数独求解器。实现的一部分是方法neighbors，它给定一个单元格(x)计算它的邻居。也就是说，哪些单元格的域取决于 x 的值。

自然地，对于数独游戏，单元格 (x) 邻居列表是与 x 同一列、与 x 同一行以及与 x 相同的 3x3 分区中的所有单元格的并集。虽然可以使用循环轻松计算前两个子集，但我无法想出一种巧妙的方法来收集分区邻居，因为根据单元在分区中的位置，存在 9 种不同的非重叠场景。

也许将值存储在集合或动态列表中并在之后进行重复数据删除可能是更好的解决方案，但我正在使用 C 编程语言，并且希望继续使用 libc 库。我在其他地方也不需要上述数据结构，因此我对实现它们犹豫不决。

下面是我的实现。

/*
 * neighbours
 * Auxiliary function to populate array with neighbour indices for cell (x) specified by index (idx).
 * That is, populate the array with indices of the cells such that constraints on their domain depend on value of x.
 * This function is only declared to increase level of abstraction and simplify coding.
 * It also doesn't generalize for different board sizes as it assumes all cells have 20 neighbours.
 * It is not intended to be used outside the scope of ac3, and therefore is marked auxiliary.
 *
 * @param idx   index of the cell which neighbours are to be determined
 * @param buf   a pointer to integer array with at least 20 elements (20 are populated)
 * @return      1 if successful, 0 otherwise
 */
int neighbours(int idx, int* buf);

int
neighbours(int idx, int* buf) {
    int x, y, partition_x, partition_y, cursor;

    cursor = 4;

    x = idx % BOARD_WIDTH;
    y = idx / BOARD_WIDTH;

    partition_x = x % 3;
    partition_y = y % 3;


    if (partition_x == 0 && partition_y == 0) {
        buf[0] = IDX(x+1, y+1);
        buf[1] = IDX(x+2, y+2);
        buf[2] = IDX(x+2, y+1);
        buf[3] = IDX(x+1, y+2);
    }

    if (partition_x == 0 && partition_y == 1) {
        buf[0] = IDX(x+1, y-1);
        buf[1] = IDX(x+2, y+2);
        buf[2] = IDX(x+2, y-1);
        buf[3] = IDX(x+1, y+2);
    }

    if (partition_x == 0 && partition_y == 2) {
        buf[0] = IDX(x+1, y-1);
        buf[1] = IDX(x+2, y-2);
        buf[2] = IDX(x+2, y-1);
        buf[3] = IDX(x+1, y-2);
    }

    if (partition_x == 1 && partition_y == 0) {
        buf[0] = IDX(x-1, y+1);
        buf[1] = IDX(x+1, y+2);
        buf[2] = IDX(x+1, y+1);
        buf[3] = IDX(x-1, y+2);
    }

    if (partition_x == 1 && partition_y == 1) {
        buf[0] = IDX(x-1, y-1);
        buf[1] = IDX(x+1, y+2);
        buf[2] = IDX(x+1, y-1);
        buf[3] = IDX(x-1, y+2);
    }

    if (partition_x == 1 && partition_y == 2) {
        buf[0] = IDX(x-1, y-1);
        buf[1] = IDX(x+1, y-2);
        buf[2] = IDX(x+1, y-1);
        buf[3] = IDX(x-1, y-2);
    }

    if (partition_x == 2 && partition_y == 0) {
        buf[0] = IDX(x-1, y+1);
        buf[1] = IDX(x-2, y+2);
        buf[2] = IDX(x-2, y+1);
        buf[3] = IDX(x-1, y+2);
    }

    if (partition_x == 2 && partition_y == 1) {
        buf[0] = IDX(x-1, y-1);
        buf[1] = IDX(x-2, y+2);
        buf[2] = IDX(x-2, y-1);
        buf[3] = IDX(x-1, y+2);
    }

    if (partition_x == 2 && partition_y == 2) {
        buf[0] = IDX(x-1, y-1);
        buf[1] = IDX(x-2, y-2);
        buf[2] = IDX(x-2, y-1);
        buf[3] = IDX(x-1, y-2);
    }


    for (int nx = 0; nx < BOARD_WIDTH; nx++) {
        if (nx == x)
            continue;
        buf[cursor] = IDX(nx, y);
        cursor++;
    }

    for (int ny = 0; ny < BOARD_WIDTH; ny++) {
        if (ny == y)
            continue;
        buf[cursor] = IDX(x, ny);
        cursor++;
    }



    return 1;
}

我正在努力干净地实现该方法，

Answer 1

包含单元格 (y, x) 的 block 位于

int basecol = (x / 3) * 3;
int baserow = (y / 3) * 3;

然后您可以执行一对简单的嵌套循环

for(int j = baserow; j < baserow + 3; j++) {
    for(int i = basecol; i<basecol + 3; i++) {
        if(j == y && i == x)
            printf(" self  ");
        else
            printf("(%d, %d) ", j, i);
    }
    printf("\n");
}