HTML5数独解算器

分享于 

10分钟阅读

Web开发

  繁體

介绍

本文介绍了一个HTML5数独解决方案。 整个程序都在一个HTML文件中,它使用JavaScript和新的HTML5 Canvas 元素。 这是我关于 html5/javascript的第三篇文章,每篇文章比以前更复杂,而且只是一系列的学习步骤。

Background

我不认为我不需要多数数独,除了它是一个非常流行和中瘾的游戏。 我妻子对我感兴趣- 我学会了解解决方案的基本规则,并且更感兴趣。

应用程序 below的屏幕截图显示了主要元素。 主要元素是显示 9 x 9网格划分为 3 x 3"正方形"的板。 当用户输入数字时,"givens"以较暗的字体显示。 板上的每个单元格都以非常轻的字体显示在 background 中的允许值。 "单体"是一个红色的字体,是一个标准的数独术语,指的是一个允许的价值。

当前单元格有粉红色的background,可以使用鼠标在单元格中单击或者使用键盘箭头键。 用户输入数字就输入数字,并输入 0位数字来清除它。

below 是一个包含母板数据的串行格式的文本框。 这是数独程序使用的一种常见格式,简单的是从上到下的每个数字,由"。"表示的空单元格。 当用户输入新数字时,串行格式被自动更新,如果按下加载按钮,则文本框中的任何文本。

所有按钮都位于板的右侧,如下所示:

  • 清除- 基本清除包括givens在内的所有单元。
  • Load - 已经提到加载串行格式,但是另一个要点是如果手动输入问题,数字会显示为用户输入,但是单击加载按钮,它会将它的设置为 givens。 因为不能修改 givens,所以区分用户值和givens是很重要的。 同时,按下重置按钮时,除givens外的所有单元格都将清除。
  • 重置- 清除除givens以外的所有单元格。
  • 接受-converts所有"单打"到实际值。
  • 提示- 输入该单元格中当前单元格的答案。 它从当前板中获得答案,因这里如果板已经不正确,则不会给出提示。
  • 撤消- 撤消输入的最后一个数字或者其他用户操作( 如接受或者解决)。 它使用堆栈实现,因此记录可以撤消无限数量的操作。 加载。重置或者清除清除堆栈堆栈。
  • 解决- 从当前位置解决整个问题。 如果值已经输入错误,这可能不会给出解决方案。 解决后,显示状态 below。按钮和所需的时间显示 below 串行格式文本框。

below 按钮为两个复选框,一个用于启用允许值的显示,另一个用于启用红色。 注意:一些数独玩家在解决问题时不愿意获得帮助,这就是为什么你要使用这些选项。

使用代码

解算器的代码使用最基本的解决方法- 首先扫描所有"givens"并确定哪些数字被允许。 如果只存在一个允许值,那么它是一个"裸"单。 因为每个数字必须在每行。列或者正方形中只出现一次,所以我们扫描其中的每一个,如果只出现一次,那么它是一个单独的"隐藏"。 单数值不一定正确- 板可以达到在同一行中给定数字的状态,在同一行中,col,因此我们测试该值是否有效,然后再应用它。

应用 上面 技术只能让你到目前为止。 事实上,我们还可以使用简单的试验和错误树方法,比如 比如。naked和 hide double。triple。quad。等等。 所以在给定的点,我们找到一个具有最少数量的alloweds的单元格,然后再试一次。 如果成功地使用该单元,那么我们进一步提高决策树,当板变成无效时,我们已经失去了。

这就是基本术语中的算法。 模型代码在四个类中实现,如下所示:

  • AllowedValues - 这将存储单元格的允许值。 如果允许数字N,则在位掩码中实现 换句话说,如果允许位N,则为 1,而 0不允许使用。 这样可以有效地存储 alloweds ( 它加快了决策树代码所需的板拷贝速度),并简化使用简单按位或者操作组合 alloweds,或者通过屏蔽。
  • Cell - 这表示board上的9个x 9位置之一。 它包含单元格的AllowedValues。给定值和用户输入值。
  • Location - 这有两个字段: 行和列用于简化计算并提供有用的函数,如行,列和正方形中同级单元格的位置列表。
  • Board - 包含 9个x 9 Cell 实例。 它实现了计算允许值。单打和解决问题的大部分相关代码。

