我正在做关于国际象棋中的Eight Queen Puzzle的任务。演习如下:
给定棋盘上的8个女王的安排,写一个C程序,该程序将评估该安排并告知用户该安排是否是该拼图的解决方案。
现在,因为有92种可能的解决方案,将用户输入与解决方案列表进行比较是不切实际的,所以我正在解决这个问题:
我认为是8x8阵列。代表一个带0的空方块和一个带有1的大号的方形,我需要检查以便解决方案是正确的:
每行,每列和可能的对角线的总和不得超过1。
这是我的问题:我已经覆盖了行和列,但我找不到添加对角线的方法。为了澄清:
每条对角线代表每次必须求和的平方。每行的结果将存储在一个数组中。这种情况发生在两个方向。
代码到目前为止:
#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指出我正确的方向!关于最终解决方案的FYI:你可以在这里找到它,并提出澄清意见:Solution
编辑-2:您可以找到整个代码here,也评论。
@Yunnosch:它可能不优雅甚至不高效,但效果很好。快速问题:这种方法是您想到的还是创新? :P
由于这是一项任务,我遵循妥协处理家庭作业问题。即我不会提供解决方案。相反,这是你应该如何解决问题的第一个暗示。
HINT1: 每个方向有15个对角线。它们的长度为1到8.除长度8外,所有长度都存在两次。
提示二: 您有一个包含列计数的数组和一个包含行数的数组,两个都是大小为8,因为有8行和8列。 您缺少一个包含/ diagonals计数的数组和一个包含\ diagonals计数的数组。 引入它们并用计数填充它们,类似于如何填充行和列数组。计数必须记住不同长度的对角线。
让我知道这有多大帮助。 我可能暗示下一步。