9

最近我写了一个 Ruby 程序来确定“Scramble Squares”拼图的解决方案：

我使用 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® 益智游戏的目的是将九个彩色插图的正方形棋子排列成一个 12" x 12" 的正方形，使棋子边缘的逼真图形完美匹配，形成各个方向的完整设计。

所以我首先要寻找的东西之一是测试两个瓷砖是否以特定的排列方式相互匹配。这是关于你的有效性问题。如果该方法无法正常工作，您将无法评估谜题是否已解决。这似乎是一个不错的起点，是完整解决方案的一小部分。当然，这还不是算法。

一旦match()工作，我们从这里去哪里？好吧，一个明显的解决方案是蛮力：从网格内所有可能的瓷砖排列的集合中，拒绝任何两个相邻瓷砖不匹配的那些。那是一种算法，它肯定会起作用（尽管在许多谜题中，宇宙的热寂发生在解决方案之前）。

如何收集沿给定边缘（LTRB）匹配的所有瓷砖对的集合？你能从那里更快地找到解决方案吗？当然，您可以轻松地对其进行测试（并试驾）。

测试不太可能为您提供算法，但它们可以帮助您思考算法，当然它们可以使验证您的方法更容易。

于 2010-12-27T17:21:25.553 回答
0

不知道这是否“回答”了这个问题

解析“谜题”

9 块瓷砖
，每块有 4 个面
，每块瓷砖有半个图案/图片

蛮力方法

要解决这个问题，你需要生成 9! 组合（9 块 X 8 块 X 7 块...）

受限于与当前图块匹配的边数

考虑的方法

Q 有多少面不同？IE 有多少匹配项？

因此 9 X 4 = 36 面 / 2（因为每一面“必须”匹配至少另一面）
否则它是一个无法完成的谜题
注意：对于 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 个方向放置
- 相同（同一拼贴的多个副本）
- 反射
- 旋转

如果他们决定让生活变得非常困难
，上帝会帮助我们，将类似的图案/图片放在同样需要匹配的另一侧，
或者甚至将瓷砖制成立方体并匹配 6 个面！！！

使用 TDD，
您将编写测试，然后编写代码来解决问题的每个小部分，
如上所述，然后编写更多测试和代码来解决整个问题

不，这并不容易，您需要坐下来编写测试和代码来练习

注意：这是地图着色问题
http://en.wikipedia.org/wiki/Four_color_theorem的变体

于 2010-12-29T13:40:27.607 回答