Rummikub Solver library

Fast and flexible Rummikub solver library, written in Python, to find the best options for placing tiles from a player's rack on to the table.

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 work with different Rummikub variations, 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
Can be used with any of the Mixed-Integer Linear Programming (MILP) solvers supported by cvxpy.

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).

Installation

rummikub_solver is a Python package, so you can install it with your favorite Python package installer or dependency manager.

pip uv

$ pip install rummikub_solver

pip is the main package installer for Python.

$ uv add rummikub_solver

uv is an extremely fast Python package and project manager, written in Rust.

Picking an alternative solver backend

This library builds on cvxpy to define the Rummikub models, which can then be solved using any of the supported MILP solver backends. By default, the SCIPY backend is used, which in turn uses a version of the HiGHS optimizer that comes bundled with SciPy.

You can also install an alternative Open Source solver backends via extras:

Extra	Backend	License
`cbc`	COIN-OR Branch-and-Cut solver	EPL-2.0
`glpk_mi`	GNU Linear Programming Kit	GPL-3.0-only	Installs the cvxopt project
`highs`	HiGHS	MIT	Arguably the best OSS MILP solver available. This installs a newer version of HiGHS than what is bundled with SciPy.
`scip`	SCIP	Apache-2.0

You can also pick from a number of commercial solvers; no extras are provided for these:

COPT: Cardinal Optimizer, https://github.com/COPT-Public/COPT-Release
CPLEX: IBM CPLEX, https://www.ibm.com/docs/en/icos
GUROBI: Gurobi Optimizer, https://www.gurobi.com/
MOSEK: https://www.mosek.com/
XPRESS: Fico XPress,, https://www.fico.com/en/products/fico-xpress-optimization

Refer to their respective documentations for installation instructions.

When HiGHS is installed, it is automatically used as the default solver.

E.g. to include the HiGHS solver in your project, use:

pip uv

$ pip install rummikub_solver[highs]

$ uv add rummikub_solver[highs]

Pass in a specific MILPSolver member when constructing your RuleSet to specify what backend to use.

Warning

This project is not being tested against the proprietary solver backends; they are included purely for completion's sake. Pull requests to address problems for specific proprietary backends are welcome, however.

Comparing backends

You can compare how well different backends perform by running the test_full_game test in the project test suite, provided you enable pytest live logging:

Clone this project from GitHub¹.
Use the following command to run the specific test:
```
$ uv run \
  --extra BACKEND_EXTRA ... \
  --with OTHER_PYTHON_PACKAGE ... \
  pytest --log-cli-level INFO --no-cov \
    --solver-backend BACKEND ... \
    tests/test_full_game.py
```
with as many --extra BACKEND_EXTRA and / or --with OTHER_PYTHON_PACKAGE switches as needed to install the desired backends (e.g. --extra highs would install the HIGHS backend into the uv-managed environment), and with a --solver-backend BACKEND line for each MILPSolver member you want to compare.

The test simulates a full rummikub game between 3 players, playing the game through from start to finish. It measures the performance of the solver at each step and then outputs some statistics about that performance at the end. In a single run of the test, all backends start with the same random seed, making the performance of each solver directly comparable.

Note

A few rounds difference between solvers is to be expected as the failure of a solver to find a better solution may allow a different player to win earlier.

E.g. comparing the GLPK_MI, HIGHS, SCIP and SCIPY backends looks like this:

$ uv run \
   --extra glpk_mi --extra highs --extra scip --extra cbc \
   pytest --log-cli-level INFO --no-cov \
     --solver-backend GLPK_MI --solver-backend HIGHS \
     --solver-backend SCIP --solver-backend SCIPY \
     --solver-backend CBC \
     tests/test_full_game.py
============================= test session starts ==============================
platform darwin -- Python 3.12.6, pytest-8.4.1, pluggy-1.6.0
Using --randomly-seed=1121915624
selected solver backends: CBC, GLPK_MI, HIGHS, SCIP, SCIPY
rootdir: /Users/martijn.pieters/Development/oss/rummikub_solver
configfile: pyproject.toml
plugins: randomly-3.16.0, cov-6.2.1, hypothesis-6.135.14
collected 5 items                                                              

tests/test_full_game.py::test_full_game[SCIPY] 
-------------------------------- live log call ---------------------------------
INFO     root:test_full_game.py:119 After 16 rounds, player 3 won the game
INFO     root:test_full_game.py:127 SCIPY solving stats across 35 calls:
  Time (mean ± δ):      16.6 ms ±   9.5 ms
  Range (min … max):     7.7 ms …  51.8 ms)
PASSED                                                                   [ 20%]
tests/test_full_game.py::test_full_game[GLPK_MI] 
-------------------------------- live log call ---------------------------------
INFO     root:test_full_game.py:119 After 16 rounds, player 3 won the game
INFO     root:test_full_game.py:127 GLPK_MI solving stats across 36 calls:
  Time (mean ± δ):       2.8 ms ±   1.4 ms
  Range (min … max):     1.2 ms …   6.3 ms)
PASSED                                                                   [ 40%]
tests/test_full_game.py::test_full_game[HIGHS] 
-------------------------------- live log call ---------------------------------
INFO     root:test_full_game.py:119 After 17 rounds, player 2 won the game
INFO     root:test_full_game.py:127 HIGHS solving stats across 37 calls:
  Time (mean ± δ):      12.0 ms ±   8.2 ms
  Range (min … max):     2.2 ms …  29.4 ms)
PASSED                                                                   [ 60%]
tests/test_full_game.py::test_full_game[CBC] 
-------------------------------- live log call ---------------------------------
INFO     root:test_full_game.py:119 After 10 rounds, player 3 won the game
INFO     root:test_full_game.py:127 CBC solving stats across 17 calls:
  Time (mean ± δ):       8.6 ms ±   4.5 ms
  Range (min … max):     5.6 ms …  21.1 ms)
PASSED                                                                   [ 80%]
tests/test_full_game.py::test_full_game[SCIP] 
-------------------------------- live log call ---------------------------------
INFO     root:test_full_game.py:119 After 17 rounds, player 1 won the game
INFO     root:test_full_game.py:127 SCIP solving stats across 37 calls:
  Time (mean ± δ):      40.6 ms ±  18.0 ms
  Range (min … max):    18.5 ms …  98.0 ms)
PASSED                                                                   [100%]
============================== 5 passed in 2.59s ===============================

Info

The timings shown are the mean, standard deviation, min and max duration of each call to ruleset.solve() except for those calls when the player has yet to complete their first move (initial is True). Initial moves are excluded because these require at least double the number of calls to the backend solver and so would unfairly skew the results.

The relative performance of each of the backends can readily change from one release to the next, so any conclusions from the above example should be re-reviewed if performance is important to you. As of the initial release of rummikub_solver, GLPK_MI is the faster solver, but will not always find the best solution when optimising for total value placed. HIGHS is a close second in performance, but will do a better job at maximizing the total value of tiles.

see Cloning a repository for the GitHub help documentation on cloning. ↩