• Search Menu
  • Advance Articles
  • Special Issues
  • Author Guidelines
  • Submission Site
  • Open Access
  • Reviewer Guidelines
  • Review and Appeals Process
  • About The Computer Journal
  • About the BCS, The Chartered Institute for IT
  • Editorial Board
  • Advertising and Corporate Services
  • Journals Career Network
  • Self-Archiving Policy
  • Dispatch Dates
  • Journals on Oxford Academic
  • Books on Oxford Academic

BCS, The Chartered Institute for IT

Article Contents

  • 1. INTRODUCTION
  • 2. ILP MODEL
  • 3. EXAMPLES
  • < Previous

Solving Rummikub Problems by Integer Linear Programming

  • Article contents
  • Figures & tables
  • Supplementary Data

D. Den Hertog, P. B. Hulshof, Solving Rummikub Problems by Integer Linear Programming, The Computer Journal , Volume 49, Issue 6, November 2006, Pages 665โ€“669, https://doi.org/10.1093/comjnl/bxl033

  • Permissions Icon Permissions

The Rummikub problem of finding the maximal number or value of the tiles that can be placed from your rack onto the table is very difficult, since the number of possible combinations are enormous. We show that this problem can be modeled as an integer linear programming problem. In this way solutions can be found in 1 s. We extend the model such that unnecessary changes of the existing sets on the table are minimized.

Email alerts

Citing articles via.

  • Recommend to your Library

Affiliations

  • Online ISSN 1460-2067
  • Print ISSN 0010-4620
  • Copyright © 2024 British Computer Society
  • About Oxford Academic
  • Publish journals with us
  • University press partners
  • What we publish
  • New features  
  • Open access
  • Institutional account management
  • Rights and permissions
  • Get help with access
  • Accessibility
  • Advertising
  • Media enquiries
  • Oxford University Press
  • Oxford Languages
  • University of Oxford

Oxford University Press is a department of the University of Oxford. It furthers the University's objective of excellence in research, scholarship, and education by publishing worldwide

  • Copyright ยฉ 2024 Oxford University Press
  • Cookie settings
  • Cookie policy
  • Privacy policy
  • Legal notice

This Feature Is Available To Subscribers Only

Sign In or Create an Account

This PDF is available to Subscribers Only

For full access to this pdf, sign in to an existing account, or purchase an annual subscription.

The Complexity of Rummikub Problems

Rummikub is a tile-based game in which each player starts with a hand of 14 14 14 14 tiles. A tile has a value and a suit. The players form sets consisting of tiles with the same suit and consecutive values (runs) or tiles with the same value and different suits (groups). The corresponding optimization problem is, given a hand of tiles, to form valid sets such that the score (sum of tile values) is maximized. We first present an algorithm that solves this problem in polynomial time. Next, we analyze the impact on the computational complexity when we generalize over various input parameters. Finally, we attempt to better understand some aspects involved in human play by means of an experiment that considers counting problems related to the number of possible immediately winning hands.

Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands

1 Introduction

Games are generally played in a precisely defined and contained environment with fixed rules and behavior. This allows humans to witness and easily interpret the power and limitations of algorithms for solving computational problemsย  [ 2 ] . In this paper we consider the complexity for the game of Rummikub, a tile game introduced in the 1930s and well-known in, amongst others, northwestern Europe. The game is played in the following way.

Rummikub uses a set of tiles containing k > 0 ๐‘˜ 0 k>0 italic_k > 0 ย  suits (represented by colors). For each suit we have n > 0 ๐‘› 0 n>0 italic_n > 0 tiles, numbered from 1 1 1 1 to n ๐‘› n italic_n . The number of a tile represents the ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ \mathit{value} italic_value of that tile. In the game of Rummikub m > 0 ๐‘š 0 m>0 italic_m > 0 copies of the n ร— k ๐‘› ๐‘˜ n\times k italic_n ร— italic_k tiles are present in the full tile set . Additionally, a small number of j โ‰ฅ 0 ๐‘— 0 j\geq 0 italic_j โ‰ฅ 0 jokers are allowed to represent any other tile. In the original game of Rummikub m = 2 ๐‘š 2 m=2 italic_m = 2 copies are used, both consisting of k = 4 ๐‘˜ 4 k=4 italic_k = 4 suits that each contain n = 13 ๐‘› 13 n=13 italic_n = 13 ย tiles. Generally, j = 2 ๐‘— 2 j=2 italic_j = 2 ย jokers are used, summing to 106 106 106 106 ย tiles. Indeed, the game can also be played using two card decks, and we use the card suit symbols for convenient tile visualization of the original game.

Rummikub is typically played with two to four players. The pool is defined to be the stack of all tiles in a random order. Initially, each player is provided with a hand consisting of 14 14 14 14 tiles from the pool. Then, players take turns in playing tiles. A tile that is played moves from the playerโ€™s closed hand to the open table . Each turn, a player can play as many tiles as he wants. If a player chooses not to play any tiles, the player takes a tile from the pool, if it still contains any. Any tile that is played must be an element of either a group or a run. A group is defined as a set of at least three tiles of the same value but a different suit. A run is as a set of at least three tiles of the same suit but with consecutive values. Examples of groups and runs are given in Figureย  1 . Players are also allowed to rearrange tiles that are on the table as long as this again finally results into (possibly completely different) valid runs and groups. At the end of a turn all tiles that were originally on the table must still be on the table, referred to as the table constraint .

At the start of the game all players are considered to be in quarantine . A player in quarantine is not allowed to play tiles until he forms a number runs and groups whose total value exceeds a certain threshold ฮธ ๐œƒ \theta italic_ฮธ (typically ฮธ = 30 ๐œƒ 30 \theta=30 italic_ฮธ = 30 ). This is sometimes referred to as the initial meld . As a consequence, players in quarantine cannot play tiles as part of runs or groups that are already on the table. After playing tiles of which the sum exceeds the threshold value, the player is no longer in quarantine. The first player who is able to play all his tiles wins and ends the game. Alternatively, the game ends whenever the pool is empty and all players choose not to play any tiles. Then some scoring function is applied based on the sum of tile values, either remaining in the hand or played on the table, determining the winner.

