9

最近、私は「スクランブルスクエア」タイルパズルの解決策を決定するためのRubyプログラムを作成しました。

私はTDDを使用してそのほとんどを実装し、次のようなテストを行いました。

it "has top, bottom, left, right" do
  c = Cards.new
  card = c.cards[0]
  card.top.should == :CT
  card.bottom.should == :WB
  card.left.should == :MT
  card.right.should == :BT
end

これは、低レベルの「ヘルパー」メソッド(タイルの「側面」の識別、タイルをグリッドに有効に配置できるかどうかの判断など)でうまく機能しました。

しかし、パズルを解くために実際のアルゴリズムをコーディングするときに問題が発生しました。私は問題の有効な可能な解決策を知らなかったので、最初にテストを書く方法を知りませんでした。

私はそれを解決するためにかなり醜い、テストされていないアルゴリズムを書くことになりました:

  def play_game
    working_states = []
    after_1 = step_1
    i = 0
    after_1.each do |state_1|
      step_2(state_1).each do |state_2|
        step_3(state_2).each do |state_3|
          step_4(state_3).each do |state_4|
            step_5(state_4).each do |state_5|
              step_6(state_5).each do |state_6|
                step_7(state_6).each do |state_7|
                  step_8(state_7).each do |state_8|
                    step_9(state_8).each do |state_9|
                      working_states << state_9[0]
                    end
                  end
                end
              end
            end
          end
        end
      end
    end 

だから私の質問は、有効な出力がまだわからないときに、TDDを使用してメソッドを作成するにはどうすればよいですか?

興味がある場合は、コードはGitHubにあります。

4

3 に答える 3

8

これは直接的な答えではありませんが、Peter Norvig と Ron Jeffries によって書かれた数独ソルバーの比較を思い起こさせます。Ron Jeffries のアプローチは従来の TDD を使用していましたが、実際に良い解決策を得ることはできませんでした。一方、Norvig は TDD なしで非常にエレガントに解決できました。

基本的な問題は、TDD を使用してアルゴリズムを作成できるかということです。

于 2010-12-27T18:46:35.163 に答える
1

パズルのウェブサイトから:

Scramble Squares® パズル ゲームの目的は、カラフルに描かれた 9 つの正方形のピースを 12 インチ x 12 インチの正方形に配置して、ピースの端のリアルなグラフィックが完全に一致し、あらゆる方向に完成したデザインを形成することです。

したがって、私が最初に探すことの 1 つは、特定の配置で 2 つのタイルが互いに一致するかどうかのテストです。これは、有効性の問題に関するものです。この方法が正しく機能しないと、パズルが解けたかどうかを評価できません。それは素晴らしい出発点のように思えます。完全な解決策に向けた、一口サイズの素敵な作品です。もちろん、これはまだアルゴリズムではありません。

ここmatch()からどこへ行くのですか?明らかな解決策は力ずくです。グリッド内のタイルのすべての可能な配置のセットから、隣接する 2 つのタイルが一致しないものを拒否します。これは一種のアルゴリズムであり、確実に機能します (ただし、多くのパズルでは、宇宙の熱による死は解の前に発生します)。

特定のエッジ (LTRB) に沿って一致するタイルのすべてのペアのセットを収集するのはどうですか? そこから、より迅速に解決策にたどり着くことができますか? 確かに、十分に簡単にテスト (および試乗) できます。

テストでアルゴリズムがられる可能性は低いですが、アルゴリズムについて考えるのに役立ちます。もちろん、アプローチの検証を容易にすることもできます。

于 2010-12-27T17:21:25.553 に答える
0

これが質問に「答える」かどうかはわかりません

「パズル」の分析

9 個のタイル
にはそれぞれ 4 つの側面があります
。各タイルには半分のパターン/絵があります。

ブルートフォースアプローチ

この問題を解決するには、9 を生成する必要があります。組み合わせ (9 タイル X 8 タイル X 7 タイル...)

すでに配置されている現在のタイルに一致する面の数によって制限されます

考慮されたアプローチ

Q 何面違うの?IE マッチはいくつありますか?

したがって、9 X 4 = 36 面 / 2 (各面は少なくとも 1 つの他の面と「一致する必要があるため」)
、そうでない場合は完成できないパズル
注: 3 X 3 パズルでは、少なくとも 12 面が「正しく」一致する必要があります

一意の文字を使用して、タイルの一致する各面にラベルを付ける

次に、各タイル
を保持するテーブルを作成します。各タイルのテーブルに 4 つのエントリが必要です。4つの
側面 (コーナー) です。したがって
、テーブルを並べて並べ替え、INDEX をテーブルに入れると、4 つの組み合わせが必要になります。

side,tile_number
ABcd tile_1
BCda tile_1
CDab tile_1
DAbc tile_1


テーブルを使用すると、多くても1つまたは2つの面を一致させる必要があるため、速度が向上します
。これにより、配置する必要のある非生産的なタイルの量が制限されます

各タイルは 3 つの方向を使用して配置できるため、パターン/画像のデザインに応じて
3 つの組み合わせ (方向) があります
- 同じ (同じタイルの複数のコピー)
- 反射
- 回転


彼らが同じようなパターン/写真を反対側に置くことによって人生を非常に困難にすることを決定した場合、神は私たちを助けてくれます
.

TDD を使用すると、前述のように、テストを作成してから
、問題の小さな部分を解決する
ためのコードを作成し、さらにテストとコードを作成して問題全体を解決します。

いいえ、簡単ではありません。座ってテストとコードを書いて練習する必要があります

注: これは、マップの色付けの問題
http://en.wikipedia.org/wiki/Four_color_theoremのバリエーションです。

于 2010-12-29T13:40:27.607 に答える