JavaScript遍历求解数独问题的主要思路小结

数独规则
数独游戏,经典的为9×9=81个单元格组成的九宫格,同时也形成了3×3=9个小九宫格,要求在81个小单元格中填入数字1~9,并且数字在每行每列及每个小九宫格中都不能重复。

数独技巧

  • 直观法
  • 候选数法
  • 相关二十格:一个数字只与其所在行列及小九宫格的二十格相关

我的思路

  • 精心设计了有效性判定函数,最多一次遍历81个小单元格就能做出方案的有效性判定。
  • 同理设计了相关20格判定,一次0~9的循环就完成有效性判定。
  • 用数组模拟堆栈,为搜索提供回溯信息。
  • 利用对象具有map性质,来辅助判断方案的有效性,大大简化了算法。

方案设计与实现
只用了一个二维数组存储数独方案,一个一维数组作堆栈,一个布尔变量作回溯标识。

1.变量定义:

var problem = [        //这是书上提到的难度10.7的题
  [8,0,0,0,0,0,0,0,0],
  [0,0,3,6,0,0,0,0,0],
  [0,7,0,0,9,0,2,0,0],
  [0,5,0,0,0,7,0,0,0],
  [0,0,0,0,4,5,7,0,0],
  [0,0,0,1,0,0,0,3,0],
  [0,0,1,0,0,0,0,6,8],
  [0,0,8,5,0,0,0,1,0],
  [0,9,0,0,0,0,4,0,0]
]
var stack = [],flag = false;

2.方案有效性判定:
充分利用了javascript对象的哈希特性,为了方便调试,判定有效时函数的返回值为0,无效时分三种情况,行冲突、列冲突、小九宫格冲突,分别返回1,2,3。前期判定用了它,后来增加了相关二十格判定,在找答案时这个函数就用不上了。

function checkValid(sudo){
  let subSudo = {}            //辅助变量,用来判定小九宫格是否冲突
  for(let i = 0; i<9; i++){
    let row = {}, col = {}       //辅助变量,用来判定行、列是否冲突
    for(let j = 0; j<9; j++){
      let cur1 = sudo[i][j], cur2 = sudo[j][i]      //一次内循环同时完成行列的判定
      if(row[cur1])          //当前元素已经在行中出现,优化掉零的判断,key为0时值为0,不需要额外判断
        return 1;          //返回错误代码
      else
        row[cur1] = cur1      //当前元素未在行中出现,存入辅助变量中
      if(col[cur2])          //列的判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断
        return 2;
      else
        col[cur2] = cur2;
      let key = Math.floor(i/3)+'-'+Math.floor(j/3)    //为不同的小九宫格生成不同的key
      if(subSudo[key]){         //小九宫格中已经有元素,优化掉零的判断,key为0时值为0,不需要额外判断
        if(subSudo[key][cur1])    //对某一个小九宫格的判定与行类似
          return 3
        else
          subSudo[key][cur1] = cur1
      }else{              //这是某小九宫格中的第一个元素
        subSudo[key] = {}       //为小九宫格新建一个辅助变量,并将第一个元素存入其中
        subSudo[key][cur1] = cur1
      }
    }
  }
  return 0;                //程序能运行到这,说明方案有效
}

3.相关二十格判定
原理同整体判定,亮点在小九宫格的定位上。

function check20Grid(sudo,i,j){
  let row = {}, col = {}, subSudo = {}        //辅助变量
  for(let k = 0; k < 9; k++){
    let cur1 = sudo[i][k], cur2 = sudo[k][j]
    if(cur1){                    //当前元素已经在行中出现,优化掉零的判断,key为0时值为0,不需要额外判断
      if(row[cur1])
        return 1;                //返回错误代码
      else
        row[cur1] = cur1            //当前元素未在行中出现,存入辅助变量中
    }
    if(cur2){                    //列的判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断
      if(col[cur2])
        return 2;
      else
        col[cur2] = cur2;
    }
    //转化循环变量到小九宫格的坐标
    let key = sudo[Math.floor(i/3)*3 + Math.floor(k/3)][Math.floor(j/3)*3+Math.floor(k%3)]
    if(subSudo[key])                //九宫格判定与行类似,优化掉零的判断,key为0时值为0,不需要额外判断
      return 3
    else
      subSudo[key] = key
  }
  return 0;
}

4.遍历求解
利用元素状态初值为零的元素即为待定的特性,并加上堆栈的辅助,没有再开辟额外的存储空间。

