我在这里找到了一个代码示例:N-QUEEN Backtracking problemsolved
它显示了这段代码:
#include <iostream>
using namespace std;
/** this is the size of chess board */
#define N 8
/** Given a completed board, this prints it to the stdout */
void print_solution(int state[N][N])
{
int i,j;
for (i = 0; i < N; ++i)
{
for (j = 0; j < N; ++j)
cout << state[i][j] << " ";
cout << endl;
}
cout << endl;
}
/** return true if placing a queen on [row][col] is acceptable
else return false */
bool accept(int state[N][N], int row, int col)
{
int i,j;
/* check the column */
for (i = 0; i < N; ++i)
{
if (state[row][i])
return false;
}
/* check the row */
for (i = 0; i < N; ++i)
{
if (state[i][col])
return false;
}
/* check the upper left diagnol */
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
{
if (state[i][j])
return false;
}
/* check the lower left diagnol */
for (i = row, j = col; i < N && j >= 0; ++i, --j)
{
if (state[i][j])
return false;
}
/* check the upper right diagnol */
for (i = row, j = col; i >= 0 && j < N; i--, ++j)
{
if (state[i][j])
return false;
}
/* check the lower right diagnol */
for (i = row, j = col; i < N && j < N; ++i, ++j)
{
if (state[i][j])
return false;
}
/* return true if all tests passed */
return true;
}
void solve_state(int state[N][N], int row)
{
int i;
/* if all queens have been placed at non conflicting positions */
if (row == N)
{
print_solution(state);
return;
}
/* Place queens on all positions in a given row and
check if the state is acceptable
Continue the process till all possibilities found */
for(i=0; i<N; ++i){
if(accept(state, row, i)){
state[row][i] = 1;
solve_state(state, row+1);
}
state[row][i] = 0;
}
}
int main()
{
/* initialise the board */
int state[N][N] = {0};
solve_state (state, 0);
return 0;
}
我在逻辑上相当失败,而且我在尝试学习递归等方面遇到了更大的麻烦。真正让我感到震惊的是,我无法理解为什么这段代码会循环遍历国际象棋问题中 8 个皇后的所有 92 个解决方案。起初我以为它只找到了一个解决方案,但是一旦我测试了代码并且它运行了所有可能的解决方案,我感到很惊讶。
我必须在这里遗漏一些非常基本的东西,因为我什至试图在一个解决方案之后让它“停止”,但我只是失败了。
所以我想我在这里要问的是,为了理解这一点,给定这段代码,如果我只想让它循环一次,并找到第一个解决方案,需要改变什么?什么样的魔法让这东西一直循环?!