What are you waiting for? (A mahjong solver) Idea thanks to @MartinBüttner from a discussion in chat

Mahjong is a tile game that is immensely popular in Asia. It is typically played with four players, and the goal of the game is to be the first person to complete a valid hand using the tiles. For this challenge, we will consider a simplified version of the game — PPCG mahjong.

In PPCG mahjong, there are three suits – m, p and s – and the tiles are numbered from 1 to 9. There are exactly four copies of each tile, and the tiles are denoted by its number followed by its suit (e.g. 3m, 9s).

A completed PPCG mahjong hand consists of four sets of three and a pair, for a total of 14 tiles.

A set of three can be either:


Three of the same tile (e.g. 4s 4s 4s, but not 4m 4p 4s), or
A sequence of three consecutive tiles in the same suit (e.g. 1s 2s 3s or 6p 7p 8p but not 3s 4m 5m or 3p 5p 7p). Sequences do not wrap (so 9m 1m 2m is invalid).


A pair is simply two identical tiles (e.g. 5s 5s).

The challenge

Your program will receive a space-separated hand of 13 tiles, with each tile appearing no more than four times. You may write either a full program or a function which takes in a string.

Your task is to find all possible 14th tiles ("waits") which, when added to the hand, would form a completed PPCG mahjong hand. The outputted tiles should be space-separated, but can be in any order. Leading or trailing whitespace is allowed.

Your program should run in a reasonable amount of time, no longer than a minute.

Examples

Input: 1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s
Output: 9s

Input: 1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p
Output:

Input: 1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s
Output: 1s

Input: 1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m
Output: 1m 2m 3m 4m 5m 6m 7m 8m 9m

Input: 1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s
Output: 1m 4m 6s 9s 


In the first example, the 1m 4s 7p 3m all form existing triplets, leaving the lone 9s to form a pair.

In the second example, the 2s 3s and 7p 8p can only form sequences, and the remaining tiles can only form triplets. Hence no pair can be formed, and there is no output.

In the third example, the hand splits into 1m2m3m 2m3m4m 3m3m 1s1s 9s9s9s. Normally this would be a wait for 3m 1s, but as all four 3m have been used, the only available wait is 1s.

In the fourth example, all of the m tiles complete the hand. For example, for 1m, one could have 1m1m1m 1m2m3m 4m5m6m 7m8m9m 9m9m which is a completed hand.

Try to work out the rest of the fourth example and the fifth example :)

Scoring

This is code-golf, so the solution in the fewest bytes wins. Standard loopholes apply.
Python, 312 281 bytes

def W(S):H=lambda C,n=0,t=1:sum([m&lt;C[0]and H([c-s for c in C][:l]+C[l:],n+1,u)for m,s,l,u in(2,3,1,t),(t,2,1,4),(4-5*all(C[:3]),1,3,t)])|H(C[1:],n,t)if C[2:]and max(C)&lt;5else n&gt;4;T=[i+s for s in"mps"for i in"12345678900"];return" ".join(t for t in T if("1"&lt;t)*H(map((S+t).count,T)))


W takes a string as input and returns a string as output.

The small number of tiles (27) makes it fast enough to test if each of them completes the hand.
The problem becomes to check if a hand is valid.
The function uses a simple backtracking algorithm that considers all possible choices of sets and checks if any of them adds up to a complete hand.

Hands are represented as tile histograms, i.e. a list of tile counts (for all the tiles, not only the ones present in the hand.) This makes it easy to both check if we have a certain number of a certain tile, and if we have a sequence of adjacent tiles (padding between tiles of different suits prevent multi-suit sequences.)