用 JavaScript 做數獨

者：寫文章的自然醒來源：自然醒的筆記本

最近看到老婆天天在手機上玩數獨，突然想起 N 年前刷 LeetCode 的時候，有個類似的算法題(37.解數獨)，是不是可以把這個算法進行可視化。

說干就干，經過一個小時的實踐，最終效果如下：

怎么解數獨

解數獨之前，我們先了解一下數獨的規則：

數字 1-9 在每一行只能出現一次。

數字 1-9 在每一列只能出現一次。

數字 1-9 在每一個以粗實線分隔的九宮格( 3x3 )內只能出現一次。

接下來，我們要做的就是在每個格子里面填一個數字，然后判斷這個數字是否違反規定。

填第一個格子

首先，在第一個格子填 1，發現在第一列里面已經存在一個 1，此時就需要擦掉前面填的數字 1，然后在格子里填上 2，發現數字在行、列、九宮格內均無重復。那么這個格子就填成功了。

填第二個格子

下面看第二個格子，和前面一樣，先試試填 1，發現在行、列、九宮格內的數字均無重復，那這個格子也填成功了。

填第三個格子

下面看看第三個格子，由于前面兩個格子，我們已經填過數字 1、2，所以，我們直接從數字 3 開始填。填 3 后，發現在第一行里面已經存在一個 3，然后在格子里填上 4，發現數字 4 在行和九宮格內均出現重復，依舊不成功，然后嘗試填上數字 5，終于沒有了重復數字，表示填充成功。

……

一直填……

填第九個格子

照這個思路，一直填到第九個格子，這個時候，會發現，最后一個數字 9 在九宮格內沖突了。而 9 已經是最后一個數字了，這里沒辦法填其他數字了，只能返回上一個格子，把第七個格子的數字從 8 換到 9，發現在九宮格內依然沖突。

此時需要替換上上個格子的數字(第六個格子)。直到沒有沖突為止，所以在這個過程中，不僅要往后填數字，還要回過頭看看前面的數字有沒有問題，不停地嘗試。

綜上所述

解數獨就是一個不斷嘗試的過程，每個格子把數字 1-9 都嘗試一遍，如果出現沖突就擦掉這個數字，直到所有的格子都填完。

通過代碼來實現

把上面的解法反映到代碼上，就需要通過遞歸 + 回溯的思路來實現。

在寫代碼之前，先看看怎么把數獨表示出來，這里參考 leetcode 上的題目：37. 解數獨。

前面的這個題目，可以使用一個二維數組來表示。最外層數組內一共有 9 個數組，表示數獨的 9 行，內部的每個數組內 9 字符分別對應數組的列，未填充的空格通過字符('.' )來表示。

const sudoku = [ 
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'], 
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'], 
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'], 
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'], 
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'], 
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'], 
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'], 
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'], 
  ['4', '7', '3', '.', '5', '.', '.', '9', '1'], 
]

知道如何表示數組后，我們再來寫代碼。

const sudoku = [……] 
// 方法接受行、列兩個參數，用于定位數獨的格子 
function solve(row, col) { 
  if (col >= 9) {  
   // 超過第九列，表示這一行已經結束了，需要另起一行 
    col = 0 
    row += 1 
    if (row >= 9) { 
      // 另起一行后，超過第九行，則整個數獨已經做完 
      return true 
    } 
  } 
  if (sudoku[row][col] !== '.') { 
    // 如果該格子已經填過了，填后面的格子 
    return solve(row, col + 1) 
  } 
  // 嘗試在該格子中填入數字 1-9 
  for (let num = 1; num <= 9; num++) { 
    if (!isValid(row, col, num)) { 
      // 如果是無效數字，跳過該數字 
      continue 
    } 
    // 填入數字 
    sudoku[row][col] = num.toString() 
    // 繼續填后面的格子 
    if (solve(row, col + 1)) { 
      // 如果一直到最后都沒問題，則這個格子的數字沒問題 
      return true 
    } 
    // 如果出現了問題，solve 返回了 false 
    // 說明這個地方要重填 
    sudoku[row][col] = '.' // 擦除數字 
  } 
  // 數字 1-9 都填失敗了，說明前面的數字有問題 
  // 返回 FALSE，進行回溯，前面數字要進行重填 
  return false 
}

上面的代碼只是實現了遞歸、回溯的部分，還有一個 isValid 方法沒有實現。該方法主要就是按照數獨的規則進行一次校驗。

const sudoku = [……] 
function isValid(row, col, num) { 
  // 判斷行里是否重復 
  for (let i = 0; i < 9; i++) { 
    if (sudoku[row][i] === num) { 
      return false 
    } 
  } 
  // 判斷列里是否重復 
  for (let i = 0; i < 9; i++) { 
    if (sudoku[i][col] === num) { 
      return false 
    } 
  } 
  // 判斷九宮格里是否重復 
  const startRow = parseInt(row / 3) * 3 
  const startCol = parseInt(col / 3) * 3 
  for (let i = startRow; i < startRow + 3; i++) { 
    for (let j = startCol; j < startCol + 3; j++) { 
      if (sudoku[i][j] === num) { 
        return false 
      } 
    } 
  } 
  return true 
}

