C++ 代码示例 : What makes this loop so many times?

Question

我在这里找到了一个代码示例:N-QUEEN Backtracking problem solved

它显示了这段代码:

#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 种解决方案。起初我以为它只找到了一个解决方案，但当我测试代码并运行所有可能的解决方案时，我感到很惊讶。

我一定在这里遗漏了一些非常基本的东西，因为我什至试图在一个解决方案之后让它“停止”，但我失败了。

所以我想我在这里要问的是，为了理解这一点，给定这段代码，如果我只想让它循环一次并找到第一个解决方案，那么需要更改什么？ 什么样的魔法让这个东西一直循环？!

Answer 1

理解递归方法的第一步是描述该方法的作用，如下所示:

/** solve_state(state, n) finds all possible solutions given a state where
 * the first n rows already have legally placed queens
 */

然后检查方法的主体并对其进行描述:

/**
 * if n == N we're done, there is a queen in every row.  print the solution.
 * otherwise for every legal spot in the current row, 
 * put a queen there, and then solve the remaining rows.
 */

---

在打印一个解决方案后让程序退出的一种非常简单的方法是在打印解决方案后抛出异常。

或者，也许更优雅，您可以修改 solve_state 以在找到解决方案时返回 1，并以这种方式停止递归:

int 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 1; // done!
    }

    /* 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;
            if (solve_state(state, row+1)) return 1;
        }
        state[row][i] = 0;
    }

    return 0; // not yet
}