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

时间:2023-12-21 11:06:14

所谓回溯(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;
}