javascript实现数独解法
作者:hebedich 发布时间:2023-10-17 17:18:28
标签:javascript,数独解法
生生把写过的java版改成javascript版,第一次写,很不专业,见谅。唉,我是有多闲。
var Sudoku = {
init: function (str) {
this.blank = [];
this.fixed = [];
this.cell = [];
this.trials=[];
for (i = 0; i < 81; i++) {
var chr = str.charCodeAt(i);
if (chr == 48) {
this.cell[i] = 511;
this.blank.push(i);
} else {
this.cell[i] = 1 << chr - 49;
this.fixed.push(i);
}
}
},
showBoard: function () {
var board = "";
for (var i = 0; i < 81; i++) {
if (i % 9 == 0) {
board = board.concat("\n");
}
board = board.concat("[");
for (var j = 0; j < 9; j++) {
if ((this.cell[i] >> j & 1) == 1) {
board = board.concat(String.fromCharCode(j + 49));
}
}
board = board.concat("]");
}
return board;
},
check: function () {
var checkpoint = [0, 12, 24, 28, 40, 52, 56, 68, 80];
for (var i in checkpoint) {
var r, b, c;
r = b = c = this.cell[checkpoint[i]];
for (j = 0; j < 8; j++) {
c ^= this.cell[this.getX(checkpoint[i])[j]];
b ^= this.cell[this.getX(checkpoint[i])[8 + j]];
r ^= this.cell[this.getX(checkpoint[i])[16 + j]];
}
if ((r & b & c) != 0x1FF) {
return false;
}
}
return true;
},
bitCount: function (i) {
var n = 0;
for (var j = 0; j < 9; j++) {
if ((i >> j & 1) == 1)
n++;
}
return n;
},
numberOfTrailingZeros: function(i){
var n = 0;
for (var j = 0; j < 9; j++) {
if ((i >> j & 1) ==0)
n++;
else{
break;
}
}
return n;
},
updateCandidates: function () {
for (var i in this.fixed) {
var opt = 0x1FF ^ this.cell[this.fixed[i]];
for (var j = 0; j < 24; j++) {
this.cell[this.getX(this.fixed[i])[j]] &= opt;
//!notice
if (this.cell[this.getX(this.fixed[i])[j]] == 0) {
//console.log("Error-0 candidate:"+x[this.fixed[i]][j]);
return false;
}
}
}
return true;
},
seekUniqueCandidate: function () {
for (var bidx in this.blank) {
var row = 0, col = 0, box = 0;
for (i = 0; i < 8; i++) {
row |= this.cell[this.getX(this.blank[bidx])[i]];
box |= this.cell[this.getX(this.blank[bidx])[8 + i]];
col |= this.cell[this.getX(this.blank[bidx])[16 + i]];
}
if (this.bitCount(this.cell[this.blank[bidx]] & ~row) == 1) {
this.cell[this.blank[bidx]] &= ~row;
continue;
}
if (this.bitCount(this.cell[this.blank[bidx]] & ~col) == 1) {
this.cell[this.blank[bidx]] &= ~col;
continue;
}
if (this.bitCount(this.cell[this.blank[bidx]] & ~box) == 1) {
this.cell[this.blank[bidx]] &= ~box;
}
}
},
seekFilledable: function () {
this.fixed = [];
var _del=[];
for (var i in this.blank) {
if (this.bitCount(this.cell[this.blank[i]]) == 1) {
this.fixed.push(this.blank[i]);
//console.log("fixed:"+this.blank[i]+"=>"+this.cell[this.blank[i]]);
//this.blank.splice(i, 1);//to delete it in the loop would cause bug
_del.push(i);
}
}
while(_del.length>0){
this.blank.splice(_del.pop(), 1);
}
},
seekMutexCell: function () {
var two = [];
for (var n in this.blank) {
if (this.bitCount(this.cell[this.blank[n]]) == 2) {
two.push(this.blank[n]);
}
}
for (var i = 0; i < two.length; i++) {
for (var j = i + 1; j < two.length; j++) {
if (this.cell[two[i]] == this.cell[two[j]]) {
var opt = ~this.cell[two[i]];
if (parseInt(two[i] / 9) ==parseInt(two[j] / 9)) {
for (n = 0; n < 8; n++) {
this.cell[this.getX(two[i])[n]] &= opt;
}
}
if ((two[i] - two[j]) % 9 == 0) {
for (n = 8; n < 16; n++) {
this.cell[this.getX(two[i])[n]] &= opt;
}
}
if ((parseInt(two[i] / 27) * 3 + parseInt(two[i] % 9 / 3)) == (parseInt(two[j] / 27) * 3 + parseInt(two[j] % 9 / 3))) {
for (n = 16; n < 24; n++) {
this.cell[this.getX(two[i])[n]] &= opt;
}
}
this.cell[two[j]] = ~opt;
}
}
}
},
basicSolve: function () {
do {
if (!this.updateCandidates(this.fixed)) {
this.backForward();
}
this.seekUniqueCandidate();
this.seekMutexCell();
this.seekFilledable();
} while (this.fixed.length != 0);
return this.blank.length == 0;
},
setTrialCell: function() {
for (var i in this.blank) {
if (this.bitCount(this.cell[this.blank[i]]) == 2) {
var trialValue = 1 << this.numberOfTrailingZeros(this.cell[this.blank[i]]);
var waitingValue = this.cell[this.blank[i]] ^ trialValue;
//console.log("try:[" + this.blank[i] + "]->" + (this.numberOfTrailingZeros(trialValue) + 1) + "#" + (this.numberOfTrailingZeros(waitingValue) + 1));
this.cell[this.blank[i]] = trialValue;
this.trials.push(this.createTrialPoint(this.blank[i], waitingValue, this.cell));
return true;
}
}
return false;
},
backForward: function() {
if (this.trials.length==0) {
console.log("Maybe no solution!");
return;
}
var back = this.trials.pop();
this.reset(back.data);
this.cell[back.idx] = back.val;
this.fixed.push(back.idx);
//console.log("back:[" + back.idx + "]->" + (this.numberOfTrailingZeros(back.val) + 1));
},
reset: function(data) {
this.blank=[];
this.fixed=[];
this.cell=data.concat();
for (var i = 0; i < 81; i++) {
if (this.bitCount(this.cell[i]) != 1) {
this.blank.push(i);
} else {
this.fixed.push(i);
}
}
},
trialSolve: function() {
while (this.blank.length!=0) {
if (this.setTrialCell()) {
this.basicSolve();
} else {
if (this.trials.length==0) {
//console.log("Can't go backforward! Maybe no solution!");
break;
} else {
this.backForward();
this.basicSolve();
}
}
}
},
play: function() {
console.log(this.showBoard());
var start = new Date().getMilliseconds();
if (!this.basicSolve()) {
this.trialSolve();
}
var end = new Date().getMilliseconds();
console.log(this.showBoard());
if (this.check()) {
console.log("[" + (end - start) + "ms OK!]");
} else {
console.log("[" + (end - start) + "ms, cannot solve it?");
}
//return this.showBoard();
},
getX:function(idx){
var neighbors=new Array(24);
var box=new Array(0,1,2,9,10,11,18,19,20);
var r=parseInt(idx/9);
var c=idx%9;
var xs=parseInt(idx/27)*27+parseInt(idx%9/3)*3;
var i=0;
for(var n=0;n<9;n++){
if(n==c)continue;
neighbors[i++]=r*9+n;
}
for(var n=0;n<9;n++){
if(n==r)continue;
neighbors[i++]=c+n*9;
}
for(var n=0;n<9;n++){
var t=xs+box[n];
if(t==idx)continue;
neighbors[i++]=t;
}
return neighbors;
},
createTrialPoint:function(idx, val, board) {
var tp = {};
tp.idx = idx;
tp.val = val;
tp.data = board.concat();
return tp;
}
};
//Sudoku.init("000000500000008300600100000080093000000000020700000000058000000000200017090000060");
//Sudoku.init("530070000600195000098000060800060003400803001700020006060000280000419005000080079");
Sudoku.init("800000000003600000070090200050007000000045700000100030001000068008500010090000400");
Sudoku.play();
0
投稿
猜你喜欢
- 1、删除Oracal在注册表中的主项:regedit.exe->LocalMachine->Software->Oracl
- 核心导出作业的 代码 和 作业备份是相似的 代码如下:alter PROC DumpJob (@job VARCHAR(100)
- 简单的显示记录已经掌握,现在需要的就是通过ASP将信息内容插入到数据库中。一、拥有数据库cnbruce.mdb本数据库的作用就是用来 * 入数
- button元素在过去一直没有被重视,其实它比<input type="button">的语义强许多,制定性
- 其实网上已经有很多ASP生成htm的文章了,有一种方法是ASP+XML的生成方法,虽然有一种好处就是不用程序写模版就可以直接引用原来的要生成
- asp之家注:学习asp,无论是做企业网站还是做个人网站一般都需要用到IP地址。如留言要记录留言者IP,用户登录也经常记录登录的IP,还有站
- 需 求 分 析 1、读取指定目录下的所有文件2、读取指定文件,输出文件内容3、创建一个文件并保存到指定目录实 现 过 程Python写代码简
- 官方实现golang 1.8 及以上版本提供了一个创建共享库(shared object)的新工具,称为 Plugins。目前 Plugin
- 下面说说主要实现思路: 1、存取图片 (1)、将图片文件转换为二进制并直接存进sql server //UploadHelper.cs //
- 在计算机和信息技术领域里 I/O 这个术语表示输入 / 输出 ( 英语:Input / Output ) ,通常指数据在存储器(内部和外部)
- 一、前言CodeIgniter 是一个简单快速的PHP MVC框架。EllisLab 的工作人员发布了 CodeIgniter。CodeIg
- 代码如下:Set Catalog_object= Server.CreateObject("ADO
- 我认为多选列表具有完美的功能——只需按下Ctrl键,同时点击鼠标从列表中选择多个项目。以下是一个典型的多选列表框: 上面那个列表框
- 记得很早以前看到过这样的一段介绍:想象你在逛街边的一家书店,如果最终你没有购买任何图书就直接离开了,店长并不会知道你来过。但是如果你买了书,
- 今天好不容易闲下来半天,所以和大家分享一下我之前总结的一套Web UI 设计命名规范,也就是网站用户界面设计(俗称网页设计)命名规范。这套规
- 今天,使用各种所见即所得工具制作主页已经是一件非常容易的事情了。但是了解HTML源代码和语法,无疑对我们制作主页有更大的帮助,也可以使用户能
- 这是 COMSHARP CMS 团队翻译的2009年海外Web设计风潮的第二部分,着重讲解了反 Box 式布局,单页布局,多栏布局,巨型插图
- 这几天有一台MySQL数据库服务器出现了频繁的掉线情况,通过排查,并没有排查出哪个网站被攻击,百思不得其解中的时候,群里有个朋友说是因为微软
- 代码如下:declare @Q_ID uniqueidentifier set @Q_ID = dbo.uf_GetParamValueBy
- Exec sp_droplinkedsrvlogin ZYB,Null --删除映射(录与链接服务器上远程登录之间的映射) Exec sp_