9,642 文字
みなさん、こんにちは。今日はPythonの実装についてお話しさせていただきます。最新のQwQ-32Bをテストしてみましょう。
ここで、16×16の数独を特定のアルゴリズムでPythonを使って実装する実際の速度をご覧いただきます。わぁ、これはすごいですね。ゆっくり読まないといけないくらいです。アルゴリズムX…これは印象的ですね。アルゴリズムが解を見つけようとしているようです。
というのも、私はこのテストを行っていて、インターネット上にはPythonの実装があまり見当たらないことを知っています。C++の実装は見たことがありますが。ここに重要な制限について書かれていますね。コードの切り替えや再帰的な推論のループについてです。もちろん、これに注目します。
次の16行について、すべての行を出力しないのがいいですね。これは論証の良い洞察です。最初のコードセグメントを構築しようとしているのが分かります。完全な最終コードが得られることを願っています。つまみ食いする必要はないはずです。もっとコードが出てきました。これはコードの大まかなスケッチですね。詳細を埋める必要があります。QwQ、かわいいですね。
これで置換をマッピングできます。要約と最終解…アプローチと数独のカバー、そしてPythonコードですね。期待通り完全なPythonコードが得られました。これはオープンソースの無料モデルで、ローカルで実行できます。私はここでクラウドベースのバージョンを実行しています。というのも、完全な精度で実行したいからです。縮小版や量子化版は避けたいのです。完全なサイズが欲しいのです。ご覧の通り、これは簡単なタスクではありませんから。
説明のノートとカラムクラス、ダンシングリンククラス、解法関数…これは本当に印象的ですが、一歩ずつ見ていきましょう。私がこれについて気に入っているのは、ここで正確な理解を与えてくれることです。01は理由を説明してくれません。
では、見てみましょう。私はPythonで16×16のような高次の数独を扱える解法を実装するよう求められました。ダンシングリンクアルゴリズムを使用します。私は標準的な9×9のグリッドでの数独とその動作については知っていますが、高次のパズルは初めてです。どのように動作するのか、なぜ数独に適しているのか、正確には分かりません。
AIは言います。高次の数独パズルがどういうものか理解する必要があります。標準的な数独は9×9のグリッドで分割されていることは知っています。16×16の場合も同様ですが、より大きなサブグリッドになると想定します。そうですね、4×4のサブグリッドに分割され、それぞれに1から16の数字が含まれ、同じルールが適用されます。
16×16の数独では、16行、16列、16のサブグリッド、1から16の数字があります。素晴らしいですね。確認する必要があります。調べてみましょう。はい、高次の数独も同じルールに従いますが、グリッドが大きくなります。16×16の数独の場合、4×4のサブグリッドに分割され、1から16の数字を使用します。
このAIが正確に何をしているのかを説明してくれるのが素晴らしいですね。これは説明的なAIで、私が気に入っているのは、ブラックボックスではなく、目を開かせてくれて結果を与えてくれることです。何が起こっているのか分からないのではなく、このAIの内部で何が起こっているのかを見て学ぶこともできます。
AIは続けて言います。正確に思い出しました。アルゴリズムは、厳密なカバー問題を解くための再帰的な深さ優先アルゴリズムですね。特定の方法で可能な配置の部分集合を選択する必要がある厳密なカバー問題としてモデル化できます。効率的な削除と復元を可能にする二重連結循環リストを使用して実装されます。
数独にダンシングリンクを使用するのは偶然の一致ですね。数独の問題を厳密なカバー問題としてモデル化する必要があります。その通りです。これは制約と、これらの制約を満たす可能な配置を定義することを意味します。パズルの制約について考えてみましょう。
各セルには正確に1つの数字が含まれていなければなりません。各数字は各行に正確に1回出現しなければなりません。その通りです。各数字は各列に正確に1回出現しなければなりません。各数字は各サブグリッドに正確に1回出現しなければなりません。
標準的な9×9の場合、9行、9列、9つのサブグリッド、9つの数字があり、81のセルになります。16×16の場合は256のセルですね。その通りです。厳密なカバーの定式化では、セル内の数字の各可能な配置がカバーになります。各セルには16の可能な数字があるので、4K…そうですね、16×16で256×16です。
各可能な配置は、特定のセルに特定の数字を選ぶことに対応します。各可能な配置は複数の制約に影響を与えます。その通りです。セルに正確に1つの数字が含まれるという制約を満たします。はい、はい、はい、全て4つ正しいです。
各可能な配置について、どの制約を満たすかを指定する必要があります。制約の数は、セルに対して256、各行に対して256、各列に対して256、サブグリッドに対して256で、合計で4倍の1,000の制約があります。4Kの可能な配置があるので、厳密なカバー問題には1,024の制約と4,096の候補があります。その通りです。これは管理可能そうですね。
このコメントが気に入りました。これはクールですね。AIは続けます。ダンシングリンクの実装では、この制約と候補の行列を表現し、検索中に効率的に操作する必要があります。しかし、ダンシングリンクを最初から実装するのは難しい場合があります。特に、効率的な削除と復元を可能にする方法で二重連結循環リストを操作する必要があるためです。
クナスの論文では、アルゴリズムが詳細に説明されており、オンラインにもいくつかの実装がありますが、Pythonで実装する必要があります。その通りです。Pythonは最速の言語ではありませんが、私はPythonが欲しくて、C++は望んでいません。コードの構造について考える必要があります。
素晴らしいですね。AIは時間をかけて、学んでいるパターンから、そうですね…ダンシングリンクノードの構造を定義する必要があります。各ノードは水平方向と垂直方向の両方で二重連結リストの一部である必要があります。行、列、リンクの属性を持つノードのクラスを作成できます。はい、その通りです。
効率的に表現する方法を見つける必要があります。クナスの論文では、各列にヘッダーノードを使用し、ノードをリンクすると述べていたことを思い出します。はい、行列のほとんどがゼロなので、スパース行列として表現することが重要です。その通りです。各可能な配置を、それがカバーする列インデックスのリストとして表現できます。はい、ダンシングリストアルゴリズムは、列を選択し、その列をカバーする行を選び、残りの問題を解くことで動作できます。
問題自体に解決策を見出すのですね。Pythonでは非効率的ですが、Pythonの解決策を見たいと思います。既存のPythonライブラリを探すことができます…いいえ、コードを見たいのです。簡単な検索で、いくつかの実装が利用可能だということが分かりますが、自分で実装する必要があります。その通りです。
このモデルが気に入っています。なぜなら、何をしているのか理解できるからです。これは一種の信頼ベクトルが確立されているのです。自分の実装を進める必要があります。その通りです、QwQ。ステップを概説してみましょう。
制約を定義します。セルの制約、行の制約、列の制約、サブグリッドの制約です。はい、可能な配置を定義します。各可能な配置は、セルに数字を選ぶことに対応します。各配置は4つの制約（セル、行、列、サブグリッド）を満たします。行が可能な配置で、列が制約である行列を表現します。各行には4つの目が対応し、それは4つの制約に対応します。
ダンシングリンク構造を実装します。ヘッダーノードを作成し、各可能な配置に対してヘッダーノードを水平方向にリンクします。各カバー制約に対してノードを作成し、垂直方向と水平方向にリンクします。アルゴリズムXの手順を実装します。はい、再帰的に…再帰が成功したら成功を返し、どの行も成功に導かなければ失敗します。
これは straightforward に見えますが、実装の詳細は難しい場合があります。その通りです。特にPythonでは、リンクを効率的に管理することが重要です。行列の表現方法について考える必要があります。一つの方法は、各列がノードのリンクリストである列のリストを持つことです。はい、それが出てきました。
各ノードには、行インデックス、列インデックス、同じ行の左ノードへの左リンク、同じ行の右ノードへの右リンク、同じ列の上のノードへの上リンク、下のノードへの下リンクが含まれます。その通りです。さらに、各列にはヘッダーノードがあり、列の中心として機能します。ヘッダーノードには、サイズ（列内のノードの数）と名前が含まれます。
そしてQwQは言います。この方法で列と行を効率的に削除し復元できますが、Pythonでこれらのリンクすべてを管理するのはエラーが発生しやすいかもしれません。列とノードをオブジェクトとして表現し、それらをリンクすることもできます。あるいは、辞書を使用してノードとその隣接ノードをマッピングすることもできますが、それは遅すぎるかもしれません。待てよ、各ノードを左、右、上、下、行、列の属性を持つオブジェクトとして表現できるかもしれません。はい、そしてヘッダーノードは列を表す特別なノードになります。
したがって、システムは今、可能なすべての配置を作成し、適切にリンクすることで行列を初期化する必要があると私に告げています。可能な配置を制約にマッピングする方法について考えてみましょう。QwQが気に入っているのは、AIが何をしようとしているのかを理解する道を開いてくれることです。プロプライエタリなブラックボックスのようなOpenAIがあれば、何が起こっているのか分かりませんが、ここでは何かを修正する必要がある場合、正確にその場所を修正できます。なぜなら、議論の背後にある論理を理解できるからです。
QwQは続けます。まず、各制約に一意の識別子を割り当てる必要があります。セルの制約、行の制約、列の制約、サブグリッドの制約です。これらの制約を一意にインデックス付けする方法を見つける必要があります。おそらく各制約に一意の整数を割り当てることができます。例えば、セルの制約には0から255までのID、行の制約には256から511までのID、列の制約には512から767までのID、サブグリッドの制約には768から1,023までのIDを割り当てます。
各可能な配置は4つの制約をカバーするので、これらの制約それぞれの正確なIDを計算する必要があります。はい、はい、はい、はい、まず正しいです。セルがどのサブグリッドに属するかを決定する必要があります。16×16の数独では4つのサブグリッドがあるので、ボックスの制約…はい、行の制約…はい、それは今1Kの制約になります。
各可能な配置について、それがカバーする4つの制約に対応するノードをリンクする必要があります。同じ演習をもう一度行います。これらの制約のノードを作成し、それらを互いにリンクする必要があります。各可能な配置について、ダンシングリンク構造にそのようなノードを作成する必要があります。各列のヘッダーを持ち、各列のノードを垂直方向に、各行のノードを水平方向にリンクする必要があります。各可能な配置について、4つのカバーに対応する行のノードを作成し、それらを水平方向にリンクし、また列を表すために垂直方向にリンクする必要がありますね。
ご覧の通り、QwQでの議論のループを見失っていなければ、とても簡単です。列をカバーするとき、その列と、それをカバーするすべての行を削除できます。これは特定の配置を選択し、それと競合する他のすべての配置を削除することに対応します。Pythonでこれを実装するには、リンクを慎重に管理する必要があります。ノードのクラスを定義する必要があります。
そして、追加のサイズ属性を持つノードオブジェクトでもあるヘッダーを各列に作成する必要があります。コードを見せてくれますね。そして、すべてのヘッダーノードを水平方向にリンクする必要があります。おお、なるほど。
コメントが続きます。これは管理可能に見えますが、リンク管理で何らかの間違いをすると不正確な動作につながる可能性があるため、正しく実装することが重要です。敏感な部分も理解しているのですね。これは単なる学習された行動なのでしょうか、それとも私と遊んでいるだけなのでしょうか。分かりませんが、自身を開示し、議論を示してくれる方法が気に入っています。
Wikipediaでアルゴリズムxのpython実装を見つけましたが、ダンシングリンクのアプローチとは少し異なります。ダンシングリンクはxを実装するために常に不可欠です。Pythonで効率的な方法で数独問題を表現する方法を見つけることができます。数独のグリッドを表現する方法について考えてみましょう。
数独パズルを入力する方法、どのセルが事前に埋められていて、どのセルが空いているかを指定する方法が必要です。簡単ですね。16×16の数独では、1から16の数字を使用するのが便利で、10から16には文字を使用する可能性があります。それらを整数として扱います。はい、もちろんです。
次に、このグリッドを処理し、それに応じて厳密なカバー問題を設定する必要があります。はい、これにより検索空間が大幅に縮小されます。カバーとアンカバーの操作を実装する方法について考えてみましょう。はい、列をアンカバーするには、列がカバーされたときに削除されたすべてのものを復元する必要があります。
私はこれを今すぐステップバイステップで読む必要はないと思いますが、これは正確に興味深く、正しい方向に進んでいるように見えます。質問は、コードの実装が…最小サイズの列を選択するのは正解でしょうか。
おそらく、ダンシングリンクアルゴリズムのコードについてのより詳細な説明を探す必要があります。まだ確信が持てません。つまり、本当にここで研究をしているのでしょうか、本当にインターネットに接続しているのでしょうか、これは可能なのでしょうか。さらなる研究について、これは単に学習したパターンなのか、本当に研究をしているのか、まだ分かりません。
ダンシングリンクでは行列が二重連結リストとして表現されることが分かりました。これは知っています。カバーについて、はい…ステップを要約する必要があります。制約を定義し、可能な配置を定義し、厳密なカバー行列を設定し、アルゴリズムXを実装し、解をマッピングし、バックトラッキングを行います。
ステップバイステップで処理し、正しく実装されていることを示す必要があります。最終解…これも表現の中で素晴らしいですね。ハイライトされています。はい、解はダンシングリンクアルゴリズムを使用した数独ソルバーのPython実装です。そして、すべてのパラメータと解のコードを与えてくれます。
コードを見たくはありません。コードが動作するかどうかだけ見たいと思います。ここには4×4のグリッドの例があります。デモンストレーション用ですね。では、このコードをIDEに入力して、動作するかどうか見てみましょう。他には何も知りません。ただ、そのままで動作するかどうかを見たいだけです。
誰もが利用できる単純なPythonノートブックで、Pythonコードをコピーしてここに挿入し、実行してみます。何が得られるか見てみましょう。すぐにエラーが出ました。46行目にエラーがありますね。次のステップ、エラーを説明してください。クリックすると、私の無料のColabノートブックでエラーの説明を求められます。属性エラー：非タイプオブジェクトに「down」属性がありません。
Geminiが介入して、仮説を説明してくれます。エラーメッセージはダンシングリンククラスのaddOrOrr関数で発生します。これは、Noneであるオブジェクトのdown属性にアクセスしようとしているということです。これは、列の問題がある場合に発生する可能性があります。はい、はい、最初は…はい、そして…はい、はい。
そして、コードへの提案された変更があります。ああ、なるほど。はい、良いですね。そうですね、説明の変更…素晴らしいですね。これは無料です。誰でも完全に無料で利用できます。システムで作業し、何が起こっているのか、この問題の解決策は何かを理解することができます。
私が示したかったのは、このためのコードを生成することが可能かどうかということですが、残念ながら答えは「いいえ」です。ここで修正を適用する必要がありますが、見てください。GPT-4にこのコードの問題を検出できるか尋ねてみましょう。このシステムとGPT-4を直接比較してみましょう。
では、私のGPT-4プレビューに来ました。コードを入力しただけで、他には何もしていません。ただコードが有効かどうか検証してくださいと言いました。47秒後に、GPT-4が戻ってきました。あなたのコードを検証し、対応する問題点を指摘させていただきます。はい、あなたのコードのレビューです。これはQwQからのコードですね。
DLXアルゴリズムを正しく実装し、高次の数独パズルを解くことを妨げるいくつかの問題に気づきました。以下で問題と修正方法のガイダンスを説明します。これは素晴らしいですね。問題が特定されました。では、GPT-4がQwQに反論します。
solveメソッドの実装が不完全で不正確です。すべての可能な組み合わせを探索するために再帰的であるべきです。あなたのコードのsolveは再帰呼び出しを行っていないため、行き詰まりに達したときに代替オプションを試すためにバックトラックすることができません。解決策は、アルゴリズムがバックトラックし、探索できるようにsolveメソッドに再帰を実装することです。
カバーとアンカバーの操作の取り扱いが不正確です。面白いですね。カバーとアンカバーメソッドがノード間のリンクを正しく更新していない可能性があり、制約の不正確な削除と復元につながります。解決策は、ノードをカバーとアンカバーするときにこれらのメソッドが適切にすべてのポインタを調整することを確認することです。
ご覧のように、GPT-4はコードを見ただけでこれを検出しました。素晴らしいですね。4×4のグリッドに対して簡略化されています。例が4×4用に与えられましたが、理解できます。はい、コードは16×16のグリッドを処理するために調整が必要です。これは今、興味深いですね。調整が必要です。私はこれがただの4×4のデモだと思っていました。グリッドサイズを更新してコードを修正する必要があります。ああ、キーがありませんね。はい、はい、これは問題ありません。
グリッドへの解のマッピングが不正確です。DLXアルゴリズムから解を収集し解釈する方法が、正確に再構築されない可能性があります。選択されたノードを追跡し、それらを正確にグリッドにマッピングするために、解スタックを維持します。興味深い、興味深いですね。
正しい実装…はい。これらの問題に対処するために、再帰的なsolveメソッドを正しく実装し、カバーとアンカバーの操作を適切に処理し、16×16のグリッドを解くようにコードを調整し、解をグリッドに戻すように正しくマッピングする修正版のコードを提供します。16×16の実行には大きな計算リソースが必要になる可能性があります。
私には無料のColabノートブックしかありません。それが得られるすべてです。そして修正されたコードが得られます。本当に素晴らしいですね。
現在の状態から、QwQのコーディング問題の説明は例外的に優れていると言えます。信じられないほど正確で、何が起こっているのか、システムが解決策を見つけるために議論を巡らせているループが見えます。しかし、残念ながら、代表的なサンプルではない単一の例から、そのままで動作するコードを生成することに失敗したと言わざるを得ません。
もちろん、カーソルなどを使ってコードを修正したり、Geminiでコードを修正したり、GPT-4プレビューに行ってコードを修正したりすることはできます。しかし、完璧ではありません。もちろん、これはQwQグループによる実験的なプロトタイプに過ぎませんが、説明部分だけでも、コードで何が起こっているのかを理解するために、非常に印象的です。
おそらく、次のイテレーションでは実際に改善されたコード実装を期待できるかもしれません。しかし、ここでGPT-4プレビューがあり、私のアカウントで見られるように、修正されたコードをここで提供してくれています。これを実行して本当に動作するか確認することもできますが、私はただQwQの力を探求したかっただけです。そして、本当に印象的だと言わなければなりません。コーディングの信頼性についてはQwQが改善できるかもしれませんが。
素晴らしいですね。このコードを見てみましょう。しかし、ここでこのビデオを終わりにしましょう。最初のコードの印象を伝えたかっただけです。使用する場合、コードに対して調整が必要かもしれませんが、何が起こっているのか、コードをどのように構築しているのか、コードの背後にある論理についての説明部分は、本当に素晴らしい実装だと言わなければなりません。
このビデオが興味深く、新しい視点があったことを願っています。次のビデオでお会いできれば素晴らしいですね。修正の説明もありますね。これは素晴らしいではありませんか。再帰的になり、Xを正しく実装し、解リストを含んでダブルリンクリストのポインタを正しく調整するように、カバーとアンカバーの操作が更新されています。16への調整も…正しいマッピングも…素晴らしいです。
解を見つけた後、この情報を使って数独グリッドを再構築します。部分的に埋められたコードは…使用説明も豊富です。スクリプトをPython 3で実行します。Pを調整できます。解が見つかった場合、グリッドはフォーマットされた形式で出力されます。解が存在しない場合は適切なメッセージが表示されます。
再帰制限は100,000に増加され、大きな数独パズルを解くときのエラーを防ぎます。DLXを使用した数独の解決には時間がかかる場合があります。アルゴリズムが解を探している間、お待ちください。
結論として、あなたの最初のコードは正しい考えを持っていましたが、DLXアルゴリズムを正しく実装するための重要なコンポーネントが不足していました。ああ、QwQ、これは痛いですね。重要なコンポーネントが不足していました。上記の修正されたコードはこの問題に対処し、解を見つけることができるはずです。コードについて質問がありましたら、お気軽にお尋ねください。
GPT-4、よくやりました。素晴らしい出来です。次のビデオでお会いしましょう。
コメント