Web page example of Sudoku problem solving algorithm implemented in Javascript

1) When we get a question, we will first conduct a preliminary sorting and analysis of the data based on the conditions we already know.

It is equivalent to filling out all the "determined items" in the 9-square grid and marking the "possible options".

function refreshStat()

2) After that, thinking will enter the guessing/verifying cycle stage.

In the 9-square grid, you can try the "possible options" to verify whether they violate the existing conditions.

For every new branch, the final result is nothing more than two, answer/error.

Copy code The code is as follows:

 While (true) {
 var a = setone ();
 var b=refreshStat();
 if(!a||b){ //If a==false or b==ture, you can break out of the loop
 break;
 }
     }

The actual thinking process of the human brain also involves traversing branches with fewer options first.
So, the program implementation is also determined point/2-branch/3-branch/....

3) When all the paths are searched, the answer is not the only one, which is contrary to the purpose of the Sudoku game.

The following part is the entire code. For the convenience of reading, the debugging information has not been deleted.

Copy code The code is as follows:

数独解题程序

<script> function keygo(evt,obj){ key = window .event?evt.keyCode:evt.which; var next=obj.tabIndex ; var inputs=document.getElementsByTagName("input"); if (key==38){//↑ if (next -9>=0 ) { inputs[next-9].select() } } if (key==40){//↓ if (next +9<81 ) { inputs[next+9].select() } } if (key==37){//← if (next -1>=0 ) { inputs[next-1].select() } } if (key==39){//→ if(next+1<81)inputs[next+1].select(); } } </script>

可以文本拷贝到下框中后点粘贴，从左到右从上往下的81个数字序列，未填为0，中间非数字字符将忽略

<script> var maxRow =9; var maxCol = 9; var strTbody = ["<table id='sodukuTable' border='0'><tbody>"]; for(var i = 0; i < maxRow; i++){ strTbody.push("<tr>"); for(var j = 0; j < maxCol; j++){ strTbody.push("<td style='border-left:"+(j%3==0?1:0) +"px solid black ;border-right:"+(j%3==2?1:0) +"px solid black;border-top:"+(i%3==0?1:0) +"px solid black;border-bottom:"+(i%3==2?1:0)+"px solid black;' ><input style='width:20px;' tabindex='"+(i*9+j) +"'onclick='check(this);' onKeyUp='return keygo(event,this)'type='text' id='input"+(i*9+j)+"'name='n"+(i*9+j)+"'value='"+i+j+"' ></td>"); } strTbody.push("</tr>"); } strTbody.push("</tbody></table>"); var sTbody = ["<table border='1'><tbody>"]; for(var i = 0; i < maxRow; i++){ sTbody.push("<tr>"); for(var j = 0; j < maxCol; j++){ sTbody.push("<td style='border-left:"+(j%3==0?1:0) +"px solid black ;border-right:"+(j%3==2?1:0) +"px solid black;border-top:"+(i%3==0?1:0) +"px solid black;border-bottom:"+(i%3==2?1:0)+"px solid black;'><div style='width:25px;height:25px' id='status"+(i*9+j)+"'name='div"+i+j+"' ></div></td>"); } sTbody.push("</tr>"); } sTbody.push("</tbody></table>"); var obj = document.getElementById("sodukuTable"); obj.innerHTML = strTbody.join(""); var obj2 = document.getElementById("statusDiv"); var grid=[ [5, 7, 0, 1, 2, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 6, 7, 0, 0, 0, 8, 0], [3, 0, 4, 0, 0, 9, 0, 7, 0], [0, 2, 0, 0, 7, 0, 0, 5, 0], [0, 1, 0, 3, 0, 0, 9, 0, 2], [0, 8, 0, 0, 0, 2, 1, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 5, 4, 0, 6, 3]]; var candidatNum=[]; var columns=[]; var rows=[]; var blook=[]; var papers=0; var discards=0; var success=false; var steps = new Array(); var log1 = document.getElementById("statusDiv"); function Step(current1,arrys){ this.temp1=new Array(); this.step=[arrys[0],arrys[1],arrys[2]]; for (var i = 0; i < 9; i++) { this.temp1[i]=new Array(); for (var j = 0; j < 9; j++) { this.temp1[i][j]=current1[i][j]; } } } out(grid); init(); function push( current1, i, j, n) { var s = new Step(current1, [ i, j, n ]); steps.push(s); } function pop(){ var step = steps.pop(); discards ++; grid=step.temp1; grid[step.step[0]][step.step[1]] = step.step[2]; var timeline = document.getElementById('PaperList'); timeline.value += ('discard: ['+discards+']:['+papers+']\n'); timeline.scrollTop = timeline.scrollHeight; return step; } function check(obj){ if(obj.value==0)return; for(var i=0;i<9;i++){ for(var j=0;j<9;j++){ var text = document.getElementById("input"+(i*9+j)); if(text.value==obj.value){ text.style.background="green"; }else{ text.style.background=""; } } } } function CheckNumInput(array,num, x, y) { // 目标: // 冲突检查参数 array:矩阵 num:检测值 x/y:检测位置 // 行列宫均无冲突,return true; // 发现冲突,return false; if (((rows[x] & (1 << num)) == 0) && (columns[y] & (1 << num)) == 0 && (blook[parseInt(x / 3) * 3 + parseInt(y / 3)] & (1 << num)) == 0) { return true; } return false; }function out(array){ var result=true; for (var i = 0; i < 9; i ) { for (var j = 0; j &lt 9; j ) =0) result = false; > // Traverse the matrix to see if it can be simply refreshed or the error can be found. for (var i = 0; i < 9; i ) { for (var j = 0; j < 9 ; j ) { // (grid[i][j] == 0 && candidatNum[i][j][0] == 0) >> No candidate number, Something went wrong ,j) >> Check whether this number is logical // Determine that there are no candidate numbers || The last candidate number does not meet the logical conditions, fall back from here or return an error if (grid[i] [j] == 0 && candidatNum[i][j][0] == 0 || ][10],i,j))) { If (steps.length>0 ) {// Retreat POP (); // The current label has been proven to be logical errors, abandoned Return true; } else { if (! Success) { Alert (Alert (Alert (Alert "The stack is empty and ends!"); //题目出错,结束 } return false; } } if (candidatNum[i][j][0] == 1) { //唯一选择 grid[i][j] = candidatNum[i][j][10]; // 更新矩阵 refreshStat3(candidatNum[i][j][10],i,j); // 更新行列宫 candidatNum[i][j][0] = 0; // 标记已选 result = true; continue; } } } if (result == false) { //对于(candidatNum[i][j][0] != 1)的情况,进行筛选 return choose(); } return result; } function refreshStat3( num, x, y) { // 更新行列宫 rows[x] |= 1<<num; columns[y] |= 1<<num; blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num ; } /********************* * 矩阵数据分析 * 统计剩余可选项 *********************/ function refreshStat(){ var over = true; // 目标: // 分解行/列/宫 for (var i = 0; i < 9; i++) { rows[i] = 0; //行 columns[i] = 0; //列 blook[i] = 0; //宫 for (var j = 0; j < 9; j++) { if (grid[i][j] != 0) { rows[i] |= 1 << grid[i][j]; } else { rows[i] &= ~(1 << grid[i][j]); } if (grid[j][i] != 0) { columns[i] |= 1 << grid[j][i]; } else { columns[i] &= ~(1 << grid[j][i]); } if (grid[parseInt(i / 3) * 3 + parseInt(j / 3)][i % 3 * 3 + j % 3] != 0) { blook[i] |= 1 << grid[parseInt(i / 3 )* 3 + parseInt(j / 3)][i % 3 * 3 + j % 3]; } } } // 目标: // 遍历矩阵,进行候选标记candidatNum[i][j][0] // candidatNum[i][j][0] = 0; >>>> 已有确定值 // candidatNum[i][j][0] = k; >>>> 可能值数目 // candidatNum[i][j][1] = 987654321x 2进制数位表示的可选数字 for (var i = 0; i < 9; i++) { for (var j = 0; j < 9; j++) { if (grid[i][j] != 0) { candidatNum[i][j][0] = 0; continue; } var size = 0; over = false; for (var k = 1; k < 10; k++) { if (CheckNumInput(grid, k, i, j)) { candidatNum[i][j][1] |= 1 << k; candidatNum[i][j][10] = k; over = false; size++; } else { candidatNum[i][j][1] &= ~(1 << k); } } candidatNum[i][j][0] = size; //标记剩余选项数目 } } return over; }function calculate(){ //Function entry //Read data var start=new Date(); for (var i = 0; i < 9; i ) grid[i ][j]=parseInt(text.value); } } //Refresh the grid refreshStat(); out(grid); / /Calculate matrix while(true){ var a=setOne(); var b=refreshStat(); if(!a||b){ //If a==false Or b==ture, you can break out of the loop break; ) "ms"); success = true; //Computation ends //Verify whether the answer is unique if (papers != discards){ if (steps. length>0) {//Back pop(); // Current label is discarded //Calculate matrix while(true){ var a=setOne(); var var b=refreshStat(); if(!a||b){ //If a==false or b==ture, you can break out of the loop break; } } if (b) { if (b) { alert("The answer is not unique! Record! " ); //The only answer } } else { alert("Error ended!"); return false; } } } function clearGrid(){ for (var i = 0; i < 9; i++){ for (var j = 0; j < 9; j++){ grid[i][j]=0; document.getElementById("input"+(i*9+j)).value=grid[i][j]; } } out(grid); } function init(){ for (var i = 0; i < 9; i++) { candidatNum[i]=new Array(); for (var j = 0; j < 9; j++) { candidatNum[i][j]=new Array(); for (var k = 0; k < 11; k ) { candidatNum[i][j][k]=0; } } } } function choose() { //Goal: // Traverse the matrix and establish a search branch from the current position. var binarynode = false; for (var i = 0; i &lt ; 9; i ) { for (var j = 0; j < 9; j ) { // 2-way tree branch: // If there are two possibilities at a certain position, option 1 /Options 2 </> // The assumption is option 1, and the verification is performed. 2 options binarynode = true; var found = -1; for (var k = 1; k < 10; k ) { if ((candidatNum[i][j] [1] & (1 << k)) > 0) { var timeline = document.getElementById('PaperList'); timeline.value = ('add papers:' papers ':' i ' ' j ' ' k 'n'); push(grid, i, j, k); } else { Found = k; } } } Grid [i] [j] = Found; Candidatnum [i] [j] ][0] = 0; // Mark selected on the current label var timeline = document.getElementById('PaperList'); timeline.value = ('TRY CURRENT:' i ' ' j ' ' found 'n'); timeline.scrollTop = timeline.scrollHeight; return true; } } } if (!binarynode) { var timeline = document.getElementById('PaperList'); timeline.value = ('2-branch not found!n'); timeline.scrollTop = timeline.scrollHeight; for (var i = 0; i < 9; i ) { for (var j = 0; j < 9; j ) { // 2-way tree search failed When , start the 3-way tree branch. As an extension, you can also start the 3-way tree branch: , and perform verification, and press option 2 to generate a new label if (candidatNum[i][j][0] == 3) {// There are 3 options var timeline = document.getElementById( 'PaperList'); timeline.value = ('3-branch found!n'); timeline.scrollTop = timeline.scrollHeight; binarynode = true; var found = -1; for (var k = 1; k < 10; k ) { if ((candidatNum[i][j][1] & (1 << k)) > 0) { If (Found & GT; 0) { Papers; VAR TIMELINE = DOCUMENT.GetelementByid ('PaperList'); '' j 'k' n '); Timeline.scrolltop = Timeline.scrollheight; Push (Grid, I, J, K); } else { Found = k; } grid[i][j] = found; candidatNum[i][j][0] = 0; // Mark selected on the current label var timeline = document.getElementById('PaperList '); timeline.value = ('TRY CURRENT:' i ' ' j ' ' found 'n'); timeline.scrollTop = timeline.scrollHeight; return true; . 🎜> a = gridstr.replace(/[^0-9]/g,''); if(a.length!=81){ alert("Incorrect data format: n" gridstr); return; } for (var i = 0; i < 9; i ) { for (var j = 0; j < 9; j ){ grid[i][j]=a.charAt(i*9 j); document.getElementById("input" (i*9 j)).value=grid[i][j]; } } out(grid); papers = 0; discards = 0; success = false; steps = new Array(); } </script>
It is recommended to use IE browser, F12 to enable debugging mode

Web page example of Sudoku problem solving algorithm implemented in Javascript_javascript skills