[codewars]如何校验数独

题目来源:http://www.codewars.com/kata/sudoku-solution-validator

如何校验数独

你怎么不知道数独?快去看看百度百科,顺便搜索一款在线游戏杀两盘。

本文不会教你如何成为数独高手,而是探讨一下如何校验数独的正确性,也就是满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复,然后用 js 来实现它。

为了能让 js 也认识数独,我们将其抽象为一个二维数组:

 var sudoku = [[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]]

然后去实现一个 validSolution(sudoku) 函数,来返回 true|false.

均含 1-9

参考来源

首先呢,我们将每一行,每一列,每一个粗线宫的数字取出来,放到相应数组内:

function validSolution(board){  
  var arrh = [[],[],[],[],[],[],[],[],[]];
  var arrv = [[],[],[],[],[],[],[],[],[]];
  var arrb = [[[],[],[]],[[],[],[]],[[],[],[]]];
  for (var i=0;i<9;i++){
    for (var j=0;j<9;j++){
      arrh[i].push(board[i][j]);
      arrv[j].push(board[i][j]);
      arrb[Math.floor(i/3)][Math.floor(j/3)].push(board[i][j]);
    }
  }
}

然后,doSomething,就是判断是否包含 1-9 咯,如何做呢?

  1. 排序,使其成为 1,2,3,4,5,6,7,8,9
    • arr.sort()
  2. 转为字符串,与 123456789 对比
    • arr.join()
function validArr(arr){  
    return arr.sort(function(a,b){return a-b}).join("") === "123456789"
}

和为 45

参考来源

  1. 首先呢,我们还是将每一行,每一列,每一个粗线宫的数字取出来,放到相应数组内
  2. 然后,加起来等于 45 吧。

但是,这样并不严密,所有数字都填 5 的话,也就通过了。

1-9 有且只有一次

参考来源

  1. 首先呢,我们还是将每一行,每一列,每一个粗线宫的数字取出来,放到相应数组内
  2. 然后,取每一个数在数组中第一次出现的位置,如果出现了两次,位置也就不对咯
    • arr.indexOf()
function validRange(arr) {  
  for (var i=0; i<arr.length; i++) {
    if (arr[i] < 1 || arr[i] > 9 || arr.indexOf(arr[i]) !== i) return false
  }
  return true;
}

递增排序后,我是我所在位置数+1

参考来源

  1. 首先呢,我们还是将每一行,每一列,每一个粗线宫的数字取出来,放到相应数组内
  2. 然后,递增排序,与位置数进行比较
function check(numbers){  
  return numbers.slice(0).sort().every(function(e, i){return e==i+1;});
}

是时候逆向思维一次了

参考来源

  1. 咱创建一个长度为 9 的 tmp 数组,每个元素由一个占位对象填充
  2. 取第一行的每一个数字做为位置数,判断 tmp 数组对应位置的占位对象是否存在
    • 如果存在,就将 tmp 数组相应位置删除
      • delete
    • 如果不存在,就表示有两个数字重复了
  3. 将每一行、每一列、每一个粗线宫按步骤二重复

总结,我是来引吐槽的

如果你是大神,或有更好的方案,欢迎在下方留言。

微信扫描查看或分享
加入我们