八皇后问题回溯法和迭代法
2019-03-23 本文已影响14人
_兜兜转转_
数据结构系列文章：
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
回溯法[试探法，递归]和迭代法
基本思路是：
1.第一行先占一个皇后
2.第二行再占一个且不能与第一个皇后攻击
3.第三行再占一个
。。。。。
n.第n行占一个，当第n行站不下的时候，取消n-1行的皇后，在第n-1皇后的下一个位置重新占一个皇后位置，知道占到最n-1行的最后一个位置，当还不行的时候，就取消第n-2行，当n-2行的皇后在n-2行的最后一个位置的时候，就取消n-3，n-2在最后一个位置，那么n-3行的一定不再最后一个位置。
再重新寻找n-2行的皇后的位置。
。。。。
。。。。
直到找到最后一个皇后。
找完第一种解法，重新开始寻找第二种解法，直接第一个皇后占第一行的第2个位置，寻找第三种解法占第一行的第3个位置。。。。直到寻找第n个解法。code 在下边。代码是Swift，正好可以练习练习语法。
struct QueenHandle {
//一次的解法皇后
var queensArray:[Queen] = [Queen]();
//所有解法
var queensWay:[[Queen]] = [[Queen]]();
init() {
}
func canStandWithOthers(queens:[Queen],queen:Queen) -> Bool {
var pass = true;
let count = queens.count;
if count == 0 {
return true;
}
for k in 0..<count{
let qSub = queens[k];
//是否存在打架行为
if qSub.unrejectWith(queen: queen) == false{
//有能打架的皇后
pass = false;
break;
}
}
return pass;
}
//回溯法
mutating func callback(x:inout Int,y:inout Int , n:inout
Int,xMax:Int,yMax:Int) -> Void {
let q = Queen(locations: Point(x: x, y: y));
//位置是否可用
let can = self.canStandWithOthers(queens: self.queensArray, queen: q);
if can {
//添加皇后
self.queensArray.append(q);
y += 1;
x = 0;
if y > yMax
{
if (self.queensArray.count == n){
//解法完毕 继续下一个解法
self.queensWay.append(self.queensArray);
self.queensArray.removeAll();
x = self.queensWay.count;
y = 0;
if (x == n){return}else{
callback(x: &x, y: &y, n: &n, xMax: xMax, yMax: yMax);
}
}else{
//回溯法核心思路 当n行没有合适位子，删除上一行的皇后，重新寻找上一行的新皇后位子
if self.queensArray.count > 0{
let lastQ = self.queensArray.removeLast();
x = lastQ.locations.x + 1;
y -= 1;
}
}
}else if(y <= yMax){
callback(x: &x, y: &y, n: &n, xMax: xMax, yMax: yMax);
}
}else if(x < xMax){
x += 1;
callback(x: &x, y: &y, n: &n, xMax: xMax, yMax: yMax);
}else if(x >= xMax){
if self.queensArray.count > 0{
let lastQ = self.queensArray.removeLast();
x = lastQ.locations.x + 1;
y -= 1;
if x > xMax{
let lastQ = self.queensArray.removeLast();
x = lastQ.locations.x + 1;
y -= 1;
}
callback(x: &x, y: &y, n: &n, xMax: xMax, yMax: yMax);
}
}
}
public mutating func handle() -> Void {
var number = 0
while number<8 {
self.find(index: number);
//首行的8种可能
if self.queensArray.count == 8 {
self.queensWay.append(self.queensArray);
}
self.queensArray.removeAll();
number += 1;
}
}
public mutating func find(index:Int) -> Void
{
var y = 0;
var x = index;
while y<8 {
while x<8{
let queen = Queen(locations: Point(x: x, y: y));
let count = self.queensArray.count;
if count>0 {
var pass = true;
for k in 0..<count{
let qSub = self.queensArray[k];
if qSub.unrejectWith(queen: queen) == false{
//有能打架的皇后
pass = false;
break;
}
}
if pass{//添加成功
self.queensArray.append(queen);
break;
}else{
x += 1;
}
}else{//添加成功跳出循环
self.queensArray.append(queen);
break;
}
}
//每一行找出一个 跳下一行
if(self.queensArray.count == y+1){
y += 1;
x = 0;
}else{
if self.queensArray.count > 0{
while x > 7{
//回溯法 寻找上一个可能的皇后 当x==8，继续找上一行的皇后
x = self.queensArray.removeLast().locations.x + 1;
y -= 1;
}
}else{
y += 1;
}
}
}
}
public func printWays() -> Void{
let count = self.queensWay.count;
for i in 0..<count {
let queens = self.queensWay[i];
let countSub = queens.count;
for j in 0..<countSub{
let q = queens[j];
q.printQueen();
}
print("--------------------");
}
}
}
