ios使用OC写算法之递归实现八皇后

2023-09-26 06:46:06 175

八皇后算法介绍

知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色，她可以上下左右通吃，和中国象棋里面的车（ju一声）一样，但是她比车更强大，她可以在斜线上也做到通吃，而我们的八皇后问题其实简单来说就是如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后

八皇后算法思路解析

既然任意一个皇后都无法吃掉其他的皇后，也就是说任两个皇后都不能处于同一条横行、纵行或斜线上，我们将棋盘当做一个二维数组，将皇后的位置标记为1而其他位置默认都为0，这样我们就可以使用递归的方式将棋盘以打印的方式打印出来，问题也就解决了，下面我将以OC和C语言两种方式来实现，当然思路都是一样的，有些人可能不熟悉OC，所以这里也顺带提供一份C语言的

OC实现八皇后

/**全局的二维数组（用于八皇后递归算法）*/
@property(nonatomic,strong)NSMutableArray*eightQueens;

#pragmamark-懒加载视图
#pragmamark-
-(NSMutableArray*)eightQueens{
if(!_eightQueens){
_eightQueens=[NSMutableArrayarray];
for(inti=0;i<8;i++){
NSMutableArray*tempArray=[NSMutableArrayarray];
for(inti=0;i<8;i++){
[tempArrayaddObject:@(0)];
}
[_eightQueensaddObject:tempArray];
}
}
return_eightQueens;
}

#pragmamark-OC八皇后递归算法
#pragmamark-

/**
八皇后的递归方法

@paramrow开始行
*/
-(void)eightQueen:(int)row{
if(row==8){
NSLog(@"这是第%lu种解法",self.count+1);
for(inti=0;i<8;i++){
for(intj=0;j<8;j++){
printf("%d",[self.eightQueens[i][j]intValue]);
}
printf("\n");
}
_count++;

}else{
for(intk=0;k<8;k++){
//查看是否这一行的这些列中是否就是存放皇后的位置
if([selfisQueenPosition:rowcol:k]){
//接着下一行找合适的皇后插入位置
[selfeightQueen:row+1];
}
//row行k列情况试探完毕将对应位置重置为0防止干扰下次结果
self.eightQueens[row][k]=@(0);
}
}
}


/**
判断当前位置是否可以存放皇后

@paramrow当前要求解的行
@paramcol位置的列数
@return是否可以存放皇后
*/
-(BOOL)isQueenPosition:(int)rowcol:(int)col{
//判断列的方向也就是竖直方向
for(inti=0;i<8;i++){
if([self.eightQueens[i][col]integerValue]==1){
//表示不能放皇后在这个位置
returnNO;
}
}
//判断左上方
for(inti=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if([self.eightQueens[i][j]integerValue]==1){
//表示不能放皇后在这个位置
returnNO;
}
}

//判断右上方
for(inti=row-1,j=col+1;i>=0&&j<8;i--,j++){
if([self.eightQueens[i][j]integerValue]==1){
//表示不能放皇后在这个位置
returnNO;
}
}

//判断右下方（由于是从第0行开始排列所以这里可以不用判断）
for(inti=row,j=col;i<8&&j<8;i++,j++){
if([self.eightQueens[i][j]integerValue]==1){
//表示不能放皇后在这个位置
returnNO;
}
}


//判断左下方（由于是从第0行开始排列所以这里可以不用判断）
for(inti=row,j=col;i<8&&j>=0;i++,j--){
if([self.eightQueens[i][j]integerValue]==1){
//表示不能放皇后在这个位置
returnNO;
}
}
//表示这个位置可以放皇后了
self.eightQueens[row][col]=@(1);
returnYES;
}

C语言实现八皇后

#pragmamark-C语言实现八皇后算法
#pragmamark-
constintQueensNumber=8;//皇后数量
intqueens[QueensNumber][QueensNumber]={0};//初始化数组
staticintQueensCount=0;//记录解法数量

voidprintSolution(){
printf("这是第%d种解法",QueensCount+1);
printf("\n");
for(inti=0;i=0&&j>=0;i--,j--){
if(queens[i][j]==1){
returnfalse;
}
}

//判断右上角
for(inti=row-1,j=col+1;i>=0&&j
总结
总得来说C语言的思路和OC是一样的，都是通过递归的方式来寻找皇后合适的插入位置，当然递归并不是唯一的实现方式，今天我们先谈递归的实现，以后有机会我会使用回溯法的方式来实现，有需要的继续关注就好


以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

ios使用OC写算法之递归实现八皇后

热门推荐

随机推荐