Javascript 實(shí)現(xiàn)的數(shù)獨(dú)解題算法網(wǎng)頁(yè)實(shí)例
1）當(dāng)我們拿到一個(gè)題目時(shí)，首先會(huì)根據(jù)已經(jīng)知道的條件，進(jìn)行數(shù)據(jù)的初步整理和分析。
相當(dāng)于填寫(xiě)出9宮格里，所有的“確定項(xiàng)”，以及標(biāo)記“可能選項(xiàng)”。
function refreshStat()
2）此后，思考會(huì)進(jìn)入 猜測(cè)/驗(yàn)證 的循環(huán)階段。
在9宮格中，可以對(duì)于“可能選項(xiàng)”進(jìn)行嘗試，驗(yàn)證是否違背現(xiàn)有條件。
每一個(gè)新的分支，最后的結(jié)果無(wú)非是兩種，答案/出錯(cuò)。
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,則可以跳出循環(huán)
break;
}
}
實(shí)際人腦思考的過(guò)程，也是要先遍歷選項(xiàng)較少的分支。
所以，程序?qū)崿F(xiàn)上也是 確定點(diǎn)/2叉分支/3叉分支/....
3）當(dāng)所有的路徑搜索下來(lái)，答案不是唯一的情況，是和數(shù)獨(dú)游戲的宗旨相悖的。
以下部分是全部代碼，為方便閱讀，調(diào)試信息未刪除。
<html>
<head>
<title>數(shù)獨(dú)解題程序</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){//↑
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>
</head>
<body onload="init();">
<div id="sodukuTable"></div><input type=button name="cal" onclick="calculate()" value="計(jì)算">
<input type=button name="clear" onclick="clearGrid()" value="清空">
<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="粘貼" >可以文本拷貝到下框中后點(diǎn)粘貼，從左到右從上往下的81個(gè)數(shù)字序列，未填為0，中間非數(shù)字字符將忽略<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) {
// 目標(biāo):
// 沖突檢查 參數(shù) array:矩陣 num:檢測(cè)值 x/y:檢測(cè)位置
// 行列宮均無(wú)沖突,return true;
// 發(fā)現(xiàn)沖突,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;
//目標(biāo):
// 遍歷矩陣,當(dāng)前是否可以簡(jiǎn)單刷新,或者已經(jīng)可以發(fā)現(xiàn)出錯(cuò).
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
//目標(biāo):
// (grid[i][j] == 0 && candidatNum[i][j][0] == 0) >> 沒(méi)有候選數(shù)字,出錯(cuò)了
// (candidatNum[i][j][0] == 1) >> 候選數(shù)字唯一
// CheckNumInput(grid,candidatNum[i][j][10],i,j) >> 檢查此數(shù)字是否符合邏輯
// 判斷 沒(méi)有候選數(shù)字||最后一個(gè)候選數(shù)字不符合邏輯的條件, 從這里回退或者返回出錯(cuò)
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) {// 回退
pop(); // 當(dāng)前標(biāo)簽已經(jīng)被證明邏輯錯(cuò)誤,廢棄
return true;
} else {
if (!success) {
alert("棧為空 結(jié)束！"); //題目出錯(cuò),結(jié)束
}
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; // 標(biāo)記已選
result = true;
continue;
}
}
}
if (result == false) { //對(duì)于(candidatNum[i][j][0] != 1)的情況,進(jìn)行篩選
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 ;
}
/*********************
* 矩陣 數(shù)據(jù)分析
* 統(tǒng)計(jì) 剩余可選項(xiàng)
*********************/
function refreshStat(){
var over = true;
// 目標(biāo):
// 分解行/列/宮
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];
}
}
}
// 目標(biāo):
// 遍歷矩陣,進(jìn)行候選標(biāo)記candidatNum[i][j][0]
// candidatNum[i][j][0] = 0; >>>> 已有確定值
// candidatNum[i][j][0] = k; >>>> 可能值數(shù)目
// candidatNum[i][j][1] = 987654321x 2進(jìn)制數(shù)位表示的可選數(shù)字
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; //標(biāo)記剩余選項(xiàng)數(shù)目
}
}
return over;
}
function calculate(){ //功能入口
//讀取數(shù)據(jù)
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);
}
}
//刷新網(wǎng)格
refreshStat();
out(grid);
//計(jì)算矩陣
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,則可以跳出循環(huán)
break;
}
}
out(grid); //答案
alert("用時(shí)："+(new Date()-start)+"ms");
success = true;
//計(jì)算結(jié)束
//驗(yàn)證答案是否唯一
if (papers != discards){
if (steps.length>0) {// 回退
pop(); // 當(dāng)前標(biāo)簽廢棄
//計(jì)算矩陣
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,則可以跳出循環(huán)
break;
}
}
if (b) {
alert("答案不唯一！記錄！");
out(grid); //答案
}
else {
alert("答案唯一！！"); //答案唯一
}
} else {
alert("出錯(cuò) 結(jié)束！");
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() {
//目標(biāo):
// 遍歷矩陣,從當(dāng)前位置建立搜索分支.
var binarynode = false;
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
// 2叉樹(shù)分支:
// 如果在某位置有兩種可能,選項(xiàng)1/選項(xiàng)2
// 則假設(shè)是選項(xiàng)1,并進(jìn)行驗(yàn)算,同時(shí)按選項(xiàng)2生成一個(gè)新的標(biāo)簽
if (candidatNum[i][j][0] == 2) {// 有2種選擇
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; // 在當(dāng)前標(biāo)簽上標(biāo)記已選
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叉分支未找到!\n');
timeline.scrollTop = timeline.scrollHeight;
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
// 2叉樹(shù)查找失敗時(shí)，啟動(dòng)3叉樹(shù)分支，作為擴(kuò)充，還可以啟動(dòng)3叉樹(shù)分支：
// 如果在某位置有三種可能,選項(xiàng)1/選項(xiàng)2/選項(xiàng)3
// 則假設(shè)是選項(xiàng)1,并進(jìn)行驗(yàn)算,同時(shí)按選項(xiàng)2生成一個(gè)新的標(biāo)簽
if (candidatNum[i][j][0] == 3) {// 有3種選擇
var timeline = document.getElementById('PaperList');
timeline.value += ('發(fā)現(xiàn)3叉分支!\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; // 在當(dāng)前標(biāo)簽上標(biāo)記已選
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("數(shù)據(jù)格式不正確:\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>
建議使用IE瀏覽器,F12開(kāi)啟調(diào)試模式<br>
<br><span>
<textarea id="PaperList" cols="30" rows="20" style="position:absolute;left:550px;"></textarea></span>
</body>
</html>
相關(guān)文章
這篇文章主要介紹了從零搭一個(gè)自用的前端腳手架的方法步驟，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09
JS實(shí)現(xiàn)的簡(jiǎn)易拖放效果示例
這篇文章主要介紹了JS實(shí)現(xiàn)的簡(jiǎn)易拖放效果的方法,涉及JS事件監(jiān)聽(tīng)、擴(kuò)展及頁(yè)面元素動(dòng)態(tài)操作的相關(guān)技巧,需要的朋友可以參考下2016-12-12
js完美實(shí)現(xiàn)@提到好友特效（兼容各大瀏覽器）
本文給大家分享的是一則使用javascript完美實(shí)現(xiàn)兼容各大瀏覽器的@好友自動(dòng)提示的特效，是根據(jù)百度貼吧的效果模仿來(lái)的，推薦給小伙伴們，希望大家能夠喜歡。2015-03-03
JS根據(jù)json數(shù)組多個(gè)字段排序及json數(shù)組常用操作
這篇文章主要介紹了js根據(jù)json數(shù)組多個(gè)字段排序及json數(shù)組常用操作，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-06-06
如何使用JavaScript檢測(cè)空閑的瀏覽器選項(xiàng)卡
這篇文章主要介紹了如何使用JavaScript檢測(cè)空閑的瀏覽器選項(xiàng)卡，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-05-05
下面小編就為大家?guī)?lái)一篇基于js中document.cookie全面解析。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-09-09
js ajaxfileupload.js上傳報(bào)錯(cuò)的解決方法
這篇文章主要為大家詳細(xì)介紹了js ajaxupload.js上傳報(bào)錯(cuò)的解決方法，感興趣的小伙伴們可以參考一下2016-05-05
本文主要介紹了js事件冒泡與事件捕獲的相關(guān)知識(shí)。具有很好的參考價(jià)值，下面跟著小編一起來(lái)看下吧2017-02-02
H5實(shí)現(xiàn)中獎(jiǎng)記錄逐行滾動(dòng)切換效果
這篇文章主要為大家詳細(xì)介紹了H5實(shí)現(xiàn)中獎(jiǎng)記錄逐行滾動(dòng)切換效果，利用定時(shí)器實(shí)現(xiàn)中獎(jiǎng)記錄逐行展示，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-03-03
后臺(tái)獲取ZTREE選中節(jié)點(diǎn)的方法
這篇文章主要介紹了后臺(tái)獲取ZTREE選中節(jié)點(diǎn)的方法,實(shí)例分析了ZTREE中g(shù)etZTreeObj方法與getCheckedNodes方法的使用技巧,需要的朋友可以參考下2015-02-02