algorithm - 求算法解决八皇后之谜

Question

可能重复：
C++ 中的 Dumb 8 Queens 问题

嗨，我遇到了这个问题**

编写一个算法来打印在棋盘上排列 8 个国王的所有方式，以便没有一个具有相同的行、列、对角线

**

//initialize chess[i][j] to 0;
int king=100; //any other number except 0/1

for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
//select any one position for the first column... lets start with j=0,i=0
if(chess[i][j]!=1)
chess[i][j]=king;
//now we should cross all rows with value i and column with value j
chess[i][]=1; 
print(when chess[][]=king)
// we cannot enter king if chess[][]=1

}
}

如何检查对角线部分？还如何枚举所有可能的情况？

谢谢你的建议。。

Answer 1

要回答具体问题：

棋盘上的对角线移动总是从 (m,n) 到 (m+/-k, n+/-k)；即，您水平移动的空间与垂直移动的空间一样多。因此，要检查两个皇后，一个在 (i,j) 上，一个在 (p,q) 上，是否在对角线攻击对方，请检查是否abs(i-p) == abs(j-q)。

要在 (p,q) 上划掉所有可以被皇后对角攻击的方格，您需要以下形式的四个循环

for (i = p, j = q; i >= 0, j >= 0; i--, j--) { board[i][j] = 1 }

for (i = p, j = q; i >= 0, j < 8; i--, j++)  { board[i][j] = 1 }

for (i = p, j = q; i < 8, j < 8; i++, j++)   { board[i][j] = 1 }

for (i = p, j = q; i < 8, j >= 0; i++, j--)  { board[i][j] = 1 }

也就是说，你以你的皇后为中心走 x 的所有四个手臂，划掉方块，直到你碰到棋盘的边缘。