通過上面的代碼，我們就能解出一個數獨了。

const sudoku = [ 
  ['.', '.', '.', '4', '.', '.', '.', '3', '.'], 
  ['7', '.', '4', '8', '.', '.', '1', '.', '2'], 
  ['.', '.', '.', '2', '3', '.', '4', '.', '9'], 
  ['.', '4', '.', '5', '.', '9', '.', '8', '.'], 
  ['5', '.', '.', '.', '.', '.', '9', '1', '3'], 
  ['1', '.', '.', '.', '8', '.', '2', '.', '4'], 
  ['.', '.', '.', '.', '.', '.', '3', '4', '5'], 
  ['.', '5', '1', '9', '4', '.', '7', '2', '.'], 
  ['4', '7', '3', '.', '5', '.', '.', '9', '1'] 
] 
function isValid(row, col, num) {……} 
function solve(row, col) {……} 
solve(0, 0) // 從第一個格子開始解 
console.log(sudoku) // 輸出結果

輸出結果

動態展示做題過程

有了上面的理論知識，我們就可以把這個做題的過程套到 react 中，動態的展示做題的過程，也就是文章最開始的 Gif 中的那個樣子。

這里直接使用 create-react-app 腳手架快速啟動一個項目

npx create-react-app sudoku 
cd sudoku

打開 App.jsx ，開始寫代碼。

import React from 'react'; 
import './App.css'; 
 
class App extends React.Component { 
  state = { 
    // 在 state 中配置一個數獨二維數組 
    sudoku: [ 
      ['.', '.', '.', '4', '.', '.', '.', '3', '.'], 
      ['7', '.', '4', '8', '.', '.', '1', '.', '2'], 
      ['.', '.', '.', '2', '3', '.', '4', '.', '9'], 
      ['.', '4', '.', '5', '.', '9', '.', '8', '.'], 
      ['5', '.', '.', '.', '.', '.', '9', '1', '3'], 
      ['1', '.', '.', '.', '8', '.', '2', '.', '4'], 
      ['.', '.', '.', '.', '.', '.', '3', '4', '5'], 
      ['.', '5', '1', '9', '4', '.', '7', '2', '.'], 
      ['4', '7', '3', '.', '5', '.', '.', '9', '1'] 
    ] 
  } 
 
 // TODO：解數獨 
  solveSudoku = async () => { 
    const { sudoku } = this.state 
  } 
 
  render() { 
    const { sudoku } = this.state 
    return ( 
      <div className="container"> 
        <div className="wrapper"> 
          {/* 遍歷二維數組，生成九宮格 */} 
          {sudoku.map((list, row) => ( 
            {/* div.row 對應數獨的行 */} 
            <div className="row" key={`row-${row}`}> 
              {list.map((item, col) => ( 
              {/* span 對應數獨的每個格子 */} 
                <span key={`box-${col}`}>{ item !== '.' && item }</span> 
              ))} 
            </div> 
          ))} 
          <button onClick={this.solveSudoku}>開始做題</button> 
        </div> 
      </div> 
    ); 
  } 
}

九宮格樣式

給每個格子加上一個虛線的邊框，先讓它有一點九宮格的樣子。

.row { 
  display: flex; 
  direction: row; 
  /* 行內元素居中 */ 
  justify-content: center; 
  align-content: center; 
} 
.row span { 
  /* 每個格子寬高一致 */ 
  width: 30px; 
  min-height: 30px; 
  line-height: 30px; 
  text-align: center; 
  /* 設置虛線邊框 */ 
  border: 1px dashed #999; 
}

可以得到一個這樣的圖形：

接下來，需要給外邊框和每個九宮格加上實線的邊框，具體代碼如下：

/* 第 1 行頂部加上實現邊框 */ 
.row:nth-child(1) span { 
  border-top: 3px solid #333; 
} 
/* 第 3、6、9 行底部加上實現邊框 */ 
.row:nth-child(3n) span { 
  border-bottom: 3px solid #333; 
} 
/* 第 1 列左邊加上實現邊框 */ 
.row span:first-child { 
  border-left: 3px solid #333; 
} 
 
/* 第 3、6、9 列右邊加上實現邊框 */ 
.row span:nth-child(3n) { 
  border-right: 3px solid #333; 
}

這里會發現第三、六列的右邊邊框和第四、七列的左邊邊框會有點重疊，第三、六行的底部邊框和第四、七行的頂部邊框也會有這個問題，所以，我們還需要將第四、七列的左邊邊框和第三、六行的底部邊框進行隱藏。

.row:nth-child(3n + 1) span { 
  border-top: none; 
} 
.row span:nth-child(3n + 1) { 
  border-left: none; 
}

做題邏輯

樣式寫好后，就可以繼續完善做題的邏輯了。

class App extends React.Component { 
  state={ 
    // 在 state 中配置一個數獨二維數組 
    sudoku: [……] 
  } 
 
