c - 在 C 中查找组合的最有效方法

Question

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

int chessboard[8][8];
int indicator, x, i, j, b, checksum, testerint, temp, row, column;
int rescounter, resstarter;

void togglecolumn(int columnumber) {
    //
    for (j = 0; j < 8; j++) {
        //
        chessboard[j][columnumber] = toggleint(chessboard[j][columnumber]);
    }
}

void togglerow(int rownumber) {
    //
    for (j = 0; j < 8; j++) {
        //
        chessboard[rownumber][j] = toggleint(chessboard[rownumber][j]);
    }
}

void fulltoggle(int i, int j) {
    //
    togglerow(i);
    togglecolumn(j);
    chessboard[i][j] = toggleint(chessboard[i][j]);

}

int toggleint(int a) {
    //
    if (a == 0) {
        b = 1;
    }
    if (a == 1) {
        b = 0;
    }
    return b;
}

void fillchessboard() {
    x = 1;
    //
    for (i = 0; i < 8; i++) {
        x = toggleint(x);
        for (j = 0; j < 8; j++) {
            //
            chessboard[i][j] = x;
            x = toggleint(x);
        }
    }
}

void showchessboard() {
    //
    printf("------------------- \n \n");

    for (i = 0; i < 8; i++) {
        //
        for (j = 0; j < 8; j++) {
            //
            if (j == 7) {
                //if end of the row
                printf("%d \n", chessboard[i][j]);
            } else {
                //
                printf("%d  ", chessboard[i][j]);
            }
        }

    }
    printf("\n \n");
    printf("------------------- \n \n");

}

int checkboard() {
    checksum = 0;

    for (i = 0; i < 8; i++) {
        //
        for (j = 0; j < 8; j++) {
            //
            if (chessboard[i][j] == 1) {
                //
                return 1;
            }
        }
    }

    return 0;
}

void rowcolindicator(int i) {
    //
    if (i % 8 == 0) {
        column = 7;
        row = i / 8 - 1;
    } else {
        row = i / 8;
        column = i % 8 - 1;
    }
}

// for proper operation i should be chosen 0

int recurfuntion(int i, int stepcounter) {
    if (stepcounter != 0) {
        stepcounter--;
        temp = i;
        for (i = temp + 1; i < 65; i++) {
            //do row and column for 
            rowcolindicator(i);
            fulltoggle(row, column);
            recurfuntion(i, stepcounter);
        }
        if (i == 65) {
            i = temp++;
            rowcolindicator(temp);
            fulltoggle(row, column);
            stepcounter++;
        }
    } else {
        //
        temp = i;
        for (i = temp + 1; i < 65; i++) {
            //do row and column for i code and return iteration number if board turns all right
            rowcolindicator(i);
            fulltoggle(row, column);

            if (checkboard() == 0) {
                //
                showchessboard();
                return 1;
            } else {
                //
                fulltoggle(row, column);
            }
        }
        if (i == 65) {
            i = temp++;
            rowcolindicator(temp);
            fulltoggle(row, column);
            stepcounter++;
            //showchessboard();
        }
    }
}

int main(int argc, char *argv[]) {

    fillchessboard();
    showchessboard();
    indicator = checkboard();
    printf("indicator is %d \n", indicator);

    for (rescounter = 0; rescounter < 1000; rescounter++) {
        fillchessboard();
        printf("iiteration number: %d \n", rescounter);
        if (recurfuntion(0, rescounter) == 1) {
            printf("iteration number is %d so is the answer :) \n", rescounter);
        }
    }

    system("PAUSE");

    return 0;
}

我正在尝试解决这个问题:“您在计算机屏幕上有一张 8x8 的 table ，所有方 block 都颜色为白色。在每个步骤中，您将选择任何方 block ，结果所有方 block 都在同​​一行和同一列 - 包括所选方 block 本身 - 将切换其颜色(白色变为黑色，黑色变为白色)。获得标准彩色棋盘最少需要多少步？”

为此，我将棋盘分成 64 block (8x8)，并计算了这个 64 簇的所有组合从 1 到 64。(我知道答案在 1 到 64 之间)。

我的方法是从末端(棋盘)开始直到全白。所以我用 ones(black) 和 zeros(white) 填充了棋盘，并成功地在函数 fillchessboard() 中构建了棋盘。我可以完美地切换行和列，我选择的初始方 block 是打开的。

检查所有棋盘是否为白色的方法是 checkboard()。如果所有棋盘都是白色，此函数返回指示器 0，否则返回 1。我从小组合开始到大组合，并在每一步检查棋盘。所以当指标第一次返回0时，将是使棋盘全白的最小迭代次数，即为问题的答案。

到目前为止，我的代码可以正常工作，并且在 10 小时内它能够升级到第 10 次迭代。然而，它会花费越来越多的时间，所以第 11 次迭代将花费大约 10 个小时，第 12 次迭代将花费 20 个小时，依此类推......我的问题是，是否有任何方法可以使这些指令更快更有效？我等不及一个星期来解决这个问题。我很感激任何帮助。谢谢!

Answer 1

首先让我们做一些命名:

• c_{i,j} 是 i 行和 j 列相交处的单元格。
• cross_{i,j} 是集合:{ c_{r,c}/r=i or c=j }。它是i 行 union 列j 中所有单元格的交叉。它包含奇数个单元格。
• odd(cross_{i,j}) 是一个函数，如果 cross_{i,j} 和 1 中有偶数个黑色单元格，则返回 0如果有奇数个黑色单元格。

让我们考虑选择单元格 c_{i,j} 的效果:

1. 它将切换 cross_{i,j} 中的奇数个单元格，因此它会切换 odd(cross_{i,j}) 的值。
2. 对于所有其他“交叉”，受影响的单元格数量将是偶数，因此 odd(cross_{k,l}) 的值对于任何 (k,l)\neq (i,j) 不会改变。

第2点的原因是cross_{k,l}与cross_{i,j}的交集只有3种情况:

1. 整行，单元格数为偶数。
2. 它是一个包含偶数个单元格的整列。
3. k 行一个单元格，l 列一个单元格。

因此对于每一种可能性，偶数个单元格都会改变颜色，因此 odd(cross_{k,l}) 的值不会改变。

所以切换odd(cross_{i,j})值的唯一方法是选择c_{i,j}。

在比赛结束时，有 32 个十字架已经改变了值(value)。因此，任何解决方案的最少步骤数都是 32。

现在，前面的推理也表明，选择感兴趣的 32 个单元格将产生最终的棋盘状态。

所以这是一个最小的解决方案。

很抱歉，这里没有编程:)