3
$\begingroup$

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.

$\endgroup$

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.