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