在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表格,所有正方形都是白色的.在每一步中你都会选择任意一个正方形,因此同一行和列上的所有正方形 - 包括所选的正方形本身 - 将切换颜色(白色变为黑色,黑色变为白色).获得标准彩色棋盘所需的最小步数是多少？"

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

我的方法是从结束(棋盘)到全白.所以我用一个(黑色)和零(白色)填充板,并在功能fillchessboard()中成功构建棋盘.我可以完美地切换行和列我选择的初始方块.

如果所有板都是白色的检查方法是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 }.它是来自行联合列的所有单元格的交叉.它包含奇数个单元格.ij
• odd(cross_{i,j})如果存在偶数个黑色单元,则返回0的函数,如果存在cross_{i,j}奇数个黑色单元,则返回1.

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

1. 它将切换奇数个单元格cross_{i,j},因此它将切换值odd(cross_{i,j}).
2. 对于所有其他"十字架",受影响的细胞数量将是均匀的,因此odd(cross_{k,l})任何细胞的价值(k,l) \neq (i,j) 都不会改变.

其原因点2是,有仅3例为的交点cross_{k,l}与cross_{i,j}:

1. 它是一整行,具有偶数个单元格.
2. 它是一个整数列,具有偶数个单元格.
3. 行为一个单元格k,列为一个单元格l.

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

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

在比赛结束时,有32个十字架已经切换了价值.因此,任何解决方案的最小步骤数为32.

现在,先前的推理还表明,选择感兴趣的32个细胞将产生最终的棋盘状态.

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

对不起,这里没有编程:)