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

作者:goldensun 时间:2023-10-13 16:41:14 

数独规则
数独游戏,经典的为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;                      //成功找到一组解
}


标签:JavaScript,数独
0
投稿

猜你喜欢

  • Python流程控制语句详解

    2022-03-01 22:36:37
  • python数据可视化之matplotlib.pyplot基础以及折线图

    2023-03-04 22:10:01
  • Vue从TodoList中学父子组件通信

    2024-05-29 22:22:20
  • 在PHP程序中运行Python脚本(接收数据及传参)的方法详解

    2023-11-24 10:14:48
  • ASP调用系统ping命令代码

    2008-04-27 20:45:00
  • git设置忽略文件.gitignore的方法

    2023-05-18 02:12:19
  • 讲述SQL Server数据转换服务小妙招

    2010-07-26 14:43:00
  • 基于Jquery+Ajax+Json的高效分页实现代码

    2024-05-21 10:12:19
  • 深入了解Go语言中web框架的中间件运行机制

    2024-04-26 17:24:33
  • PyTorch数据读取的实现示例

    2022-01-31 04:15:48
  • Python实现的数据结构与算法之基本搜索详解

    2021-07-25 03:47:44
  • 解决Python3.8用pip安装turtle-0.0.2出现错误问题

    2021-04-07 03:51:20
  • Python数据可视化 pyecharts实现各种统计图表过程详解

    2022-04-08 17:28:37
  • 利用python Selenium实现自动登陆京东签到领金币功能

    2021-11-09 12:00:33
  • sql 中 case when 语法使用方法

    2024-01-19 13:31:13
  • 解决python写的windows服务不能启动的问题

    2023-01-21 04:10:38
  • 举例讲解Python常用模块

    2022-03-21 07:35:49
  • python中__init__()方法详情

    2023-06-05 21:22:46
  • 详解MySQL数据库之更新语句

    2010-08-08 09:15:00
  • 利用python实现简单的情感分析实例教程

    2021-12-27 18:19:42
  • asp之家 网络编程 m.aspxhome.com