JavaScript を使用した数独の完全な実装プロセス

JavaScript を使用した数独の完全な実装プロセス

序文

最近、妻が携帯電話で毎日数独をプレイしているのを見ました。突然、何年も前に LeetCode N をプレイしていたときに、同様のアルゴリズムの問​​題 (37. 数独を解く) があったことを思い出しました。このアルゴリズムを視覚化することは可能ですか?

とにかくやってみてください。1 時間の練習の後、最終的な効果は次のようになります。

数独の解き方

数独を解く前に、まず数独のルールを理解しましょう。

  1. 1~9 の数字は各行に 1 回だけ表示できます。
  2. 1 ~ 9 の数字は各列に 1 回だけ出現します。
  3. 1 ~ 9 の数字は、太い実線で区切られた 3x3 のグリッドごとに 1 回だけ表示されます。

次に、各ボックスに数字を入力し、その数字がルールに違反しているかどうかを判断する必要があります。

最初のボックスに記入してください

まず、最初のグリッドに 1 を記入します。すると、最初の列にはすでに 1 があることがわかります。このとき、前に記入した数字 1 を消してから、グリッドに 2 を記入する必要があります。行、列、および 9 つの正方形のグリッドで数字が重複していないことがわかります。するとグリッドが正常に埋められます。

2番目のボックスに記入してください

2 番目のグリッドを見てみましょう。前と同じように、まず 1 を入力してみます。行、列、グリッドに重複した数字がない場合は、このグリッドも正常に入力されています。

3番目のボックスに記入してください

3 番目のボックスを見てみましょう。最初の 2 つのボックスにはすでに 1 と 2 の数字が入力されているので、3 の数字を直接入力し始めることができます。 3 を記入した後、最初の行にすでに 3 があることがわかりました。次に、グリッドに 4 を記入したところ、行とグリッドの両方で数字 4 が繰り返されていることがわかりました。それでも失敗しました。次に、数字 5 を記入しようとしました。最終的に、重複した数字はなく、記入が成功したことが示されました。

記入を続けます...

9番目のボックスに記入してください

この考え方に従って、9 番目のマス目まで埋めていきます。この時点で、最後の数字 9 が 9 つのマス目のグリッド内で矛盾していることがわかります。しかし、9はすでに最後の数字なので、ここに他の数字を入力する方法はありません。前のグリッドに戻って、7番目のグリッドの数字を8から9に変更することしかできませんが、9マスのグリッドにはまだ矛盾があることがわかりました。

このとき、前のグリッド(6 番目のグリッド)の数字を置き換える必要があります。矛盾がなくなるまで、このプロセスでは、数字を逆順に入力するだけでなく、前の数字に問題がないか確認して、試行を続けます。

要約すれば

数独を解くには、試行錯誤を続ける必要があります。各グリッドに 1 ~ 9 の数字を入力してください。矛盾がある場合は、すべてのグリッドが埋まるまで数字を消してください。

コードを通じて実装

上記のソリューションをコードに反映するには、再帰 + バックトラックを通じて実装する必要があります。

コードを書く前に、数独の表現方法を見てみましょう。LeetCode の質問への参照は、次のとおりです: 37. 数独を解きます。

前の質問は 2 次元配列で表すことができます。最も外側の配列には 9 つの配列があり、数独の 9 行を表しています。各内側の配列の 9 つの文字は配列の列に対応し、空白部分は文字 (「.」) で表されます。

const 数独 = [
  ['.', '.', '.', '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'],
]

配列の表現方法がわかったので、コードを記述してみましょう。

