1

ここでコード例を見つけました：N-QUEENバックトラッキングの問題が解決しました

これはこのコードを示しています：

#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の解決策すべてをループするのか理解できないということです。最初は1つの解決策しか見つからないと思っていましたが、コードをテストして考えられるすべての解決策を実行すると、驚きました。

たった1つの解決策の後でそれを「停止」させようとしたので、ここでは非常に基本的なものが欠けているに違いありませんが、失敗します。

したがって、ここで私が求めているのは、これを理解するために、このコードを前提として、一度ループして最初の解決策を見つけたい場合、何を変更する必要があるかということだと思います。どんな魔術がこのことをいつもループさせているのか？！

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;
}

このループは、あなたが説明したことを正確に実行します。行の8列をループしているため、8つの可能性があります。最初の許容可能な状態で停止する場合は、内部条件を更新し、再帰呼び出しを削除する必要があります。代わりに、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配列、intaがジョブを実行する場所の使用bool）であり、C ++の部分は、関数内での使用std::coutと関数std::endl内での使用のみです。print_solution古き良きものに簡単に交換できますprintf。

于 2013-03-05T23:11:33.517 に答える
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.
 */

1つのソリューションを印刷した後にプログラムを終了させる非常に簡単な方法の1つは、ソリューションを印刷した後に例外をスローすることです。

または、おそらくもっとエレガントに、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
}
于 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 に答える