This question is meant as a follow-up this question and my answer here.

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:

  1. Does there exists a subcollection $S\subseteq H$ such that there exists a valid arrangement for $S \cup B$; and
  2. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.