用 JavaScript 做數(shù)獨(dú)
最近看到老婆天天在手機(jī)上玩數(shù)獨(dú)，突然想起 N 年前刷 LeetCode 的時(shí)候，有個(gè)類似的算法題（37.解數(shù)獨(dú)），是不是可以把這個(gè)算法進(jìn)行可視化。
說(shuō)干就干，經(jīng)過(guò)一個(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)一次。
接下來(lái)，我們要做的就是在每個(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)均無(wú)重復(fù)。那么這個(gè)格子就填成功了。
填第二個(gè)格子
下面看第二個(gè)格子，和前面一樣，先試試填 1，發(fā)現(xiàn)在行、列、九宮格內(nèi)的數(shù)字均無(wú)重復(fù)，那這個(gè)格子也填成功了。
填第三個(gè)格子
下面看看第三個(gè)格子，由于前面兩個(gè)格子，我們已經(jīng)填過(guò)數(shù)字 1、2，所以，我們直接從數(shù)字 3 開(kāi)始填。填 3 后，發(fā)現(xiàn)在第一行里面已經(jīng)存在一個(gè) 3，然后在格子里填上 4，發(fā)現(xiàn)數(shù)字 4 在行和九宮格內(nèi)均出現(xiàn)重復(fù)，依舊不成功，然后嘗試填上數(shù)字 5，終于沒(méi)有了重復(fù)數(shù)字，表示填充成功。
……
一直填……
填第九個(gè)格子
照這個(gè)思路，一直填到第九個(gè)格子，這個(gè)時(shí)候，會(huì)發(fā)現(xiàn)，最后一個(gè)數(shù)字 9 在九宮格內(nèi)沖突了。而 9 已經(jīng)是最后一個(gè)數(shù)字了，這里沒(méi)辦法填其他數(shù)字了，只能返回上一個(gè)格子，把第七個(gè)格子的數(shù)字從 8 換到 9，發(fā)現(xiàn)在九宮格內(nèi)依然沖突。
此時(shí)需要替換上上個(gè)格子的數(shù)字（第六個(gè)格子）。直到?jīng)]有沖突為止，所以在這個(gè)過(guò)程中，不僅要往后填數(shù)字，還要回過(guò)頭看看前面的數(shù)字有沒(méi)有問(wèn)題，不停地嘗試。
綜上所述
解數(shù)獨(dú)就是一個(gè)不斷嘗試的過(guò)程，每個(gè)格子把數(shù)字 1-9 都嘗試一遍，如果出現(xiàn)沖突就擦掉這個(gè)數(shù)字，直到所有的格子都填完。
通過(guò)代碼來(lái)實(shí)現(xiàn)
把上面的解法反映到代碼上，就需要通過(guò) 遞歸 + 回溯 的思路來(lái)實(shí)現(xiàn)。
在寫(xiě)代碼之前，先看看怎么把數(shù)獨(dú)表示出來(lái)，這里參考 leetcode 上的題目：37. 解數(shù)獨(dú)。
前面的這個(gè)題目，可以使用一個(gè)二維數(shù)組來(lái)表示。最外層數(shù)組內(nèi)一共有 9 個(gè)數(shù)組，表示數(shù)獨(dú)的 9 行，內(nèi)部的每個(gè)數(shù)組內(nèi) 9 字符分別對(duì)應(yīng)數(shù)組的列，未填充的空格通過(guò)字符（'.' ）來(lái)表示。
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è)賮?lái)寫(xiě)代碼。
const?sudoku?=?[……]
//?方法接受行、列兩個(gè)參數(shù)，用于定位數(shù)獨(dú)的格子
function?solve(row,?col)?{
??if?(col?>=?9)?{?
???//?超過(guò)第九列，表示這一行已經(jīng)結(jié)束了，需要另起一行
????col?=?0
????row?+=?1
????if?(row?>=?9)?{
??????//?另起一行后，超過(guò)第九行，則整個(gè)數(shù)獨(dú)已經(jīng)做完
??????return?true
????}
??}
??if?(sudoku[row][col]?!==?'.')?{
????//?如果該格子已經(jīng)填過(guò)了，填后面的格子
????return?solve(row,?col?+?1)
??}
??//?嘗試在該格子中填入數(shù)字?1-9
??for?(let?num?=?1;?num?<=?9;?num++)?{
????if?(!isValid(row,?col,?num))?{
??????//?如果是無(wú)效數(shù)字，跳過(guò)該數(shù)字
??????continue
????}
????//?填入數(shù)字
????sudoku[row][col]?=?num.toString()
????//?繼續(xù)填后面的格子
????if?(solve(row,?col?+?1))?{
??????//?如果一直到最后都沒(méi)問(wèn)題，則這個(gè)格子的數(shù)字沒(méi)問(wèn)題
??????return?true
????}
????//?如果出現(xiàn)了問(wèn)題，solve?返回了?false
????//?說(shuō)明這個(gè)地方要重填
????sudoku[row][col]?=?'.'?//?擦除數(shù)字
??}
??//?數(shù)字?1-9?都填失敗了，說(shuō)明前面的數(shù)字有問(wèn)題
??//?返回?FALSE，進(jìn)行回溯，前面數(shù)字要進(jìn)行重填
??return?false
}
上面的代碼只是實(shí)現(xiàn)了遞歸、回溯的部分，還有一個(gè) isValid 方法沒(méi)有實(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?3;?i++)?{
????for?(let?j?=?startCol;?j?3;?j++)?{
??????if?(sudoku[i][j]?===?num)?{
????????return?false
??????}
????}
??}
??return?true
}
通過(guò)上面的代碼，我們就能解出一個(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è)格子開(kāi)始解
console.log(sudoku)?//?輸出結(jié)果
輸出結(jié)果動(dòng)態(tài)展示做題過(guò)程
有了上面的理論知識(shí)，我們就可以把這個(gè)做題的過(guò)程套到 react 中，動(dòng)態(tài)的展示做題的過(guò)程，也就是文章最開(kāi)始的 Gif 中的那個(gè)樣子。
這里直接使用 create-react-app 腳手架快速啟動(dòng)一個(gè)項(xiàng)目
npx?create-react-app?sudoku
cd?sudoku
打開(kāi) App.jsx ，開(kāi)始寫(xiě)代碼。
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}>開(kāi)始做題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è)這樣的圖形：
接下來(lái)，需要給外邊框和每個(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è)問(wèn)題，所以，我們還需要將第四、七列的左邊邊框和第三、六行的底部邊框進(jìn)行隱藏。
.row:nth-child(3n?+?1)?span?{
??border-top:?none;
}
.row?span:nth-child(3n?+?1)?{
??border-left:?none;
}
做題邏輯
樣式寫(xiě)好后，就可以繼續(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)并沒(méi)有出現(xiàn)動(dòng)態(tài)的效果，而是直接一步到位的將結(jié)果同步到了視圖中。
這是因?yàn)?setState 是一個(gè)偽異步調(diào)用，在一個(gè)事件任務(wù)中，所以的 setState 都會(huì)被合并成一次，需要看到動(dòng)態(tài)的做題過(guò)程，我們需要將每一次 setState 操作放到該事件流之外，也就是放到 setTimeout 中。更多關(guān)于 setState 異步的問(wèn)題，可以參考我之前的文章：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)
}
最后效果如下：
- END -