利用JavaScript做數(shù)獨的完整實現(xiàn)過程

更新時間：2021年09月08日 11:35:28 作者：寫文章的自然醒

數(shù)獨游戲是在一個9*9的方格中進行填數(shù)字的游戲,需要滿足的規(guī)則是每行每列和每個子九宮格都是1~9的不重復數(shù)字,下面這篇文章主要給大家介紹了關于如何利用JavaScript做數(shù)獨的相關資料,需要的朋友可以參考下

前言

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

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

怎么解數(shù)獨

解數(shù)獨之前，我們先了解一下數(shù)獨的規(guī)則：

數(shù)字 1-9 在每一行只能出現(xiàn)一次。
數(shù)字 1-9 在每一列只能出現(xiàn)一次。
數(shù)字 1-9 在每一個以粗實線分隔的九宮格（ 3x3 ）內(nèi)只能出現(xiàn)一次。

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

填第一個格子

首先，在第一個格子填 1，發(fā)現(xiàn)在第一列里面已經(jīng)存在一個 1，此時就需要擦掉前面填的數(shù)字 1，然后在格子里填上 2，發(fā)現(xiàn)數(shù)字在行、列、九宮格內(nèi)均無重復。那么這個格子就填成功了。

填第二個格子

下面看第二個格子，和前面一樣，先試試填 1，發(fā)現(xiàn)在行、列、九宮格內(nèi)的數(shù)字均無重復，那這個格子也填成功了。

填第三個格子

下面看看第三個格子，由于前面兩個格子，我們已經(jīng)填過數(shù)字 1、2，所以，我們直接從數(shù)字 3 開始填。填 3 后，發(fā)現(xiàn)在第一行里面已經(jīng)存在一個 3，然后在格子里填上 4，發(fā)現(xiàn)數(shù)字 4 在行和九宮格內(nèi)均出現(xiàn)重復，依舊不成功，然后嘗試填上數(shù)字 5，終于沒有了重復數(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ù)獨就是一個不斷嘗試的過程，每個格子把數(shù)字 1-9 都嘗試一遍，如果出現(xiàn)沖突就擦掉這個數(shù)字，直到所有的格子都填完。

通過代碼來實現(xiàn)

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

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

前面的這個題目，可以使用一個二維數(shù)組來表示。最外層數(shù)組內(nèi)一共有 9 個數(shù)組，表示數(shù)獨的 9 行，內(nèi)部的每個數(shù)組內(nèi) 9 字符分別對應數(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ù)獨的格子
function solve(row, col) {
  if (col >= 9) { 
   // 超過第九列，表示這一行已經(jīng)結束了，需要另起一行
    col = 0
    row += 1
    if (row >= 9) {
      // 另起一行后，超過第九行，則整個數(shù)獨已經(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，進行回溯，前面數(shù)字要進行重填
  return false
}

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

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
}

通過上面的代碼，我們就能解出一個數(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']
]
function isValid(row, col, num) {……}
function solve(row, col) {……}
solve(0, 0) // 從第一個格子開始解
console.log(sudoku) // 輸出結果

動態(tài)展示做題過程

有了上面的理論知識，我們就可以把這個做題的過程套到 react 中，動態(tài)的展示做題的過程，也就是文章最開始的 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 中配置一個數(shù)獨二維數(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ù)獨
  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 對應數(shù)獨的行 */}
            <div className="row" key={`row-${row}`}>
              {list.map((item, col) => (
              {/* span 對應數(shù)獨的每個格子 */}
                <span key={`box-${col}`}>{ item !== '.' && item }</span>
              ))}
            </div>
          ))}
          <button onClick={this.solveSudoku}>開始做題</button>
        </div>
      </div>
    );
  }
}

九宮格樣式

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

.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;
  /* 設置虛線邊框 */
  border: 1px dashed #999;
}

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

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

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

/* 第 3、6、9 列右邊加上實現(xiàn)邊框 */
.row span:nth-child(3n) {
  border-right: 3px solid #333;
}

這里會發(fā)現(xià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ù)獨二維數(shù)組
    sudoku: [……]
  }

  solveSudoku = async () => {
    const { sudoku } = this.state
    // 判斷填入的數(shù)字是否有效，參考上面的代碼，這里不再重復
    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 (……)
  }
}

對比之前的邏輯，這里只是在對數(shù)獨的二維數(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)的效果，而是直接一步到位的將結果同步到了視圖中。

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

solveSudoku = async () => {
  const { sudoku } = this.state
  // 判斷填入的數(shù)字是否有效，參考上面的代碼，這里不再重復
  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())
      })
    })
  }
  // 遞歸+回溯的方式進行解題
  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)
}

最后效果如下：

總結

到此這篇關于利用JavaScript做數(shù)獨的文章就介紹到這了,更多相關JavaScript做數(shù)獨內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

JavaScript中捕獲與冒泡詳解及實例
這篇文章主要介紹了JavaScript中捕獲與阻止捕獲、冒泡與阻止冒泡詳解及實例的相關資料,需要的朋友可以參考下
2017-02-02
理解javascript中的with關鍵字
這篇文章主要幫助大家理解javascript中的with關鍵字，學習with關鍵字的作用，感興趣的小伙伴們可以參考一下
2016-02-02
js實現(xiàn)簡單的選項卡效果
本文主要介紹了js實現(xiàn)簡單的選項卡效果的示例代碼，具有很好的參考價值，下面跟著小編一起來看下吧
2017-02-02
javascript實現(xiàn)對話框功能警告（alert 消息對話框）確認（confirm 消息對話框）
這篇文章主要介紹了javascript：警告（alert 消息對話框），確認（confirm 消息對話框）的實現(xiàn)代碼，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下
2019-05-05
使用JavaScript輕松實現(xiàn)拖拽功能
這篇文章主要介紹了使用JavaScript輕松實現(xiàn)拖拽功能,讓你的網(wǎng)頁動起來,文中通過代碼示例講解的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下
2024-06-06
一個支持ff的modaldialog的js代碼
一個支持ff的modaldialog的js代碼...
2007-03-03
微信小程序時間戳轉日期的詳解
這篇文章主要介紹了微信小程序時間戳轉日期，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2019-04-04
微信小程序云開發(fā)實現(xiàn)云數(shù)據(jù)庫讀寫權限
這篇文章主要為大家詳細介紹了微信小程序云開發(fā)實現(xiàn)云數(shù)據(jù)庫讀寫權限，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-05-05
JavaScript中清空數(shù)組的三種方法分享
JavaScript中清空數(shù)組的三種方法分享，需要的朋友可以參考下。
2011-04-04
前端使用cookie的兩種方式詳細講解
這篇文章主要介紹了前端使用cookie的兩種方式,分別是通過瀏覽器自動管理和通過JavaScript顯式操作,文章詳細講解了如何設置、讀取和刪除Cookie,并強調(diào)了安全性問題,需要的朋友可以參考下
2025-02-02