Most effective way to find combinations in 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;
}

I am trying solve this problem: "You have an 8x8 table on a computer screen with all squares colored to white. In each step you will select any square and as a result all the squares on the same row and column -including the selected square itself- will switch their colors (white becomes black, and black becomes white). What is the minimum number of steps required for obtaining a standard colored chessboard?"

To do that, I percieved the chessboard into 64 pieces(8x8) and calculating all the combinations of this 64s cluster from 1 to 64. (I know the answer is between 1 and 64).

My method is to begin from the end(chessboard) through to all white. So I fill the board with ones(black) and zeros(white) and construct the chessboard in function fillchessboard() successfully. And I can perfectly toggle row and the column the initial square I choose is on.

Checking method if all board is white is checkboard(). This function returns indicator as 0 if all board is white, 1 if not. I start from little combinations to bigger combinations and check the board in each step. So when the indicator returns as 0 for the first time, it will be the smallest iteration number to make the board all white and be the answer of the question.

So far, my code works and in 10 hours it is able to step up to 10th iteration. However it will take more and more time so 11th iteration will take about 10 hours and 12th iteration will take 20 hours and so on... My question is, is there any method to these instructions more fast and effective? I can not wait for a week to solve this. I d appreciate any help. Thanks!

Answer 1

First let's do some naming:

• c_{i,j} is the cell at intersection of row i and column j.
• cross_{i,j} is the set: { c_{r,c} / r=i or c=j }. It is the cross of all cells from row i union column j. It contains an odd number of cells.
• odd(cross_{i,j}) is a function which returns 0 if there is an even number of black cells in cross_{i,j} and 1 if there is an odd number of black cells.

Let's consider the effect of selecting cell c_{i,j}:

1. It will switch an odd number of cells in cross_{i,j} and so it will switch the value of odd(cross_{i,j}).
2. For all other "crosses" the number of cells impacted will be even and so the value of odd(cross_{k,l}) for any (k,l) \neq (i,j) will not change.

The reason for point 2 is that there are only 3 cases for the intersection of cross_{k,l} with cross_{i,j}:

1. It is a whole row, with an even number of cells.
2. It is a whole column with an even number of cells.
3. It is one cell for row k and one cell for column l.

So for every possibility an even number of cells change colors, and so the value of odd(cross_{k,l}) doesn't change.

So the only way to switch the value of odd(cross_{i,j}) is to select c_{i,j}.

At the end of the game there are 32 crosses which have switched value. So the minimal number of steps for any solution is 32.

Now, the previous reasoning also show that selecting the 32 cells of interest will produce the final checkerboard state.

So this is a minimal solution.

I'm sorry but there is no programming here :)