首页 > 代码库 > 算法回顾--N皇后问题简单回顾
算法回顾--N皇后问题简单回顾
前言
最近学习的过程中,不知道哪门子的思维发散,突然又遇见皇后问题了,于是乎老调重弹,心里琢磨,虽然思路大家都容易懂,哪怕是最简单的野蛮回溯法,说着简单,但是如果非得编码实现?我可以一次性写出来OK的代码吗?我对此表示疑问,于是乎动手写代码,发现写此类算法问题,最重要的是边界条件的判断。这里说明一下,这篇纯属练手,不考虑算法效率,只是为了实现,为了练习最暴力野蛮的回溯,说白了,就是怎样简单粗暴的玩弄for和while这些个玩意!
实现
本人比较懒,所以懒得搞二维数组来存储皇后坐标,其实用二维数组来存储,然后根据行列来遍历和匹配,确实效率高了不少,但是,我在这里仅仅只是练习回溯的思想,所以只是使用简单的数组来存储N*N个数,比如8皇后问题,我就用数组来存储 {1,2,3,,,,,,,,,,64},然后使用queens数组存储安全的皇后
代码
/// <summary>/// 皇后算法非递归实现,主要思想如下:/// 初始化皇后备选列表为空(安全),将所有坐标的棋子尝试放入/// 如果符合安全,则放入(如果数目达到则保留输出),如果不安全则跳过继续搜索/// 如果搜索到结尾依然未搜到,则循环向上回溯到上一次解的下一个继续/// </summary>public class Queen{ // 矩阵维度 int size; // 从1编号,存放所有整数 int[] array; int count; public Queen() : this(4) { } public Queen(int s) { this.size = s; InitList(); } private void InitList() { count = size * size; array = new int[count]; for (int i = 0; i < count; i++) { array[i] = i + 1; } } public void PrintQueenResult() { List<int> queens = new List<int>(); // 记录探测索引 int tryIndex = 0; // 记录最后一次皇后解 int lastQueen = 0; // 记录皇后总数 int queenCount = 0; // 记录所有全皇后解个数 int solutions = 0; while (true) { // 探测元素 int tryItem = array[tryIndex]; // 如果探测到最后一个元素,并且皇后已经回溯为空 // 表示回溯已经全部完成,返回 if (tryItem == array[count - 1] && queenCount == 0) break; // 找到安全的皇后 if (IsSafe(queens, tryItem)) { queens.Add(tryItem); // 皇后数加1 queenCount++; // 记录最后一次放置的皇后 lastQueen = tryItem; // 如果皇后获取足够,输出 if (queenCount == size) { Console.WriteLine("找到皇后排列:{0}", string.Join(",", queens)); solutions++; } } else { if (tryIndex < count - 1) { // 如果不安全,还未搜索结束,继续搜索 tryIndex++; } else { // 如果不安全,但搜索结束,则回溯 while (tryIndex >= count - 1) { queens.Remove(lastQueen); queenCount--; tryIndex = lastQueen; // 如果回溯完毕则跳出 if (queenCount == 0) break; lastQueen = queens[queenCount - 1]; } } } } Console.WriteLine("全部解个数为:{0}", solutions); } private bool IsSafe(List<int> list, int target) { if (list == null || list.Count == 0) return true; return list.All(d => !IsDangerous(d, target)); } private bool IsDangerous(int a, int b) { int rowA = (a - 1) / size + 1; int rowB = (b - 1) / size + 1; int colA = (a - 1) % size + 1; int colB = (b - 1) % size + 1; if (a == b) return true; if (rowA == rowB) return true; if (colA == colB) return true; if (Math.Abs(rowA - rowB) == Math.Abs(colA - colB)) return true; return false; } private int Pop(List<int> list) { int last = list[list.Count - 1]; list.Remove(last); return last; } private int Peek(List<int> list) { return list[list.Count - 1]; }}
测试
八皇后测试代码:Queen q = new Queen(8); q.PrintQueenResult();
结语
脑子不练会生锈,还是要经常做做这些最基础的东西,把不习惯变成习惯,慢慢来,不早了,先睡了
算法回顾--N皇后问题简单回顾
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。