The game of Rummikub contains an optimization problem, which we call the Rummikub puzzle . Given the combination of a hand and a table, the goal is to maximize the number of points that can be obtained by making valid runs and groups. The main contribution of this paper is a classification of which generalizations of the Rummikub puzzle are computationally difficult, and which ones are not. Specifically, we give an algorithm that solves the optimization problem in polynomial time, and discuss how different alternative input parameters influence the complexity of that algorithm. Subsequently, we use the algorithm to address a counting problem regarding the percentage of hands that can be played in one move in an attempt to gain more insight in possible strategies for the multi-player game.

The remainder of this paper is organized as follows. First, in Sectionย  2 relevant previous work on Rummikub and similar games is discussed. Next, a formal problem definition and characterization of the problemโ€™s input parameters is given in Sectionย  3 . In Sectionย  4 a polynomial algorithm for a particular class of Rummikub puzzles is described. Sectionย  5 uses this algorithm to address the aforementioned counting problem. Finally, Sectionย  6 provides concluding remarks and suggestions for future work.

2 Related work

Rummikub is somewhat related to so-called โ€œhand-making gamesโ€. Inย  [ 4 ] an online model has been developed that attempts to solve the โ€œremovable online knapsack problemโ€, a version of the knapsack problem where items are handled in a certain order and the player needs to decide whether such an item will be added to the knapsack or not. Items that are added can later be removed from the knapsack, but items that are neglected or removed cannot be added later on. The authors claim that this model can be applied to hand-making games such as Rummy. A simplified version of the game Gin Rummy is used to compare various self-play methods against each other inย  [ 5 ] .

The Rummikub puzzle as it is considered in this paper, has not been studied much. Inย  [ 6 ] an unsuccessful attempt was made to prove a generalized version of the Rummikub puzzle NP-complete. An integer linear programming method for solving the Rummikub puzzle is proposed in [ 3 ] . There, it is stated that the optimization problem of obtaining as many points in one move as possible is โ€œvery difficult, since the number of possible combinations are enormousโ€. Integer linear programming is an optimization technique often used to approximate intractable problems. As we will show, this optimization problem can actually be solved in polynomial time.

3 Preliminaries

The results presented in this work focus on the Rummikub puzzle:

Definition 3.1 .

Rummikub puzzle Given a subset of the Rummikub tile set of n ร— k ร— m ๐‘› ๐‘˜ ๐‘š n\times k\times m italic_n ร— italic_k ร— italic_m tiles with n ๐‘› n italic_n values, k ๐‘˜ k italic_k suits and m ๐‘š m italic_m copies of each tile, form valid sets of runs and groups such that the score (sum of used tile values) is maximized.

Note that this optimization problem is the equivalent of minimizing the value of the unused tiles in the subset. The problem is closely related to the following decision problem: given a subset of the Rummikub tile set, can we use all tiles in valid runs and groups? This decision problem can trivially be reduced to the optimization problem, as the outcome of the decision problem is true if and only if the solution to the optimization problem is equal to the sum of the values of the tiles in the particular subset.

This optimization problem is related to the original multi-player game. Each turn a player uses the tiles in his hand combined with the tiles on the table to form valid groups and runs. The particular subset for which the Rummikub puzzle is solved, is the union of the tiles on the table and the tiles in the playerโ€™s hand. The aforementioned table constraint is easily satisfied by disregarding solutions in which unused tiles were on the table. The availability of a constant number of jokers can also be accommodated, as we discuss in Sectionย  4.5 .

To reason about complexity problems, we should also define which variables are parameters of the problem. Here we distinguish between tile set parameters and the set size parameter. The tile set parameters are the previously mentioned k ๐‘˜ k italic_k for the number of suits, n ๐‘› n italic_n for the number of tiles of each suit and m ๐‘š m italic_m for the number of copies of k ร— n ๐‘˜ ๐‘› k\times n italic_k ร— italic_n tiles in the full tile set. The set size parameter s ๐‘  s italic_s is the minimal size of a set (either a group or a run), which is equal to s = 3 ๐‘  3 s=3 italic_s = 3 in the original Rummikub game.

The question of defining the input size of the problem is open to some interpretation with respect to which parameters should be considered. For example, one could say that by increasing the number of suits k ๐‘˜ k italic_k we should also increase the minimal set size, for example by fixing it at s = k โˆ’ 1 ๐‘  ๐‘˜ 1 s=k-1 italic_s = italic_k - 1 . This would also mean increasing the minimal run length, which is not always possible if k > n ๐‘˜ ๐‘› k>n italic_k > italic_n . To avoid all kinds of ambiguous situations that are undefined in the original game (such as replacing the minimal set size parameter by separate parameters for the minimum run length and minimal group size), we only consider tile set variables n ๐‘› n italic_n , k ๐‘˜ k italic_k and m ๐‘š m italic_m as input parameters, and fix the set size parameter at s = 3 ๐‘  3 s=3 italic_s = 3 .

4 Polynomial algorithm

Given a particular subset of the Rummikub tile set, we aim for an algorithm that makes valid sets of runs and groups and thus solves the Rummikub puzzle optimization problem posed in Definitionย  3.1 . For a given hand, for each tile in this hand we can choose to use it in a run, use it in a group or not to use it in either one. Indeed, given a hand of t ๐‘ก t italic_t tiles, a brute-force approach would find the solution after exploring 3 t superscript 3 ๐‘ก 3^{t} 3 start_POSTSUPERSCRIPT italic_t end_POSTSUPERSCRIPT states. Clearly, this does not scale and is not feasible for the original Rummikub game.

In this section we give a polynomial algorithm for solving the Rummikub puzzle. The section starts by describing group formation in Sectionย  4.1 and a representation of the state space in Sectionย  4.2 . The proposed algorithm for exploring this state space is then the subject of Sectionย  4.3 . The complexity is analyzed in Sectionย  4.4 and in Sectionย  4.5 we discuss various smaller aspects and constraints that need to be satisfied in Rummikub.

4.1 Forming groups

