N皇后问题
问题描述:
N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)
1.由于每个棋子不可能同行,因此可以理解为从棋盘每行拿个棋子出来
2.由于每列棋子也不相同,因此没有同一个数字可以在一个列
3.综合1,2,问题转化为给[0-7]做全排列,然后满足没有两个数字在同一个斜线
4.根据斜率公式 (x1-x2)/(y1-y2),因此根据这个条件排出同线的组合
5.余下的组合即为每行棋子的列位置,索引,就是行号
var MAX = 8;
var Ann = function a(arr){
if(arr.length == 1){return arr;}
var rr = new Array();
for(var i = 0; i<arr.length;i++){
//get a copy
var ar = new Array();
for(var j = 0; j < arr.length;j++){ar[j] = arr[j];}
//assume i
var current = ar[i];
ar.splice(i,1);
var childRet = a(ar);
for(var k = 0 ;k < childRet.length;k++){
var str = (current + "," + childRet[k]);
if(str.length != 2 * MAX-1 || !sameLine(str)){
rr.push(str);
}
}
}
return rr;
}
var initArr = new Array();
for(var i = 0;i < MAX; i++){initArr.push(i);}
var ret = Ann(initArr);
for(var i = 0;i < ret.length;i++){
outRet(ret[i]);
}
var count = 0;
function outRet(r) {
count = count + 1;
console.log("==============" + "," + count.toString());
var a = r.split(',');
for(var i = 0;i < MAX; i++){
var aa = new Array();
for(var j = 0;j < MAX; j++){
aa.push(0);
}
aa[a[i]] = 1;
console.log(aa);
}
}
function sameLine(str){
var arr = str.split(',');
for(var i = 0;i < arr.length; i++){
for(var j = 0;j < arr.length; j++){
if(i!=j&&Math.abs(i-j) == Math.abs(arr[i]-arr[j])){return true;}
}
}
return false;
}
分享到:
相关推荐
主要介绍了Java基于循环递归回溯实现八皇后问题算法,结合具体实例形式分析了java的遍历、递归、回溯等算法实现八皇后问题的具体步骤与相关操作技巧,需要的朋友可以参考下
这道题可以用递归循环来做,分别一一测试每一种摆法,直到得出正确的答案。主要解决以下几个问题: 1、冲突。包括行、列、两条对角线: (1)列:规定每一列放一个皇后,不会造成列上的冲突; (2)行:当第I行被...
递归回溯,像8皇后问题,本质上和多重for 循环是一样的
利用C++中的栈数据结构实现N皇后问题的求解,使用了回溯法(循环结构)而非递归调用。
八皇后问题要求在一个8*8的棋盘上放上8个皇后,使得每一个皇后既攻击不到另外七个皇后,也不被另外七个皇后所攻击.按照国际象棋的规则,一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子....
58.八皇后问题(回溯法) 59.求N阶幻方 60.计算分数的精确值 61.找零钱 62.求一元二次方程的根(公式法) 63.比赛日程(分治法) 64.两个有序数组的合并 65.统计投色子(2个)的结果 66.12小球问题 67.改进冒泡排序法 68....
该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的...
A 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决0/1背包问题的是(A ) A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照(C )的顺序。...
八皇后问题(回溯法) 求N阶幻方 计算分数的精确值 找零钱 求一元二次方程的根(公式法) 比赛日程(分治法) 两个有序数组的合并 统计投色子(2个)的结果 12小球问题 改进冒泡排序法 螺旋数组 射击环数 猜数字游戏 桶排序 ...
7 第 8 章 回溯法 8 .1 概述 8 .2 图问题中的回溯法 8 .3 组合问题中的回溯法 8 .4 实验项目— — —0/ 1 背包问题 阅读材料— — —禁忌搜索算法 习题 8 第 9 章 分支限界法 9 .1 概述 9 .2 图问题中的分支限界法 9...
3.6 回溯法 3.6.1 基本概念 3.6.2 四皇后问题求解 3.7 数值概率算法 3.7.1 基本概念 3.7.2 计算定积分 第2部分 编程实例解析 第4章 编程基本功 4.1 字符类型统计器 4.2 计算字符的ASCII码 4.3 嵌套if.else语句的妙...
N皇后问题回溯算法.c 万年历 动态计算网络最长最短路线.c 矩阵乘法动态规划.c 网络最短路径Dijkstra算法.c 货郎担分枝限界图形演示.c 货郎担限界算法.c 骑士遍历 ./问题算法/万年历: 万年历.c 万年历的算法 .c ...
N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...
16进制10进制.txt 32.txt asm.txt Crctable.txt C标志符命名源程序.txt erre.txt erre2.txt ff.txt for循环的.txt list.log N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt ...
n皇后问题 动态规划Dynamic Planning 应用 求最长公共子序列LCS 矩阵连乘问题 爬楼梯问题 找零问题 0-1背包问题 分治算法Divide and Conquer 应用:归并排序 其它 Rabin ...
N皇后问题回溯算法.txt ping.txt re.txt source.txt winsock2.txt ww.txt 万年历.txt 万年历的算法 .txt 乘方函数桃子猴.txt 乘法矩阵.txt 二分查找1.txt 二分查找2.txt 二叉排序树.txt 二叉树.txt ...