N 皇后问题的回溯法实现 (C++)

用户头像
老王同学
关注
发布于: 2020 年 08 月 02 日

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

原载于: https://blog.csdn.net/aheroofeast/article/details/7525506

#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



发布于: 2020 年 08 月 02 日 阅读数: 25
用户头像

老王同学

关注

还未添加个人签名 2020.04.30 加入

还未添加个人简介

评论

发布
暂无评论
N皇后问题的回溯法实现(C++)