¿Cómo puedo usar TDD para resolver un rompecabezas con una respuesta desconocida?

Question

Hace poco escribió un programa de Ruby para determinar soluciones a un rompecabezas "Scramble Squares" baldosas:

Solía ​​TDD para poner en práctica la mayor parte de ella, lo que lleva a las pruebas que se veía así:

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 

Esto funcionó bien para los métodos "auxiliares" de nivel inferior: identificar los "lados" de una tesela, determinar si una tesela puede colocarse válidamente en la cuadrícula, etc.

Pero yo se encontró con un problema al codificar el algoritmo real para resolver el acertijo. Como no sabía soluciones posibles válidas para el problema, no supe cómo escribir una prueba primero.

terminé escribiendo una muy fea, no probado, algoritmo para resolverlo:

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 

Así que mi pregunta es: ¿cómo se utiliza TDD escribir un método cuando no lo sabe ya la salidas válidas?

Si está interesado, el código en GitHub:

• pruebas: Código https://github.com/mattdsteele/scramblesquares-solver/blob/master/golf-creator-spec.rb
• Producción: https://github.com/mattdsteele/scramblesquares-solver/blob/master/game.rb

Answer 1

Esto no es una respuesta directa, pero esto me recuerda a the comparison entre los solucionadores de Sudoku escritos por Peter Norvig y Ron Jeffries. El enfoque de Ron Jeffries usó TDD clásico, pero nunca obtuvo una buena solución. Norvig, por otro lado, pudo resolverlo muy elegantemente sin TDD.

La pregunta fundamental es: ¿puede surgir un algoritmo usando TDD?

Answer 2

Desde el puzzle website:

El objeto de Scramble Squares® pu El juego zzle consiste en organizar las nueve piezas cuadradas ilustradas en un cuadrado de 12 "x 12" para que los gráficos realistas en los bordes de las piezas coincidan perfectamente para formar un diseño completo en todas las direcciones.

Así que una de las primeras cosas que buscaría es una prueba de si dos fichas, en una disposición particular, coinciden entre sí. Esto es con respecto a su pregunta de validez. Sin ese método funcionando correctamente, no se puede evaluar si el rompecabezas se ha resuelto. Eso parece ser un buen punto de partida, una buena pieza del tamaño de un bocado para la solución completa. No es un algoritmo todavía, por supuesto.

Una vez que match() está funcionando, ¿a dónde vamos desde aquí? Bueno, una solución obvia es la fuerza bruta: del conjunto de todas las disposiciones posibles de las teselas dentro de la cuadrícula, rechaza aquellas en las que dos fichas adyacentes no coinciden. Es un algoritmo, y es bastante cierto que funciona (aunque en muchos acertijos la muerte por calor del universo ocurre antes de una solución).

¿Qué hay de recoger el conjunto de todos los pares de fichas que coinciden a lo largo de un borde determinado (LTRB)? ¿Podrías ir de allí a una solución, más rápido? Ciertamente puede probarlo (y probarlo) con la suficiente facilidad.

Es poco probable que las pruebas den un algoritmo, pero pueden ayudarlo a pensar en algoritmos y, por supuesto, pueden hacer que validar su enfoque sea más fácil.

Answer 3

No sé si este "respuestas" La pregunta ya sea

análisis del "rompecabezas"

9 azulejos
cada uno tiene 4 lados
cada baldosa tiene la mitad de un patrón/imagen

BRUTO ENFOQUE DE FUERZA

para resolver este problema necesita generar 9! Combinaciones (9 azulejos X 8 X 7 azulejos azulejos ...)

limitado por el número de lados iguales para el azulejo (s) actual ya en su lugar

consideró que el enfoque

Q ¿Cuántos lados son ¿diferente? IE ¿Cuántas coincidencias hay?

por lo tanto, 9 X 4 = 36 lados/2 (desde cada lado "debe" partido al menos 1 otro lado)
de lo contrario su un rompecabezas uncompleteable
NOTA: al menos 12 debe coincidir con "correctamente" para un 3 X 3 rompecabezas

etiqueta de cada lado correspondiente de una baldosa usando una carta única

luego construir una tabla que contiene cada baldosa
necesitará 4 entradas en la tabla para cada baldosa
4 lados (esquinas) de ahí 4 combinaciones
si ordena la mesa al lado del otro y de índice en la tabla

lado, tile_number
ABcd tile_1
BCDA tile_1
CDAB tile_1
dabc tile_1

utilizando la tabla debe acelerar las cosas
ya que solo debe coincidir con 1 o 2 lados como máximo
Esto limita la cantidad de baldosas NO PRODUCTIVAS que tiene que hacer

dependiendo del diseño del patrón/imagen
hay 3 combinaciones (orientaciones) desde cada baldosa se puede colocar usando 3 orientaciones
- los mismos (múltiples copias de la misma baldosa)
- reflexión
- la rotación

Dios nos ayude si se deciden a hacer la vida muy difícil
poniendo similares patrones/imágenes en el otro lado que también es necesario para que coincida con
o incluso hacer las baldosas en cubos y resultados 6 lados !!!

El uso de TDD,
que iba a escribir ensayos y luego el código para resolver cada pequeña parte del problema,
como se indica arriba y escribir más pruebas y el código para resolver todo el problema

NO no es fácil, que necesita para sentarse y escribir pruebas y el código para practicar

NOTA: esta es una variación del problema mapa coloración