八皇后的問題是 8*8的棋盤妇智。 上面 放上八個皇后抬闷，每個皇后的 上下歇攻、左右厨疙、和對角線不能放皇后墙牌。
一共有幾種方法？
當(dāng)前高斯 數(shù)學(xué)法師都算錯了魄缚，我為了鞏固數(shù)據(jù)結(jié)構(gòu)和遞歸思想宝与。 代碼如下最最最重要的思想， 全部掃一遍鲜滩，判斷每下一步棋伴鳖。八皇后 是否成立节值。
-
swift 版本
//: Playground - noun: a place where people can playimport UIKit ///記錄當(dāng)前的 var count = 0 /// 用于判斷當(dāng)前皇后是否 安全 ///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 相當(dāng)于是一個找出一個可放8個皇后的棋盤 count += 1 print("第\(count)種") ///打印當(dāng)前的棋盤 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) { ///當(dāng)前行 清空 for i in 0..<8 { chessc[row][i] = 0 } ///標(biāo)記可以放的 chessc[row][j] = 1 ///遞歸下一行 找合適位置 eightQuee(row+1, chessc: chessc) } } } } ///初始化數(shù)組搞疗，- -嗓蘑。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 語言實現(xiàn)，是遞歸和回溯
#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++) { ///保存?zhèn)鬟M(jìn)來的棋盤 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; } 總結(jié)
swift 好像 沒有 c 的快,
也可能swift 在Playground模式下 調(diào)用圖形界面的結(jié)果
都是在Xcode 可能是我的代碼寫的爛幢炸。
大量的函數(shù)遞歸 非常消耗內(nèi)存的分配和調(diào)用泄隔。
但是 這樣 易于理解
個人博客： www.liangtongzhuo.com