function findAnswer(){
  for(let i = 0; i<9; i++){
    for(let j = 0; j<9; ){
      if(problem[i][j] === 0 || flag){       //当前位置为待定元素的首次处理或回溯到当前位置,两种情况看似不同,其实处理相同,自加1即可
        flag = false;
        let k = problem[i][j] + 1;        //搜索向下一个合法值迈进
        while(k<10){               //循环找到下一个合法值
          problem[i][j] = k;          //填值
          if(check20Grid(problem,i,j) == 0){  //判定合法,相关二十格判定
            stack.push([i,j++])        //存储回溯点,并步进
            break;
          }
          k++;
        }
        if(k>9){                 //当前位置找不到合法值,回溯
          problem[i][j] = 0;          //回溯前归零
          let rt = stack.pop();         //堆栈中取回溯信息
          if(!rt)                //无解判断,返回0
            return 0;
          i=rt[0]                //穿越
          j=rt[1]
          flag = true;
        }
      }else{                    //当前位置数字为题目给定
        j++;
      }
    }
  }
  return 1;                      //成功找到一组解
}
(0)

相关推荐

  • PHP实现的数独求解问题示例

    本文实例讲述了PHP实现的数独求解问题.分享给大家供大家参考,具体如下: 一.数独问题描述: 对于给出的数字二维数组,要求每行每列的数字不能重复. 二.实现代码: <?php /* 数独求解程序 * Created on 2017-4-18 * */ class Sudoku { var $matrix; function __construct($arr = null) { if ($arr == null) { $this->clear(); } else { $this->matr

  • Java实现解数独的小程序

    前言 数独相信很多人都玩过,趣味性很强,十分的耐玩.可有没有程序员想过玩实现一个数独布局的算法呢?算法是个很有意思,很神奇的东西. 算法如下,需要预先给出几个固定的值,目前解决的一个最难的数独是大概26个已知值的情况,理论上应该能解决任意已知值的数独,不过不知道会不会迭代栈溢出--因为在26个已知值的情况下就迭代了3000多次了,囧~~~ 结果显示如下: 这是已知值: 1 1 2 1 4 8 1 5 5 1 6 1 1 7 7 1 8 3 2 1 1 2 2 6 2 4 4 3 5 9 3 7

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • JQuery开发的数独游戏代码

    用了很多Jquery的插件,支持鼠标滚轮选数字.没有什么高深的技术点.工作原因很长时间没有更新了,具体代码都有些记不清了,欢迎大家来拍砖.截图:演示地址:http://demo.jb51.net/js/jsukudo/index.html下载地址:jsukudo20081110v0.3.0.5.zip 下载列表:http://code.google.com/p/jsukudo/downloads/list 用到的JS文件 文件名 出处 说明 blockUI.js http://malsup.co

  • Go语言实现的最简单数独解法

    soduku.go 复制代码 代码如下: package main import (     "fmt" ) type node []int var sudokuMay [9][9]node var Sudoku = [9][9]int{     {0, 0, 0, 0, 0, 0, 8, 0, 0},     {0, 8, 2, 4, 0, 0, 0, 0, 0},     {1, 9, 0, 0, 6, 3, 0, 0, 0},     {0, 5, 0, 0, 8, 0, 7,

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • PHP经典算法集锦【经典收藏】

    本文实例总结了PHP经典算法.分享给大家供大家参考,具体如下: 1.首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半. 思路:多少行for一次,然后在里面空格和星号for一次. <?php for($i=0;$i<=3;$i++){ echo str_repeat(" ",3-$i); echo str_repeat("*",$i*2+1); echo '<br/>'; } 2.冒泡排序,C里基础算法,从小到大对一组数

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • PHP实现的方程求解示例分析

    本文实例讲述了PHP实现的方程求解.分享给大家供大家参考,具体如下: 一.需求 1. 给出一个平均值X,反过来求出来,得到这个平均值X的三个数X1 ,X2, X3,最大值与最小值的差值要小于0.4(X1-X3都是保留1位小数的数) 2. 这三个数X1, X2, X3代表了三组数.满足下面的公式: X1 = [(m1 - m2)/(m1 - m0) ] * 100 (@1); m0, m1, m2三个数的边界条件如下: 1)48<m0<51 2)0.45<m1 - m1<0.55 3

  • php数字转汉字代码(算法)

    复制代码 代码如下: //将数字转换为汉字,比如1210转换为一千二百一十 $num = "842105580";//九位数 function del0($num) //去掉数字段前面的0 { return "".intval($num); } function n2c($x) //单个数字变汉字 { $arr_n = array("零","一","二","三","四"

  • python实现数独算法实例

    本文实例讲述了python实现数独算法的方法.分享给大家供大家参考.具体如下: # -*- coding: utf-8 -*- ''' Created on 2012-10-5 @author: Administrator ''' from collections import defaultdict import itertools a = [ [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0 [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1 [ 0, 6, 2

随机推荐