回溯算法与数独

在很多情况下,回溯算法相当于穷举算法的巧妙实现。但性能并不理想。不过情况并非总是如此,即使如此，在某些情况下它相比于蛮力穷举搜索，工作量也有显著节省。当然,性能是相对的，对于排序而言，O(N²)的算法是相当差的,但对于旅行售货员(或任何NP完全问题)，O(N⁵)的算法则是里程碑式的结果。

数独问题，也可以通过回溯算法实现。虽然存在许多可能的尝试，但是只有少量的几个是具体要考虑的。开始，给定一个留有空白的数独，将其转成长度为81的一维数组。如果，所有的空白都填写上对应的数字，并且符合数独的规则，那么算法终止。如果填写到某一个空格，该空格之后的所有数字摆放都不理想，那么我们必须使用其他的数字，填充这一个空格。当然，这也可能导致另外的重新摆放。如果我们发现，第一个空格尝试了所有的可能，并且没有找到问题的解，那么该问题就不存在解。否则，我们最终终止在完成问题的解。这个算法基本上是蛮力的，当时它并不直接尝试所有的可能。例如，如果数字n(1~9)已经出现在空白所属的行、列或时小九宫格中，该值是绝对不考虑的。通过条件约束，可以过滤大出一大组可能的组合。

一、边界条件的判定

1、列的判定

 /**
  * 边界条件的判定
  * @param {int} p 位置
  * @param {int} v 值
  * @param {array} arr 数独列表
  * @return {boolean}
  */
  checkCol (p, v, arr) {
    // 计算该元素所属的列
     let col = p % 9
     for (const len = col + 72; col <= len; col += 9) {
       if (arr[col] && p !== col && arr[col].number === v) {
         return false
       }
     }
     return true
  }

2、行的判定

/**
 * 边界条件的判定
 * 
 * @param {int} p 位置
 * @param {int} v 值
 * @param {array} arr 数独列表
 * @return {boolean}
 */
 checkRow (p, v, arr) {
   // 计算 p所属的行 起始位置
   let i = parseInt(p / 9) * 9

   for (const len = i + 9; i < len; i++) {
     if (arr[i] && p !== i && arr[i].number === v) {
        return false
     }
   }
   return true
 }

3、3 * 3九宫格的判定

/**
 * 边界条件的判定
 * 
 * @param {int} p 位置
 * @param {int} v 值
 * @param {array} arr 数独列表
 * @return {boolean}
 */
 checkGrid (p, v, arr) {
   // 计算 p 位置所在的小九宫格的第一个元素下标
   let position = parseInt(p % 9 / 3) * 3 + parseInt(parseInt(p / 9) / 3) * 27

  for (let i = 0, len = 3; i < len; i++) {
    if (arr[position] && p !== position && arr[position].number === v) {
      return false
    }

    if (arr[++position] && p !== position && arr[position].number === v) {
      return false
    }

    if (arr[++position] && p !== position && arr[position].number === v) {
      return false
    }

    position += 7
  }

   return true
 }

二、初始化

生成一个随机的数独，并不是所有位置的数字都是随机的，只需要在特定的位置放置几个随机数，然后通过回溯算法填充完毕即可。那么随机数的数量和位置需要怎么选择呢？考虑到数独是一个9 * 9的表格，其规则是在行、列或是3 * 3的小九宫格中不能出现同样的数字。我们就可以在斜对角线的3个3 * 3的小九宫格中，各自随机摆放1~9的随机数，而无需考虑行和列的约束。如下所示。

我们可以通过如下代码，为3 * 3的小九宫格生成一个随机数。

/**
 * 为小的九宫格分配随机数
 * 
 * @param {int} position 小九宫格的起始位置
 * @param {array} arr 数独列表
 * @returns {void}
 */
 assignRandom (position, arr) {
   const numberList = Array.apply(null, { length: 9 }).map((val, index) => index + 1)
   let tempRandom

   for (let j = 0, len = 3; j < len; j++) {
      for (let i = 0, length = 3; i < length; i++) {
         tempRandom = Math.floor(Math.random() * numberList.length)
         arr[position + i] = { id: arr[position + i].id, number: numberList[tempRandom], fixed: true }
         numberList.splice(tempRandom, 1)
      }
      position += 9
   }
 }

三、回溯

/**
 * 使用回溯生成数独表格
 * 
 * @param {array} arr
 */
 backTracking (arr) {
   let n = 3 // 数组下标

   while(n >= 3) {
     // 如果值已经被初始化,不进行操作     // fixed 表示该值是预定义的，无需更改 
     if (arr[n].fixed) {
       ++n
       continue
     }

     do {
       ++arr[n].number
     } while(arr[n].number <= 9 && ! this.checkCeil(n, arr[n].number, arr))

     // 如果数组超过 9,回溯
     if (arr[n].number > 9) {
       arr[n].number = 0       // 回溯操作
       do{
         --n
       }while(arr[n].fixed)
       } else if (n === 77) {
         // 判断是否结束
         return
         } else {
           ++n
     }
   }
 }

四、最终效果

提交

暂无评论

一、 边界条件的判定