C ++代码示例：什么使这个循环这么多次？ [英] C++ code example: What makes this loop so many times?

问题描述

我在这里找到了一个代码示例： N-QUEEN回溯问题已解决

I found a code example here: 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;
}

我用逻辑失败了，我更难学习递归等等。真正打败我的是，我只是不能理解为什么这个代码循环通过所有的92解决方案的8个女王在国际象棋问题。起初，我认为它只找到一个解决方案，但我惊讶，一旦我测试的代码，它运行所有可能的解决方案。

I fail rather hard with logic and I have even more trouble trying to learn recursion and such. What really ticks me off is that I just cannot comprehend why this code loops through all the 92 solutions of the 8 queens in chess problem. At first I thought it only found one solution but I was surprised once I tested the code and it ran all the possible solutions.

我必须在这里缺少一些非常基本的东西，因为我甚至试图让它停止只是一个解决方案，但我只是失败。

I must be missing something very basic here because I've even attempted to make it "stop" after just one solution but I just fail.

所以我想这里要求的是，为了理解这一点，给定这个代码，如果我只是想让它循环一次，并找到第一个解决方案，什么会需要改变吗？什么样的魔法使这个东西循环所有这些时间？

So I suppose what I am asking here is that in order to understand this, given this code, if I just wanted it to loop through once, and find the first solution, what would need to be changed? What kind of sorcery makes this thing loop all these times?!

推荐答案

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

The first step to understanding a recursive method is to verbalize what the method does, like this:

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

然后检查方法的主体并对其进行说明：

Then examine the body of the method and verbalize it:

/**
 * 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.
 */

---

让程序退出后打印一个解决方案是在打印解决方案后抛出异常。

---

One very easy way to have the program exit after printing one solution is to throw an exception after printing the solution.

或者，也许更优雅地，你可以修改solve_state在找到一个解决方案时返回1，然后停止递归：

Or, perhaps more elegantly, you could modify solve_state to return 1 when it finds a solution, and stop the recursion that way:

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
}

这篇关于C ++代码示例：什么使这个循环这么多次？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！