递归与N皇后问题

递归的基本概念

一个函数调用其自身，就是递归

递归的作用

1) 替代多重循环

2) 解决本来就是用递归形式定义的问题

3) 将问题分解为规模更小的子问题进行求解

一行只能有一个皇后，这个根据游戏规则中的皇后的势力就可以得知。

首先先让A皇后放在左上角（0,0),B皇后再从第二行找到合适的位置，以此类推C皇后在第三行找到合适的位置，一直到N皇后，一组解就出来了，但是问题并不是这么简单。

假设现在是4皇后问题，第A个皇后在（0，0）B皇后在（1，3）

C皇后在(3,1)此时D皇后就无位置可以放置。

细心的你，可能会有疑问，每次D皇后，找不到合适的位置，就去让BC重新寻找位置，当BC皇后在它所处的行，再也找不到合适的位置，A皇后的位置就需要变动了。棋盘上就一个皇后A，寻找他的合适位置只需右移一个位置即可。A皇后位移后，再去为BC皇后找合适位置，如果有合适位置，就再去为D皇后寻找合适的位置；如果BC皇后都没有合适的位置，就需要再次右移A皇后，循环上面的过程。

#include<bits/stdc++.h>

using namespace std;

int N;

int queenPos[100];

/*用来存放算好的皇后位置。最左上角是(0,0)

每一行都有一个只用记录它的列坐标*/

void NQueen(int k);

int main()

{

    cin >> N;

    NQueen(0); //从第0行开始摆皇后

    return 0;

}

void NQueen(int k)

{ //在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后

    int i;

    if(k==N)

    { // N 个皇后已经摆好

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

        cout<<queenPos[i]+1<<" ";

        cout<<endl;

        return ;

    }

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

    { //逐尝试第k个皇后的位置

        int j;

        for( j = 0; j < k; j ++ )

        {//和已经摆好的k 个皇后的位置比较，看是否冲突

            if(queenPos[j]==i||abs(queenPos[j]-i)==abs(k-j))  break;

            //冲突，则试下一个位置

        }

        if( j == k )

        { //当前选的位置i 不冲突

            queenPos[k] = i; //将第k个皇后摆放在位置i

            NQueen(k+1);

        }

    }

}

巴特西

递归与N皇后问题

递归的基本概念

递归的作用

最新文章

热门文章