序文最近、妻が携帯電話で毎日数独をプレイしているのを見ました。突然、何年も前に 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、リモートリンクサーバー
MongoDB を起動すると、プロンプトは次のようになります。共有ライブラリのロード中にエラーが発...
目次抽象化と再利用シリアルセグメントシリアル、セグメントパラレル要約するはじめに: JS は当然並列...
今日、redis をインストールしたところ、今までになかったいくつかのエラーが発生しました。ここで記...
undefined JavaScript では、値が undefined かどうかを判断したい場合は...
目次カスタム Vite プラグインvite-plugin-markdownの使用Front Matt...
この記事では、ドロップダウンテーブルの複数選択と検索を実現するためのvue+elementuiの具体...
1. Dockerネットワークモードdocker run が Docker コンテナを作成するときに...
この記事では、写真の自動再生効果を実現するためのJSの具体的なコードを参考までに紹介します。具体的な...
機能: データ表示、テーブルアプリケーションシナリオ。 <table> テーブル<...
目次1. 使用2. メッセージポップアップウィンドウが繰り返し表示される問題を解決する1. 使用Vu...
Safari (Technology Preview 106) および Firefox (バージョン...
プロジェクトで使用されている特殊文字とアイコンHTMLコードXML/HTML コードコンテンツをクリ...
背景開発やデバッグには Chrome Dev Tools がよく使用されますが、ページのパフォーマン...
デフォルトでは、Docker はネットワーク化されていない UNIX ソケット上で実行されます。オプ...
1. .shファイルを実行する./sh ファイルを使用して直接実行することもできますが、現在のターミ...