Algorithm to find streets and same kind in a hand

问题:

This is actually a Mahjong-based question, but a Romme- or even Poker-based background will also easily suffice to understand.

In Mahjong 14 tiles (tiles are like cards in Poker) are arranged to 4 sets and a pair. A street ("123") always uses exactly 3 tiles, not more and not less. A set of the same kind ("111") consists of exactly 3 tiles, too. This leads to a sum of 3 * 4 + 2 = 14 tiles.

There are various exceptions like Kan or Thirteen Orphans that are not relevant here. Colors and value ranges (1-9) are also not important for the algorithm.

I'm trying to determine if a hand can be arranged in the way described above. For certain reasons it should not only be able to deal with 14 but any number of tiles. (The next step would be to find how many tiles need to be exchanged to be able to complete a hand.)

Examples:

11122233344455 - easy enough, 4 sets and a pair.
12345555678999 - 123, 456, 789, 555, 99
11223378888999 - 123, 123, 789, 888, 99
11223344556789 - not a valid hand

My current and not yet implemented idea is this: For each tile, try to make a) a street b) a set c) a pair. If none works (or there would be > 1 pair), go back to the previous iteration and try the next option, or, if this is the highest level, fail. Else, remove the used tiles from the list of remaining tiles and continue with the next iteration.

I believe this approach works and would also be reasonably fast (performance is a "nice bonus"), but I'm interested in your opinion on this. Can you think of alternate solutions? Does this or something similar already exist?

(Not homework, I'm learning to play Mahjong.)

回答1:

The sum of the values in a street and in a set can be divided by 3:

• n + n + n = 3n
• (n-1) + n + (n + 1) = 3n

So, if you add together all the numbers in a solved hand, you would get a number of the form 3N + 2M where M is the value of the tile in the pair. The remainder of the division by three (total % 3) is, for each value of M :

total % 3 = 0  -> M = {3,6,9}
total % 3 = 1  -> M = {2,5,8}
total % 3 = 2  -> M = {1,4,7}

So, instead of having to test nine possible pairs, you only have to try three based on a simple addition. For each possible pair, remove two tiles with that value and move on to the next step of the algorithm to determine if it's possible.

Once you have this, start with the lowest value. If there are less than three tiles with that value, it means they're necessarily the first element of a street, so remove that street (if you can't because tiles n+1 or n+2 are missing, it means the hand is not valid) and move on to the next lowest value.

If there are at least three tiles with the lowest value, remove them as a set (if you ask "what if they were part of a street?" consider that if they were, then there are also three of tile n+1 and three of tile n+2, which can also be turned into sets) and continue.

If you reach an empty hand, the hand is valid.

For example, for your invalid hand the total is 60, which means 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

With your second example 12345555678999, the total is 78, which means 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]

Your third example 11223378888999 also has a total of 78, which causes backtracking:

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]

回答2:

There is a special case that you need to do some re-work to get it right. This happens when there is a run-of-three and a pair with the same value (but in different suit).

Let b denates bamboo, c donates character, and d donates dot, try this hand:

b2,b3,b4,b5,b6,b7,c4,c4,c4,d4,d4,d6,d7,d8

d4,d4 should serve as the pair, and c4,c4,c4 should serve as the run-of-3 set.

But because the 3 "c4" tiles appear before the 2 d4 tiless, the first 2 c4 tiles will be picked up as the pair, leaving an orphan c4 and 2 d4s, and these 3 tiles won't form a valid set.

In this case, you'll need to "return" the 2 c4 tiles back to the hand (and keep the hand sorted), and search for next tile that meets the criteria (value == 4). To do that you'll need to make the code "remember" that it had tried c4 so in next iteration it should skip c4 and looks for other tiles with value == 4. The code will be a bit messy, but doable.

回答3:

I would break it down into 2 steps.

1. Figure out possible combinations. I think exhaustive checking is feasible with these numbers. The result of this step is a list of combinations, where each combination has a type (set, street, or pair) and a pattern with the cards used (could be a bitmap).
2. With the previous information, determine possible collections of combinations. This is where a bitmap would come in handy. Using bitwise operators, you could see overlaps in usage of the same tile for different combinators.

You could also do a step 1.5 where you just check to see if enough of each type is available. This step and step 2 would be where you would be able to create a general algorithm. The first step would be the same for all numbers of tiles and possible combinations quickly.