  solveSudoku=async ()=> { 
    const { sudoku }=this.state 
    // 判斷填入的數字是否有效，參考上面的代碼，這里不再重復 
    const isValid=(row, col, num)=> { 
      …… 
    } 
    // 遞歸+回溯的方式進行解題 
   const solve=async (row, col)=> { 
      if (col >=9) {  
        col=0 
        row +=1 
        if (row >=9) return true 
      } 
      if (sudoku[row][col] !=='.') { 
        return solve(row, col + 1) 
      } 
      for (let num=1; num <=9; num++) { 
        if (!isValid(row, col, num)) { 
          continue 
        } 
  
        sudoku[row][col]=num.toString() 
        this.setState({ sudoku }) // 填了格子之后，需要同步到 state 
 
        if (solve(row, col + 1)) { 
          return true 
        } 
 
        sudoku[row][col]='.' 
        this.setState({ sudoku }) // 填了格子之后，需要同步到 state 
      } 
      return false 
    } 
    // 進行解題 
    solve(0, 0) 
  } 
 
  render() { 
    const { sudoku }=this.state 
    return (……) 
  } 
}

對比之前的邏輯，這里只是在對數獨的二維數組填空后，調用了 this.setState 將 sudoku 同步到了 state 中。

function solve(row, col) { 
   …… 
   sudoku[row][col]=num.toString() 
+  this.setState({ sudoku }) 
  …… 
   sudoku[row][col]='.' 
+  this.setState({ sudoku }) // 填了格子之后，需要同步到 state 
}

在調用 solveSudoku 后，發現并沒有出現動態的效果，而是直接一步到位的將結果同步到了視圖中。

這是因為 setState 是一個偽異步調用，在一個事件任務中，所以的 setState 都會被合并成一次，需要看到動態的做題過程，我們需要將每一次 setState 操作放到該事件流之外，也就是放到 setTimeout 中。更多關于 setState 異步的問題，可以參考我之前的文章：React 中 setState 是一個宏任務還是微任務?

solveSudoku=async ()=> { 
  const { sudoku }=this.state 
  // 判斷填入的數字是否有效，參考上面的代碼，這里不再重復 
  const isValid=(row, col, num)=> { 
    …… 
  } 
  // 脫離事件流，調用 setState 
  const setSudoku=async (row, col, value)=> { 
    sudoku[row][col]=value 
    return new Promise(resolve=> { 
      setTimeout(()=> { 
        this.setState({ 
          sudoku 
        }, ()=> resolve()) 
      }) 
    }) 
  } 
  // 遞歸+回溯的方式進行解題 
  const solve=async (row, col)=> { 
    …… 
    for (let num=1; num <=9; num++) { 
      if (!isValid(row, col, num)) { 
        continue 
      } 
 
   await setSudoku(row, col, num.toString()) 
 
      if (await solve(row, col + 1)) { 
        return true 
      } 
 
   await setSudoku(row, col, '.') 
    } 
    return false 
  } 
  // 進行解題 
  solve(0, 0) 
}

最后效果如下：

端數獨變形系列——表面數獨

規則

1、將1-9填入空格，使每一行、每一列、每一宮數字不重復。

2、標記黑點的四格數字逆時針方向逐漸增大，標記白點的四格數字呈順時針方向逐漸增大，四格中的起點未定，符合條件的已經全部標出，即未標記黑白點的不能有順或逆時針逐漸增大。

此題型也是下周窮錦賽周賽的變形題型，歡迎大家提前了解。

在線做題：

http://www.sudokufans.org.cn/pk7a/ti.php?id=171

廣告分割線

當當當當，下面是廣告時間，經過長時間的努力，精選高端數獨發過的20種題型的《趣味變型數獨題集》終于上市了。

讓我們引用羅老師的話，少啰嗦，先看東西！

看到圖片，是不是就想買了，那下面這段自吹自擂的介紹你就別看了。

《趣味變型數獨題集:升級版》精選了20種變型數獨題型，共計200道題，不僅有額外區域數獨、重影數獨、候選數數獨、箭頭數獨、連續數獨等大賽中常見題型，還集結了反對角線數獨、外提示3數獨、標桿數獨等市面難覓的題型。本書不僅可以為開拓孩子數學思維使用，也可供準備參加大賽的選手提高解題水平練習使用，是數獨愛好者必備的變型數獨練習題集。書中各種題型依據難易程度，循序漸進，難度設置合理并配有答案。

書名：趣味變型數獨題集：升級版；出版社：知識產權出版社；開本：32開；印張7.5；尺寸148*210；定價：35元；ISBN 978-7-5130-5528-4

購買鏈接

http://product.dangdang.com/25296102.html

https://item.jd.com/12387698.html

何用數獨來進行表白（高端數獨變形系列）

規則
1、將數字1-9填入盤內空白格，使每一行每一列每一宮數字不重復。
2、標記白點（順）表示四格數字按順時針方向逐漸增大，標記黑點（逆）表示四格數字按逆時針方向逐漸增大，符合條件的已經全部標出。

接下來，你要做的是，關注公眾號，轉發給想念的人，然后就可以開始虐狗了。