Как я могу использовать TDD для решения головоломки с неизвестным ответом?

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

  •  13-10-2019
  •  | 
  •  

Вопрос

Недавно я написал программу 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:

Это было полезно?

Решение

Это не прямой ответ, но это напоминает мне сравнение Между решателями Судоку, написанным Питером Норвигом и Роном Джеффрисом. Подход Рона Джеффриса использовал классический TDD, но он никогда не получил хорошего решения. Норвиг, с другой стороны, смог решить его очень элегантно без TDD.

Фундаментальный вопрос: может ли алгоритм появиться с помощью TDD?

Другие советы

От Сайт головоломки:

Объект игры головоломки Scramble Squares® состоит в том, чтобы разместить девять красочно иллюстрированных квадратных кусочков в площадь 12 "x 12", так что реалистичная графика по краям кусочков идеально совпадала, чтобы сформировать завершенный дизайн во всех направлениях.

Итак, одна из первых вещей, которые я бы искал, - это проверить, соответствуют ли две плитки в определенной договоренности друг друга. Это относится к вашему вопросу о достоверности. Без этого метода правильно работает, вы не можете оценить, была ли головоломка решена. Это кажется хорошей отправной точкой, хорошей кусочкой размером с укус к полному решению. Конечно, это еще не алгоритм.

Один раз match() Работает, куда мы идем отсюда? Что ж, очевидным решением является грубая сила: из набора всех возможных расположений плиток в сетке отвергните те, где любые две соседние плитки не совпадают. Это своего рода алгоритм, и он почти наверняка будет работать (хотя во многих головоломках тепло смерти вселенной возникает перед решением).

Как насчет сбора набора всех пар плиток, которые соответствуют данному краю (LTRB)? Не могли бы вы добраться оттуда в решение, быстрее? Конечно, вы можете проверить его (и тестировать его) достаточно легко.

Тесты вряд ли дайте Вы алгоритм, но они могут помочь вам подумать об алгоритмах, и, конечно, они могут облегчить проверку вашего подхода.

не знаю, если это «отвечает» на вопрос

Анализ "головоломки"

9 плиток
у каждого 4 стороны
Каждая плитка имеет половину рисунка / картинки

Подход грубой силы

Чтобы решить эту проблему, вам нужно генерировать 9! Комбинации (9 плиток x 8 плитки x 7 плиток ...)

ограничено количеством соответствующих сторон до нынешней плитки (ы) уже на месте

Считается подход

Q Сколько сторон отличается? Т.е. Сколько там матчей?

Следовательно, 9 x 4 = 36 сторон / 2 (поскольку каждая сторона «должна» соответствовать не менее 1 другой стороне)
В противном случае это неподходящая головоломка
ПРИМЕЧАНИЕ. По крайней мере, 12 должны соответствовать «правильно» для головоломки 3 x 3

Запретить каждую соответствующую сторону плитки, используя уникальную букву

Затем постройте стол с каждой плитой
Вам понадобится 4 записи в таблицу для каждой плитки
4 стороны (углы) отсюда 4 комбинации
Если вы отсортируете таблицу рядом и индекс в таблицу

сторона, tile_number
ABCD TILE_1
BCDA TILE_1
CDAB TILE_1
DABC TILE_1

Использование таблицы должно ускорить ситуацию
Поскольку вам нужно только соответствовать 1 или 2 сторонам максимум
Это ограничивает количество не продуктивного размещения плитки

В зависимости от дизайна рисунка / картины
Есть 3 комбинации (ориентации), поскольку каждая плитка может быть размещена с помощью 3 ориентаций
- одинаково (несколько копий одной и той же плитки)
- отражение
- вращение

Боже поможет нам, если они решит сделать жизнь очень трудной
Поместив аналогичные шаблоны / изображения на другую сторону, которые также должны соответствовать
Или даже сделать плитки в кубики и соответствуя 6 сторонам !!!

Используя TDD,
Вы будете писать тесты, а затем кодировать для решения каждой небольшой части проблемы,
Как указано выше и напишите больше тестов и кода, чтобы решить всю проблему

Нет, это не просто, вам нужно сесть и писать тесты и код для практики

ПРИМЕЧАНИЕ: это вариация проблемы раскраски карты
http://en.wikipedia.org/wiki/four_color_theorem

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top