写文章

前端刷题路-Day15｜刷题打卡

吐槽君 分类：javascript

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

解数独（题号37）

题目

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

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.'表示。

示例：

img

输入：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"]
]
输出：[
	["5","3","4","6","7","8","9","1","2"],
	["6","7","2","1","9","5","3","4","8"],
	["1","9","8","3","4","2","5","6","7"],
	["8","5","9","7","6","1","4","2","3"],
	["4","2","6","8","5","3","7","9","1"],
	["7","1","3","9","2","4","8","5","6"],
	["9","6","1","5","3","7","2","8","4"],
	["2","8","7","4","1","9","6","3","5"],
	["3","4","5","2","8","6","1","7","9"]
]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

img

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

链接

leetcode-cn.com/problems/su…

解释

着实有点难，自己写的时候GG了，但不知道是哪里GG，有可能是性能吃的太多，也有可能是递归写GG了，写得很复杂，不清楚，感觉还是没有理清楚，下次需要注意

整体的逻辑是这样的，在递归的时候不用传递board，直接修改全局board即可。

递归的函数会返回true或者false，在递归前修改board中的数据，之后判断下一次递归是否成功，如果不成功，回溯一下，将board中的数据改回去，就这样一直一直改就好了，干到最后board就是修改完成后的。

重点就在于回溯的理解，有两点需要注意：

  1. 回到上一步，如果这一步错了就往上一步继续走
  2. 不要同时开始所有可能性的计算，要一种一种的计算，否则会有超时问题

自己的答案

无

更好的方法（暴力解法）

var solveSudoku = (board) => {
  function isInside(row, col, val) {
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === val || board[i][col] === val) {
        return true
      }
    }
    var startI = parseInt(row /3) * 3
        startJ = parseInt(col / 3) * 3
    for (let i = startI; i < startI + 3; i++) {
      for (let j = startJ; j < startJ + 3; j++) {
        if (board[i][j] === val) return true
      }      
    }
    return false
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1);
    for (let i = 1; i < 10; i++) {
      if (!isInside(row, col, `${i}`)) {
        board[row][col] = `${i}`
        if (fill(row, col + 1)) {
          return true
        } else {
          board[row][col] = '.'
        }
      }
    }
    return false
  }
  fill(0, 0)
  return board
};

这段代码是看了答案之后写出来的，其实还是比较简单的。

首先看看isInside方法，该方法根据当前传入的坐标值来对board进行查找，判断出当前行、当前列和当前块都没有重复的数字，如此证明这个数字可以被填在当前的格子里，如果不通过则该数字不能填在当前格子里，跳过即可，继续进行下一步填写操作。

这个方法确实比较简单，缺点就是每次都要重新查询下，有点耗费性能，下面这种方法会存储一些数据，减少查询时间。

更好的方法（存储数据）

var solveSudoku = (board) => {
  function getBlockIndex(i, j) {
    return parseInt(i / 3) * 3 + parseInt(j / 3)
  }
  var rowArr = new Array(9)
      colArr = new Array(9)
      blockArr = new Array(9)
      defaultSetting = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
  for (let i = 0; i < 9; i++) {
    rowArr[i] = new Set(defaultSetting) 
    colArr[i] = new Set(defaultSetting) 
    blockArr[i] = new Set(defaultSetting) 
  }
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      var val = board[i][j]
      if (val !== '.') {
        rowArr[i].delete(val)
        colArr[j].delete(val) 
        blockArr[getBlockIndex(i, j)].delete(val)
      }      
    }
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1);
    for (let i = 1; i < 10; i++) {
      var strNum = `${i}`
      if (rowArr[row].has(strNum) && colArr[col].has(strNum) && blockArr[getBlockIndex(row, col)].has(strNum)) {
        board[row][col] = strNum
        rowArr[row].delete(strNum)
        colArr[col].delete(strNum)
        blockArr[getBlockIndex(row, col)].delete(strNum)
        if (fill(row, col + 1)) {
          return true
        } else {
          board[row][col] = '.'
          rowArr[row].add(strNum)
          colArr[col].add(strNum)
          blockArr[getBlockIndex(row, col)].add(strNum)
        }
      }
    }
    return false
  }
  fill(0, 0)
  return board
};

这里主去掉了isInside方法，直接将9行、9列、9块中没有出现的数字填到三个数组中去，每次需要添加新数字的时候，判断这三个数组中是否有这个数字，如果都有，则可以添加，否则就不能添加。添加完成后不仅仅要修改board，也要修改三个数组。

之后判断下个空格有没有数字可填，如果没有，则回溯一下，撤销对board和三个数组的修改，进行下一次循环，以此类推。

但笔者感觉这里稍微有点复杂，其实默认传个空Set，之后往里面插入已经存在的数据。循环的时候判断当前Set是否有无也行，为了实践一下，笔者用数组也实现了一手?：

var solveSudoku = function(board) {
  var rowArr = Array.from({length: 9}, () => ([]))
      colArr = Array.from({length: 9}, () => ([]))
      blockArr = Array.from({length: 9}, () => ([]))
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] !== '.') {
        rowArr[i].push(board[i][j])
        colArr[j].push(board[i][j])
        var block = ~~(i / 3) * 3 + ~~(j / 3)
        blockArr[block].push(board[i][j])
      }      
    }    
  }
  function fill(row, col) {
    if (col === 9) {
      row++
      col = 0
      if (row === 9) return true
    }
    if (board[row][col] !== '.') return fill(row, col + 1)
    var block = ~~(row / 3) * 3 + ~~(col / 3)
    for (let i = 1; i < 10; i++) {
      if (rowArr[row].includes(`${i}`)) continue
      if (colArr[col].includes(`${i}`)) continue
      if (blockArr[block].includes(`${i}`)) continue
      board[row][col] = `${i}`
      rowArr[row].push(`${i}`)
      colArr[col].push(`${i}`)
      blockArr[block].push(`${i}`)
      if (fill(row, col + 1)) {
        return true
      } else {
        board[row][col] = '.'
        rowArr[row].pop()
        colArr[col].pop()
        blockArr[block].pop()
      }
    }
    return false
  }
  fill(0, 0)
  return board
};

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ

回复

我来回复

  • 暂无回复内容