1

我在这里找到了一个代码示例：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 个解决方案。起初我以为它只找到了一个解决方案，但是一旦我测试了代码并且它运行了所有可能的解决方案，我感到很惊讶。

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

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

4

3 回答 3

1 
/* 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;
}

该循环完全按照您的描述进行。您在一行的八列上循环，从而给出了八种可能性。如果要在第一个可接受的状态下停止，则必须更新内部条件并删除递归调用。相反，您可以调用您的print_solution函数来打印结果。

这给了你类似的东西：

for(i=0; i<N; ++i){

    if(accept(state, row, i)){
        state[row][i] = 1;
        print_solution(state);
        return; // this prevents printing the solution multiple times
                // in case the queen may be placed on other colum on the same row
    }
    state[row][i] = 0;
}

旁注：对我来说，这段代码是一个 C 代码（在函数开头声明的变量，普通的旧 C 数组，使用intwhere abool可以完成这项工作），唯一的 C++ 部分是函数中std::cout和std::endl的使用，print_solution可以很容易地被旧的printf.

于 2013-03-05T23:11:33.517 回答
1

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.

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
}
于 2013-03-06T01:40:37.787 回答
0

也许我的代码会帮助你，我不是最会说英语的人......

//coded by SwinGYOu

#include<iostream>
#pragma warning(disable:4996)
using namespace std;

/* this is the size of chess board */
const int boardSize=8;

/* Given a completed board, this prints it to the console */
void print_solution(int board[boardSize][boardSize], int i=0, int j=0){
    if(i==boardSize){ cout<<endl; return; }
    if(j==boardSize){ cout<<endl; print_solution(board, ++i, 0); return; }
    cout<<"[";
    if((i+j)%2)
        putwchar(board[i][j] ? '\u2655' : ' ');
    else
        putwchar(board[i][j] ? '\u265B' : ' ');
    cout<<"]";
    print_solution(board, i, ++j);
}
/* Check up, up left and up right to veritify that there are no other Queens, return true if right */
bool accept(int board[boardSize][boardSize], int row, int col, int rowD=0, int colD=0){
    if(!(rowD||colD)){
        return
            accept(board, row, col, -1, 0)&&
            accept(board, row, col, -1, -1)&&
            accept(board, row, col, -1, 1);
    }
    if(!(row>=0&&col>=0&&row<boardSize&&col<boardSize)){
        return true;
    }
    if(board[row][col]==1) return false;
    return accept(board, row+rowD, col+colD, rowD, colD);
}
/* check and return sultions for every sultion that possible*/
void solve_board(int board[boardSize][boardSize], int row=0, int col=0){
    //if the row befor was the last row of the table, its meants that is a sultion, print it.
    if(row==boardSize){
        print_solution(board);
        return;
    }
    //if col is out of the board, dont run check on it, its not a vaild path.
    if(col==boardSize) return;
    //run for this, if true, go to next row until end of row's or until a not vaild row is given than carry on with checking the next col.
    if(accept(board, row, col)){
        board[row][col]=1;
        solve_board(board, row+1);
    }
    board[row][col]=0;
    //carry on to next spot on the col in the given row.
    solve_board(board, row, col+1);
}

int main(){
    /* Make board */
    int board[boardSize][boardSize]={0};

    solve_board(board);

    return 0;
}
于 2017-01-22T11:51:16.780 回答