一条街道和一个集合中的值之和可以除以 3:
- n + n + n = 3n
- (n-1) + n + (n + 1) = 3n
因此,如果您将一手已解决的牌中的所有数字相加,您将得到一个 3N + 2M 形式的数字,其中 M 是该对中牌的值。total % 3
对于 M 的每个值,除以三 ( ) 的余数是:
total % 3 = 0 -> M = {3,6,9}
total % 3 = 1 -> M = {2,5,8}
total % 3 = 2 -> M = {1,4,7}
因此,您不必测试九对可能的配对,只需基于简单的加法尝试三个。对于每个可能的对,删除具有该值的两个图块,然后继续算法的下一步以确定它是否可能。
一旦你有了这个,从最低的价值开始。如果具有该值的瓷砖少于三个,则意味着它们必然是街道的第一个元素,因此删除该街道(如果您不能因为瓷砖 n+1 或 n+2 丢失,则意味着手无效)并移至下一个最低值。
如果至少有三个具有最低值的图块,则将它们作为一组移除(如果您问“如果它们是街道的一部分怎么办?”考虑如果它们是,那么图块 n+1 中也有 3 个和 3 个瓷砖n + 2,也可以变成集合)并继续。
如果您到达空手,则该手有效。
例如,对于您的无效手牌,总数为 60,这意味着 M = {3,6,9}:
Remove the 3: 112244556789
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there is only one
Remove the 9: impossible, there is only one
对于第二个示例12345555678999
,总数为 78,这意味着 M = {3,6,9}:
Remove the 3: impossible, there is only one
Remove the 6: impossible, there is only one
Remove the 9: 123455556789
- Start with 1: there is only one, so remove a street
-> 455556789
- Start with 4: there is only one, so remove a street
-> 555789
- Start with 5: there are three, so remove a set
-> 789
- Start with 7: there is only one, so remove a street
-> empty : hand is valid, removals were [99] [123] [456] [555] [789]
您的第三个示例 11223378888999 也共有 78 个,这会导致回溯:
Remove the 3: 11227888899
- Start with 1: there are less than three, so remove a street
-> impossible: 123 needs a 3
Remove the 6: impossible, there are none
Remove the 9: 112233788889
- Start with 1: there are less than three, so remove streets
-> 788889
- Start with 7: there is only one, so remove a street
-> 888
- Start with 8: there are three, so remove a set
-> empty, hand is valid, removals were : [99] [123] [123] [789] [888]