yiminghe
- 浏览: 1461849 次
- 性别:
- 来自: 上海
-
文章分类
最新评论
-
luhouxiang：
写的很不错，学习了
Extjs 模块化动态加载js实践 -
kingkongtown：
如果想改成淘宝后台那样，可以在编辑器批量上传图片呢？
kissy editor 阶段体会 -
317966578：
兄弟我最近也在整jquery和caja 开放一些接口。在git ...
caja 原理 : 前端 -
liuweihug：
Javascript引擎单线程机制及setTimeout执行原 ...
setTimeout ,xhr,event 线程问题 -
辽主临轩：
怎么能让浏览器不进入 文档模式的quirks模式，进入标准的
浏览器模式与文本模式
书中没有给出具体实现，但是算法1也不难，自己实现玩玩用来测智商吧。
规则：
一个由3个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，且数独矩阵中每行每列都没有重复数字。
3*3子矩阵数字各不相同
效果图：
代码： （可copy直接运行，或 附件 ）
1.0 (2009-07-22 16:54)
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-CN" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>数独游戏</title>
<script type="text/javascript">
//<![CDATA[
/***
产生一个 9*9 的数独矩阵，满足数独规则 :
1.一个由9个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，
2.且数独矩阵中每行每列都没有重复数字。
关键方法：
深度搜索，记下每个单元格对应的可选数序列，当没有路线时清空自己的可选数序列,
利用回朔，改变上个单元格已选泽的值
****/
if(!Array.prototype.indexOf) {
Array.prototype.indexOf = function(v){
for(var i=0;i<this.length;i++)
if(this[i] === v) return i;
return -1;
}
}
//http://blog.stevenlevithan.com/archives/faster-trim-javascript
//fast !
if(!String.prototype.trim) {
String.prototype.trim=function() {
var str = this.replace(/^\s\s*/, ''),
ws = /\s/,
i = str.length;
while (ws.test(str.charAt(--i)));
return str.slice(0, i + 1);
}
}
/*
*********************************************************************
start : 数组随机函数组
floy 算法对数组进行重排序
http://yiminghe.iteye.com/blog/409039
*/
function randIt(l,u){
return l+Math.floor(Math.random()*(u-l+1));
}
/*
1 - n 中随机取m个数组成序列
*/
function randomList(m,n) {
var start=n-m+1;
var holder=[];
for(var i=start;i<=n;i++) {
//random 1~i not 1~i-1
var cur=randIt(1,i);
//trick tick
var position=holder.indexOf(cur)+1;
var insert=position?i:cur;
holder.splice(position,0,insert);
}
return holder;
}
/**
arr 数组元素随机打乱
**/
function randomArray(arr) {
var rIndex=randomList(arr.length,arr.length);
var newArr=[];
for(var i=0;i<rIndex.length;i++) {
newArr[i]=arr[rIndex[i]-1];
}
return newArr;
}
/*
end : 数组随机函数组
********************************************************************************
*/
/*
数独 core 对象 ,其实就是对2维数组的封装
*/
function Sudoku(){
}
/*
得到当前单元格的一个可选值，-1 表示没有可选值了，要向前回朔
*/
Sudoku.prototype.getNextRandom = function(currentCell){
var currentX=currentCell%9; //col
var currentY=Math.floor(currentCell/9); //row
var currentSubMaxtrixX=Math.floor(currentX/3); //sub this.matrix col
var currentSubMaxtrixY=Math.floor(currentY/3); //sub this.matrix row
var index=0;
//初始可选数字
var avails=[1,2,3,4,5,6,7,8,9];
//没有计算过，计算可选序列，用于回朔枚举
if(!this.matrix[currentY][currentX]) {
/*
根据数独规则进行过滤
*/
//同一行不能重复
for(var i=0;i<currentX;i++) {
if(avails.indexOf(this.matrix[currentY][i].value)!=-1)
avails.splice(avails.indexOf(this.matrix[currentY][i].value),1);
}
//同一列不能重复
for(var i=0;i<currentY;i++) {
if(avails.indexOf(this.matrix[i][currentX].value)!=-1)
avails.splice(avails.indexOf(this.matrix[i][currentX].value),1);
}
//3*3 小矩阵不能重复
outer:for(var j=currentSubMaxtrixY*3;j<currentSubMaxtrixY*3+3;j++) {
for(var i=currentSubMaxtrixX*3;i<currentSubMaxtrixX*3+3;i++) {
//小矩阵验证到当前单元格就行了
if(j==currentY && i==currentX) break outer;
if(avails.indexOf(this.matrix[j][i].value)!=-1)
avails.splice(avails.indexOf(this.matrix[j][i].value),1);
}
}
//没有选择了
if(avails.length==0) return -1;
//avails 最好随机打乱，每次生成不同的数独
avails=randomArray(avails);
} else {
index=this.matrix[currentY][currentX].index;
//枚举完毕，仍然不行，清除计算状态，
if(index == this.matrix[currentY][currentX].availList.length-1) {
this.matrix[currentY][currentX]=null;
return -1;
}
//回朔到这里了，当前数字不行，那么在可选序列中选中下一个可选数字
++index;
avails=this.matrix[currentY][currentX].availList;
}
//返回数独单元的结构表示
return {
//当前单元格选择的值的index
index:index,
//记下产生的可选序列，回朔时用于枚举下一个值
availList:avails,
value:avails[index]
};
}
/*
指定编号的 Cell 设置数值
*/
Sudoku.prototype.setValueOfMatrix = function(currentCell,val) {
var currentX=Math.floor(currentCell%9); //col
var currentY=Math.floor(currentCell/9); //row
this.matrix[currentY][currentX]=val;
}
/*
静态方法：验证是否符合数独规则
*/
Sudoku.validate = function (matrix){
var cache={};
for(var i=0;i<9;i++) {
cache={};
for(var j=0;j<9;j++) {
if(cache[matrix[i][j]]) {
return "row "+(i+1)+" error";
}
cache[matrix[i][j]] = 1;
}
}
for(var i=0;i<9;i++) {
cache={};
for(var j=0;j<9;j++) {
if(cache[matrix[j][i]]) {
return "col "+(j+1)+" error";
}
cache[matrix[j][i]] = 1;
}
}
for(var i=0;i<3;i++) {
for(var j=0;j<3;j++) {
cache={};
for(var subi=i*3;subi<i*3+3;subi++) {
for(var subj=j*3;subj<j*3+3;subj++) {
if(cache[[matrix[subi][subj]]]) {
return "submatrix "+(i*3+j)+"error";
}
cache[matrix[subi][subj]] = 1;
}
}
}
}
return null;
}
/*
重要，生成符合数独规则的矩阵
*/
Sudoku.prototype.generate = function (space) {
this.matrix=[];
for(var i=0;i<9;i++)
this.matrix.push([]);
var currentCell=0;
//按照行编号 0~80 ,共 9*9=81 个单元格
while(true) {
var nextValue=this.getNextRandom(currentCell);
if(nextValue!=-1) {
this.setValueOfMatrix(currentCell,nextValue);
++currentCell;
} else {
//无值可选了，回朔
--currentCell;
}
//9*9 全部完成
if(currentCell==81) break;
}
/*
矩阵已经搞好了--------------------------------------------
*/
var holes=randomList(space,81);
for(var i=0;i<holes.length;i++) {
var currentX=Math.floor((holes[i]-1)%9); //col
var currentY=Math.floor((holes[i]-1)/9); //row
this.matrix[currentY][currentX]=null;
}
return this.matrix;
}
//]]>
</script>
<style type="text/css">
table {
border-collapse: collapse;
width: 80%;
padding-left: 5%;
table-layout: fixed;
margin: 20px;
}
div {
margin: 20px;
padding-left: 5%;
}
input#space {
margin-right: 10px;
}
td {
padding: 5px;
border: 1px solid black;
}
input.tableCell {
width: 80%;
}
</style>
</head>
<body>
<table cellspacing="0" cellpadding="0">
<caption>我的数独</caption>
<tbody id="dataTable">
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
<td>1</td>
</tr>
</tbody>
</table>
<div>
<label for="space">空格数：</label>
<input type="text" id="space" size="2" value="2" />
<input type="button" value="生成数独" id="run" />
<input type="button" value="我要验证" id="validate" />
</div>
<script type="text/javascript">
//<![CDATA[
function collectData(tableEl){
var matrix=[];
for(var i=0;i<tableEl.childNodes.length;i++) {
var tr=tableEl.childNodes[i].childNodes;
var row=[];
for(var j=0;j<tr.length;j++) {
var td=tr[j];
var ti=0;
while(td.childNodes[ti] && td.childNodes[ti].nodeType ==3 )ti++;
if(td.childNodes[ti]) {
if( ! /^[1-9]$/.test(td.childNodes[ti].value.trim())) {
return "输入1-9之间";
}
row.push(parseInt(td.childNodes[ti].value.trim()));
}
else {
row.push(parseInt(td.innerHTML));
}
}
matrix.push(row);
}
return matrix;
}
function startValidate(){
var dataTable=document.getElementById("dataTable");
var newMatrix = collectData(dataTable);
if(typeof newMatrix == "string") {
alert(newMatrix);
return;
}
var info=Sudoku.validate(newMatrix);
if(info)
alert(info);
else
alert("恭喜你，成功了");
}
/*
*****************************************************
启动函数来了：
*/
function main(){
var space =parseInt(document.getElementById("space").value);
if(isNaN(space))
space=0;
if(space>81 || space<0) {
alert("空格数不合规范:(");
return;
}
var sudoku = new Sudoku();
var matrix= sudoku.generate(space);
var dataTable=document.getElementById("dataTable");
while (dataTable.childNodes[0]) {
dataTable.removeChild(dataTable.childNodes[0]);
}
for(var i=0;i<9;i++) {
var dataTableTr=document.createElement("tr");
for(var j=0;j<9;j++) {
var dataTableTd=document.createElement("td");
if(matrix[i][j])
dataTableTd.innerHTML=matrix[i][j].value;
else
dataTableTd.innerHTML="<input type='text' class='tableCell' />";
dataTableTr.appendChild(dataTableTd);
//document.writeln(matrix[i][j].value+" ");
}
dataTable.appendChild(dataTableTr);
}
}
main();
document.getElementById("run").onclick=function(){
main();
};
document.getElementById("validate").onclick=function(){
startValidate();
};
//]]>
</script>
</body>
</html>
0
顶
顶
0
踩
踩
分享到：
发表评论
-
构建前端 DSL
2012-10-11 22:10 5361目前在传统的软件开 ... -
circular dependency
2011-12-11 18:23 3925循环依赖是和语言无关 ... -
write html parser
2011-12-01 02:48 2918首先需要声明 html 不能用正则表达式来直接匹配进行内容抽取 ... -
转载：瀑布流布局浅析
2011-09-29 19:02 2847简介 如果你经 ... -
循环引用下的深度克隆
2011-08-04 20:39 2308深度复制和浅度复制 是当初初学 c 遇到的第一批问题，似乎使 ... -
开关状态信息的保存
2010-08-30 15:23 1682系统中常常会存在大量的状态信息，特别是0-1值信息，某个条件是 ... -
LL文法算法-1
2010-03-12 22:30 3473为了实现自顶向下的语法分析器，需要将文法的 1.左递归消 ... -
NFA到DFA的转换演示
2010-03-07 20:57 12731复习一下编译，在龙书中提到的NFA（不确定有穷自动机）到D ... -
gzip压缩实现注意
2010-01-18 22:19 0给你提点建议，你自己实现的compress不是很好哦，1. C ... -
三点共线判断
2010-01-12 19:43 14358经典的计算几何方面问题，判断二维坐标系中是否三个点在一条直线上 ... -
多维数组迭代器应用
2010-01-10 18:04 1717在代码之美中提到了这个问题，经常遇到嵌套数组的情况即多维数组情 ... -
google 开源项目
2009-12-28 20:25 0Google是支持开源运动的最大公司之一，它们现在总共发布 ... -
大数据量，海量数据 处理方法总结
2009-12-12 02:14 0最近有点忙，稍微空闲下来，发篇总结贴。 大数据量的问题是很 ... -
Bloom Filter Technical Report
2009-12-12 01:57 0Bloom Filter Technical Report ... -
找零问题
2009-10-31 16:07 2378问题描述： 有n美元需找零. 美 ... -
背包问题javascript演示
2009-10-26 16:28 2519背景： 经典递归示例：背包问题 ... -
hanoi问题求解
2009-10-19 23:54 0http://jnotnull.iteye.com/ ... -
后缀表达式的javascript转化演示
2009-10-19 23:46 1637复习经典算法，原算法：数据结构（用面向对象方法与c++描述） ... -
LCA In Javascript 演示
2009-10-05 17:24 1757理论： LCA 即 Least Common Anc ... -
Array.prototype.sort 稳定性问题
2009-09-16 13:49 2897引例 首先看一段代码： ...
相关推荐
JavaScript数独游戏是一种基于网页的互动游戏，利用JavaScript编程语言实现。JavaScript是一种广泛应用于Web开发的脚本语言，它在浏览器端运行，为用户提供动态、交互式的网页体验。在这个数独游戏中，用户可以在...
本项目探讨的是将一个使用JavaScript实现的数独游戏转换为TypeScript的过程，这是一种从弱类型到强类型的语言迁移，旨在提升代码的稳定性和可维护性。 JavaScript是动态类型的脚本语言，而TypeScript是它的超集，...
《JS数独 v1.0.2》是一款基于JavaScript实现的数独小游戏，适用于现代浏览器，尤其是基于WebKit内核的浏览器如Chrome或Safari。在IE浏览器中，部分验证功能可能无法正常工作，但不影响基本的游戏体验。这个项目展示...
在本项目中，我们讨论的是JavaScript实现的数独游戏。JavaScript是一种常用的编程语言，常用于网页和浏览器交互，也适用于开发各种类型的游戏。在这个js版数独游戏中，开发者利用JavaScript的特性创建了一个交互式的...
- 逻辑算法：实现数独的填充逻辑，包括合法性检查（每行、每列、每个宫格内数字是否唯一）、递归填充等。 - UI交互：用户输入数字、清除、提示等功能的实现，需要结合WXML和JavaScript进行事件绑定。 - 状态管理：...
在这个“精选_基于JavaScript实现的数独游戏_源码打包”中，我们将深入探讨如何使用JavaScript这一强大的客户端开发语言来创建一个互动式的数独游戏。 首先，我们需要理解JavaScript的基础语法和DOM操作。...
"数独计算器(HTML+JavaScript)"是一个利用网页技术实现的数独解算程序，它允许用户在网页上填写数独网格，并通过JavaScript进行计算。 首先，我们来看HTML部分。HTML（超文本标记语言）是构建网页的基础，它定义了...
在编程实现数独解法时，通常会涉及到一些特定的算法，其中一种常见的方法是使用回溯算法，还有一种是基于位运算的算法。下面详细说明javascript实现数独解法中的关键知识点。 ### 初始化数独游戏板 在JavaScript中...
在这个特定的项目中，“sudoku:JavaScript 中的简单数独游戏”是一个利用JavaScript实现的数独游戏。 JavaScript是一种广泛用于网页和互联网应用的编程语言，它允许开发者在客户端进行动态内容的创建。在这个项目中...
9. **模块化编程**：现代JavaScript开发常采用模块化，例如使用ES6的import/export语法，将代码拆分为可重用的组件，提高代码组织性和可维护性。 10. **性能优化**：对于大型数独网格，应用可能使用事件委托来减少...
通过以上步骤，我们可以构建一个完整的JavaScript数独游戏应用，包括生成器和求解器。这个项目不仅涵盖了基本的JavaScript编程技巧，还涉及到了数据结构、算法以及用户交互设计等多个方面，对于提升编程技能是非常有...
在这个“Sudoku:用Javascript制作的简单数独”项目中，我们将探讨如何利用JavaScript语言实现一个基本的数独游戏。 首先，我们需要理解项目的结构。"Sudoku-master"可能是一个Git仓库的名称，通常包含项目源代码、...
jsSudoku是一款以JavaScript实现的开源数独游戏，它的出现不仅提供了一种在线娱乐方式，也为开发者和编程学习者提供了宝贵的资源。开源性质使得这个游戏具备了持续改进和创新的可能性，同时也促进了技术分享和社区...
《JavaScript实现的数独游戏 v1.0.1》 数独是一种广受欢迎的逻辑解谜游戏，它基于一个9x9的网格，分为9个3x3的小宫格。玩家的目标是根据给出的部分数字填充空白格子，使得每一行、每一列以及每个小宫格内的数字从1...
在这个项目中，使用JavaScript作为编程语言，这是因为JavaScript在网页开发中非常常见，且可以方便地实现交互式界面。用户可以自定义数独题目，程序将利用递归回溯算法快速或可视化地解决这些题目。 在"index.html"...
在这个项目中，我们探讨的是一个名为“sudoku-js”的JavaScript实现，它是一个专门用于解决数独谜题的库。JavaScript作为一种广泛应用于前端开发和服务器端的编程语言，非常适合创建这种交互式的游戏或工具。 首先...
在这个“数独：数独的PHP实现”主题中，我们将探讨如何使用PHP编程语言来创建一个能够生成、解决和验证数独谜题的系统。 首先，我们需要理解数独的基本数据结构。在PHP中，我们可以使用二维数组来表示9×9的数独...
本话题涉及的知识点主要集中在JavaScript编程语言上，用于实现数独的解答和自定义题目的生成。 一、数独解法算法 1. 基于回溯的深度优先搜索（DFS）：这是一种典型的递归方法，从空格最多的单元格开始尝试填入数字...
这个过程可以通过编程来实现，本例中我们将探讨如何使用JavaScript来实现数独的求解算法。 首先，我们需要理解数独的特性，即每个单元格的候选数集合。在数独的初始状态下，部分单元格已经填有数字，而其余单元格则...
该项目包含两个版本的数独解算器：一个使用Python编程语言实现，另一个使用JavaScript。这两种语言各有特点，Python以其简洁明了的语法和丰富的库支持在数据分析和算法实现上广受青睐，而JavaScript作为前端开发的...