問題タブ [backtracking]

Haskellのn-queens問題のさまざまな解決策をウェブで検索しましたが、O（1）時間で安全でない位置をチェックできるものは見つかりませんでした。たとえば、/対角線の配列と\対角線。

私が見つけたほとんどの解決策は、それぞれの新しい女王を以前のすべての女王と照合しました。このようなもの：http： //www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

Haskellでそのような「O（1）アプローチ」を実装するための最良の方法は何でしょうか？私は「超最適化」されたものを探していません。「この対角線はすでに使用されていますか？」機能的な方法で配列。

アップデート：

皆さん、すべての答えをありがとう！私が最初に質問した理由は、より難しいバックトラックの問題を解決したかったからです。私はそれを命令型言語で解決する方法を知っていましたが、その仕事をするための純粋に機能的なデータ構造を簡単に考えることはできませんでした。クイーンズの問題は、全体的なデータ構造の問題の良いモデルになると思いましたが（バックトラッキングの問題です:)）、それは私の本当の問題ではありません。

私は実際に、O（1）ランダムアクセスを許可し、「初期」状態（n-queensの場合はフリーライン/対角）または「最終」状態（占有）のいずれかの値を保持するデータ構造を見つけたいと思っています。線/対角）、遷移（自由から占有）はO（1）です。これは命令型言語の可変配列を使用して実装できますが、値の更新の制限により、純粋に機能的な優れたデータ構造しか可能にならないように感じます（たとえば、本当に可変配列が必要なQuicksortとは対照的です）。

sthのソリューションは、Haskellで不変の配列を使用するのと同じくらい優れていると思います。また、「main」関数は、私が望んでいたもののように見えます。

ただし、Haskell配列ではO（n）が更新されるため、主な問題はより良いデータ構造を見つけることであるようです。他の素晴らしい提案は、神話上のO（1）の聖杯には及ばない：

