通りとセットの値の合計は、3 で割ることができます。
- n + n + n = 3n
- (n-1) + n + (n + 1) = 3n
したがって、解決されたハンドのすべての数字を合計すると、3N + 2M の形式の数字が得られます。ここで、M はペアのタイルの値です。3 による除算の余り ( total % 3) は、M の各値に対して次のようになります。
total % 3 = 0 -> M = {3,6,9}
total % 3 = 1 -> M = {2,5,8}
total % 3 = 2 -> M = {1,4,7}
したがって、9 つの可能なペアをテストする代わりに、単純な追加に基づいて 3 つのペアを試すだけで済みます。可能なペアごとに、その値を持つ 2 つのタイルを削除し、アルゴリズムの次のステップに進み、可能かどうかを判断します。
これを取得したら、最も低い値から始めます。その値を持つタイルが 3 つ未満の場合、それらは必ず通りの最初の要素であることを意味するため、その通りを削除します (タイル n+1 または n+2 が見つからないために削除できない場合は、ハンドを意味します)。は無効)、次に低い値に進みます。
最小値のタイルが 3 つ以上ある場合は、それらをまとめて削除します (「それらが道路の一部だったらどうなるか?」と尋ねる場合は、そうであればタイル 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
2 番目の例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]
3 番目の例 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]