有很多代码要覆盖,所以我会提到一段关键代码,这是 below 所允许的值的计算。

//Board.prototype.updateAllowed = function () {
 // Called whenever the user sets a value or via auto solve// Updates the allowed values for each cell based on existing digits// entered in a cell's row, col or squarevar cols = new Array(BoardSize);
 var rows = new Array(BoardSize);
 var squares = new Array(BoardSize);
 // First aggregate assigned values to rows, cols, squaresvar locs = Location.grid();
 for (var i = 0; i <locs.length; i++) {
 var loc = locs[i];
 // Disallow for all cells in this rowvar contains = this.getCell(loc).valueMask();
 rows[loc.row] |= contains;
 cols[loc.col] |= contains;
 squares[loc.getSquare()] |= contains;
 }
 // For each cell, aggregate the values already set in that row, col and square.// Since the aggregate is a bitmask, the bitwise inverse// of that is therefore the allowed values.this._isValid = true;
 this._isSolved = true;
 for (var i = 0; i <locs.length; i++) {
 var loc = locs[i];
 // Set allowed valuesvar contains = rows[loc.row] | cols[loc.col] | squares[loc.getSquare()];
 var cell = this.getCell(loc);
 // set allowed values to what values are not// already set in this row, col or square cell.setAllowed(~contains);
 cell.setAnswer(0); //clear any previous answers// As an extra step look for"naked singles",// i.e. cells that have only one allowed value, and use// that to set the answer (note this is different// from the"value" as this can only be assigned// by the user or any auto solve functions like"accept singles"if (!cell.isAssigned()) {
 this._isSolved = false;
 var mask = new AllowedValues(~contains);
 var count = mask.count();
 if (count == 0)
 this._isValid = false;
 elseif (count == 1)
 cell.setAnswer(mask.getSingle());
 }
 }
 // Step 2: Look for"hidden singles".// For each row, col, square, count number of times each digit appears.// If any appear once then set that as the answer for that cell.// Count in rowsfor (var i = 0; i <locs.length; i++) {
 var loc = locs[i];
 if (!this.checkForHiddenSingles(loc, SibType.Row))
 // first check row sibs for a hiddne singleif (!this.checkForHiddenSingles(loc, SibType.Col))
 // then check colsthis.checkForHiddenSingles(loc, SibType.Square);
 // then check square }
 // TO DO: Add code here to detect naked/hidden doubles/triples/quads};

第一步是创建表示板上每行。列和正方形的array。 在面板上提供一个列表,得到所有单元格的值,获取它的值位掩码,或者它们一起获取该行,列或者正方形,比如,rows[loc.row] |= contains的所有数字。

接下来,我们再次遍历每个单元格,并将该单元格行。列和正方形中使用的数字组合在一起 var contains = rows[loc.row] | cols[loc.col] | squares[loc.getSquare()] 如果还没有指定单元格,则将允许的值设置为 bitwise inverse。 如果允许数字中只有一个值,我们将"单元格应答"设置为数字- 这是一个裸的。 我使用这个词,但事实上它是一个很好的可能性。

如果使用允许值,我们会在每个单元格中扫描一行单元格,如果它有一个允许的值,那么我们扫描一行单元格,它是隐藏的单个元素。

Points of Interest

我在本文中了解了更多关于JavaScript的内容。 它是suprisingly强大但性能不同的浏览器。 为了解决问题( 具有 18或者更少givens的) 我发现 Chrome 是最快的。

历史记录

当我有空闲时间时,尝试其他数独变体( 比如 25 ) 会非常有趣。 感谢你的评论。 我已经根据这些评论对当前版本进行了几个修正。 在本文的第二个更新中,我添加了: 撤消按钮,提示按钮和所有按钮的工具提示。


Html5  Solver  SUDO  Sudoku  
相关文章