JavaScript实现三阶幻方算法谜题解答

谜题

三阶幻方。试将1~9这9个不同整数填入一个3×3的表格，使得每行、每列以及每条对角线上的数字之和相同。

策略

穷举搜索。列出所有的整数填充方案，然后进行过滤。

JavaScript解

代码如下:

/**
 * Created by cshao on 12/28/14.
 */

function getPermutation(arr) {
  if (arr.length == 1) {
    return [arr];
  }

var permutation = [];
  for (var i=0; i<arr.length; i++) {
    var firstEle = arr[i];
    var arrClone = arr.slice(0);
    arrClone.splice(i, 1);
    var childPermutation = getPermutation(arrClone);
    for (var j=0; j<childPermutation.length; j++) {
      childPermutation[j].unshift(firstEle);
    }
    permutation = permutation.concat(childPermutation);
  }
  return permutation;
}

function validateCandidate(candidate) {
  var sum = candidate[0] + candidate[1] + candidate[2];
  for (var i=0; i<3; i++) {
    if (!(sumOfLine(candidate,i)==sum && sumOfColumn(candidate,i)==sum)) {
      return false;
    }
  }
  if (sumOfDiagonal(candidate,true)==sum && sumOfDiagonal(candidate,false)==sum) {
    return true;
  }
  return false;
}
function sumOfLine(candidate, line) {
  return candidate[line*3] + candidate[line*3+1] + candidate[line*3+2];
}
function sumOfColumn(candidate, col) {
  return candidate[col] + candidate[col+3] + candidate[col+6];
}
function sumOfDiagonal(candidate, isForwardSlash) {
  return isForwardSlash ? candidate[2]+candidate[4]+candidate[6] : candidate[0]+candidate[4]+candidate[8];
}

var permutation = getPermutation([1,2,3,4,5,6,7,8,9]);
var candidate;
for (var i=0; i<permutation.length; i++) {
  candidate = permutation[i];
  if (validateCandidate(candidate)) {
    break;
  } else {
    candidate = null;
  }
}
if (candidate) {
  console.log(candidate);
} else {
  console.log('No valid result found');
}

结果

代码如下:

[ 2, 7, 6, 9, 5, 1, 4, 3, 8 ]

描绘成幻方即为：

代码如下:

2    7    6
9    5    1
4    3    8

分析

使用此策略理论上可以获取任意n阶幻方的解，但实际上只能获得3阶幻方这一特定解，因为当n>3时，获取所有填充方案这一穷举操作的耗时将变得极其巨大。

赞 (0)

