成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

聊聊用 JavaScript 做數獨

作者：寫文章的自然醒
開發 前端
最近看到老婆天天在手機上玩數獨，突然想起 N 年前刷 LeetCode 的時候，有個類似的算法題（37.解數獨），是不是可以把這個算法進行可視化。

[[421904]]

最近看到老婆天天在手機上玩數獨，突然想起 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 字符分別對應數組的列，未填充的空格通過字符('.' )來表示。

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

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

  1. const sudoku = [……] 
  2. // 方法接受行、列兩個參數，用于定位數獨的格子 
  3. function solve(row, col) { 
  4.   if (col >= 9) {  
  5.    // 超過第九列，表示這一行已經結束了，需要另起一行 
  6.     col = 0 
  7.     row += 1 
  8.     if (row >= 9) { 
  9.       // 另起一行后，超過第九行，則整個數獨已經做完 
  10.       return true 
  11.     } 
  12.   } 
  13.   if (sudoku[row][col] !== '.') { 
  14.     // 如果該格子已經填過了，填后面的格子 
  15.     return solve(row, col + 1) 
  16.   } 
  17.   // 嘗試在該格子中填入數字 1-9 
  18.   for (let num = 1; num <= 9; num++) { 
  19.     if (!isValid(row, col, num)) { 
  20.       // 如果是無效數字，跳過該數字 
  21.       continue 
  22.     } 
  23.     // 填入數字 
  24.     sudoku[row][col] = num.toString() 
  25.     // 繼續填后面的格子 
  26.     if (solve(row, col + 1)) { 
  27.       // 如果一直到最后都沒問題，則這個格子的數字沒問題 
  28.       return true 
  29.     } 
  30.     // 如果出現了問題，solve 返回了 false 
  31.     // 說明這個地方要重填 
  32.     sudoku[row][col] = '.' // 擦除數字 
  33.   } 
  34.   // 數字 1-9 都填失敗了，說明前面的數字有問題 
  35.   // 返回 FALSE，進行回溯，前面數字要進行重填 
  36.   return false 
  37. } 

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

  1. const sudoku = [……] 
  2. function isValid(row, col, num) { 
  3.   // 判斷行里是否重復 
  4.   for (let i = 0; i < 9; i++) { 
  5.     if (sudoku[row][i] === num) { 
  6.       return false 
  7.     } 
  8.   } 
  9.   // 判斷列里是否重復 
  10.   for (let i = 0; i < 9; i++) { 
  11.     if (sudoku[i][col] === num) { 
  12.       return false 
  13.     } 
  14.   } 
  15.   // 判斷九宮格里是否重復 
  16.   const startRow = parseInt(row / 3) * 3 
  17.   const startCol = parseInt(col / 3) * 3 
  18.   for (let i = startRow; i < startRow + 3; i++) { 
  19.     for (let j = startCol; j < startCol + 3; j++) { 
  20.       if (sudoku[i][j] === num) { 
  21.         return false 
  22.       } 
  23.     } 
  24.   } 
  25.   return true 
  26. } 

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

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

輸出結果

動態展示做題過程

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

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

  1. npx create-react-app sudoku 
  2. cd sudoku 

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

  1. import React from 'react'; 
  2. import './App.css'; 
  3.  
  4. class App extends React.Component { 
  5.   state = { 
  6.     // 在 state 中配置一個數獨二維數組 
  7.     sudoku: [ 
  8.       ['.', '.', '.', '4', '.', '.', '.', '3', '.'], 
  9.       ['7', '.', '4', '8', '.', '.', '1', '.', '2'], 
  10.       ['.', '.', '.', '2', '3', '.', '4', '.', '9'], 
  11.       ['.', '4', '.', '5', '.', '9', '.', '8', '.'], 
  12.       ['5', '.', '.', '.', '.', '.', '9', '1', '3'], 
  13.       ['1', '.', '.', '.', '8', '.', '2', '.', '4'], 
  14.       ['.', '.', '.', '.', '.', '.', '3', '4', '5'], 
  15.       ['.', '5', '1', '9', '4', '.', '7', '2', '.'], 
  16.       ['4', '7', '3', '.', '5', '.', '.', '9', '1'] 
  17.     ] 
  18.   } 
  19.  
  20.  // TODO：解數獨 
  21.   solveSudoku = async () => { 
  22.     const { sudoku } = this.state 
  23.   } 
  24.  
  25.   render() { 
  26.     const { sudoku } = this.state 
  27.     return ( 
  28.       <div className="container"> 
  29.         <div className="wrapper"> 
  30.           {/* 遍歷二維數組，生成九宮格 */} 
  31.           {sudoku.map((list, row) => ( 
  32.             {/* div.row 對應數獨的行 */} 
  33.             <div className="row" key={`row-${row}`}> 
  34.               {list.map((item, col) => ( 
  35.               {/* span 對應數獨的每個格子 */} 
  36.                 <span key={`box-${col}`}>{ item !== '.' && item }</span> 
  37.               ))} 
  38.             </div> 
  39.           ))} 
  40.           <button onClick={this.solveSudoku}>開始做題</button> 
  41.         </div> 
  42.       </div> 
  43.     ); 
  44.   } 
  45. } 

