JavaScript实现有效数独验证算法详解

有效数独验证算法概述

本文通过具体实例，展示如何使用JavaScript代码来验证数独的有效性，供读者参考学习。

我们需要判断一个9x9规格的数独盘面是否有效。验证的核心在于检查已填入的数字是否符合既定规则，无需考虑数独是否有解。

有效数独需满足以下三个条件： 1. 数字1至9在每一行中不得重复出现。 2. 数字1至9在每一列中不得重复出现。 3. 数字1至9在每一个由粗实线分隔的3x3小宫格内不得重复出现。

数独盘面中部分空格已填入数字，空白位置使用字符‘.'进行标识。

测试用例与规则解析

以下是第一个测试用例：

输入数据如下：

[ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ]

预期输出结果为：true

第二个测试用例如下：

输入数据如下：

[ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ]

预期输出结果为：false

该示例与示例1的区别仅在于第一行第一个数字由5变为8。

由于左上角的3x3宫格内出现了两个数字8，违反了数独规则，因此判定该数独无效。

补充说明如下：

1. 一个部分填充的有效数独未必存在唯一解或可解。 2. 验证过程仅需依据上述规则检查已填入数字的有效性。 3. 输入的数独序列仅包含数字1-9以及字符‘.'。 4. 输入的数独格式固定为9x9。

<script>
var isValidSudoku = function(board) {
 const boxes = [{}, {}, {}, {}, {}, {}, {}, {}, {}];
 const cols = [{}, {}, {}, {}, {}, {}, {}, {}, {}];
 const rows = [{}, {}, {}, {}, {}, {}, {}, {}, {}];
 let test = [{}, {}, {}, {}, {}, {}, {}, {}, {}];
 for (let i = 0; i < 9; i++) {
  for (let j = 0; j < 9; j++) {
   const digit = board[i][j];
   if (digit !== '.') {
    const k = Math.floor(j / 3) + (Math.floor(i / 3) * 3);
    if (boxes[k][digit] || cols[j][digit] || rows[i][digit]) {
     return false;
    }
    boxes[k][digit] = cols[j][digit] = rows[i][digit] = true;
   }
  }
 }
 return true;
};
const board = [
 ["5","3",".",".","7",".",".",".","."],
 ["6",".",".","1","9","5",".",".","."],
 [".","9","8",".",".",".",".","6","."],
 ["8",".",".",".","6",".",".",".","3"],
 ["4",".",".","8",".","3",".",".","1"],
 ["7",".",".",".","2",".",".",".","6"],
 [".","6",".",".",".",".","2","8","."],
 [".",".",".","4","1","9",".",".","5"],
 [".",".",".",".","8",".",".","7","9"]
]
console.log(isValidSudoku(board))
</script>

代码测试与扩展阅读

可通过在线HTML/CSS/JavaScript代码运行工具（如http://tools.jb51.net/code/HtmlJsRun）测试上述代码，查看运行结果。

若需进一步了解JavaScript相关知识，可参考本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》。

希望本文提供的JavaScript程序设计思路能对大家有所帮助。