相关推荐

  • 浅析java 归并排序算法

    浅析java 归并排序算法

    归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))

  • java字符串相似度算法

    本文实例讲述了java字符串相似度算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: public class Levenshtein {     private int compare(String str, String target) {         int d[][]; // 矩阵         int n = str.length();         int m = target.length();         int i; // 遍历str的      

  • 浅析java 希尔排序(Shell)算法

    浅析java 希尔排序(Shell)算法

    先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插入排序:然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<:-<d2<d1),即所有记录放在同一组中进行直接插入排序为止. 该方法实质上是一种分组插入方法. 原理图: 源代码 复制代码 代码如下: package com.zc.manythread; /**  *  * @author 偶my耶  *  *

  • 浅析java双向冒泡排序算法

    浅析java双向冒泡排序算法

    以整数升序排序为例来简单说明一下双向冒泡排序的过程:首先从前往后把最大数移到最后,然后反过来从后往前把最小的一个数移动到数组最前面,这一过程就是第一轮,然后重复这一过程,最终就会把整个数组从小到大排列好.双向冒泡排序要稍微优于传统的冒泡排序,因为双向排序时数组的两头都排序好了,我们只需要处理数组的中间部分即可,而单向即传统的冒泡排序只有尾部的元素是排好序的,这时每轮处理都需要从头一直处理到已经排好序元素的前面一个元素.虽然它在效率上有了点改进,但它也不能大幅度提高其排序的效率,这是由冒泡排序的基

  • JavaScript实现穷举排列(permutation)算法谜题解答

    谜题 穷举一个数组中各个元素的排列 策略 减而治之.递归 JavaScript解 复制代码 代码如下: /**  * Created by cshao on 12/23/14.  */ function getPermutation(arr) {   if (arr.length == 1) {     return [arr];   } var permutation = [];   for (var i=0; i<arr.length; i++) {     var firstEle = a

  • 浅析java快速排序算法

    浅析java快速排序算法

    快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正 确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)

  • 浅析java贪心算法

    贪心算法的基本思路 1.建立数学模型来描述问题. 2.把求解的问题分成若干个子问题. 3.对每一子问题求解,得到子问题的局部最优解. 4.把子问题的解局部最优解合成原来解问题的一个解. 实现该算法的过程: 从问题的某一初始解出发: while 能朝给定总目标前进一步 do 求出可行解的一个解元素: 由所有解元素组合成问题的一个可行解. 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题

  • JavaScript实现N皇后问题算法谜题解答

    谜题 N皇后问题.将N个皇后放置在NxN的国际象棋棋盘上,其中没有任何两个皇后处于同一行.同一列或同一对角线上,以使得它们不能互相攻击. 策略 回溯法. JavaScript解 以8皇后问题为例: 复制代码 代码如下: /**  * Created by cshao on 12/28/14.  */ function getNQueens(order) {   if (order < 4) {     console.log('N Queens problem apply for order b

  • 浅析java 循序与二元搜索算法

    浅析java 循序与二元搜索算法

    循序搜索法 就是一个一个去比较,找到时返回: 二元搜索法 二元搜索算法是在排好序的数组中找到特定的元素. 首先, 比较数组中间的元素,如果相同,则返回此元素的指针,表示找到了. 如果不相同, 此函数就会继续搜索其中大小相符的一半,然后继续下去. 如果剩下的数组长度为0, 则表示找不到,那么函数就会结束. 实现代码: 复制代码 代码如下: package com.zc.manythread; import java.util.Random; import java.util.Scanner; /*

  • JavaScript实现三阶幻方算法谜题解答

    谜题 三阶幻方.试将1~9这9个不同整数填入一个3×3的表格,使得每行.每列以及每条对角线上的数字之和相同. 策略 穷举搜索.列出所有的整数填充方案,然后进行过滤. JavaScript解 复制代码 代码如下: /**  * Created by cshao on 12/28/14.  */ function getPermutation(arr) {   if (arr.length == 1) {     return [arr];   } var permutation = [];   f

  • javascript解三阶幻方（九宫格）

    谜题:三阶幻方, 试将1~9这9个不同整数填入一个3×3的表格,使得每行.每列以及每条对角线上的数字之和相同. 策略:穷举搜索.列出所有的整数填充方案,然后进行过滤. 亮点为递归函数getPermutation的设计,文章最后给出了几个非递归算法 // 递归算法,很巧妙,但太费资源 function getPermutation(arr) { if (arr.length == 1) { return [arr]; } var permutation = []; for (var i = 0;

  • JavaScript实现的Tween算法及缓冲特效实例代码

    JavaScript实现的Tween算法及缓冲特效实例代码

    本文实例讲述了JavaScript实现的Tween算法及缓冲特效.分享给大家供大家参考,具体如下: 这里演示Tween 算法及缓冲特效的JavaScript代码,利用它可以做缓动.弹簧等很多动画效果,怎么利用flash的Tween类的算法,来做js的Tween算法,并利用它做一些简单的缓动效果呢,看懂了本代码你就明白了. 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/js-tween-run-style-codes/ 具体代码如下: <!DOC

  • JavaScript实现算术平方根算法-代码超简单

    前几天看见了一个来自雷神之槌的平方根源码,原理多方有介绍,不赘述. 源码是c语言写的,我思考后发现这样的算法在javascript中也是可以完成的. function InvSqrt(x){ var h=0.5*x; var b=new ArrayBuffer(4); var d=new DataView(b,0); d.setFloat32(0,x); var i=d.getInt32(0); i=0x5f375a86-(i>>1); d.setInt32(0,i); var r=d.get

  • JavaScript使用二分查找算法在数组中查找数据的方法

    本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

  • JavaScript实现微信红包算法及问题解决方法

    专栏停更了很久,向大家说声抱歉.今天的主题是使用JavaScript模拟实现微信抢红包的算法.这个题目看起来很简单,不就是一个随机函数吗?我们一起实现看看. 我们假设有一个100元的红包,要发给10个人.为了保证公平,算法需要保证以下的原则: 每个人最少能抢到0.01元 每个人的机会平等 所有人的金额之和等于100元 1.简单的随机函数实现 很多朋友的一般思路是: 第一步:从0-100中随机一个数,得到第一个红包金额. 第二步:从0-剩余金额中随机一个数,得到第二个红包金额. 第三步:... 最

  • JavaScript实现的级联算法示例【省市二级联动功能】

    JavaScript实现的级联算法示例【省市二级联动功能】

    本文实例讲述了JavaScript实现的级联算法.分享给大家供大家参考,具体如下: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta ht

  • 基于javascript实现获取最短路径算法代码实例

    这篇文章主要介绍了基于javascript实现获取最短路径算法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 //A算法 自动寻路 路径 class GetAutoPath{ constructor(id, map, sPos, ePos, mapArr){ //this.type = id.type; this.id = id; this.map = map; this.sPos = sPos; this.ePos = eP

随机推荐