I'm trying to solve the following problem :

A tile results of a number and a color.

  • a tile can be black, red, orange or blue.
  • a tile number is >= 1 and <= 15.

Given a random set a tiles (a same tile cannot be present more than twice in the set, so we have 15 * 4 * 2 = 120 tiles maximum), find if all the tiles can be grouped in valid subsets at one time.

There are two types of valids subsets :

  • The first one is a group. A group is a set of either three or four tiles of the same number but in different colors. (ex. 8 black, 8 red, 8 blue, 8 orange)
  • The second is a run. A run is a set of three or more consecutive numbers, all in the same color. (ex. 5 red, 6 red, 7 red).

My first try was a bruteforce/backtracking attempt : find all valid subsets, remove one from the set, find all valid subsets again (backtrack if none found and try another), remove one again ... but there are too many possibilities for my cpu (i7 8700).

How could i solve this problem ?

Thanks for help,

  • $\begingroup$ If my quick runtime estimation is correct, you should be able to solve it using dynamic programming, where the state is given by 1) $n$ such that all tiles with values $>n$ are used and none tiles $< n-2$ are used. 2) For each color and for each value between $n-2$ and $n$, the number of such tiles. The idea is somewhat similar to DP on broken profile. $\endgroup$ – user114966 Feb 28 at 22:28
  • 1
    $\begingroup$ Actually, a simple solution should work. Just write a recursive brute-force solution, but 1) add memorization (i.e. if you've been at some state, don't process it again), as in top-down DP 2) Always select a group/run which uses the highest-value tile. I.e. if the maximum tile value is $10$, then you must select a subset which has a tile with value $10$. You can also process colors in a fixed order to reduce the number of states $\endgroup$ – user114966 Feb 28 at 22:33
  • $\begingroup$ This looks a lot like the Rummikub game (the colors match ^^). $\endgroup$ – Hugo Manet Mar 2 at 12:53

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.