• DiffArrayは接近しますが、バックトラックで混乱します。彼らは実際に超遅くなります:(。
• STUArrayは、かなり機能的なバックトラッキングアプローチと競合するため、破棄されます。
• マップとセットの更新はO（log n）のみです。

全体的に解決策があるかどうかはわかりませんが、有望なようです。

アップデート：

TrailerArraysで見つけた最も有望なデータ構造。基本的にはHaskellDiffArrayですが、バックトラックすると元に戻ります。

遅延リスト処理を提供する OCaml ライブラリは何ですか? 私はこれらの行に沿って何かを探しています:

Camlp4 パーサーをバックトラッキングStreamするための型とシンタックス シュガーとの統合は素晴らしいでしょう。

9x9 の数独グリッドを保持する 2 次元配列を想定すると、私のソルブ関数はどこで壊れますか? 単純なバックトラッキング アプローチを使用してこれを解決しようとしています。ありがとう！

問題を変更した後でもisSolved、私の解決策は無限ループに陥っているようです。基本的な手順が欠けているように見えますが、その場所や理由がわかりません。同様の解決策を見てきましたが、まだ問題を特定できません。基本的なソルバーを作成しようとしているだけで、効率を上げる必要はありません。助けてくれてありがとう！

まず第一に私の英語をごめんなさい。

Erlangでバックトラッキングアルゴリズムを使用したいと思います。部分的に満たされた数独を解くための推測として役立ちます。9x9数独は、81個の要素のリストとして保存され、すべての要素には、そのセルに入る可能性のある数が保存されます。

4x4数独の場合、私の最初のソリューションは次のようになります：[[1]、[3]、[2]、[4]、[4]、[2]、[3]、[1]、[2,3]、 [4]、[1]、[2,3]、[2,3]、[1]、[4]、[2,3]]

この数独には2つの解決策があります。私はそれらの両方を書き出す必要があります。その最初の解決策に達した後、バックトラッキングアルゴリズムを実装する必要がありますが、それを作成する方法がわかりません。

私の考えは、固定要素をfixedlistと呼ばれる新しいリストに書き出すことです。これにより、複数のソリューションのセルが[]に変更されます。

上記の例では、固定リストは次のようになります：[[1]、[3]、[2]、[4]、[4]、[2]、[3]、[1]、[]、[4] 、[1]、[]、[]、[1]、[4]、[]]

ここから「サンプル」があり、ソリューションリストで1に等しくない最小の長さを探し、このセルの最初の可能な数を試し、それをその固定リストに入れます。ここに、セルを更新して、それがまだ解決可能な数独であるかどうかをチェックするアルゴリズムがあります。そうでなければ、私は1つを後退させて新しいものを試す方法がわかりません。私はそれの擬似コードを知っており、命令型言語には使用できますが、erlangには使用できません。（prologは実際にバックトラックアルゴリズムを実装しましたが、erlangは実装しませんでした）

何か案が？

Xキログラムを入れることができるバッグがあります。ものの配列とその重量を取得します。true とそれぞれの重みを出力し、答えがない場合は false を出力します

例：

「プログラミングの課題（プログラミングコンテストトレーニングマニュアル）」は、おそらくアルゴリズムに関する最も優れた演習の本の1つです。最初の11の演習を解決しましたが、「CryptKicker」の問題で立ち往生しています。

Crypt Kicker
テキストを暗号化する一般的ですが安全でない方法は、アルファベットの文字を並べ替えることです。言い換えると、アルファベットの各文字は、テキスト内で一貫して他の文字に置き換えられます。暗号化を元に戻せるようにするために、2つの文字が同じ文字に置き換えられることはありません。

あなたの仕事は、各行が異なる置換のセットを使用し、復号化されたテキスト内のすべての単語が既知の単語の辞書からのものであると仮定して、テキストのいくつかのエンコードされた行を復号化することです。

入力
入力は、整数nを含む行と、それに続くn個の小文字（行ごとに1つ）で構成され、アルファベット順になります。これらのn個の単語は、復号化されたテキストに表示される可能性のある単語の辞書を構成します。
辞書に続いて、数行の入力があります。各行は上記のように暗号化されます。

辞書には1,000語しかありません。16文字を超える単語はありません。暗号化された行には小文字とスペースのみが含まれ、長さは80文字を超えません。

出力
各行を復号化し、標準出力に出力します。複数の解決策がある場合は、誰でもかまいません。
解決策がない場合は、アルファベットのすべての文字をアスタリスクに置き換えてください。

サンプル入力6
と
ディック
ジェーン
パフ
スポット
ヤートル

bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd

サンプル出力
ディックとジェーンとパフとスポットとヤートル..。

この演習を解決するには、どのような戦略を取る必要がありますか？私は古典的で野蛮なバックトラックソリューションを考えていましたが、もっとインテリジェントなものが見つかるまでそれを避けようとしています。

PS：これは宿題とは関係ありません。私は自分の全体的なスキルを向上させようとしているだけです。

F# 型の構文を解析しようとしています。[F]Parsec 文法を書き始めて問題が発生したので、文法を次のように単純化しました。

FParsec で問題が発生した後、私は Parsec に切り替えました。なぜなら、私はそれを説明するための本の完全な章を持っているからです。この文法の私のコードは

問題は、Parsec がデフォルトでバックトラックしないことです。

私が最初に試みたのは、typeP の順序を変更することでした。

しかし、文法が左再帰であるため、これは単なるスタック オーバーフローidentPですarrowP。次に、さまざまな場所で試しtryました。たとえば、

しかし、（1）スタックオーバーフローまたは（2）識別子に続く「->」の非認識の基本的な動作を変更することは何もないようです。

私の間違いは、Parsec 文法の記述に成功した人なら誰にでも明らかです。誰かがそれを指摘できますか？

How to Design Programs の拡張演習 28.2 で行き詰まっています。リストを使用する代わりに、真または偽の値のベクトルを使用してボードを表現しました。これは私が持っているもので、動作しません:

私が次のPrologナレッジベースを持っているとしましょう：

次のCコードを作成する場合：

述語「likes」を1回だけ呼び出し、結果として「mary」のみになります。それをバックトラックして、すべての結果を生成して印刷するにはどうすればよいですか？

ありがとうございました、

マトリックスをトラバースして、各タイプの「特徴的な領域」がいくつあるかを言わなければなりません。

特性領域は、値 n または >n の要素が隣接するゾーンとして定義されます。

たとえば、次の行列があるとします。

元のマトリックスと等しいタイプ 1 の単一の特性領域があります。

タイプ 2 には 2 つの特徴的な領域があります。

タイプ 3 の 1 つの特徴的な領域:

したがって、関数呼び出しの場合:

結果は

私はまだ countAreas を定義していませんvisit。移動できる正方形がなくなったときに機能が停止し、適切な再帰呼び出しが行われません。私は関数型プログラミングが初めてで、ここでバックトラッキングアルゴリズムを実装する方法についてまだ頭を悩ませています。コードを見てみましょう。変更するにはどうすればよいですか?