1

lonpos.ccから脳パズルをプレゼントされました。さまざまなソリューションがいくつもあることに興味があり、アルゴリズムやコードを書くのがとても楽しいので、ブルートフォース攻撃を行うアプリケーションを書き始めました。

パズルは次のようになります：http ：//www.lonpos.cc/images/LONPOSdb.jpg / http://cdn100.iofferphoto.com/img/item/191/498/944/u2t6.jpg

20x14の「ポイント」のボードです。そして、すべてのパズルのピースは裏返して回すことができます。各ピース（およびパズル）が次のように表示されるアプリケーションを作成しました。

01010
00100
01110
01110
11111
01010

これまでの私のアプリケーションはかなり単純です。

それはピースのリストと空白のボードを取り、ピース＃0のポップはそれをあらゆる方向に反転させ、そのピースはすべてのx座標とy座標に配置しようとします。ピースが正常に配置されると、新しい「ボード」のコピーが渡され、いくつかのピースが再帰関数に取り込まれ、それらのピースのすべての組み合わせが試行されます。

擬似コードで説明：

bruteForce(Board base, List pieces) {
    for (Piece in pieces.pop, piece.pop.flip, piece.pop.flip2...) {
        int x,y = 0;
        if canplace(piece, x, y) {
            Board newBoard = base.clone();
            newBoard.placePiece(piece, x, y);
            bruteForce(newBoard, pieces);
        }
        ## increment x until x > width, then y
    }
}

今、私はこれをより速くする方法を見つけようとしています。私がこれまでに考えたこと：

  1. 並行して解決する-実装され、現在は4つのスレッドを使用しています。
  2. ピースを並べ替えて、フィットしようとしているx、yスペースに収まるピースのみを配置しようとします。（つまり、一番下の行にいて、位置から一番下までの「ポイント」が4つしかない場合は、高さが8のポイントを試さないでください）。
  3. ボードを複製するのではなく、placePieceやremovePieceなどを使用します。
  4. 「無効な」ボードをチェックします。これは、ピースに到達できない場合（完全にボックス化されている場合）です。

誰かが私がこれをより速くすることができる方法について何か創造的なアイデアを持っていますか？または、いくつの異なる組み合わせがあるかを数学的に計算する方法はありますか？

4

2 に答える 2

3

物事を速く行うための明白な方法はわかりませんが、役立つかもしれないいくつかのヒントがあります。

まず、バンプを無視すると、1x2ブロックで埋める6x4グリッドがあります。各ブロックには、バンプまたは穴を設定できる6つの位置があります。したがって、各エッジでバンプが穴と一致するようにブロックの配置を見つけようとしています。また、この情報を使用して、ピースをはるかに効率的に表すことができます。

次に、特定のブロックをどこでも再生するためのすべての場所ではなく、特定の場所にブロックを配置するためのすべての方法を試すことをお勧めします。これはあなたが降りる誤った道の数を減らすでしょう。

于 2012-10-23T19:42:09.943 に答える
1

これは、正確なカバーの問題のように見えます。基本的に、ボード上のすべてのフィールドを指定されたピースでカバーする必要があります。ドナルド・クヌースが発行したDancingLinksをお勧めします。この論文では、ペントミノ問題の明確な例を見つけて、それがどのように機能するかについての良いアイデアを与えるはずです。

基本的に、ボード上に特定のブロックを配置するためのすべての可能な方法を追跡するシステムをセットアップします。ブロックを配置することで、フィールド上の一連の位置をカバーします。これらの位置を使用して、他のブロックを配置することはできません。その後、別のブロックを配置する前に、問題の設定からすべての可能性が消去されます。ダンスリンクにより、可能性の迅速なバックトラックと消去が可能になります。

于 2012-10-24T07:21:18.633 に答える