如何使用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上：

有帮助吗？

解决方案

这不是直接的答案，但这使我想起 比较 在Peter Norvig和Ron Jeffries撰写的Sudoku求解器之间。罗恩·杰弗里斯（Ron Jeffries）的方法使用了经典的TDD，但他从来没有真正有一个很好的解决方案。另一方面，诺维格能够在没有TDD的情况下非常优雅地解决它。

基本问题是：可以使用TDD出现算法吗？

其他提示

来自 拼图网站:

争夺Squares®益智游戏的对象是将九种色彩插图的方形件放入12“ x 12”正方形中，以使碎片边缘上的逼真的图形完美匹配，以在每个方向上形成完整的设计。

因此，我要寻找的第一件事是测试两个瓷砖是否在特定的布置中相互匹配。这是关于您的有效性问题。如果没有该方法正常工作，您将无法评估该难题是否已解决。这似乎是一个不错的起点，这是一个很好的咬合大小的材料。当然，这还不是算法。

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

如何收集沿给定边缘（LTRB）匹配的所有瓷砖集集？您可以从那里到达解决方案吗？当然，您可以很容易地对其进行测试（和测试驱动）。

测试不太可能 给 您是算法，但是它们可以帮助您考虑算法，当然，它们可以使您的方法更加容易。

dunno是否要“回答”这个问题

分析“难题”

9个瓷砖
每个有4个侧面
每个瓷砖都有一半的图案 /图片

蛮力方法

要解决此问题，您需要生成9！组合（9个瓷砖x 8瓷砖x 7瓷砖...）

受当前瓷砖的匹配侧数的限制

被考虑的方法

问有多少个方面有不同的方面？即有几场比赛？

因此，9 x 4 = 36侧 / 2（因为每一侧“必须”至少匹配另一侧）
否则它是一个不可决的难题
注意：至少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