转载

数独求解（javascript实现）

看《算法的乐趣》，试着用非递归穷举来解数独，看效率如何！

数独规则

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

数独技巧

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

我的思路

精心设计了有效性判定函数，最多一次遍历81个小单元格就能做出方案的有效性判定，大部分情况，都会中途判定无效返回，因此没有再去设计相关二十格判定函数。
用数组模拟堆栈，为搜索提供回溯信息。
利用对象具有map性质，来辅助判断方案的有效性，大大简化了算法。

方案设计与实现

只用了一个二维数组存储数独方案，一个一维数组作堆栈，一个布尔变量作回溯标识。

变量定义

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;

方案有效性判定

充分利用了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(cur1){                        //行当前元素不为零                 if(row[cur1])                //当前元素已经在行中出现                     return 1;                //返回错误代码                 else                     row[cur1] = cur1        //当前元素未在行中出现，存入辅助变量中                  let key = Math.floor(i/3)+'-'+Math.floor(j/3)        //为不同的小九宫格生成key                 if(subSudo[key]){             //小九宫格中已经有元素                     if(subSudo[key][cur1])    //对某一个小九宫格的判定与行类似                         return 3                     else                         subSudo[key][cur1] = cur1                 }else{                        //这是某小九宫格中的第一个元素                     subSudo[key] = {}         //为小九宫格新建一个辅助变量，并将第一个元素存入其中                     subSudo[key][cur1] = cur1                 }             }             if(cur2){                        //列的判定与行类似                 if(col[cur2])                     return 2;                 else                     col[cur2] = cur2;             }         }     }     return 0;                                //程序能运行到这，说明方案有效 }

遍历求解

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

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(checkValid(problem) == 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++;             }         console.log('i:'+i+'---j:'+j)                //监视输出         }     }     return 1;                                        //成功找到一组解 }

完整代码

代码托管在开源中国，其中的sudoku.js即数独解法。

https://git.oschina.net/zhoutk/test.git

答案

书上提到的难度为10.7的题目的答案，十秒解决，效率还行。

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

原文 http://hao.jser.com/archive/10225/

正文到此结束