八皇后的问题是 8*8的棋盘。 上面 放上八个皇后，每个皇后的 上下、左右、和对角线不能放皇后。
一共有几种方法？
当前高斯 数学法师都算错了，我为了巩固数据结构和递归思想。 代码如下最最最重要的思想， 全部扫一遍，判断每下一步棋。八皇后 是否成立。
-
swift 版本
//: Playground - noun: a place where people can playimport UIKit ///记录当前的 var count = 0 /// 用于判断当前皇后是否 安全 ///row 行 ，列 j 。棋盘 func notDanger(row:Int,j:Int,chessc:[[Int]]) -> Bool { ///同一列是否用安全 for i in 0..<8 { if chessc[i][j] == 1{ return false } } //左上角 for (var i = row, k = j; i >= 0 && k >= 0; i--,k-- ){ if chessc[i][k] == 1 { return false } } //右下角 for (var i = row, k = j; i < 8 && k < 8; i++,k++ ){ if chessc[i][k] == 1 { return false } } //右上角 for (var i = row, k = j; i >= 0 && k < 8; i--,k++ ){ if chessc[i][k] == 1 { return false } } //左下角 for (var i = row, k = j; i < 8 && k >= 0; i++,k-- ){ if chessc[i][k] == 1 { return false } } //此位置可以放皇后 return true } ///row行 chessc是棋盘 func eightQuee(row:Int,var chessc:[[Int]]){ if row == 8{ ///等于8 相当于是一个找出一个可放8个皇后的棋盘 count += 1 print("第\(count)种") ///打印当前的棋盘 for rowChessc in chessc { for dot in rowChessc { print("\(dot) ",terminator:"")//输出末尾不换行 } print("")//换行 } print("")//换行 print("")//换行 }else{ for j in 0 ..< 8 { ///判断皇后是否能放在这里 if notDanger(row, j: j, chessc: chessc) { ///当前行 清空 for i in 0..<8 { chessc[row][i] = 0 } ///标记可以放的 chessc[row][j] = 1 ///递归下一行 找合适位置 eightQuee(row+1, chessc: chessc) } } } } ///初始化数组，- -。8*8的棋盘 var chessc = [[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0]] eightQuee(0, chessc: chessc) -
c 语言实现，是递归和回溯
#include <stdio.h>int count = 0; ///这个方法判断周围是否有其他皇后 ///row 那一行 j 那一列 ，棋盘 int notDanger(int row,int j,int (*chess)[8]){ int i,k=0; ///同一列 有没有其他皇后 for (i = 0; i < 8; i++) { if (*(*(chess+i)+j) != 0){ return 0; } } /// 左上角 有没有皇后 for (i = row,k = j; i>=0 && k>=0; i--,k--) { if (*(*(chess+i)+k) != 0){ return 0; } } /// 右下角 有没有皇后 for (i = row,k = j; i<8 && k<8; i++,k++) { if (*(*(chess+i)+k) != 0){ return 0; } } /// 右上角 有没有皇后 for (i = row,k = j; i>=0 && k<8; i--,k++) { if (*(*(chess+i)+k) != 0){ return 0; } } /// 左下角 有没有皇后 for (i = row,k = j; i<8 && k>=0; i++,k--) { if (*(*(chess+i)+k) != 0){ return 0; } } ///走到这里 就表示 安全。 return 1; } //row 代表第几行 //(*chess)[8]代表指向每行的指针 void eightQuee(int row,int (*chess)[8]) { ///临时棋盘 int chess2[8][8]; for (int i = 0 ; i < 8 ; i++) { for(int j = 0 ; j < 8 ; j++) { ///保存传进来的棋盘 chess2[i][j] = chess[i][j]; } } if (row == 8){ printf("第%d种\n",count+1); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { printf("%d ",*(*(chess2+i)+j)); } printf("\n"); } printf("\n"); count++; }else{ ///这行 ，每一列 for(int j = 0;j < 8; j++){ ///判断是否 可以放在这里, if (notDanger(row,j,chess2)){ ///这一行 清空为0 for(int i = 0; i < 8; i++){ *(*(chess2+row)+i) = 0; } ///可以放的位置 变成1 *(*(chess2+row)+j) = 1; ///递归下一行 eightQuee(row + 1, chess2); } } } } int main() { ///初始化一个棋盘 int chess[8][8]={0}; eightQuee(0,chess); return 0; } 总结
swift 好像 没有 c 的快,
也可能swift 在Playground模式下 调用图形界面的结果
都是在Xcode 可能是我的代码写的烂。
大量的函数递归 非常消耗内存的分配和调用。
但是 这样 易于理解
个人博客： www.liangtongzhuo.com
