CODEWITHSUNDEEP
carraysdiagonal
lightspot21
lightspot21

Reputation: 49

verify Eight Queens solution via sums of diagonal elements in a 2D array

I'm working on an assignment concerning the Eight Queen Puzzle in chess. The exercise is as follows:

Given an arrangement of the 8 queens on the chessboard, write a C program which will evaluate the arrangement and inform the user if this arrangement is a solution of the puzzle.

Now, because there are 92 possible solutions, it's not practical to compare the user input with a solution list, so I'm solving the problem like this:

I consider an 8x8 array. Representing an empty square with 0 and a square with a queen with 1, all I need to check in order for the solution to be correct is:

The sum of each row, column and possible diagonal line must not exceed 1.

And here is my problem: I've covered the rows and columns, but I can' t find a method to add the diagonals. For clarification:

Sums

Every diagonal line represents the squares that must be summed every time. The result of each line will be stored in an array. This happens for both directions.

Code so far:

#include <stdio.h>

int check(int array[8][8])
{
    int i, j;
    int rowsum[8] = {0, 0, 0, 0, 0, 0, 0, 0};
    int colsum[8] = {0, 0, 0, 0, 0, 0, 0, 0};

    for (i = 0; i <= 7; i++) //test if are 2 queens on the same row (i: row, j: column)
    {
        for (j = 0; j <= 7; j++)
        {
            rowsum[i] += array[i][j]; /*since they are represented by 0s and 1s,
                                if a row's sum is bigger than 1
                                there is more than 1 queen on that particular row
                                here the row doesn't change until all
                                columns are accessed (we get a row sum)*/
        }
    }


    for (i = 0; i <= 7; i++) //same as before, but for columns
    {
        for (j = 0; j <= 7; j++)
        {
            colsum[i] += array[j][i]; //here the col. doesn't change until all rows are accessed (we get a col. sum)
        }
    }
}

int main(void)
{
    int i = 1; //counter for the input
    int row = 0;
    int column = 0; //row and column numbers

    int board[8][8] = {
        {0, 0, 0, 0, 0, 0, 0, 0},   //here we initialize an empty board as an 8x8 array
        {0, 0, 0, 0, 0, 0, 0, 0},   //from now on: a 0 is an empty square, a 1 is a queen
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0}
    };

    while (i <= 8) //we fill our board with queens
    {
        printf("Queen #%d row:", i);
        scanf("%d", &row);
        printf("Queen #%d column:", i);
        scanf("%d", &column);
        board[row - 1][column - 1] = 1;
        i++;
    }

    check(board);
}

Any help would be greatly appreciated.

EDIT: Solved it. Many thanks to @Yunnosch for pointing me to the right direction! FYI about the final solution: You can find it here, with comments for clarification: Solution

EDIT-2: You can find the whole code here, also commented.

@Yunnosch: It might not be elegant or even efficient, but it works well. Quick question: Was this method the one you had in mind or is this an innovation? :P

Upvotes: 2

Views: 484

Answers (1)

Yunnosch
Yunnosch

Reputation: 26703

Since this is a assignment, I follow the compromise for handling homework questions. I.e. I will not provide a solution. Instead here is a first hint at how you should approach the problem.

Hint1:
There are 15 diagonals of each direction. Their length is from 1 to 8. All lengths exist twice, except the length 8.

Hint2:
You have an array with counts for columns and one array with counts for rows, both are of size 8, because there are 8 rows and 8 columns.
You are lacking an array with counts for / diagonals and an array with counts for \ diagonals.
Introduce them and fill them with counts, similarily to how you fill the row and column arrays. Counting has to keep the varying lengths of diagonals in mind.

Let me know how much that helps.
I might hint the next step.

(policy is described here: How do I ask and answer homework questions? )

Upvotes: 2

Related Questions