每周算法练习——n皇后问题

一、八皇后问题的描述

    八皇后问题是一个以国际象棋为背景的问题:如何能够在8×8的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。(摘自维基百科)

    其实这里是作为我的一个算法练习,在以前的学习中,我曾经使用过GA算法实现过八皇后问题,主要的思路是将八皇后问题转化成为一种组合优化问题,设置在不同情况下的适应值的大小,当然,在组合中有重复的和在对角线上的被视为不符合要求的,假设设计的是求问题的最小值,那么此时的适应值便会设计得很大,这样便不会选择这样的解。在以后的更新中我会将那部分程序和原理更新到这个平台上。

二、求解思路

    在这里,主要是使用最原始的方式求解。其实八皇后问题或者n皇后问题可以通过深度优先搜索(DFS)的方式求解。

(摘自:http://blog.sina.com.cn/s/blog_eb52001d0102v284.html)

所以此时就可以使用递归的方式去查询。这是个简单的问题,我是拿来练手的。。。顺便充一篇博文,这样是不是不好。。。

Java代码:

package org.algorithm.nqueens;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 用深度优先搜索查找N皇后问题
 * 
 * @author dell
 * 
 */
public class SolveNQueens {
	public static void main(String args[]) {
		ArrayList<Integer> array = new ArrayList<Integer>();
		ArrayList<String> arrayResult = new ArrayList<String>();
		int n = 9;
		returnNQueen(array, arrayResult, n);
		System.out.println("总的解的个数为:" + arrayResult.size());
		Iterator<String> it = arrayResult.iterator();
		while (it.hasNext()) {
			System.out.println(it.next());
		}
	}
	
	/**
	 * 深度优先搜索DFS可以采用递归的方式求解
	 * @param array为存储的是数字,表示每一行的皇后所在的列数
	 * @param arrayResult为一个解,主要把解转换成字符串
	 * @param n皇后的问题规模
	 */
	public static void returnNQueen(ArrayList<Integer> array,
			ArrayList<String> arrayResult, int n) {
		// 判断ArrayList是否已满
		if (array.size() == n) {
			arrayResult.add(array.toString());
		}
		// 没满的情况
		for (int i = 0; i < n; i++) {
			if (checkIsNQueen(array, i)) {
				array.add(i);
				returnNQueen(array, arrayResult, n);//递归求解
				array.remove(array.size() - 1);
			}
		}
	}
	
	/**
	 * 对解进行检查,主要有两种:1、皇后出现在同一列上
	 * 2、皇后在两个对角线上
	 * @param array存放的以求出的皇后的位置
	 * @param k新的皇后的位置
	 * @return 如果将新的皇后插入,检查此时是否会有冲突
	 */
	public static boolean checkIsNQueen(ArrayList<Integer> array, int k) {
		int n = array.size();// 得到数组的大小
		for (int i = 0; i < n; i++) {
			// 第一种情况
			if (array.get(i) == k) {
				return false;
			}
			
			// 第二种情况
			if (n - i == Math.abs(k - array.get(i))) {
				return false;
			}
		}
		return true;
	}

}

部分结果:

(当n=9时)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Gym 100952E&&2015 HIAST Collegiate Programming Contest E. Arrange Teams【DFS+剪枝】

E. Arrange Teams time limit per test:2 seconds memory limit per test:64 megabyte...

2686
来自专栏程序你好

二叉树搜索树(程序员都知道)

4101
来自专栏lhyt前端之路

从MDN上的canvas例子受到的启发0.前言1.面向对象编程的实践2.相互纠缠的现象3.解决方案4.模拟核裂变5.大鱼吃小鱼

在面对碰撞检测后还有后续动作的情况,必须考虑一下相互纠缠的问题: 如果两个小球被检测到碰撞的时候,而且加上他们的速度下一步还是处于碰撞范围内,就像引力一样无法脱...

1432
来自专栏owent

POJ PKU 1986 Distance Queries 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1986

792
来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

953
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

2008
来自专栏数据科学学习手札

(数据科学学习手札06)Python在数据框操作上的总结(初级篇)

数据框(Dataframe)作为一种十分标准的数据结构,是数据分析中最常用的数据结构,在Python和R中各有对数据框的不同定义和操作。 Python 本文涉及...

6905
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

2011
来自专栏aCloudDeveloper

LeetCode:149_Max Points on a line | 寻找一条直线上最多点的数量 | Hard

题目:Max Points on a line Given n points on a 2D plane, find the maximum number of...

26810
来自专栏灯塔大数据

每周学点大数据 | No.5算法的分析之图灵机

No.5期 算法的分析之图灵机 小可:那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢? Mr. 王:有的,这里既然提到了多项式算法和易解难解问题,...

3768

扫码关注云+社区

领取腾讯云代金券