回溯算法——解决n皇后问题

所谓回溯(backtracking)是通过系统地搜索求解问题的方法。这种方法适用于类似于八皇后这样的问题:求得问题的一个解比较困难,但是检查一个棋局是否构成解很容易。

不多说，放上n皇后的回溯问题代码：

//Queens.h
#define Queens_H
#ifndef Queeens_H#include <vector>
using namespace std;class Queens
{
public:
Queens(int size);   //构造规模为n行n列的空棋盘
bool is_solved() const;  //当前棋盘构成解
void print() const;   //输出当前棋盘
bool unguarded(int col) const;  //在(count,col)处放置皇后没有冲突
void insert(int col);   //在(count,col)处放置皇后
void remove(int col);  //删除(count,col)处放置的皇后
void solve_from(Queens &configuration);   //n皇后问题回溯算法
int board_size;    //棋盘规模
private:
int count;   //当前棋盘上皇后个数
vector<vector<bool> > queen_square;
};#endif

//Queens.cpp
#include "Queens.h"
#include <vector>
#include <iostream>
using namespace std;Queens::Queens(int size)
{
queen_square.resize(size);
int i;
for(i = 0;i < queen_square.size();i++)
{
queen_square[i].resize(size);
}
board_size = size;
count = 0;   //还没有放置任何皇后
}bool Queens::is_solved() const
{
if(count == board_size)
return true;
else
return false;
}void Queens::print() const
{
cout << "下面是解决" << board_size << "皇后问题的一组解（\"O\"表示该位置有皇后,\"X\"表示给位置无皇后):" << endl;
int i,j;
for(i = 0;i < board_size;i++)
{
for(j = 0;j < board_size;j++)
{
if(queen_square[i][j])
cout << "O  " ;
else
cout << "X  " ;
}
cout << endl;
}
}bool Queens::unguarded(int col) const
{
//先把当前的坐标表示出来
int x = count;
int y = col;
int i,j;
for(i = 0;i < board_size;i++)
{
if(i != y && queen_square[x][i])
return false;
}
for(j = 0;j < board_size;j++)
{
if(j != x && queen_square[j][y])
return false;
}
for(i = 1;i < board_size;i++)
{
if(x - i >= 0 && x - i < board_size && y - i >= 0 && y - i < board_size)
{
if(queen_square[x-i][y-i])
return false;
}
if(x + i >= 0 && x + i < board_size && y + i >= 0 && y + i < board_size)
{
if(queen_square[x+i][y+i])
return false;
}
if(x + i >= 0 && x + i < board_size && y - i >= 0 && y - i < board_size)
{
if(queen_square[x+i][y-i])
return false;
}
if(x - i >= 0 && x - i < board_size && y + i >= 0 && y + i < board_size)
{
if(queen_square[x-i][y+i])
return false;
}
}
return true;
}void Queens::insert(int col)
{
queen_square[count][col] = true;
count++;
}void Queens::remove(int col)
{
count--;
queen_square[count][col] = false;
}void Queens::solve_from(Queens &configuration)
{
if(configuration.is_solved())
configuration.print();
else
{
for(int col = 0;col < configuration.board_size;col++)
{
if(configuration.unguarded(col))
{
configuration.insert(col);   //在(count,col)处放置皇后
solve_from(configuration);   //递归，继续求解
configuration.remove(col);   //去掉先前在(count,col)处放置的皇后
}
}
}
}

//test.cpp
#include <iostream>
#include "Queens.h"
//#include <vector>
using namespace std;int main()
{
int n = 8;   //尝试解决8皇后问题
Queens qq(n);
qq.solve_from(qq);
return 0;
}