八皇后算法介紹
知道國(guó)際象棋的朋友們應(yīng)該知道里面的皇后是最厲害的角色，她可以上下左右通吃，和中國(guó)象棋里面的車（ju 一聲）一樣，但是她比車更強(qiáng)大，她可以在斜線上也做到通吃，而我們的八皇后問題其實(shí)簡(jiǎn)單來說就是如何能夠在 8×8 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無法直接吃掉其他的皇后
八皇后算法思路解析
既然任意一個(gè)皇后都無法吃掉其他的皇后，也就是說任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上，我們將棋盤當(dāng)做一個(gè)二維數(shù)組，將皇后的位置標(biāo)記為1 而其他位置默認(rèn)都為0，這樣我們就可以使用遞歸的方式將棋盤以打印的方式打印出來，問題也就解決了，下面我將以O(shè)C和C語(yǔ)言兩種方式來實(shí)現(xiàn)，當(dāng)然思路都是一樣的，有些人可能不熟悉OC，所以這里也順帶提供一份C語(yǔ)言的
OC實(shí)現(xiàn)八皇后
/** 全局的二維數(shù)組（用于八皇后遞歸算法） */@property(nonatomic,strong) NSMutableArray<NSMutableArray *> *eightQueens;#pragma mark - 懶加載視圖#pragma mark -- (NSMutableArray<NSMutableArray *> *)eightQueens { if (!_eightQueens) { _eightQueens = [NSMutableArray array]; for (int i = 0; i < 8; i++) { NSMutableArray *tempArray = [NSMutableArray array]; for (int i = 0; i < 8; i++) { [tempArray addObject:@(0)]; } [_eightQueens addObject:tempArray]; } } return _eightQueens;}#pragma mark - OC八皇后遞歸算法#pragma mark -/** 八皇后的遞歸方法 @param row 開始行 */- (void)eightQueen:(int)row{ if (row == 8) { NSLog(@"這是第%lu種解法",self.count +1); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j ++) { printf("%d ",[self.eightQueens[i][j] intValue]); } printf("/n"); } _count++; }else { for (int k = 0; k < 8; k++) { //查看是否這一行的這些列中是否就是存放皇后的位置 if ([self isQueenPosition:row col:k]) { //接著下一行找合適的皇后插入位置 [self eightQueen:row + 1]; } //row行 k列情況試探完畢 將對(duì)應(yīng)位置重置為0 防止干擾下次結(jié)果 self.eightQueens[row][k] = @(0); } }}/** 判斷當(dāng)前位置是否可以存放皇后 @param row 當(dāng)前要求解的行 @param col 位置的列數(shù) @return 是否可以存放皇后 */- (BOOL)isQueenPosition:(int)row col:(int)col { //判斷列的方向 也就是豎直方向 for (int i = 0; i < 8; i++) { if ([self.eightQueens[i][col] integerValue] == 1) { //表示不能放皇后在這個(gè)位置 return NO; } } //判斷左上方 for (int i = row -1,j = col - 1; i >= 0 && j>=0; i--,j--) { if ([self.eightQueens[i][j] integerValue] == 1) { //表示不能放皇后在這個(gè)位置 return NO; } } //判斷右上方 for (int i = row - 1,j = col + 1; i >= 0 && j < 8 ; i--,j++) { if ([self.eightQueens[i][j] integerValue] == 1) { //表示不能放皇后在這個(gè)位置 return NO; } } //判斷右下方（由于是從第0行開始排列 所以這里可以不用判斷） for (int i = row,j = col; i < 8 && j < 8; i++,j++) { if ([self.eightQueens[i][j] integerValue] == 1) { //表示不能放皇后在這個(gè)位置 return NO; } } //判斷左下方（由于是從第0行開始排列 所以這里可以不用判斷） for (int i = row,j = col; i < 8 && j >= 0 ; i++,j--) { if ([self.eightQueens[i][j] integerValue] == 1) { //表示不能放皇后在這個(gè)位置 return NO; } } //表示這個(gè)位置可以放皇后了 self.eightQueens[row][col] = @(1); return YES;}C語(yǔ)言實(shí)現(xiàn)八皇后
#pragma mark - C語(yǔ)言實(shí)現(xiàn)八皇后算法#pragma mark -const int QueensNumber = 8 ;//皇后數(shù)量int queens[QueensNumber][QueensNumber] = {0};//初始化數(shù)組static int QueensCount = 0;//記錄解法數(shù)量void printSolution() { printf("這是第%d種解法",QueensCount +1); printf("/n"); for (int i = 0; i < QueensNumber; i++) { for (int j = 0; j < QueensNumber; j ++) { printf("%d ",queens[i][j]); } printf("/n"); }}bool rightPosition(int row,int col) { //判斷列也就是豎直方向是否有皇后 for (int i = 0; i < QueensNumber; i++) { if (queens[i][col] == 1) { return false; } } //判斷左上角 for (int i = row - 1,j = col -1; i >= 0 && j >= 0; i--,j--) { if (queens[i][j] == 1) { return false; } } //判斷右上角 for (int i = row - 1,j = col + 1; i >= 0 && j < QueensNumber; i--,j++) { if (queens[i][j] == 1) { return false; } } //走到這里證明皇后是可以插入的 此時(shí)將它標(biāo)記為1 queens[row][col] = 1; return true;}void eightQueen(int row) { if (QueensNumber == row) { //當(dāng)行數(shù)為8時(shí) 直接打印 count++ printSolution(); QueensCount++; }else { //判斷當(dāng)前行的所有列中是否有一個(gè)位置可以插入皇后 for (int col = 0; col < QueensNumber; col++) { if (rightPosition(row,col)) { //如果上一行位置合適了 接著找下一行 eightQueen(row + 1); } //這里如果是不能插入皇后 就要將當(dāng)前行所有的元素賦值為0 防止對(duì)下次造成干擾 queens[row][col] = 0; } }}總結(jié)
總得來說C語(yǔ)言的思路和OC是一樣的，都是通過遞歸的方式來尋找皇后合適的插入位置，當(dāng)然遞歸并不是唯一的實(shí)現(xiàn)方式，今天我們先談遞歸的實(shí)現(xiàn)，以后有機(jī)會(huì)我會(huì)使用回溯法的方式來實(shí)現(xiàn)，有需要的繼續(xù)關(guān)注就好
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點(diǎn)
疑難解答
圖片精選