const 数独 = [……]
// メソッドは、数独のグリッドを見つけるために、行と列の2つのパラメータを受け取ります。 functionsolve(row, col) {
  (列> = 9)の場合{ 
   // 9 列目を超えると、この行は終了し、新しい行を開始する必要があることを意味します col = 0
    行 += 1
    行数 >= 9 の場合
      // 新しい行を開始した後、9行目を超えると、数独全体が完成し、trueを返します
    }
  }
  数独[行][列] !== '.' の場合 {
    // グリッドが埋められている場合は、次のグリッドを埋めます。 returnsolve(row, col + 1)
  }
  // グリッドに1~9の数字を入力してみてください
  (num = 1; num <= 9; num++) の場合 {
    if (!isValid(行、列、数値)) {
      // 無効な番号の場合は、その番号をスキップして続行します
    }
    // 数字を入力する sudoku[row][col] = num.toString()
    // 次のグリッドに入力を続けます if (solve(row, col + 1)) {
      // 最後まですべてが正常であれば、このグリッドの数字は正常です。true を返します。
    }
    // 問題がある場合は、solve は false を返します
    // この場所を補充する必要があることを示します sudoku[row][col] = '.' // 数字を消去します }
  // 1~9 の数字がすべて入力されなかったため、前の数字に問題があることが示されています // FALSE を返し、戻って前の数字を再入力します false を返します
}

上記のコードでは再帰とバックトラック部分のみが実装されており、実装されていない isValid メソッドがあります。この方法は主に数独のルールに従って検証を行います。

const 数独 = [……]
関数 isValid(行、列、数値) {
  // 行が繰り返されているかどうかをチェックする for (let i = 0; i < 9; i++) {
    if (sudoku[行][i] === num) {
      偽を返す
    }
  }
  // 列に重複があるかどうかを確認します for (let i = 0; i < 9; i++) {
    if (sudoku[i][col] === num) {
      偽を返す
    }
  }
  // 9 マスのグリッドが繰り返されるかどうかを判定します const startRow = parseInt(row / 3) * 3
  定数 startCol = parseInt(col / 3) * 3
  (i = startRow; i < startRow + 3; i++) の場合 {
    (j = startCol; j < startCol + 3; j++) の場合 {
      数独[i][j] === numの場合
        偽を返す
      }
    }
  }
  真を返す
}

上記のコードを使用すると、数独を解くことができます。

const 数独 = [
  ['.', '.', '.', '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']
]
関数 isValid(行、列、数値) {……}
関数は(行、列)を解決します{……}
solve(0, 0) // 最初のグリッドから解く console.log(sudoku) // 結果を出力

テストプロセスの動的表示

上記の理論的知識があれば、問題解決のプロセスを反応に適用し、問題解決のプロセスを動的に表示することができます。これが記事の冒頭の GIF です。

ここではcreate-react-app scaffoldingを使用してプロジェクトを素早く開始します

npx 作成-React-アプリ 数独
CD 数独

App.jsx を開いてコードの記述を開始します。

'react' から React をインポートします。
'./App.css' をインポートします。

クラスAppはReact.Componentを拡張します。
  状態 = {
    // 状態 sudoku で数独の 2 次元配列を設定します: [
      ['.', '.', '.', '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: 数独を解くsolveSudoku = async () => {
    const { 数独 } = this.state
  }

  与える() {
    const { 数独 } = this.state
    戻る (
      <div className="コンテナ">
        <div className="ラッパー">
          2 次元配列を走査し、9 つの正方形のグリッドを生成します*/
          {sudoku.map((リスト、行) => (
            *div.row は数独の行に対応します*/
            <div className="row" キー={`row-${row}`}>
              {list.map((item, col) => (
              */* span は数独の各グリッドに対応します*/
                <span key={`box-${col}`}>{ 項目 !== '.' && 項目 }</span>
              ))}
            </div>
          ))}
          <button onClick={this.solveSudoku}>問題を解き始める</button>
        </div>
      </div>
    );
  }
}

9グリッドスタイル

各グリッドに点線の境界線を追加して、9 つのグリッドのように見えるようにします。

。行 {
  ディスプレイ: フレックス;
  方向: 行;
  /* 行内の要素を中央揃えにする */
  コンテンツの中央揃え: 中央;
  コンテンツの位置を中央揃えにします。
}
.行スパン{
  /*各グリッドの幅と高さは同じです*/
  幅: 30ピクセル;
  最小高さ: 30px;
  行の高さ: 30px;
  テキスト配置: 中央;
  /* 点線の境界線を設定します */
  境界線: 1px 破線 #999;
}

次のようなグラフが得られます。

