c - 通过二维数组中对角线元素的总和验证八皇后解

Question

我正在做一项关于 Eight Queen Puzzle 的作业在国际象棋中。 练习如下:

给定棋盘上 8 个皇后的排列，编写一个 C 程序来评估该排列并通知用户该排列是否是难题的解决方案。

现在，由于有 92 种可能的解决方案，因此将用户输入与解决方案列表进行比较是不切实际的，因此我将这样解决问题:

我考虑一个 8x8 数组。用 0 表示一个空方 block ，用 1 表示一个带有皇后的方 block ，为了使解决方案正确，我需要检查的是:

每行、每列以及可能的对角线的总和不得超过 1。

这是我的问题:我已经覆盖了行和列，但我找不到添加对角线的方法。澄清一下:

Sums

每条对角线代表每次必须求和的平方。每行的结果将存储在一个数组中。两个方向都会发生这种情况。

到目前为止的代码:

#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);
}

任何帮助将不胜感激。

编辑:解决了。非常感谢@Yunnosch 为我指明了正确的方向! 关于最终解决方案的仅供引用:您可以在这里找到它，并附有澄清评论:Solution

编辑2:您可以找到整个代码 here ，也发表了评论。

@Yunnosch:它可能不优雅，甚至不高效，但效果很好。快速提问:这种方法是您想要的还是一种创新？ :P

Answer 1

由于这是一项作业，所以我在处理作业问题时遵循妥协的做法。 IE。我不会提供解决方案。相反，这里是您应该如何解决该问题的第一个提示。

提示1:
每个方向有 15 条对角线。它们的长度是从1到8。除了长度8之外，所有长度都存在两次。

提示2:
您有一个包含列计数的数组和一个包含行计数的数组，两者的大小均为 8，因为有 8 行和 8 列。
您缺少一个包含/对角线计数的数组和一个包含\对角线计数的数组。
引入它们并用计数填充它们，类似于填充行和列数组的方式。计数时必须记住对角线长度的变化。

让我知道这有多大帮助。
我可能会暗示下一步。

(政策描述如下: How do I ask and answer homework questions? )