利用JavaScript做數(shù)獨(dú)的完整實(shí)現(xiàn)過程
前言
最近看到老婆天天在手機(jī)上玩數(shù)獨(dú),突然想起 N 年前刷 LeetCode 的時(shí)候,有個(gè)類似的算法題(37.解數(shù)獨(dú)),是不是可以把這個(gè)算法進(jìn)行可視化。
說干就干,經(jīng)過一個(gè)小時(shí)的實(shí)踐,最終效果如下:
怎么解數(shù)獨(dú)
解數(shù)獨(dú)之前,我們先了解一下數(shù)獨(dú)的規(guī)則:
- 數(shù)字 1-9 在每一行只能出現(xiàn)一次。
- 數(shù)字 1-9 在每一列只能出現(xiàn)一次。
- 數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的九宮格( 3x3 )內(nèi)只能出現(xiàn)一次。
接下來,我們要做的就是在每個(gè)格子里面填一個(gè)數(shù)字,然后判斷這個(gè)數(shù)字是否違反規(guī)定。
填第一個(gè)格子
首先,在第一個(gè)格子填 1,發(fā)現(xiàn)在第一列里面已經(jīng)存在一個(gè) 1,此時(shí)就需要擦掉前面填的數(shù)字 1,然后在格子里填上 2,發(fā)現(xiàn)數(shù)字在行、列、九宮格內(nèi)均無重復(fù)。那么這個(gè)格子就填成功了。
填第二個(gè)格子
下面看第二個(gè)格子,和前面一樣,先試試填 1,發(fā)現(xiàn)在行、列、九宮格內(nèi)的數(shù)字均無重復(fù),那這個(gè)格子也填成功了。
填第三個(gè)格子
下面看看第三個(gè)格子,由于前面兩個(gè)格子,我們已經(jīng)填過數(shù)字 1、2,所以,我們直接從數(shù)字 3 開始填。填 3 后,發(fā)現(xiàn)在第一行里面已經(jīng)存在一個(gè) 3,然后在格子里填上 4,發(fā)現(xiàn)數(shù)字 4 在行和九宮格內(nèi)均出現(xiàn)重復(fù),依舊不成功,然后嘗試填上數(shù)字 5,終于沒有了重復(fù)數(shù)字,表示填充成功。
……
一直填……
填第九個(gè)格子
照這個(gè)思路,一直填到第九個(gè)格子,這個(gè)時(shí)候,會(huì)發(fā)現(xiàn),最后一個(gè)數(shù)字 9 在九宮格內(nèi)沖突了。而 9 已經(jīng)是最后一個(gè)數(shù)字了,這里沒辦法填其他數(shù)字了,只能返回上一個(gè)格子,把第七個(gè)格子的數(shù)字從 8 換到 9,發(fā)現(xiàn)在九宮格內(nèi)依然沖突。
此時(shí)需要替換上上個(gè)格子的數(shù)字(第六個(gè)格子)。直到?jīng)]有沖突為止,所以在這個(gè)過程中,不僅要往后填數(shù)字,還要回過頭看看前面的數(shù)字有沒有問題,不停地嘗試。
綜上所述
解數(shù)獨(dú)就是一個(gè)不斷嘗試的過程,每個(gè)格子把數(shù)字 1-9 都嘗試一遍,如果出現(xiàn)沖突就擦掉這個(gè)數(shù)字,直到所有的格子都填完。
通過代碼來實(shí)現(xiàn)
把上面的解法反映到代碼上,就需要通過 遞歸 + 回溯 的思路來實(shí)現(xiàn)。
在寫代碼之前,先看看怎么把數(shù)獨(dú)表示出來,這里參考 leetcode 上的題目:37. 解數(shù)獨(dú)。
前面的這個(gè)題目,可以使用一個(gè)二維數(shù)組來表示。最外層數(shù)組內(nèi)一共有 9 個(gè)數(shù)組,表示數(shù)獨(dú)的 9 行,內(nèi)部的每個(gè)數(shù)組內(nèi) 9 字符分別對(duì)應(yīng)數(shù)組的列,未填充的空格通過字符('.' )來表示。
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'], ]
知道如何表示數(shù)組后,我們?cè)賮韺懘a。
const sudoku = [……] // 方法接受行、列兩個(gè)參數(shù),用于定位數(shù)獨(dú)的格子 function solve(row, col) { if (col >= 9) { // 超過第九列,表示這一行已經(jīng)結(jié)束了,需要另起一行 col = 0 row += 1 if (row >= 9) { // 另起一行后,超過第九行,則整個(gè)數(shù)獨(dú)已經(jīng)做完 return true } } if (sudoku[row][col] !== '.') { // 如果該格子已經(jīng)填過了,填后面的格子 return solve(row, col + 1) } // 嘗試在該格子中填入數(shù)字 1-9 for (let num = 1; num <= 9; num++) { if (!isValid(row, col, num)) { // 如果是無效數(shù)字,跳過該數(shù)字 continue } // 填入數(shù)字 sudoku[row][col] = num.toString() // 繼續(xù)填后面的格子 if (solve(row, col + 1)) { // 如果一直到最后都沒問題,則這個(gè)格子的數(shù)字沒問題 return true } // 如果出現(xiàn)了問題,solve 返回了 false // 說明這個(gè)地方要重填 sudoku[row][col] = '.' // 擦除數(shù)字 } // 數(shù)字 1-9 都填失敗了,說明前面的數(shù)字有問題 // 返回 FALSE,進(jìn)行回溯,前面數(shù)字要進(jìn)行重填 return false }
上面的代碼只是實(shí)現(xiàn)了遞歸、回溯的部分,還有一個(gè) isValid 方法沒有實(shí)現(xiàn)。該方法主要就是按照數(shù)獨(dú)的規(guī)則進(jìn)行一次校驗(yàn)。
const sudoku = [……] function isValid(row, col, num) { // 判斷行里是否重復(fù) for (let i = 0; i < 9; i++) { if (sudoku[row][i] === num) { return false } } // 判斷列里是否重復(fù) for (let i = 0; i < 9; i++) { if (sudoku[i][col] === num) { return false } } // 判斷九宮格里是否重復(fù) 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 }
通過上面的代碼,我們就能解出一個(gè)數(shù)獨(dú)了。
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) // 從第一個(gè)格子開始解 console.log(sudoku) // 輸出結(jié)果
動(dòng)態(tài)展示做題過程
有了上面的理論知識(shí),我們就可以把這個(gè)做題的過程套到 react 中,動(dòng)態(tài)的展示做題的過程,也就是文章最開始的 Gif 中的那個(gè)樣子。
這里直接使用 create-react-app 腳手架快速啟動(dòng)一個(gè)項(xiàng)目
npx create-react-app sudoku cd sudoku
打開 App.jsx ,開始寫代碼。
import React from 'react'; import './App.css'; class App extends React.Component { state = { // 在 state 中配置一個(gè)數(shù)獨(dú)二維數(shù)組 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:解數(shù)獨(dú) solveSudoku = async () => { const { sudoku } = this.state } render() { const { sudoku } = this.state return ( <div className="container"> <div className="wrapper"> {/* 遍歷二維數(shù)組,生成九宮格 */} {sudoku.map((list, row) => ( {/* div.row 對(duì)應(yīng)數(shù)獨(dú)的行 */} <div className="row" key={`row-${row}`}> {list.map((item, col) => ( {/* span 對(duì)應(yīng)數(shù)獨(dú)的每個(gè)格子 */} <span key={`box-${col}`}>{ item !== '.' && item }</span> ))} </div> ))} <button onClick={this.solveSudoku}>開始做題</button> </div> </div> ); } }
九宮格樣式
給每個(gè)格子加上一個(gè)虛線的邊框,先讓它有一點(diǎn)九宮格的樣子。
.row { display: flex; direction: row; /* 行內(nèi)元素居中 */ justify-content: center; align-content: center; } .row span { /* 每個(gè)格子寬高一致 */ width: 30px; min-height: 30px; line-height: 30px; text-align: center; /* 設(shè)置虛線邊框 */ border: 1px dashed #999; }
可以得到一個(gè)這樣的圖形:
接下來,需要給外邊框和每個(gè)九宮格加上實(shí)線的邊框,具體代碼如下:
/* 第 1 行頂部加上實(shí)現(xiàn)邊框 */ .row:nth-child(1) span { border-top: 3px solid #333; } /* 第 3、6、9 行底部加上實(shí)現(xiàn)邊框 */ .row:nth-child(3n) span { border-bottom: 3px solid #333; } /* 第 1 列左邊加上實(shí)現(xiàn)邊框 */ .row span:first-child { border-left: 3px solid #333; } /* 第 3、6、9 列右邊加上實(shí)現(xiàn)邊框 */ .row span:nth-child(3n) { border-right: 3px solid #333; }
這里會(huì)發(fā)現(xiàn)第三、六列的右邊邊框和第四、七列的左邊邊框會(huì)有點(diǎn)重疊,第三、六行的底部邊框和第四、七行的頂部邊框也會(huì)有這個(gè)問題,所以,我們還需要將第四、七列的左邊邊框和第三、六行的底部邊框進(jìn)行隱藏。
.row:nth-child(3n + 1) span { border-top: none; } .row span:nth-child(3n + 1) { border-left: none; }
做題邏輯
樣式寫好后,就可以繼續(xù)完善做題的邏輯了。
class App extends React.Component { state = { // 在 state 中配置一個(gè)數(shù)獨(dú)二維數(shù)組 sudoku: [……] } solveSudoku = async () => { const { sudoku } = this.state // 判斷填入的數(shù)字是否有效,參考上面的代碼,這里不再重復(fù) const isValid = (row, col, num) => { …… } // 遞歸+回溯的方式進(jìn)行解題 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 } // 進(jìn)行解題 solve(0, 0) } render() { const { sudoku } = this.state return (……) } }
對(duì)比之前的邏輯,這里只是在對(duì)數(shù)獨(dú)的二維數(shù)組填空后,調(diào)用了 this.setState 將 sudoku 同步到了 state 中。
function solve(row, col) { …… sudoku[row][col] = num.toString() + this.setState({ sudoku }) …… sudoku[row][col] = '.' + this.setState({ sudoku }) // 填了格子之后,需要同步到 state }
在調(diào)用 solveSudoku 后,發(fā)現(xiàn)并沒有出現(xiàn)動(dòng)態(tài)的效果,而是直接一步到位的將結(jié)果同步到了視圖中。
這是因?yàn)?setState 是一個(gè)偽異步調(diào)用,在一個(gè)事件任務(wù)中,所以的 setState 都會(huì)被合并成一次,需要看到動(dòng)態(tài)的做題過程,我們需要將每一次 setState 操作放到該事件流之外,也就是放到 setTimeout 中。更多關(guān)于 setState 異步的問題,可以參考我之前的文章:React 中 setState 是一個(gè)宏任務(wù)還是微任務(wù)?
solveSudoku = async () => { const { sudoku } = this.state // 判斷填入的數(shù)字是否有效,參考上面的代碼,這里不再重復(fù) const isValid = (row, col, num) => { …… } // 脫離事件流,調(diào)用 setState const setSudoku = async (row, col, value) => { sudoku[row][col] = value return new Promise(resolve => { setTimeout(() => { this.setState({ sudoku }, () => resolve()) }) }) } // 遞歸+回溯的方式進(jìn)行解題 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 } // 進(jìn)行解題 solve(0, 0) }
最后效果如下:
總結(jié)
到此這篇關(guān)于利用JavaScript做數(shù)獨(dú)的文章就介紹到這了,更多相關(guān)JavaScript做數(shù)獨(dú)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
javascript eval()應(yīng)用實(shí)例 select
javascript eval應(yīng)用小例子。實(shí)例代碼就是控制checkbox的選擇與取消的函數(shù),非常不錯(cuò)。2009-07-07JavaScript.The.Good.Parts閱讀筆記(二)作用域&閉包&減緩全局空間污染
塊級(jí)作用域: 大多數(shù)使用c語言語法的語言都有塊級(jí)作用域,而JavaScript沒有塊級(jí)作用域。2010-11-11Javascript寫了一個(gè)清除“l(fā)ogo1_.exe”的殺毒工具(可掃描目錄)
Javascript寫了一個(gè)清除“l(fā)ogo1_.exe”的殺毒工具(可掃描目錄)...2007-02-02JavaScript trim 去除字符串空格的三種方法(附代碼詳解)
個(gè)人認(rèn)為最好的方法.采用的是正則表達(dá)式,這是最核心的原理.因?yàn)榭崭裼卸喾N形式。2010-05-05JavaScript結(jié)合Canvas繪畫畫運(yùn)動(dòng)小球
這篇文章主要介紹了JavaScript結(jié)合Canvas畫運(yùn)動(dòng)小球,canvas被稱為畫布,可以結(jié)合javascript實(shí)現(xiàn)繪制各種圖形,制作各種炫酷的動(dòng)畫效果,下面文章更多詳細(xì)內(nèi)容介紹需要的小伙伴可以參考一下2022-03-03uniapp實(shí)現(xiàn)人臉識(shí)別功能的具體實(shí)現(xiàn)代碼
最近在使用uniapp開發(fā)項(xiàng)目,有刷臉實(shí)名認(rèn)證的需求,下面這篇文章主要給大家介紹了關(guān)于uniapp實(shí)現(xiàn)人臉識(shí)別功能的具體實(shí)現(xiàn),文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-12-12JavaScript時(shí)間與時(shí)間戳的轉(zhuǎn)換操作實(shí)例分析
這篇文章主要介紹了JavaScript時(shí)間與時(shí)間戳的轉(zhuǎn)換操作,結(jié)合實(shí)例形式分析了javascript日期與時(shí)間戳轉(zhuǎn)換相關(guān)函數(shù)與操作技巧,需要的朋友可以參考下2018-12-12給頁面渲染時(shí)間加速 干掉Dom Level 0 Event
我們?nèi)サ羰录壎ǖ倪壿?發(fā)現(xiàn)只渲染dom元素,不綁定事件的時(shí)間,僅僅125ms,可見事件綁定的時(shí)間消耗還是很大的 ,尤其是第一種方式,也就是Dom Level 0 Event,最為耗時(shí)2012-12-12