序文最近、妻が携帯電話で毎日数独をプレイしているのを見ました。突然、何年も前に LeetCode N をプレイしていたときに、同様のアルゴリズムの問題 (37. 数独を解く) があったことを思い出しました。このアルゴリズムを視覚化することは可能ですか? とにかくやってみてください。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 を応援していただければ幸いです。 以下もご興味があるかもしれません:
|
<<: Alibaba Cloud ECS サーバーの開始プロセス (初心者必読のチュートリアル)
>>: MySQLにNavicatをインストールした後、2059が表示され、認証プラグインとローカルリンク仮想マシンdocker、リモートリンクサーバー
序文プロジェクトを開発しているときに、かなり厄介な問題に遭遇しました。この製品では、判断のためにブラ...
自動ビルドとは、Docker Hub を使用して、Dockerfile ファイルを含む GitHub...
まず、GB2312、GBK、UTF-8 はすべて文字エンコーディングであることを理解する必要がありま...
まずコードを見てみましょう #/bin/sh datename=$(日付 +%Y%m%d-%H%M%...
歴史的な理由により、MySQL レプリケーションは、REDO ログではなく論理バイナリ ログに基づい...
プラットフォームの展開1. JDKをインストールするステップ1. OracleJDKをダウンロードす...
struts2 アクションの実行後にジャンプした jsp が表示されると、css が機能しません。問...
1. 公式サイトを参照してdockerをインストールする2. MySQLイメージをプルします(デフォ...
目次序文1. 現在の時刻を取得する1.1 現在の日付と時刻を返す1.2 現在の日付を取得する1.3 ...
この記事では、MySQL の単一テーブル クエリ操作について説明します。ご参考までに、詳細は以下の通...
CSS3 アニメーション トランジションを使用して、リンクの上にマウスを移動すると小さなポップアップ...
序文MySQL は、2016 年もデータベースの人気において力強い成長傾向を維持し続けました。 My...
0x0 はじめにまず、ハッシュアルゴリズムとは何でしょうか?メッセージやセッション項目など、一部のデ...
目次概要1. パスモジュール2. モジュールまで3. fsモジュール4. イベントモジュール5. h...
2 台のテスト マシンを見つけます。 [root@docker1 centos_zabbix]# d...