写点什么

N 皇后问题的回溯法实现

作者:老王同学
  • 2023-02-28
    广东
  • 本文字数:1932 字

    阅读完需:约 6 分钟

摘自《计算机算法基础》(华中科技大学出版社)。

#include <iostream>#include <cmath>#include <vector>#include <array>#include <algorithm>using namespace std; template<int N>class NQueen{public:    typedef array<int, N> ColumnType;     NQueen()    {        Column.fill(-1);    }     /*使用回溯法,求出在一个n*n的棋盘上放置n个皇后,使其不能互相攻击的所有可能位置。 */    void Nqueen()    {        int count = 0;        int currentRow = 0; // currentRow 是当前行         while(currentRow > -1) // 对所有的行执行以下语句        {             Column[currentRow] += 1; //移动到下一列            while((Column[currentRow] < N) &&                (!Place(Column, currentRow)))            {                Column[currentRow] += 1;            }            if (Column[currentRow] < N) // 找到一个位置            {                 if(currentRow == (N-1)) // 是一个完整的解吗                {                    resVec.push_back(Column);                }                else                {                    currentRow++;                    Column[currentRow] = -1; // 转向下一行                }             }            else            {                currentRow--; // 回溯            }        }    }     void PrintAll()    {        cout << "一共有" << resVec.size() << "组解。" << endl;         for_each(resVec.begin(), resVec.end(), []                 (ColumnType& column)                 {                     for_each(column.begin(), column.end(), [](int& value){cout << value << " ";});                     cout << endl;                 });    } private:    vector<ColumnType> resVec; //存放所有的解    ColumnType Column; //存放回溯过程中的一组成功解,下标代表行,数组值代表列     //一个皇后是否能放在第 row 行,和第 Column[row] 列?    bool Place(ColumnType& columnArray, int row)    {        for(int oldRow = 0; oldRow < row; ++oldRow)        {            if (columnArray[oldRow] == columnArray[row] || //同一行有两个皇后                abs(columnArray[oldRow]-columnArray[row]) == abs(oldRow-row)) //在同一斜线上            {                return false;            }        }        return true;    }}; int main(){    /* N皇后问题,找出在一个N*N的棋盘上防止N个皇后,并使其不能互相攻击的所有方案。     即,所有的皇后不能同行或同列。*/    NQueen<8> Queen8;     Queen8.Nqueen();    Queen8.PrintAll();}
复制代码


8 皇后问题结果如下,列出的数字代表列数,下标代表行。

一共有 92 组解。

0 4 7 5 2 6 1 3

0 5 7 2 6 3 1 4

0 6 3 5 7 1 4 2

0 6 4 7 1 3 5 2

1 3 5 7 2 0 6 4

1 4 6 0 2 7 5 3

1 4 6 3 0 7 5 2

1 5 0 6 3 7 2 4

1 5 7 2 0 3 6 4

1 6 2 5 7 4 0 3

1 6 4 7 0 3 5 2

1 7 5 0 2 4 6 3

2 0 6 4 7 1 3 5

2 4 1 7 0 6 3 5

2 4 1 7 5 3 6 0

2 4 6 0 3 1 7 5

2 4 7 3 0 6 1 5

2 5 1 4 7 0 6 3

2 5 1 6 0 3 7 4

2 5 1 6 4 0 7 3

2 5 3 0 7 4 6 1

2 5 3 1 7 4 6 0

2 5 7 0 3 6 4 1

2 5 7 0 4 6 1 3

2 5 7 1 3 0 6 4

2 6 1 7 4 0 3 5

2 6 1 7 5 3 0 4

2 7 3 6 0 5 1 4

3 0 4 7 1 6 2 5

3 0 4 7 5 2 6 1

3 1 4 7 5 0 2 6

3 1 6 2 5 7 0 4

3 1 6 2 5 7 4 0

3 1 6 4 0 7 5 2

3 1 7 4 6 0 2 5

3 1 7 5 0 2 4 6

3 5 0 4 1 7 2 6

3 5 7 1 6 0 2 4

3 5 7 2 0 6 4 1

3 6 0 7 4 1 5 2

3 6 2 7 1 4 0 5

3 6 4 1 5 0 2 7

3 6 4 2 0 5 7 1

3 7 0 2 5 1 6 4

3 7 0 4 6 1 5 2

3 7 4 2 0 6 1 5

4 0 3 5 7 1 6 2

4 0 7 3 1 6 2 5

4 0 7 5 2 6 1 3

4 1 3 5 7 2 0 6

4 1 3 6 2 7 5 0

4 1 5 0 6 3 7 2

4 1 7 0 3 6 2 5

4 2 0 5 7 1 3 6

4 2 0 6 1 7 5 3

4 2 7 3 6 0 5 1

4 6 0 2 7 5 3 1

4 6 0 3 1 7 5 2

4 6 1 3 7 0 2 5

4 6 1 5 2 0 3 7

4 6 1 5 2 0 7 3

4 6 3 0 2 7 5 1

4 7 3 0 2 5 1 6

4 7 3 0 6 1 5 2

5 0 4 1 7 2 6 3

5 1 6 0 2 4 7 3

5 1 6 0 3 7 4 2

5 2 0 6 4 7 1 3

5 2 0 7 3 1 6 4

5 2 0 7 4 1 3 6

5 2 4 6 0 3 1 7

5 2 4 7 0 3 1 6

5 2 6 1 3 7 0 4

5 2 6 1 7 4 0 3

5 2 6 3 0 7 1 4

5 3 0 4 7 1 6 2

5 3 1 7 4 6 0 2

5 3 6 0 2 4 1 7

5 3 6 0 7 1 4 2

5 7 1 3 0 6 4 2

6 0 2 7 5 3 1 4

6 1 3 0 7 4 2 5

6 1 5 2 0 3 7 4

6 2 0 5 7 4 1 3

6 2 7 1 4 0 5 3

6 3 1 4 7 0 2 5

6 3 1 7 5 0 2 4

6 4 2 0 5 7 1 3

7 1 3 0 6 4 2 5

7 1 4 2 0 6 3 5

7 2 0 5 1 4 6 3

7 3 0 2 5 1 6 4

————————————————

发布于: 刚刚阅读数: 3
用户头像

老王同学

关注

还未添加个人签名 2020-04-30 加入

还未添加个人简介

评论

发布
暂无评论
N皇后问题的回溯法实现_c++_老王同学_InfoQ写作社区