九宮格樣式

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

  1. .row { 
  2.   display: flex; 
  3.   direction: row; 
  4.   /* 行內元素居中 */ 
  5.   justify-content: center; 
  6.   align-content: center; 
  7. } 
  8. .row span { 
  9.   /* 每個格子寬高一致 */ 
  10.   width: 30px; 
  11.   min-height: 30px; 
  12.   line-height: 30px; 
  13.   text-align: center; 
  14.   /* 設置虛線邊框 */ 
  15.   border: 1px dashed #999; 
  16. } 

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

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

  1. /* 第 1 行頂部加上實現邊框 */ 
  2. .row:nth-child(1) span { 
  3.   border-top: 3px solid #333; 
  4. } 
  5. /* 第 3、6、9 行底部加上實現邊框 */ 
  6. .row:nth-child(3n) span { 
  7.   border-bottom: 3px solid #333; 
  8. } 
  9. /* 第 1 列左邊加上實現邊框 */ 
  10. .row span:first-child { 
  11.   border-left: 3px solid #333; 
  12. } 
  13.  
  14. /* 第 3、6、9 列右邊加上實現邊框 */ 
  15. .row span:nth-child(3n) { 
  16.   border-right: 3px solid #333; 
  17. } 

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

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

做題邏輯

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

  1. class App extends React.Component { 
  2.   state = { 
  3.     // 在 state 中配置一個數獨二維數組 
  4.     sudoku: [……] 
  5.   } 
  6.  
  7.   solveSudoku = async () => { 
  8.     const { sudoku } = this.state 
  9.     // 判斷填入的數字是否有效，參考上面的代碼，這里不再重復 
  10.     const isValid = (row, col, num) => { 
  11.       …… 
  12.     } 
  13.     // 遞歸+回溯的方式進行解題 
  14.    const solve = async (row, col) => { 
  15.       if (col >= 9) {  
  16.         col = 0 
  17.         row += 1 
  18.         if (row >= 9) return true 
  19.       } 
  20.       if (sudoku[row][col] !== '.') { 
  21.         return solve(row, col + 1) 
  22.       } 
  23.       for (let num = 1; num <= 9; num++) { 
  24.         if (!isValid(row, col, num)) { 
  25.           continue 
  26.         } 
  27.   
  28.         sudoku[row][col] = num.toString() 
  29.         this.setState({ sudoku }) // 填了格子之后，需要同步到 state 
  30.  
  31.         if (solve(row, col + 1)) { 
  32.           return true 
  33.         } 
  34.  
  35.         sudoku[row][col] = '.' 
  36.         this.setState({ sudoku }) // 填了格子之后，需要同步到 state 
  37.       } 
  38.       return false 
  39.     } 
  40.     // 進行解題 
  41.     solve(0, 0) 
  42.   } 
  43.  
  44.   render() { 
  45.     const { sudoku } = this.state 
  46.     return (……) 
  47.   } 
  48. } 

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

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

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

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

  1. solveSudoku = async () => { 
  2.   const { sudoku } = this.state 
  3.   // 判斷填入的數字是否有效，參考上面的代碼，這里不再重復 
  4.   const isValid = (row, col, num) => { 
  5.     …… 
  6.   } 
  7.   // 脫離事件流，調用 setState 
  8.   const setSudoku = async (row, col, value) => { 
  9.     sudoku[row][col] = value 
  10.     return new Promise(resolve => { 
  11.       setTimeout(() => { 
  12.         this.setState({ 
  13.           sudoku 
  14.         }, () => resolve()) 
  15.       }) 
  16.     }) 
  17.   } 
  18.   // 遞歸+回溯的方式進行解題 
  19.   const solve = async (row, col) => { 
  20.     …… 
  21.     for (let num = 1; num <= 9; num++) { 
  22.       if (!isValid(row, col, num)) { 
  23.         continue 
  24.       } 
  25.  
  26.    await setSudoku(row, col, num.toString()) 
  27.  
  28.       if (await solve(row, col + 1)) { 
  29.         return true 
  30.       } 
  31.  
  32.    await setSudoku(row, col, '.') 
  33.     } 
  34.     return false 
  35.   } 
  36.   // 進行解題 
  37.   solve(0, 0) 
  38. } 