次に、外側の境界線と各 9 マスのグリッドに実線の境界線を追加する必要があります。具体的なコードは次のとおりです。

/* 1行目の先頭に境界線を追加します*/
.row:n番目の子(1) span {
  上境界線: 3px 実線 #333;
}
/* 3、6、9行目の下部に境界線を追加します*/
.row:n番目の子(3n) span {
  下部境界線: 3px 実線 #333;
}
/* 最初の列の左側に境界線を追加します*/
.row span:最初の子 {
  左境界線: 3px 実線 #333;
}

/* 3、6、9 列目の右側に境界線を追加します*/
.row span:n番目の子(3n) {
  右境界線: 3px 実線 #333;
}

ここで、3 列目と 6 列目の右境界線と、4 列目と 7 列目の左境界線が少し重なっていることがわかります。3 行目と 6 行目の下境界線と、4 行目と 7 行目の上境界線にもこの問題があります。したがって、4 列目と 7 列目の左境界線と、3 行目と 6 行目の下境界線も非表示にする必要があります。

.row:n番目の子(3n + 1) span {
  上境界線: なし;
}
.row span:n番目の子(3n + 1) {
  左境界線: なし;
}

質問ロジック

スタイルが記述された後、質問に答えるロジックを継続的に改善できます。

クラスAppはReact.Componentを拡張します。
  状態 = {
    // 状態 sudoku で数独の 2 次元配列を構成します: [...]
  }

  数独を解く = 非同期 () => {
    const { 数独 } = this.state
    // 入力された数字が有効かどうかを確認します。上記のコードを参照し、ここでは繰り返さない const isValid = (row, col, num) => {
      …
    }
    // 再帰 + バックトラックを使用して問題を解決します constsolve = async (row, col) => {
      (列> = 9)の場合{ 
        列 = 0
        行 += 1
        行 >= 9 の場合、true を返す
      }
      数独[行][列] !== '.' の場合 {
        戻り値:solve(行, 列 + 1)
      }
      (num = 1; num <= 9; num++) の場合 {
        if (!isValid(行、列、数値)) {
          続く
        }
 
        数独[行][列] = num.toString()
        this.setState({ sudoku }) // グリッドに入力したら、状態に同期する必要があります

        if (solve(行, 列 + 1)) {
          真を返す
        }

        数独[行][列] = '.'
        this.setState({ sudoku }) // グリッドに入力したら、状態に同期する必要があります
      }
      偽を返す
    }
    // 問題を解くsolve(0, 0)
  }

  与える() {
    const { 数独 } = this.state
    戻る (……)
  }
}

前のロジックと比較すると、ここでは、数独の 2 次元配列に入力した後、 this.setState を呼び出して数独を状態に同期するだけです。

関数solve(行,列) {
   …
   数独[行][列] = num.toString()
+ this.setState({ 数独 })
  …
   数独[行][列] = '.'
+ this.setState({ sudoku }) // グリッドに入力したら、状態に同期する必要があります
}

solveSudoku を呼び出した後、動的な効果はないが、結果が 1 ステップでビューに同期されることがわかります。

これは、setState が疑似非同期呼び出しであるためです。イベント タスクでは、すべての setState 呼び出しが 1 つにマージされます。質問に回答する動的なプロセスを確認する必要がある場合は、各 setState 操作をイベント フローの外側、つまり setTimeout に配置する必要があります。 setState の非同期性に関するその他の質問については、以前の記事「React の setState はマクロ タスクですか、それともマイクロ タスクですか?」を参照してください。

数独を解く = 非同期 () => {
  const { 数独 } = this.state
  // 入力された数字が有効かどうかを確認します。上記のコードを参照し、ここでは繰り返さない const isValid = (row, col, num) => {
    …
  }
  // イベントフローから外れてsetStateを呼び出す
  const setSudoku = async (行、列、値) => {
    数独[行][列] = 値
    新しいPromiseを返します(resolve => {
      タイムアウトを設定する(() => {
        this.setState({
          数独
        }, () => 解決())
      })
    })
  }
  // 再帰 + バックトラックを使用して問題を解決します constsolve = async (row, col) => {
    …
    (num = 1; num <= 9; num++) の場合 {
      if (!isValid(行、列、数値)) {
        続く
      }

   setSudoku(行、列、num.toString()) を待機します。

      if (awaitsolve(row, col + 1)) {
        真を返す
      }

   setSudoku(行、列、'.') を待機します。
    }
    偽を返す
  }
  // 問題を解くsolve(0, 0)
}