We consider the task of forming groups consisting of tiles of the same value but a different suit given k ๐‘˜ k italic_k suits and m ๐‘š m italic_m tile set copies. We are interested in the number of ways G ( k , m ) ๐บ ๐‘˜ ๐‘š G(k,m) italic_G ( italic_k , italic_m ) in which this can be done.

๐‘˜ 2 G(k,1)=1+{{k}\choose{k-1}}+{{k}\choose{k}}=1+k+1=k+2 italic_G ( italic_k , 1 ) = 1 + ( binomial start_ARG italic_k end_ARG start_ARG italic_k - 1 end_ARG ) + ( binomial start_ARG italic_k end_ARG start_ARG italic_k end_ARG ) = 1 + italic_k + 1 = italic_k + 2 . To generalize over k ๐‘˜ k italic_k (but still with constant m = 1 ๐‘š 1 m=1 italic_m = 1 ) given our definition of a constant s ๐‘  s italic_s , the number of groups is one (no groups) plus the number of ways we can form groups of size s ๐‘  s italic_s up to size k ๐‘˜ k italic_k :

To generalize over m ๐‘š m italic_m we first observe that for m = 2 ๐‘š 2 m=2 italic_m = 2 we have a copy of the full tile set with which we can again form groups in G ( k , 1 ) ๐บ ๐‘˜ 1 G(k,1) italic_G ( italic_k , 1 ) possible ways. Indeed, a trivial upper bound for G ( k , m ) ๐บ ๐‘˜ ๐‘š G(k,m) italic_G ( italic_k , italic_m ) is then:

However, this upper bound is not necessarily tight: there are combinations that are counted more than once, for example because the order in which we form groups does not matter and because groups may have overlapping tiles. For example, for m = 2 ๐‘š 2 m=2 italic_m = 2 and k = 5 ๐‘˜ 5 k=5 italic_k = 5 selecting the two groups { โ™ฃ , โ™ก , โ™  } โ™ฃ โ™ก โ™  \{\clubsuit,\heartsuit,\spadesuit\} { โ™ฃ , โ™ก , โ™  } and { โ™ก , โ™  , โ™ข , โ–ณ } โ™ก โ™  โ™ข โ–ณ \{\heartsuit,\spadesuit,\diamondsuit,\triangle\} { โ™ก , โ™  , โ™ข , โ–ณ } achieves the same tile usage as selecting groups { โ™ก , โ™  , โ™ข } โ™ก โ™  โ™ข \{\heartsuit,\spadesuit,\diamondsuit\} { โ™ก , โ™  , โ™ข } and { โ™ฃ , โ™ก , โ™  , โ–ณ } โ™ฃ โ™ก โ™  โ–ณ \{\clubsuit,\heartsuit,\spadesuit,\triangle\} { โ™ฃ , โ™ก , โ™  , โ–ณ } . Although the upper bound presented here is not tight, we expect that the number of ways to form groups is still exponential or perhaps even factorial. Thus, considering all possible ways of forming groups (and using the remaining tiles in runs) is not a good idea for an algorithm for solving Rummikub. In the next section we investigate the other way around: first making runs, and then using the remaining tiles in groups.

4.2 State space

๐‘  1 4 s+1=4 italic_s + 1 = 4 different cases (and, importantly, not n ๐‘› n italic_n different cases).

๐‘ฃ 2 ๐‘ฃ 1 ๐‘ฃ (v-2)+(v-1)+v ( italic_v - 2 ) + ( italic_v - 1 ) + italic_v . The algorithm also scores at each tile value the score obtained by either making groups of that value or by continuing valid runs using a tile of the current value v ๐‘ฃ v italic_v . In such a way, a run of length three does not have to be distinguished from a run of length larger than three, as adding a tile to the run will simple give the value of that tile as added score. If an existing run is not continued, the run ends, its length is reset to zero and no score is obtained for this run.

For m = 2 ๐‘š 2 m=2 italic_m = 2 , the number of different configurations of ๐‘Ÿ๐‘ข๐‘›๐‘  ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{runs} italic_runs for a particular suit is 10 10 10 10 : { 0 , 0 } 0 0 \{0,0\} { 0 , 0 } , { 0 , 1 } 0 1 \{0,1\} { 0 , 1 } , { 0 , 2 } 0 2 \{0,2\} { 0 , 2 } , { 0 , 3 } 0 3 \{0,3\} { 0 , 3 } , { 1 , 1 } 1 1 \{1,1\} { 1 , 1 } , { 1 , 2 } 1 2 \{1,2\} { 1 , 2 } , { 1 , 3 } 1 3 \{1,3\} { 1 , 3 } , { 2 , 2 } 2 2 \{2,2\} { 2 , 2 } , { 2 , 3 } , 2 3 \{2,3\}, { 2 , 3 } , and { 3 , 3 } 3 3 \{3,3\} { 3 , 3 } . For general m ๐‘š m italic_m and s ๐‘  s italic_s the number of configurations f ( m ) ๐‘“ ๐‘š f(m) italic_f ( italic_m ) is given by the number of distinct permutations of size m ๐‘š m italic_m in a multiset of k ๐‘˜ k italic_k distinct elements of multiplicity m ๐‘š m italic_m , denoted by the multinomial coefficient:

While this may not seem polynomial, for the Rummikub set size parameter s = 3 ๐‘  3 s=3 italic_s = 3 , we get exactly the tetrahedral (or triangular pyramidal) numbers:

So the size of the considered state space is at most n ร— k ร— f ( m ) ๐‘› ๐‘˜ ๐‘“ ๐‘š n\times k\times f(m) italic_n ร— italic_k ร— italic_f ( italic_m ) , i.e., it is polynomial in n ๐‘› n italic_n , k ๐‘˜ k italic_k , and m ๐‘š m italic_m .

4.3 Algorithm

