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

八皇后算法介绍

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

八皇后算法思路解析

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

OC实现八皇后

/** 全局的二维数组(用于八皇后递归算法) */
@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列情况试探完毕 将对应位置重置为0 防止干扰下次结果
      self.eightQueens[row][k] = @(0);
    }
  }
}

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

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

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

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

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

C语言实现八皇后

#pragma mark - C语言实现八皇后算法
#pragma mark -
const int QueensNumber = 8 ;//皇后数量
int queens[QueensNumber][QueensNumber] = {0};//初始化数组
static int QueensCount = 0;//记录解法数量

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;
    }
  }

  //走到这里证明皇后是可以插入的 此时将它标记为1
  queens[row][col] = 1;
  return true;
}

void eightQueen(int row) {
  if (QueensNumber == row) {
    //当行数为8时 直接打印 count++
    printSolution();
    QueensCount++;
  }else {
    //判断当前行的所有列中是否有一个位置可以插入皇后
    for (int col = 0; col < QueensNumber; col++) {
      if (rightPosition(row,col)) {
        //如果上一行位置合适了 接着找下一行
        eightQueen(row + 1);
      }
      //这里如果是不能插入皇后 就要将当前行所有的元素赋值为0 防止对下次造成干扰
      queens[row][col] = 0;
    }
  }
}

总结

总得来说C语言的思路和OC是一样的,都是通过递归的方式来寻找皇后合适的插入位置,当然递归并不是唯一的实现方式,今天我们先谈递归的实现,以后有机会我会使用回溯法的方式来实现,有需要的继续关注就好

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

(0)

相关推荐

  • JavaScript解八皇后问题的方法总结

    关于八皇后问题的 JavaScript 解法,总觉得是需要学习一下算法的,哪天要用到的时候发现真不会就尴尬了 背景 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上 八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为 n×n ,而皇后个数也变成n .当且仅当n = 1或n ≥ 4时问题有解 盲目的枚举算法 通过N重循环,枚举满足约束条件的解(

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • 八皇后问题的相关C++代码解答示例

    八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7

  • Java基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • 八皇后问题实现代码分享

    main.cpp 复制代码 代码如下: #include<iostream>#include<cstring> using namespace std; const int N = 7; int count = 0; void QueenPrint(int LayOut[N][N])  //打印结果{ cout<<"第"<<++count<<"种布局:"<<endl; for(int i = 0

  • java实现八皇后问题示例分享

    问题描述:将八个皇后放在棋盘上,任何两个皇后都不能互相攻击(即没有任何两个皇后在同一行.同一列或者同一对角线上)如图所示   在本文中,对于两道题采用了稍微不同的解决方式,但都使用的是一维数组.6.20中,要求求出一种有效布局,我建立了一个 有八个元素的一位数组,通过随意打乱数组的值,通过值与下标的比较,直至得出一个有效布局:6.22中,要求求出所有有效布局,这里我使用了八进制数,遍历了  从001234567-076543210的所有数字,通过将其转化为八进制字符串,每位与其下标相比较,输出满

  • c++递归实现n皇后问题代码(八皇后问题)

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

  • C#用递归算法解决八皇后问题

    1.引子 中国有一句古话,叫做"不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走.然后再继续尝试向前.通过这样的波浪式前进方法,最终达到目的地.当然整个过程需要很多往返,这样的前进方式,效率比较低下. 2.适用范围 适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题. 3.应用场景 在

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

    八皇后算法介绍 知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后 八皇后算法思路解析 既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行.纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • iOS 10 和Xcode8 一起 创建 Siri 功能步骤详解(OC写的 )

    iOS 10 出来之后,我们开发者也可以使用类似Siri的功能..让我们来看看怎么使用吧,其实他是使用Siri里面的一个语音识别框架Speech framework. 让我们来看看 一些 主要的代码吧. 我们需要一个 UITextView 和 UIButton 就 能体现了. 第一步:定义属性 @interface ViewController () <SFSpeechRecognizerDelegate> @property (strong, nonatomic) UIButton *sir

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • IOS开发OC代码中创建Swift编写的视图控制器

    IOS开发OC代码中创建Swift编写的视图控制器 背景 近日在和一群朋友做项目,我和另一位同学负责iOS客户端,我是一直使用OC的,而他只会Swift,因此在我们分工协作之后,就需要把代码合在一起,这就牵扯到如何在TabbarController中添加一个swift创建的子控制器的问题. 解决 首先在一个OC项目中新建一个Swift类,继承自UITableViewController,并且修改其view背景色,方便后续测试. import UIKit class ESSwiftTableVie

  • iOS 纯代码写个侧滑栏功能

    代码原理就是使用UIView并对其移动来完成,一个twoView作为侧滑栏,一个oneView作为主界面,需要弹出侧滑栏时对twoView向右移动200,当隐藏侧滑栏时,向左移动200就行了,twoVIew初始的x地址为-200. #import <UIKit/UIKit.h> @interface ViewController : UIViewController<UITableViewDelegate,UITableViewDataSource> @property (stro

  • C语言之快速排序算法(递归Hoare版)介绍

    废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =

  • Java数据结构与算法实现递归与回溯

    目录 1.什么是递归? 2.代码案例一——迷宫问题 3.代码案例二——八皇后问题 1.什么是递归? 简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁. 看个实际应用场景,迷宫问题(回溯), 递归(Recursion) 我列举两个小案例,来帮助大家理解递归,这里在给大家回顾一下递归调用机制 打印问题 阶乘问题 public static void test(int n) { if (n > 2) { test(n - 1); }

  • Flutter iOS开发OC混编Swift动态库和静态库问题填坑

    目录 引言 OC接入Swift 插件 静态库和 Framework 区别 新的问题: non-modular heade 不能在Framework Module中使用非Modular 的 Header 引言 Flutter 在 iOS 上的编译问题相信大家多多少少遇到过,不知道大家在搜索这方便的问题时,得到的答案是不是让你 clean 或者 install 多几次,很多时候就算解决完问题,也是处于薛定谔的状态,所以本篇也简单记录下 Flutter 开发中,OC 混编 Swift 遭遇动态库和静态

随机推荐