最后效果如下：

本文轉載自微信公眾號「自然醒的筆記本」，可以通過以下二維碼關注。轉載本文請聯系自然醒的筆記本公眾號。

 

責任編輯：武曉燕 來源： 自然醒的筆記本
JavaScript 數獨 LeetCode
相關推薦

2021-10-17 22:40:51

JavaScript開發 框架

2021-01-07 07:53:10

JavaScript內存管理

2023-11-06 11:33:15

C++數獨

2022-02-09 11:02:16

JavaScript前端框架

2021-01-31 23:54:23

數倉模型

2013-06-20 10:52:37

算法實踐數獨算法數獨源碼

2022-07-29 14:47:34

數獨Sudoku鴻蒙

2019-07-23 15:04:54

JavaScript調用棧事件循環

2021-06-02 09:01:19

JavaScript 前端異步編程

2023-11-20 08:01:38

并發處理數Tomcat

2013-06-17 12:44:38

WP7開發Windows Pho數獨游戲

2022-10-19 15:19:53

數獨Sudoku鴻蒙

2022-10-19 15:27:36

數獨Sudoku鴻蒙

2022-10-18 15:45:17

數獨Sudoku鴻蒙

2021-09-08 08:55:45

Javascript 高階函數前端

2022-02-23 09:03:29

JavaScript開發命名約定

2022-02-23 08:18:06

nginx前端location

2022-03-01 17:16:16

數倉建模ID Mapping

2020-06-15 08:13:42

Linux服務端并發數

2020-09-24 16:40:20

人工智能量子計算技術
點贊
收藏

51CTO技術棧公眾號

主站蜘蛛池模板： 精品久久久久国产 | 国产成人综合一区二区三区 | 在线视频 亚洲 | 色婷婷综合久久久中字幕精品久久 | 婷婷激情综合 | 国产日韩一区二区三区 | av片在线观看 | 欧美亚洲视频 | 人人鲁人人莫人人爱精品 | 免费视频成人国产精品网站 | 99爱国产 | 欧美精品免费观看二区 | 欧美成人a∨高清免费观看 色999日韩 | 精品国产鲁一鲁一区二区张丽 | 在线三级网址 | 亚洲v日韩v综合v精品v | 欧美一区二区免费电影 | 日本三级日产三级国产三级 | 亚洲最色视频 | 在线观看免费国产 | 亚洲综合色网 | 不卡av电影在线播放 | 国产在线一区二 | 国产亚洲一区二区三区 | 国产小视频在线观看 | 国产精品美女一区二区 | 超碰激情 | 国产成人在线一区二区 | 午夜精品一区二区三区在线视 | 日韩精品一区二区三区视频播放 | 国产99视频精品免费视频7 | 色视频在线免费观看 | 日韩av成人在线观看 | 亚洲视屏 | 久久成人综合 | 日韩美av| 亚洲午夜精品 | 日韩欧美一区在线 | 久久国产香蕉 | 国产三级大片 | 欧美lesbianxxxxhd视频社区 |