The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a set of Rummikub pieces $S$, determines whether they can be arranged as a set of valid plays (called an arrangement).
However, when we actually play Rummikub, the situation is slightly different: there is a given board state $B$ and a hand $H$. We want to empty our hand by adding pieces to the board. We assume the board $B$ has a valid arrangement.
So, the problem now becomes:
- Does there exists a subcollection $S\subseteq H$ such that there exists a valid arrangement for $S \cup B$; and
- What is the largest such subcollection $S$ ?
Obviously, we can iterate over every subcollection $S$ of $H$ and test validity for each of them, but that is inefficient. To make precise what I mean by 'efficient' here, consider the game to be played with $3,4$ or $5$ colours and the numbers $1\ldots n$ for each color.
Does there exist an polynomial (in $n$) time algorithm that solves problem 1 or 2? Or this 1 or 2 intractable (e.g. NP-hard)? Feel free ignore complications such as jokers or assume all tiles are distinct.