Javascript implementation of the sudoku algorithm web page example
- 2020-03-26 21:31:36
- OfStack
1) when we get a topic, we will first sort out and analyze the data according to the conditions we already know.
This is equivalent to filling out 9 boxes, all the "ok items", and marking "possible options".
The function refreshStat ()
2) after that, the thinking moves into a guessing/verification cycle.
In the box 9, you can try out the "possible options" to verify that an existing condition is violated.
For each new branch, the end result is nothing more than two answers/errors.
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //If a==false or b== true, the loop can be broken
break;
}
}
The actual process of human thinking also involves traversing the less selective branches first.
Therefore, the program implementation is also determined by the point /2 fork /3 fork /...
3) when all the paths are searched down, the answer is not the only case, is contrary to the purpose of sudoku.
The following part is the entire code. For easy reading, the debugging information has not been deleted.
<html>
<head>
<title> Sudoku program </title>
<meta http-equiv="Content-Type" content="text/html; charset=GBK" />
<script>
function keygo(evt,obj){
key = window .event?evt.keyCode:evt.which;
var next=obj.tabIndex ;
var inputs=document.getElementsByTagName("input");
if (key==38){// write
if (next -9>=0 ) {
inputs[next-9].select()
}
}
if (key==40){// left
if (next +9<81 ) {
inputs[next+9].select()
}
}
if (key==37){// please
if (next -1>=0 ) {
inputs[next-1].select()
}
}
if (key==39){// -
if(next+1<81)inputs[next+1].select();
}
}
</script>
</head>
<body onload="init();">
<div id="sodukuTable"></div><input type=button name="cal" onclick="calculate()" value=" To calculate ">
<input type=button name="clear" onclick="clearGrid()" value=" empty ">
<br><span><textarea id="gtxt" cols="19" rows="10">004502006
000000005
002014007
008000012
070080050
930020700
600190200
020000000
300208500</textarea></span>
<input type=button name="cal" onclick="paste()" value=" paste " > You can copy the text into the box below and then paste it, from left to right, from top to bottom 81 Sequence of Numbers, not filled in as 0 , intermediate non-numeric characters will be ignored <br>
<span></span><br><span id="statusDiv"></span><span id="log"></span>
<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) {
// Goal:
// Conflict check & NBSP; Parameter array: matrix num: check value x/y: check position
// There is no conflict between rows and rows,return true;
// Conflict detected,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 < 9; j++)
{
document.getElementById("input"+(i*9+j)).value=array[i][j];
if(array[i][j]==0)result=false;
}
}
return result;
}
function setOne(){
var result = false;
//Goal:
// Traversing the matrix, whether it is currently easy to refresh, or can already detect errors.
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
//Goal:
//(grid [I] [j] = = 0 && candidatNum [I] [j] [0] = = 0) >> There are no candidate Numbers
//(candidatNum [I] [j] [0] = = 1) >> Candidate number unique
//CheckNumInput (grid, candidatNum [I] [j] [10], I, j) >> Check that this number is logical
//Judge that there is no candidate number || the last candidate number is not a logical condition,& NBSP; There was a fallback or return error from here
if (grid[i][j] == 0 && candidatNum[i][j][0] == 0||
(candidatNum[i][j][0] == 1&&!CheckNumInput(grid,candidatNum[i][j][10],i,j))) {
if (grid[i][j] == 0) {
result = false;
}
if (steps.length>0) {// The fallback
pop(); //The current tag has been proven to be logically incorrect and deprecated
return true;
} else {
if (!success) {
alert(" The stack is empty The end! "); //They're wrong. End
}
return false;
}
}
if (candidatNum[i][j][0] == 1) { //The only choice
grid[i][j] = candidatNum[i][j][10]; // Update matrix
refreshStat3(candidatNum[i][j][10],i,j); // Palace of renewal
candidatNum[i][j][0] = 0; // Mark the selected
result = true;
continue;
}
}
}
if (result == false) { //For (candidatNum [I] [j] [0]! = 1), select
return choose();
}
return result;
}
function refreshStat3( num, x, y) { // Palace of renewal
rows[x] |= 1<<num;
columns[y] |= 1<<num;
blook[parseInt(x / 3) * 3 + parseInt(y / 3)] |= 1 << num ;
}
function refreshStat(){
var over = true;
// Goal:
// Break down the rows/columns/houses
for (var i = 0; i < 9; i++) {
rows[i] = 0; // line
columns[i] = 0; // column
blook[i] = 0; // palace
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];
}
}
}
// Goal:
// Traversal matrix for candidate marker candidatNum[I][j][0]
// CandidatNum [I] [j] [0] = 0; >>>> Established value
// CandidatNum [I] [j] [0] = k; >>>> Number of possible values
// CandidatNum [I] [j] [1] = 987654321 x An optional digit represented by a base 2 digit
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; //Mark the number of remaining options
}
}
return over;
}
function calculate(){ //Function of entrance
//Read the data
var start=new Date();
for (var i = 0; i < 9; i++)
{
for (var j = 0; j < 9; j++)
{
var text = document.getElementById("input"+(i*9+j));
grid[i][j]=parseInt(text.value);
}
}
//Refresh the grid & cake;
refreshStat();
out(grid);
//Calculation of matrix
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //If a==false or b== true, the loop can be broken
break;
}
}
out(grid); // The answer
alert(" Available: "+(new Date()-start)+"ms");
success = true;
//Calculate the end
//Verify that the answer is unique
if (papers != discards){
if (steps.length>0) {// The fallback
pop(); //Current label discard
//Calculation of matrix
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //If a==false or b== true, the loop can be broken
break;
}
}
if (b) {
alert(" Not the only answer! Record! ");
out(grid); // The answer
}
else {
alert("The only answer !!!!! "); //The only answer
}
} else {
alert(" error The end! ");
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:
// Traverses the matrix, creating a search branch from the current location.
var binarynode = false;
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
// 2 branches:
// If there are two possibilities at a certain location, choice 1 over choice 2
// Then assume option 1 and check it. At the same time, generate a new label according to option 2
if (candidatNum[i][j][0] == 2) {//There are two choices
binarynode = true;
var found = -1;
for (var k = 1; k < 10; k++) {
if ((candidatNum[i][j][1] & (1 << k)) > 0) {
if (found > 0) {
papers ++;
var timeline = document.getElementById('PaperList');
timeline.value += ('add papers:'+papers+':'+i+' '+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;
}
}
}
if (!binarynode) {
var timeline = document.getElementById('PaperList');
timeline.value += ('2 Fork branch not found !n');
timeline.scrollTop = timeline.scrollHeight;
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
//If the two-tree search fails, the three-tree branch can be started. As an extension, the three-tree branch can also be started:
// If there are three possibilities in a location, choice 1 over choice 2 over choice 3
// Then assume option 1 and check it. At the same time, generate a new label according to option 2
if (candidatNum[i][j][0] == 3) {//There are three options
var timeline = document.getElementById('PaperList');
timeline.value += (' found 3 Fork branch !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 > 0) {
papers ++;
var timeline = document.getElementById('PaperList');
timeline.value += ('add papers:'+papers+':'+i+' '+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;
}
}
}
}
return false;
}
function paste(){
var gridstr= document.getElementById("gtxt").value;
var a = gridstr.replace(/[^0-9]/g,'');
if(a.length!=81){
alert(" The data format is incorrect :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 The browser ,F12 Turn on debug mode <br>
<br><span>
<textarea id="PaperList" cols="30" rows="20" style="position:absolute;left:550px;"></textarea></span>
</body>
</html>