LeetCode 37.解数独(注释完整+JavaScript解题)

简介: LeetCode 37.解数独(注释完整+JavaScript解题)

LeetCode 37.解数独

问题描述

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 ‘.’ 表示。

一个数独。

答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

题目分析

看到题目我们很容易地想到应该要用回溯算法来解答此题,对此我们需要一个检查位置的函数来判断当前位置能否填写某一数字。之后遍历每个位置,试着将1~9填入每个位置,直到填满整个9宫格结束遍历。

小九宫格下标:

代码

var columns = [],//保存每一行的数字
    rows = [],//保存每一列的数字
    grids = [],//保存每一个九宫格的数字
    f = 0;//结束标记
// 初始化,遍历已有填充值
var init = function(board){
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      // 获取值
      const value = board[i][j];
      // 先判断非 . 元素
      if (value !== '.') {
          rows[i].push(value);
          columns[j].push(value);
          //九宫格下标
          const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
          grids[gridIndex].push(value);
        } 
      }
    }
};
//检查能否填入该位置
var check = function(i,j,board,value){
    const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 对应的盒子
    if (rows[i].includes(value) || columns[j].includes(value) || grids[gridIndex].includes(value)) {
        return false;
    }
    return true;
};
//遍历填充数独
var fillBoard = function(i,j,board){
    //已填满
    if(f == 1 || i > 8) {
        return ;
    }
    //需要填充
    if(board[i][j] == '.'){
        //遍历9个数字
        for(let num = 1; num < 10; num++){
            if(f == 0 && check(i,j,board,num.toString())){
                rows[i].push(num.toString());//更新列
                columns[j].push(num.toString());//更新行
                const gridIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
                grids[gridIndex].push(num.toString());//更新小九宫格
                board[i][j] = num.toString();//填入数字
                if(i == 8 && j == 8) {//已填满
                    f = 1;
                    return;
                }else if(j == 8) fillBoard(i + 1,0,board);//换行
                else fillBoard(i,j+1,board);//换列
                 if(f == 0){//回溯
                    rows[i].pop();//更新列
                    columns[j].pop();//更新行
                    grids[gridIndex].pop();//更新小九宫格
                    board[i][j] = '.';//更新大九宫格
                }
            }
        }
    }else if(i == 8 && j == 8) {//遍历结束
        f = 1;
        return;
    }else if(j == 8) fillBoard(i + 1,0,board);//换行
    else fillBoard(i,j+1,board);//换列
    return board;
};
var solveSudoku = function(board) {
    f = 0;
    for(let i = 0; i < 9; i++){
        columns[i] = [];
        rows[i] = [];
        grids[i] = [];
    }
    init(board);  
    board = fillBoard(0,0,board);
};

其他

个人博客:http://kscccisu.cn:8090/

目录
相关文章
|
2月前
|
人工智能 自然语言处理 程序员
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
欢迎来到工程师令狐小哥的频道。本文介绍如何利用AI工具高效刷LeetCode,通过通义灵码插件在IntelliJ IDEA中实现代码生成、优化、单元测试等功能,提升编程学习效率。
91 1
通义灵码:融合创新玩法与探索,重塑LeetCode解题策略
|
2月前
|
存储 算法 C++
Leetcode第三十六题(有效的数独)
这篇文章介绍了如何使用C++编写一个算法来验证一个9x9数独是否有效,遵循数独的规则,即数字1-9在每一行、每一列和每个3x3宫内只能出现一次。
50 0
|
3月前
|
JSON JavaScript 前端开发
如何使用代码注释:关于JavaScript与TypeScript
TSDoc是一种标准化TypeScript代码文档注释的规范,使不同工具能无干扰地提取内容。它包括多种标记,如@alpha、@beta等发布阶段标记;@decorator、@deprecated等功能标记;@defaultValue、@eventProperty等描述标记;@example、@experimental等示例与实验性标记;@inheritDoc、@internal等引用与内部标记;@label、@link等链接标记;@override、@sealed等修饰符标记;以及@packageDocumentation、@param、
58 5
|
4月前
|
存储 算法 索引
LeetCode第36题有效的数独
这篇文章介绍了LeetCode第36题"有效的数独"的解题方法,通过使用三个二维数组分别记录每一行、每一列以及每个3x3宫格内1-9数字出现的次数,来验证给定数独是否有效。
|
6月前
|
JavaScript 前端开发
JavaScript 注释
JavaScript 注释
42 11
|
5月前
|
网络架构
若依修改 :id 不跳转注释的资料,路由配置:id不跳转修改,若依的store的permission.js对动态路由有控制
若依修改 :id 不跳转注释的资料,路由配置:id不跳转修改,若依的store的permission.js对动态路由有控制
若依修改 :id 不跳转注释的资料,路由配置:id不跳转修改,若依的store的permission.js对动态路由有控制
|
6月前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
90 1
|
6月前
|
存储 JavaScript 前端开发
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LeetCode350:两个数组的交集 II(Java/C/Python3/JavaScript实现含注释说明,Easy)
33 1
|
6月前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
52 0
|
7月前
|
JSON 前端开发 JavaScript
【2024-04-22 源码】最新PDF批注注释插件库,pdf.js插件库,纯前端离线JavaScript库(PDF高亮、下划线、橡皮擦、文本框、画笔、历史记录)
一款基于 pdf.js 开发的PDF批注插件库,支持纯离线内网部署,功能完善、强大且在不断升级,极易上手,欢迎关注!
205 4
【2024-04-22 源码】最新PDF批注注释插件库,pdf.js插件库,纯前端离线JavaScript库(PDF高亮、下划线、橡皮擦、文本框、画笔、历史记录)