Javascript 实现的数独解题算法网页实例
发布时间:2024-02-26 15:26:16
1)当我们拿到一个题目时,首先会根据已经知道的条件,进行数据的初步整理和分析。
相当于填写出9宫格里,所有的“确定项”,以及标记“可能选项”。
function refreshStat()
2)此后,思考会进入 猜测/验证 的循环阶段。
在9宫格中,可以对于“可能选项”进行尝试,验证是否违背现有条件。
每一个新的分支,最后的结果无非是两种,答案/出错。
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环
break;
}
}
实际人脑思考的过程,也是要先遍历选项较少的分支。
所以,程序实现上也是 确定点/2叉分支/3叉分支/....
3)当所有的路径搜索下来,答案不是唯一的情况,是和数独游戏的宗旨相悖的。
以下部分是全部代码,为方便阅读,调试信息未删除。
<html>
<head>
<title>数独解题程序</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="计算">
<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="粘贴" >可以文本拷贝到下框中后点粘贴,从左到右从上往下的81个数字序列,未填为0,中间非数字字符将忽略<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) {
// 目标:
// 冲突检查 参数 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 < 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;
//目标:
// 遍历矩阵,当前是否可以简单刷新,或者已经可以发现出错.
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
//目标:
// (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 && 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(); // 当前标签已经被证明逻辑错误,废弃
return true;
} else {
if (!success) {
alert("栈为空 结束!"); //题目出错,结束
}
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(){ //功能入口
//读取数据
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);
}
}
//刷新网格
refreshStat();
out(grid);
//计算矩阵
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环
break;
}
}
out(grid); //答案
alert("用时:"+(new Date()-start)+"ms");
success = true;
//计算结束
//验证答案是否唯一
if (papers != discards){
if (steps.length>0) {// 回退
pop(); // 当前标签废弃
//计算矩阵
while(true){
var a=setOne();
var b=refreshStat();
if(!a||b){ //如果 a==false 或者 b==ture,则可以跳出循环
break;
}
}
if (b) {
alert("答案不唯一!记录!");
out(grid); //答案
}
else {
alert("答案唯一!!"); //答案唯一
}
} else {
alert("出错 结束!");
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() {
//目标:
// 遍历矩阵,从当前位置建立搜索分支.
var binarynode = false;
for (var i = 0; i < 9; i++) {
for (var j = 0; j < 9; j++) {
// 2叉树分支:
// 如果在某位置有两种可能,选项1/选项2
// 则假设是选项1,并进行验算,同时按选项2生成一个新的标签
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; // 在当前标签上标记已选
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叉树查找失败时,启动3叉树分支,作为扩充,还可以启动3叉树分支:
// 如果在某位置有三种可能,选项1/选项2/选项3
// 则假设是选项1,并进行验算,同时按选项2生成一个新的标签
if (candidatNum[i][j][0] == 3) {// 有3种选择
var timeline = document.getElementById('PaperList');
timeline.value += ('发现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; // 在当前标签上标记已选
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("数据格式不正确:\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开启调试模式<br>
<br><span>
<textarea id="PaperList" cols="30" rows="20" style="position:absolute;left:550px;"></textarea></span>
</body>
</html>
猜你喜欢
- ff默认不让改 statusopera9 测试通过ie6 测试通过这东西是给统计部门用的,分析用户习惯以改良网站布局
- PIL 图片操作读取图片img = Image.open(“a.jpg”)显示图片im.show() # im是Image对象,im是num
- 前言本文主要介绍了关于Python中TCP socket的写法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。一、 服务器
- 一、CNN简介1. 神经网络基础输入层(Input layer),众多神经元(Neuron)接受大量非线形输入讯息。输入的讯息称为输入向量。
- transforms.Resize()的简单使用简单来说就是调整PILImage对象的尺寸,注意不能是用io.imread或者cv2.imr
- lambda函数lambda是什么大家好,今天给大家带来的是有关于Python里面的lambda表达式详细解析。lambda在Python里
- #python中的函数定义,使用和传参###------------------- 必要参数 -----------------------
- 1. vue打包后font-awesome字体失效解决方案:2. 打包后图片资源失效解决方案:针对html中引用的图片针对css添加的背景中
- 最近用Python写了个 * ,需要部署到Linux环境的服务器上,由于之前本地开发时使用virtualenv,使用这个虚拟环境有个好处是项目
- django程序,需要写很多api,每个函数都需要几个装饰器,例如@csrf_exempt @require_POST 
- tf.diag(diagonal,name=None) #生成对角矩阵import tensorflowas tf;diagonal=[1,
- 背景在吉日嘎拉的软件编程走火入魔之:数据库事务处理入门(适合初学者阅读)文章中关于MS SQL Server和Oracle对数据库事务处理的
- 不管是用import还是用from mmmm import *的方式导入模块,当程序运行之后,回头在看那个存储着mmmm.py文件的目录中,
- 内容摘要:下面是虚机维护中,经常碰到的一些ASP程序中的数据库调用的错误,现收集整理如下:1.不能打开注册表关键字(8007000e);2.
- 要判断自定义对象的类型,用__class__方法,或者用isinstance(object, class-or-type-or-tuple)
- 在所有的比例中黄金分割是最能引起人的美感的,0.618被公认为最具有审美意义的比例数字。黄金分割之所以那么普遍的流行,我猜一定跟理想女人体的
- 一、命令提示符窗口安装卸载1、安装第一种,最常用的,初学者也是基本都是用的这个方法,直接在cmd里面安装。首先键盘按住win+r就会弹出来运
- 众所周知,凡是用 FrontPage 做的网页里面都有类似这样的标记:<META content="Microso
- 使用递归查找父元素,知道查到想要的元素,然后return getParentTag(startTag) { var self
- Python实现图像处理:PiL依赖库的应用本文包含的练习题主要是PIL依赖库,即pillow相关的应用。练习一:使用python给图片增加