Wie kann ich TDD verwenden, um ein Puzzle mit einer unbekannten Antwort zu lösen?

StackOverflow https://stackoverflow.com/questions/4540265

  •  13-10-2019
  •  | 
  •  

Frage

Kürzlich habe ich ein Ruby -Programm geschrieben, um Lösungen für a zu bestimmen "Scramble Quadrares" Kachelpuzzle:

Ich habe TDD verwendet, um das meiste davon zu implementieren, was zu Tests führte, die so aussahen:

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

Dies funktionierte gut für die unteren "Helfer" -Methoden auf der unteren Ebene: Identifizierung der "Seiten" einer Fliese, festzustellen, ob eine Fliese in der Gitter usw. gültig platziert werden kann.

Aber ich stieß auf ein Problem, als ich den tatsächlichen Algorithmus kodierte, um das Puzzle zu lösen. Da ich keine gültigen möglichen Lösungen für das Problem kannte, Ich wusste nicht, wie man zuerst einen Test schreibt.

Am Ende schrieb ich einen ziemlich hässlichen, ungetesteten Algorithmus, um ihn zu lösen:

  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

Meine Frage ist also: Wie verwenden Sie TDD, um eine Methode zu schreiben, wenn Sie die gültigen Ausgaben noch nicht kennen?

Wenn Sie interessiert sind, ist der Code auf GitHub:

War es hilfreich?

Lösung

Dies ist keine direkte Antwort, aber das erinnert mich an mich an der Vergleich Zwischen den von Peter Norvig und Ron Jeffries geschriebenen Sudoku -Solvers. Ron Jeffries 'Ansatz verwendete klassische TDD, aber er hat nie wirklich eine gute Lösung bekommen. Norvig dagegen konnte es ohne TDD sehr elegant lösen.

Die grundlegende Frage ist: Kann ein Algorithmus mit TDD auftauchen?

Andere Tipps

Von dem Puzzle -Website:

Das Objekt des Scramble Squares® Puzzle -Spiels besteht darin, die neun farbenfrohen quadratischen Stücke in ein 12 "x 12" Quadrat zu ordnen, damit die realistischen Grafiken an den Teilen perfekt zu einem fertigen Design in alle Richtungen passen.

Eines der ersten Dinge, nach denen ich suchen würde, ist ein Test, ob zwei Kacheln in einer bestimmten Anordnung einander übereinstimmen. Dies betrifft Ihre Frage der Gültigkeit. Ohne diese Methode kann man nicht bewerten, ob das Puzzle gelöst wurde. Das scheint ein schöner Ausgangspunkt zu sein, ein schönes, mundgerechtes Stück in Richtung der vollen Lösung. Es ist natürlich noch kein Algorithmus.

Einmal match() Arbeitet wir, wohin gehen wir von hier aus? Nun, eine offensichtliche Lösung ist die Brute -Kraft: Lehnen Sie aus dem Satz aller möglichen Anordnungen der Fliesen innerhalb des Netzes diejenigen ab, bei denen zwei benachbarte Fliesen nicht übereinstimmen. Das ist eine Art Algorithmus, und es ist ziemlich sicher, dass es funktioniert (obwohl in vielen Rätseln der Hitze -Tod des Universums vor einer Lösung vorkommt).

Wie wäre es mit dem Sammeln des Satzes aller Fliesenpaare, die entlang einer bestimmten Kante (LTRB) übereinstimmen? Könnten Sie schneller von dort zu einer Lösung gelangen? Natürlich können Sie es leicht genug testen (und testen).

Die Tests sind unwahrscheinlich geben Sie sind ein Algorithmus, aber sie können Ihnen helfen, über Algorithmen nachzudenken, und natürlich können sie die Validierung Ihres Ansatzes erleichtern.

Keine Ahnung, wenn dies auch die Frage "beantwortet"

Analyse des "Puzzles"

9 Fliesen
Jeder hat 4 Seiten
Jede Kachel hat ein halbes Muster / Bild

Brute Force -Ansatz

Um dieses Problem zu lösen, müssen Sie 9 generieren! Kombinationen (9 Kacheln x 8 Fliesen x 7 Kacheln ...)

begrenzt durch die Anzahl der passenden Seiten auf die bereits vorhandenen aktuellen Kacheln (en)

Betrachtung Ansatz

F Wie viele Seiten sind unterschiedlich? Dh wie viele Spiele gibt es?

Daher 9 x 4 = 36 Seiten / 2 (da jede Seite "mindestens 1 andere Seite" übereinstimmen muss)
Ansonsten ist es ein unvollständiges Rätsel
Hinweis: Mindestens 12 müssen "richtig" für ein 3 x 3 -Puzzle übereinstimmen

Beschriften Sie jede passende Seite einer Fliese mit einem einzigartigen Buchstaben

Erstellen Sie dann einen Tisch, der jede Fliese hält
Sie benötigen 4 Einträge in die Tabelle für jede Fliese
4 Seiten (Ecken) daher 4 Kombinationen
Wenn Sie die Tabelle nach Seite sortieren und in die Tabelle indexieren

Seite, Tile_Number
ABCD Tile_1
BCDA Tile_1
CDab Tile_1
DABC Tile_1

Die Verwendung der Tabelle sollte die Dinge beschleunigen
Da sollten Sie höchstens 1 oder 2 Seiten übereinstimmen
Dies begrenzt die Menge an nicht produktiven Fliesen, die sie platzieren müssen

Abhängig vom Design des Musters / Bildes
Es gibt 3 Kombinationen (Orientierungen), da jede Fliese unter Verwendung von 3 Orientierungen platziert werden kann
- Das gleiche (mehrere Kopien derselben Fliese)
- Betrachtung
- Rotation

Gott hilf uns, wenn sie sich entscheiden, das Leben sehr schwierig zu machen
Durch das Aufstellen ähnlicher Muster / Bilder auf der anderen Seite, die ebenfalls übereinstimmen müssen
Oder sogar die Fliesen zu Würfeln machen und 6 Seiten passen !!!

Mit TDD,
Sie würden Tests schreiben und dann codieren, um jeden kleinen Teil des Problems zu lösen.
wie oben beschrieben und schreiben Sie mehr Tests und Code, um das gesamte Problem zu lösen

Nein, es ist nicht einfach, Sie müssen sitzen und Tests und Code schreiben, um sie zu üben

HINWEIS: Dies ist eine Variation des Kartenfärbungsproblems
http://en.wikipedia.org/wiki/four_color_theorem

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top