The proposed recursive procedure to compute the maximum score given some hand of Rummikub tiles is outlined in Algorithmย  1 . The algorithm represents the entire state space using an n ร— k ร— f ( m ) ๐‘› ๐‘˜ ๐‘“ ๐‘š n\times k\times f(m) italic_n ร— italic_k ร— italic_f ( italic_m ) multi-dimensional array named ๐‘ ๐‘๐‘œ๐‘Ÿ๐‘’ ๐‘ ๐‘๐‘œ๐‘Ÿ๐‘’ \mathit{score} italic_score which contains the maximum score that can be obtained given this state of the puzzle. This array is initialized to โˆ’ โˆž -\infty - โˆž . The global variable โ„Ž๐‘Ž๐‘›๐‘‘ โ„Ž๐‘Ž๐‘›๐‘‘ \mathit{hand} italic_hand contains the particular subset of tiles for which we are running the algorithm, and is implicitly used at various moments. The algorithm is initially called with ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ \mathit{value} italic_value = 1 absent 1 =1 = 1 and with a ๐‘Ÿ๐‘ข๐‘›๐‘  ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{runs} italic_runs vector of size k ๐‘˜ k italic_k initialized for each suit to a multi-set of size m ๐‘š m italic_m with precisely m ๐‘š m italic_m zeros.

๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ 1 \mathit{value}+1 italic_value + 1 is made, of which the resulting score is added to the score of the groups and runs made at the current value (lineย 11). The ๐‘ ๐‘๐‘œ๐‘Ÿ๐‘’ ๐‘ ๐‘๐‘œ๐‘Ÿ๐‘’ \mathit{score} italic_score array is then updated with this total score (lineย 12). Finally, the algorithm returns the highest possible score given the current ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ \mathit{value} italic_value and ๐‘Ÿ๐‘ข๐‘›๐‘  ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{runs} italic_runs (lineย 13). Upon a later query for the maximum score given the current ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ ๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ \mathit{value} italic_value and ๐‘Ÿ๐‘ข๐‘›๐‘  ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{runs} italic_runs , the previously computed score can be returned (lineย 7), i.e., the dynamic programming aspect.

๐‘ฃ๐‘Ž๐‘™๐‘ข๐‘’ 1 ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{value}+1,\mathit{runs} italic_value + 1 , italic_runs ] yielded its score. Furthermore, we mention that many smaller optimizations can be made, for example by ending the recursion when a score equal to the sum of all values of the tiles in the tile set (perhaps even subtracting the value of tiles that can never be part of any run or group) is reached.

4.4 Complexity

The makeRuns ( normal-( ( ( โ€ฆ ) ) ) ) function on lineย 9 of Algorithmย  1 iterates over all possible ways of making runs given the current configuration of ๐‘Ÿ๐‘ข๐‘›๐‘  ๐‘Ÿ๐‘ข๐‘›๐‘  \mathit{runs} italic_runs . In Sectionย  4.2 we have shown that the number of these configurations for some suit is bounded by f ( m ) ๐‘“ ๐‘š f(m) italic_f ( italic_m ) , showing that the size of the state space is bounded by a polynomial. Now, to derive the time complexity of the proposed algorithm, let us consider the number of possibly ways of continuing runs, i.e., the number of states generated by the makeRuns ( normal-( ( ( โ€ฆ ) ) ) ) function.