最終的な効果は次のようになります。

要約する

これで、JavaScript を使用して数独を解く方法についての記事は終わりです。JavaScript 数独に関するより関連性の高いコンテンツについては、123WORDPRESS.COM の以前の記事を検索するか、以下の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM を応援していただければ幸いです。

以下もご興味があるかもしれません:
  • 数独アルゴリズムの Web ページ例の Javascript 実装
  • 数独解答のJavascript実装
  • javascript 数独 数独パズルゲーム生成コード
  • 有効な数独アルゴリズムの例の JS 実装
  • JavaScript トラバーサルを通じて数独問題を解くための主なアイデアの要約

<<:  Alibaba Cloud ECS サーバーの開始プロセス (初心者必読のチュートリアル)

>>:  MySQLにNavicatをインストールした後、2059が表示され、認証プラグインとローカルリンク仮想マシンdocker、リモートリンクサーバー

推薦する

文字列の GBK および GB2312 エンコードとデコードのフロントエンド実装 (概要)

序文プロジェクトを開発しているときに、かなり厄介な問題に遭遇しました。この製品では、判断のためにブラ...

Docker 自動ビルド 自動ビルド実装プロセス図

自動ビルドとは、Docker Hub を使用して、Dockerfile ファイルを含む GitHub...

ウェブページのエンコードにおける GB2312、GBK、UTF-8 の違い

まず、GB2312、GBK、UTF-8 はすべて文字エンコーディングであることを理解する必要がありま...

Linux で指定された期間に数分ごとにタスク スケジュール crontab を自動的に実行する方法

まずコードを見てみましょう #/bin/sh datename=$(日付 +%Y%m%d-%H%M%...

MySQL マスタースレーブ同期遅延の原因と解決策

歴史的な理由により、MySQL レプリケーションは、REDO ログではなく論理バイナリ ログに基づい...

Ubuntu 18.04 Linux システムに JDK と Mysql をインストールする方法

プラットフォームの展開1. JDKをインストールするステップ1. OracleJDKをダウンロードす...

Struts2 ジャンプ後に CSS と JS が無効になる問題の解決策のアイデアと実装手順

struts2 アクションの実行後にジャンプした jsp が表示されると、css が機能しません。問...

Dockerを使用してMySQL 8.0をデプロイする方法の例

1. 公式サイトを参照してdockerをインストールする2. MySQLイメージをプルします(デフォ...

Mysqlの日付と時刻関数を扱う記事

目次序文1. 現在の時刻を取得する1.1 現在の日付と時刻を返す1.2 現在の日付を取得する1.3 ...

MySQL の単一テーブル クエリ操作例の詳細な説明 [構文、制約、グループ化、集計、フィルタリング、並べ替えなど]

この記事では、MySQL の単一テーブル クエリ操作について説明します。ご参考までに、詳細は以下の通...

CSS3 ベジェ曲線の例: リンクホバーアニメーション効果の作成

CSS3 アニメーション トランジションを使用して、リンクの上にマウスを移動すると小さなポップアップ...

MySQL における 8 つの一般的な SQL 使用例

序文MySQL は、2016 年もデータベースの人気において力強い成長傾向を維持し続けました。 My...

Nest.js のハッシュと暗号化の例の詳細な説明

0x0 はじめにまず、ハッシュアルゴリズムとは何でしょうか?メッセージやセッション項目など、一部のデ...

Node.js組み込みモジュールの詳細な説明

目次概要1. パスモジュール2. モジュールまで3. fsモジュール4. イベントモジュール5. h...

Dockerはmacvlanをベースにホスト間コンテナ通信を実装する

2 台のテスト マシンを見つけます。 [root@docker1 centos_zabbix]# d...