通过二维数组中对角线元素的总和验证八皇后解决方案
verify Eight Queens solution via sums of diagonal elements in a 2D array
我正在做一项关于国际象棋 Eight Queen Puzzle 的作业。
练习如下:
给定棋盘上 8 个皇后的排列,编写一个 C 程序来评估排列并告知用户这种排列是否是拼图的解。
现在,因为有 92 种可能的解决方案,将用户输入与解决方案列表进行比较是不切实际的,所以我这样解决问题:
我考虑一个 8x8 数组。用 0 表示一个空方块,用 1 表示一个皇后方块,为了使解决方案正确,我需要检查的是:
每行、每列和可能的对角线之和不得超过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
EDIT-2: 你可以找到完整的代码here,也有注释。
@Yunnosch:可能不够优雅,甚至不够高效,但效果很好。快速提问:这种方法是您想到的还是一种创新? :P
既然是作业,我在处理作业题上就折中了。 IE。我不会提供解决方案。相反,这是您应该如何解决问题的第一个提示。
提示 1:
每个方向有 15 条对角线。它们的长度是从1到8。所有长度都存在两次,除了长度8。
提示2:
您有一个包含列数的数组和一个包含行数的数组,两者的大小均为 8,因为有 8 行和 8 列。
您缺少一个包含 / 对角线计数的数组和一个包含 \ 对角线计数的数组。
引入它们并用计数填充它们,类似于填充行和列数组的方式。计数必须记住对角线的不同长度。
告诉我这有多大帮助。
我可能会提示下一步。
我正在做一项关于国际象棋 Eight Queen Puzzle 的作业。 练习如下:
给定棋盘上 8 个皇后的排列,编写一个 C 程序来评估排列并告知用户这种排列是否是拼图的解。
现在,因为有 92 种可能的解决方案,将用户输入与解决方案列表进行比较是不切实际的,所以我这样解决问题:
我考虑一个 8x8 数组。用 0 表示一个空方块,用 1 表示一个皇后方块,为了使解决方案正确,我需要检查的是:
每行、每列和可能的对角线之和不得超过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
EDIT-2: 你可以找到完整的代码here,也有注释。
@Yunnosch:可能不够优雅,甚至不够高效,但效果很好。快速提问:这种方法是您想到的还是一种创新? :P
既然是作业,我在处理作业题上就折中了。 IE。我不会提供解决方案。相反,这是您应该如何解决问题的第一个提示。
提示 1:
每个方向有 15 条对角线。它们的长度是从1到8。所有长度都存在两次,除了长度8。
提示2:
您有一个包含列数的数组和一个包含行数的数组,两者的大小均为 8,因为有 8 行和 8 列。
您缺少一个包含 / 对角线计数的数组和一个包含 \ 对角线计数的数组。
引入它们并用计数填充它们,类似于填充行和列数组的方式。计数必须记住对角线的不同长度。
告诉我这有多大帮助。
我可能会提示下一步。