1

超高層ビルのパズルを解くアルゴリズムを書いています:

超高層ビル パズルは、数独の行と列の制約を外部の手がかり値と組み合わせて、数値の各行または列をさまざまな高さの超高層ビルでいっぱいの道路として再想像します。数字が大きいほど高い建物を表します。

超高層ビルのパズルを解くには、1 から 5、または 1 から 1 をパズルのサイズに関係なく、すべての行と列に 1 つずつ配置し、指定された超高層ビルの手がかりをそれぞれ解決する必要があります。

超高層ビル パズルを理解するには、グリッドに配置する各値が、その階数の超高層ビルを表していると想像する必要があります。1 は 1 階建ての超高層ビル、4 は 4 階建ての超高層ビルです。ここで、手がかりの数字の 1 つがあるグリッドの外に出て立ち、グリッドを振り返ると想像してください。その手がかりの数は、手がかりのある行または列に沿ってのみ、手がかりの視点から見て、そのポイントから見える高層ビルの数を示します。背の高い建物は常に低い建物を覆い隠します。つまり、数字が大きいと常に小さい数字が隠されます。

すべての基本的なテクニックが実装され、機能していますが、より大きなパズル (5x5>) では、ある種の再帰アルゴリズムが必要であることに気付きました。まともに機能するpython scriptを見つけましたが、基本的な手がかりを解決する以外に実際に何をするかについてはあまり詳しくありません。

これらのパズルを解く適切な方法を知っている人はいますか、または上記のコードの本質を明らかにできる人はいますか?

4

2 に答える 2

9

ミーシャは強引な方法を教えてくれました。制約の伝播に基づいて、はるかに高速な再帰アルゴリズムを作成できます。Peter Norvig (Google Research の責任者) は、この手法を使用して Python で数独を解く方法についての優れた記事を書きました。それを読んで、すべての詳細を理解しようとすると、多くのことが保証されます. 超高層ビルのパズルは数独と多くの共通点があるため (3X3 ブロックはありませんが、端の数​​字によっていくつかの追加の制約が与えられます)、おそらく彼のコードの多くを盗むことができます。

数独と同様に、各フィールドには 1..N の可能なすべての数字のリストが含まれています。その後、一度に 1 つの水平/垂直線またはエッジの手がかりを見て、不正なオプションを削除します。たとえば、5x5 の場合、エッジ 3 は、最初の 2 つの正方形から 5 を除外し、最初の正方形から 4 を除外します。制約の伝播が残りを行う必要があります。エッジの制約が満たされるまでループし続けるか、すべての制約を循環した後にスタックします。Norvig が示しているように、推測を開始し、矛盾する場合は数字を削除します。

数独の場合、1 つの数字を 1 つの正方形に割り当てると (他のすべての可能性を削除します)、手がかりのすべての情報が使用されるため、与えられた手がかりは 1 回だけ処理する必要があります。ただし、超高層ビルでは、与えられた手がかりが完全に満たされるまで (たとえば、完全な線が解かれる場合)、その手がかりを何度も適用する必要がある場合があります。

于 2013-09-18T13:55:00.890 に答える
5

絶望的な場合は、パズルをブルート フォースすることができます。私は通常、パズルに慣れるための最初のステップとしてこれを行います。NxN基本的に、次の制約に従って、正方形に 1 から N までの整数を入力する必要があります。

  • 各整数は、すべての行に 1 回だけ表示されます
  • 各整数は、すべての列に 1 回だけ表示されます
  • 行「手がかり」は満たされています
  • 列「手がかり」は満たされています

ブルート フォース ソリューションは次のように機能します。まず、ボードを整数の 2D 配列として表します。次にis_valid_solution、ボードが上記の制約を満たしている場合に True を返し、そうでない場合に False を返す関数を作成します。この部分は、 で比較的簡単に実行できますO(N^2)。

最後に、可能なボードの順列を繰り返し、is_valid_solution順列ごとに呼び出します。それが True を返したら、解決策が見つかりました。考えられる取り決めは全部あるN^(NxN) ので、完全な解は になりますO(N^(NxN))。検索スペースを減らすために上記の制約を使用することで、より良い結果を得ることができます。

上記の方法は、実行に比較的長い時間がかかりO(N^(NxN))ます (アルゴリズムにとってはかなり恐ろしいことです) が、(最終的には) 解決策が得られます。それが機能するようになったら、より良い方法を考えてみてください。行き詰まったら、ここに戻ってきてください。

編集

上記の代わりに、空のボードから検索 (深さ優先など) を実行することをお勧めします。検索を繰り返すたびに、テーブルの 1 つのセルに数値を入力します (ただし、制約に違反することはありません)。たまたまボードがいっぱいになったら、完了です。

これは、再帰的な力ずくの深さ優先検索の擬似コードです。検索はNxNノードの深さまで行われ、各ノードでの分岐係数は最大でNです。1 + N + N^2 + ... + N^(N-1)これは、最大でまたは(N^N-1)/(N-1)ノードを調べる必要があることを意味します。これらのノードのそれぞれについてis_valid_board、最悪の場合 (ボードがいっぱいの場合) O(N^2) である which を呼び出す必要があります。

def fill_square(board, row, column):
  if row == column == N-1: # the board is full, we're done
    print board
    return
  next_row, next_col = calculate_next_position(row, col)
  for value in range(1, N+1):
    next_board = copy.deepcopy(board)
    next_board[row][col] = value
    if is_valid_board(next_board):
      fill_square(next_board, next_row, next_col)

board = initialize_board()
fill_square(board, 0, 0)

この関数calculate_next_positionは、次に塗りつぶす正方形を選択します。これを行う最も簡単な方法は、ボードのスキャンライン トラバーサルです。よりスマートな方法は、行と列を交互に埋めることです。

于 2013-09-18T13:30:08.053 に答える