๐‘š 1 ๐‘“ ๐‘š ๐‘˜ ((m+1)\cdot f(m))^{k} ( ( italic_m + 1 ) โ‹… italic_f ( italic_m ) ) start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT , which is O ( ( m 4 ) k O((m^{4})^{k} italic_O ( ( italic_m start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT ) start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT . However, most importantly, we note that the number of states generated by makeRuns ( normal-( ( ( โ€ฆ ) ) ) ) is polynomial in m ๐‘š m italic_m , i.e., the number of suits k ๐‘˜ k italic_k is the only parameter over which we cannot generalize in polynomial time. The above leads us to the following conclusions about the complexity of Rummikub:

The traditional Rummikub puzzle with fixed m ๐‘š m italic_m and k ๐‘˜ k italic_k can be solved in polynomial time. In fact, the presented algorithm solves the puzzle in linear O ( n ) ๐‘‚ ๐‘› O(n) italic_O ( italic_n ) time, which is optimal.

The state space of the Rummikub puzzle is at most of size O ( n โ‹… k โ‹… m 4 ) ๐‘‚ โ‹… ๐‘› ๐‘˜ superscript ๐‘š 4 O(n\cdot k\cdot m^{4}) italic_O ( italic_n โ‹… italic_k โ‹… italic_m start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT ) , so polynomial in all input parameters n ๐‘› n italic_n , m ๐‘š m italic_m and k ๐‘˜ k italic_k .

The Rummikub puzzle can be solved in polynomial time O ( n โ‹… m 4 ) ๐‘‚ โ‹… ๐‘› superscript ๐‘š 4 O(n\cdot m^{4}) italic_O ( italic_n โ‹… italic_m start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT ) when the number of tile values n ๐‘› n italic_n and the number of tile set copies m ๐‘š m italic_m are considered as input parameters.

Our algorithm for solving Rummikub runs in exponential O ( n โ‹… ( m 4 ) k ) ๐‘‚ โ‹… ๐‘› superscript superscript ๐‘š 4 ๐‘˜ O(n\cdot(m^{4})^{k}) italic_O ( italic_n โ‹… ( italic_m start_POSTSUPERSCRIPT 4 end_POSTSUPERSCRIPT ) start_POSTSUPERSCRIPT italic_k end_POSTSUPERSCRIPT ) time when in addition to n ๐‘› n italic_n and m ๐‘š m italic_m the number suits k ๐‘˜ k italic_k is considered as input parameter.

4.5 Discussion

The proposed algorithm for solving Rummikub puzzles can be employed in the game of Rummikub as discussed in Sectionย  1 . In each turn we run Algorithmย  1 on the union of all tiles in the playerโ€™s hand and all tiles on the table. Then we play the move that results in the highest score, of course taking the initial meld at the beginning of the game into account.

Furthermore, the table constraint can easily be satisfied by checking at each value whether or not all tiles of a formed group are actually used in the newly formed hand. For newly started runs, it may not be clear whether or not a tile of value v โˆ’ 2 ๐‘ฃ 2 v-2 italic_v - 2 is actually used in a run until we are at value v ๐‘ฃ v italic_v (when a valid run is formed, or not). This can be solved by means of bookkeeping: we use a constant size sliding vector of two counters indicating how many tiles of each suit we used at iteration v โˆ’ 1 ๐‘ฃ 1 v-1 italic_v - 1 and v โˆ’ 2 ๐‘ฃ 2 v-2 italic_v - 2 , and disregard the current solution should we find that we ended up disregarding a run of which the tiles were previously on the table, which would have meant violating the table constraint.

The availability of a constant number of jokers can also be accommodated in the puzzle variant of Rummikub. Usually, there are two joker tiles which can both be used to represent any regular tile in the game. Independent of whether these tiles are actually present, i.e., there can be configurations where a joker represents a value of a certain suit while the two copies of this value and suit are also present. Without this rule the addition of jokers would be trivial. For Algorithmย  1 this means that we can add a dimension to the search space representing the number of jokers that we used so far. Then for each value in { 1 , 2 , โ€ฆ , n } 1 2 โ€ฆ ๐‘› \{1,2,\ldots,n\} { 1 , 2 , โ€ฆ , italic_n } we substitute a joker for each missing tile of this value (provided there are enough jokers remaining). For j = 2 ๐‘— 2 j=2 italic_j = 2 we increase the search space with a factorย  3 3 3 3 , i.e., 0 0 , 1 1 1 1 , or 2 2 2 2 ย jokers remaining.

To accommodate the possibility of having more than two values of a particular suit we can still use the same construction. The method of creating groups must be adjusted because potentially more groups can be created. We also have more possibilities of having both groups and runs to consider. The search space will not increase beyond the aforementioned constant factor, keeping Algorithmย  1 for the original Rummikub puzzle in O ( n ) ๐‘‚ ๐‘› O(n) italic_O ( italic_n ) .

Jokers do not contribute to the score of the configuration. However, 25 25 25 25 ย penalty points per joker are given in rare occasions where a joker cannot be used in a configuration. Note that this minor score modification still allows for the conversion of the optimization problem to its corresponding decision problem.

5 Counting winning hands

Now that we have better idea of the theoretical complexity of Rummikub, let us consider an aspect of the game that has some importance when Rummikub is played by a human. We study the number of hands that can be won in one move, which has some relevance during the game, as it provides insight in the likelihood of the game ending at different points in time.

Counting problems have attracted some attention in the literature. For many games, the size of the state space has either been estimated or exactly determinedย  [ 2 ] . For one-player games (puzzles), different counting problems are typically addressed. For example in [ 7 ] , the number of Patience games that cannot be won is estimated. In this section we address a similar question: Given a hand of t ๐‘ก t italic_t tiles, what percentage of all possible hands of this size can be played in one move? We refer to such hands as winning hands .

The number of possible hands of a given size can be determined using the multinomial coefficient:

Effectively, the problem is reduced to enumerating over all possible hands of this size and then using Algorithmย  1 to determine whether we can use all tiles in valid groups and runs. As the multinomial numbers grow exponentially, this approach becomes already impractical for rather small input.

A more practical method to count the number of winning hands is the following. We start by generating all partitions of a hand of size t ๐‘ก t italic_t . In fact, we only consider partitions consisting of subsets of size 3 3 3 3 , 4 4 4 4 and 5 5 5 5 , so that each partition potentially represents a valid run or group. Note that we do not need to consider partitions of size larger than five, as every number larger than three can be written as a summand of 3 3 3 3 , 4 4 4 4 and 5 5 5 5 . Depending on how this method enumerates the partitions, some winning hands can be encountered multiple times. For this reason, we also need to store all winning hands in memory. This way we can check whether a hand was already counted and avoid counting duplicates.

Tableย  1 shows for each hand size t ๐‘ก t italic_t the total number of such hands and the number of winning hands, whereas the column โ€œratioโ€ denotes the ratio of hands that are winning. From this table it follows immediately that at the start of a game, there is a chance of 0.0000273 % percent 0.0000273 0.0000273\% 0.0000273 % that the starting player will win the game in one move. As the size of the hands is relatively small compared to the number of tiles in a game of Rummikub, it seems plausible that the ratio of winning hands is rather low.

One observation from Tableย  1 is that having more tiles does not necessarily improve the percentage of the hands that can be played in one move. However, it is reasonable to assume that at some point the ratio of winning hands grows considerably.

It can be seen that when a hand consists of all tiles in the game it is by definition a winning hand, as there are trivial ways to play all tiles. The same holds when a hand consists of all tiles except one or two; regardless of which tiles are missing, we can play all tiles as groups. Also for hands consisting of all tiles except three or four it holds that it is always a winning hand; this can be verified using Algorithmย  1 . Hands consisting of fewer tiles are not necessarily winning hands. Another observation from Tableย  1 is that overall, the ratio seems to decrease as the number of tiles grows, but at every t ๐‘ก t italic_t divisible by three it slightly increases before decreasing again. This appears to be a direct effect of the set size parameter s ๐‘  s italic_s .

As it is computationally expensive to compute the winning ratios for larger hands, we also study a smaller instance with n = 6 ๐‘› 6 n=6 italic_n = 6 , m = 2 ๐‘š 2 m=2 italic_m = 2 and k = 4 ๐‘˜ 4 k=4 italic_k = 4 . This leaves the number of suits and copies of the tile set identical to the original version, and brings the total number of tiles approximately to half of that in the original game. The ratio of winning sets was calculated for all hand sizes in this configuration. The results are shown in Figureย  2 . It shows the size of the sets against the ratio of winning hands (logarithmic scale). We observe the same pattern as for the original game. For small hands the ratio seems to decrease as the hand size increases, except for spikes at multiples of three. At some point, this effect diminishes and the ratio strictly increases. This happens from hands of size 20 20 20 20 and on. However, the ratio is still rather low. Even with a hand consisting of half of all the tiles, chances of being able to play all tiles in one move are very low ( 0.2 % percent 0.2 0.2\% 0.2 % ). It seems plausible that this percentage is even lower for the original game with n = 13 ๐‘› 13 n=13 italic_n = 13 . This observation could be useful for some dynamics in the two-player game, e.g., for determining whether the player should play some tiles or take one from the pool.

6 Conclusion

We have presented a polynomial algorithm with a dynamic programming approach that can solve the Rummikub puzzle. Next, we gave an analysis of the influence of different input parameters on the space and time complexity of both the proposed algorithm and the general problem of solving the Rummikub puzzle. Furthermore, we have used the algorithm to compute the percentage of hands of a given number of tiles can be played at once as part of a first attempt to understand the aspects involved in the multi-player game of Rummikub.

In future work we plan to more elaborately address the multi-player game: although we show that the presented algorithm for solving the Rummikub puzzle can be used in the Rummikub game, the strategy aspects of the multi-player game, such as hand-making decisions, are not considered. Two-player games with a bound on the number of moves are generally PSPACE-completeย  [ 1 ] ; whether this holds for Rummikub remains an open question worth researching further. Last but not least, the complexity of solving the Rummikub optimization problem when the number of suits k ๐‘˜ k italic_k is considered as an input parameter also remains an interesting open problem: this proof would be the final piece to solving the Rummikub puzzle.

  • [1] R.ย A. Hearn. Amazons, Konane, and Cross Purposes are PSPACE-complete. In Games of No Chance III, Proceedings of BIRS Workshop on Combinatorial Games , pages 287โ€“306, 2005.
  • [2] H. J. van den Herik, J.ย W. H.ย M. Uiterwijk, and J.ย Vanย Rijswijck. Games solved: Now and in the future. Artificial Intelligence , 134(1):277โ€“311, 2002.
  • [3] D. den Hertog and P.ย B. Hulshof. Solving Rummikub problems by integer linear programming. The Computer Journal , 49(6):665โ€“669, 2006.
  • [4] K.ย Iwama and S.ย Taketomi. Removable online knapsack problems. In Automata, Languages and Programming , volume 2380 of Lecture Notes in Computer Science , pages 293โ€“305. Springer, 2002.
  • [5] C.ย Kotnik and J.ย Kalita. The significance of temporal-difference learning in self-play training TD-Rummy versus EVO-Rummy. In Proceedings of the 20th International Conference on Machine Learning , pages 369โ€“375, 2003.
  • [6] J. N. van Rijn. Playing games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess. Masterโ€™s thesis, Leiden University, 2012.
  • [7] X.ย Yan, P.ย Diaconis, P.ย Rusmevichientong, and B.ย Vanย Roy. Solitaire: Man versus machine. In Proceedings of Advances in Neural Information Processing Systems 17 , pages 1553โ€“1560, 2004.

ar5iv homepage

Tilburg University Research Portal Logo

  • Help & FAQ

Solving Rummikub problems by integer linear programming

  • Research Group: Operations Research
  • Econometrics and Operations Research

Research output : Contribution to journal โ€บ Article โ€บ Scientific โ€บ peer-review

T1 - Solving Rummikub problems by integer linear programming

AU - den Hertog, D.

AU - Hulshof, P.B.

M3 - Article

SN - 0010-4620

JO - The Computer Journal

JF - The Computer Journal

RummikubConsole 1.2.5

pip install RummikubConsole Copy PIP instructions

Released: Jan 4, 2024

Rummikub solver console with multi-game support and persistence.

Project links

  • Github: issues
  • Github: repo
  • Open issues:

View statistics for this project via Libraries.io , or by using our public dataset on Google BigQuery

License: MIT License (MIT)

Author: Martijn Pieters

Requires: Python >=3.8

Maintainers

Avatar for mj from gravatar.com

Classifiers

  • End Users/Desktop
  • OSI Approved :: MIT License
  • Python :: 3
  • Python :: 3.8
  • Python :: 3.9
  • Python :: Implementation :: CPython
  • Games/Entertainment :: Board Games

Project description

Rummikub console.

A Rummikub solver console supporting multiple games and persistence, written in Python.

screenshot of a macOS terminal window with a Rummikub Console session in progress

The algorithm used builds on the approach described by D. Den Hertog, P. B. Hulshof (2006), "Solving Rummikub Problems by Integer Linear Programming", The Computer Journal, 49(6) , 665-669 ( DOI 10.1093/comjnl/bxl033 ).

  • Can track multiple games, letting you switch between named games
  • Saves tracked games automatically
  • Can work with different Rummikub rules, letting you adjust the number of colours, tiles, and other aspects
  • You can freely adjust what tiles are on the rack or on the table, within the limits of what tiles are available according to the current rules

Solver improvements

The original models described by Den Hertog and Hulshof assume that all possible sets that meet the minimum length requirements and can't be split up are desirable outcomes.

However, any group set (tiles with the same number but with different colours) containing at least one joker, but which is longer than the minimal run, in effect contains a redundant joker, something you wouldn't want to leave on the table for the next player to use. The same applies to run sets (tiles of the same colour but with consecutive numbers), that are longer than the minimal set length but start or end with a joker. In this implementation, such sets are omitted from the possible options.

The implementation also includes a solver for the initial move, where you can only use tiles from your own rack and must place a minimum amount of points before you can use tiles already on the table. This solver is a variant of the original solver that maximizes tiles placed, but is constrained by the minimal point amount and disregards jokers (which means jokers are only used for the opening meld if that is the only option available).

You can install this project the usual way:

or use a tool like pipx to help you manage command-line tool installations like these:

Run the rsconsole command-line tool to open the console, or run rsconsole --help to see how you can adjust the Rummikub rules (you can adjust tile count, colours, joker count, the minimum number of tiles to make a set and the minimum score for the initial placement).

You then enter the console command loop. Enter ? or h or help to list the available commands, and help <command> to get help on what each command does.

Development

The source code for this project can be found on GitHub .

When running locally, install Pipenv , then run:

to run the console solver.

The initial version of the solver and console were written by Ollie Hooper .

This version is a complete rewrite by Martijn Pieters , with new console implementation, expansion of the solver to improve performance and address shortcomings in the original paper, as well as multi-game, game state tracking and persistence support.

Project details

Release history release notifications | rss feed.

Jan 4, 2024

Mar 13, 2023

Nov 8, 2022

Sep 13, 2022

Apr 9, 2021

Mar 26, 2021

Mar 25, 2021

Mar 22, 2021

Mar 20, 2021

1.0.0b3 pre-release

Mar 19, 2021

1.0.0b2 pre-release

1.0.0b1 pre-release

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages .

Source Distribution

Uploaded Jan 4, 2024 source

Built Distribution

Uploaded Jan 4, 2024 py2 py3

Hashes for RummikubConsole-1.2.5.tar.gz

Hashes for rummikubconsole-1.2.5-py2.py3-none-any.whl.

  • portuguรชs (Brasil)

Supported by

solving rummikub problems by integer linear programming

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

  • Notifications

Rummikub solver coded in Python that uses integer linear programming to maximise the number or value of tiles placed in the popular board game.

Ollie-Hooper/RummikubSolver

Folders and files.

  • Python 100.0%

Solving Rummikub Problems by Integer Linear Programming

Ieee account.

  • Change Username/Password
  • Update Address

Purchase Details

  • Payment Options
  • Order History
  • View Purchased Documents

Profile Information

  • Communications Preferences
  • Profession and Education
  • Technical Interests
  • US & Canada: +1 800 678 4333
  • Worldwide: +1 732 981 0060
  • Contact & Support
  • About IEEE Xplore
  • Accessibility
  • Terms of Use
  • Nondiscrimination Policy
  • Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

  • På svenska
  •   Etusivu
  • Åbo Akademi
  • Maisteri- ja lisensiaattitutkielmat sekä diplomityöt
  • Rajoitetun saatavuuden opinnäytetyöt
  • Näytä viite

Solving Rummikub with computational power

Gulin, magnus (2019).

solving rummikub problems by integer linear programming

Avaa tiedosto

Tiivistelmä.

  • Rajoitetun saatavuuden opinnäytetyöt [344]

Selaa kokoelmaa

Omat tiedot.

Library homepage

  • school Campus Bookshelves
  • menu_book Bookshelves
  • perm_media Learning Objects
  • login Login
  • how_to_reg Request Instructor Account
  • hub Instructor Commons
  • Download Page (PDF)
  • Download Full Book (PDF)
  • Periodic Table
  • Physics Constants
  • Scientific Calculator
  • Reference & Cite
  • Tools expand_more
  • Readability

selected template will load here

This action is not available.

Mathematics LibreTexts

13.6: Integer Solutions of Linear Programming Problems

  • Last updated
  • Save as PDF
  • Page ID 97954

  • Mitchel T. Keller & William T. Trotter
  • Georgia Tech & Morningside College

A linear programming problem is an optimization problem that can be stated in the following form: Find the maximum value of a linear function

\(c_1x_1+c_2x_2+c_3x_3+ \cdot \cdot \cdot +c_nx_n\)

subject to \(m\) constraints \(C_1\), \(C_2\),…,\(C_m\), where each constraint \(C_i\) is a linear equation of the form:

\(C_i\): \(a_{i1}x_1+a_{i2}x_2+a_{i3}x_3+ \cdot \cdot \cdot +a_{in}x_n=b_i\)

where all coefficients and constants are real numbers.

While the general subject of linear programming is far too broad for this course, we would be remiss if we didn't point out that:

  • Linear programming problems are a very important class of optimization problems and they have many applications in engineering, science, and industrial settings.
  • There are relatively efficient algorithms for finding solutions to linear programming problems.
  • A linear programming problem posed with rational coefficients and constants has an optimal solution with rational values—if it has an optimal solution at all.
  • A linear programming problem posed with integer coefficients and constants need not have an optimal solution with integer values—even when it has an optimal solution with rational values.
  • A very important theme in operations research is to determine when a linear programming problem posed in integers has an optimal solution with integer values. This is a subtle and often very difficult problem.
  • The problem of finding a maximum flow in a network is a special case of a linear programming problem.
  • A network flow problem in which all capacities are integers has a maximum flow in which the flow on every edge is an integer. The Ford-Fulkerson labeling algorithm guarantees this!
  • In general, linear programming algorithms are not used on networks. Instead, special purpose algorithms, such as Ford-Fulkerson, have proven to be more efficient in practice.

IMAGES

  1. solving rummikub problems by integer linear programming

    solving rummikub problems by integer linear programming

  2. solving rummikub problems by integer linear programming

    solving rummikub problems by integer linear programming

  3. solving rummikub problems by integer linear programming

    solving rummikub problems by integer linear programming

  4. solving rummikub problems by integer linear programming

    solving rummikub problems by integer linear programming

  5. solving rummikub problems by integer linear programming

    solving rummikub problems by integer linear programming

  6. How to Solve Integer Linear Programming in Excel (With Easy Steps)

    solving rummikub problems by integer linear programming

VIDEO

  1. Vid03 Problem formulation and Integer Linear Programming

  2. Linear Programming

  3. 4 1 to 4 13 linear programming

  4. Linear Programming Classic Problems 10

  5. Integer Linear programming/Module 2 part 1 /Optimization Techniques/MGU

  6. Linear programming 4 8 to 4 10

COMMENTS

  1. Solving Rummikub Problems by Integer Linear Programming

    Issue Section: Games 1. INTRODUCTION Computers have frequently been used to solve different kinds of puzzles or games. In many cases it appeared that the combination of computer power and efficient mathematical techniques is able to solve such problems. Wilson [ 1] used integer linear programming (ILP) for compiling crossword puzzles.

  2. PDF The Complexity of Rummikub Problems

    We first present an algorithm that solves this problem in polynomial time. Next, we analyze the impact on the computational complexity when we generalize over various input parameters.

  3. Solving Rummikub Problems by Integer Linear Programming

    Solving Rummikub Problems by Integer Linear Programming November 2006 Source DBLP Authors: Dick den Hertog Tilburg University P. B. Hulshof Abstract The Rummikub problem of finding the...

  4. Finding if a Valid Rummikub Solution exist from selected Tiles

    The most recent approach is ILP (integer linear programming). Basically, it means you define a function you wish to maximize, and put constraints on it. For instance: make a list of all unique tiles (53 in a standard game) make a list of all possible valid sets (1174) Define: yi = number of times tile i is chosen in optimal solution

  5. [1604.07553] The Complexity of Rummikub Problems

    The Rummikub puzzle as it is considered in this paper, has not been studied much. In an unsuccessful attempt was made to prove a generalized version of the Rummikub puzzle NP-complete. An integer linear programming method for solving the Rummikub puzzle is proposed in . There, it is stated that the optimization problem of obtaining as many ...

  6. Solving Rummikub problems by integer linear programming

    TY - JOUR. T1 - Solving Rummikub problems by integer linear programming. AU - den Hertog, D. AU - Hulshof, P.B. PY - 2006. Y1 - 2006. M3 - Article

  7. gregorias/rummikubsolver: A solver for the Rummikub board game

    Rummikub Solver uses integer linear programming to find the solution which maximizes the number of tiles placed on the table from the rack. You just need to provide the current description of the state of the game. Rummikub Solver will display possible sets that are achievable and tiles that may be placed to achieve them. Installation

  8. RummikubConsole ยท PyPI

    The algorithm used builds on the approach described by D. Den Hertog, P. B. Hulshof (2006), "Solving Rummikub Problems by Integer Linear Programming", The Computer Journal, 49 (6), 665-669 ( DOI 10.1093/comjnl/bxl033 ). Features Can track multiple games, letting you switch between named games Saves tracked games automatically

  9. [PDF] The Complexity of Rummikub Problems

    An algorithm is presented that solves the optimization problem of Rummikub to form valid sets such that the score of tile values is maximized in polynomial time and some aspects involved in human play are better understood. Expand [PDF] Semantic Reader Save to Library Create Alert Cite Figures and Tables from this paper figure 1 table 1 figure 2

  10. GitHub

    Code Rummikub solver coded in Python that uses integer linear programming to maximise the number or value of tiles placed in the popular board game. - GitHub - Ollie-Hooper/RummikubSolver: Rummikub solver coded in Python that uses integer linear programming to maximise the number or value of tiles placed in the popular board game.

  11. How to validate a Rummikub combination with Jokers

    I've built a Rummikub solver based on work by D. Den Hertog, P. B. Hulshof, described in their paper "Solving Rummikub Problems by Integer Linear Programming" ... This uses Mixed-Integer Linear Programming to find possible solutions given the tiles on the player's rack and the tiles in play on the board. If you leave the rack empty, the same ...

  12. Solving Rummikub Problems by Integer Linear Programming

    The Rummikub problem of finding the maximal number or value of the tiles that can be placed from your rack onto the table is very difficult, since the number of possible combinations are enormous. We show that this problem can be modeled as an integer linear programming problem. In this way solutions can be found in 1 s. We extend the model such that unnecessary changes of the existing sets on ...

  13. Solving Rummikub with computational power

    have been proposed for solving this game. The earliest is based on Integer linear programming, where a mathematical model for finding a solution to the game is presented. A later work proposes an algorithm based on heuristic guided state space search. In "The Complexity of Rummikub Problems", a polynomial algorithm is described.

  14. An introduction to mixed-integer linear programming: The knapsack problem

    Jul 1, 2022 Photo by Denisse Leon on Unsplash The knapsack problem is probably one of the first problems one faces when studying integer programming, optimization, or operations research. In this problem, from a given set of items, one must choose the most valuable combination to fit in a knapsack of a certain capacity (weight, volume, or both).

  15. PDF Integer Programming 9

    This problem is called the (linear) integer-programming problem. It is said to be a mixed integer program when some, but not all, variables are restricted to be integer, and is called a pure integer program when all ... Second, we consider basic approaches that have been developed for solving integer and mixed-integer programming problems. 9.1 ...

  16. (PDF) The Complexity of Rummikub Problems

    An integer linear programming method for solving the Rummikub puzzle is proposed in [3]. There, it is stated that the optimization problem of obtaining as many points in one move as possible is ...

  17. 13.6: Integer Solutions of Linear Programming Problems

    13: Network Flows Expand/collapse global location

  18. PDF Section 2.1

    To solve a linear programming problem, we first need to know the Fundamental Theorem of Linear Programming: Given that an optimal solution to a linear programming problem exists, it must occur at a vertex of the feasible set.

  19. Puzzle โ€”Solving the Battleship Puzzle as an Integer Programming Problem

    Abstract. One's aim in solving logical puzzles is to find the solution by making use of several clues and restrictions. In this paper, we solve a logical puzzle, the Battleship puzzle, by integer ...

  20. PDF Lecture 7 1 Linear Programming Relaxations

    In which we show how to use linear programming to approximate the vertex cover problem. 1 Linear Programming Relaxations An integer linear program (abbreviated ILP) is a linear program (abbreviated LP) with the additional constraints that the variables must take integer values. For ex-ample, the following is an ILP: maximize x 1 x 2 + 2x 3 ...

  21. Solving Rummikub Problems by Integer Linear Programming

    This paper solves a logical puzzle, the Battleship puzzle, by integer programming and shows that the ship-based model requires more preprocessing work before running the integer program than the cell- based model, but strongly outperforms the latter one. 16 PDF The Complexity of Rummikub Problems J. V. Rijn Frank W. Takes J. K. Vis

  22. Solving conservation planning problems with integer linear programming

    Fig. 1. Comparisons of processing times ( y -axis) and solution quality (text labels) between integer linear programming software (Gurobi; open symbols) and simulated annealing software (Marxan; solid symbols) over a range of problem sizes ( x -axis). Two problems were evaluated: a simple, linear reserve selection problem (a), and Marxan's ...

  23. What are some examples of problems well suited for Integer Linear

    Downvote: there a few issues with this answer. I would suggest using objective function instead of target function, which is the standard name. It's true that the objective function must be linear. The constraints must also be linear. It's also not strictly true that you can solve "any problem on your computer" with integer programming. -

  24. An Introduction to Air Travel Network Optimization Using Mixed Integer

    This is precisely the kind of problem that Mixed Integer Programs (MIP) are designed for! ... However, this would make the constraint non-linear and very complicated to solve. Instead, we can use Big-M again, this time to linearize the problem while getting the same effect: ... Solve Optimization Problems: Exploring Linear Programming with Python.