C[omp]ute

From: andrew cooke <andrew@...>

Date: Thu, 12 Jan 2023 16:48:36 -0300

I have been working on a solver for Rummikub, but I haven't actually
made much progress.  This email is to note down some of my ideas and
related issues.

The underlying insight is that this is a graph colouring problem.  The
nodes of the graph are the known tiles.  Edges connect any two tiles
that can appear "next to each other" in a group.  The colouring
identifies each group (a successful colouring meets the appropriate
rules).

There may be an efficiency gain in using the previous colouring as a
starting point when searching for a new one.

This is fine as far as it goes.  It becomes more problematic when you
include jokers.

A naive first approach is to include the jokers as additional nodes.
The problem is that these are connected to *every* other node.  This
complicates hugely the search process when trying t find a colouring.

In practice, when you play, you tend to separate things into two
stages: first, liberating a joker and second, using that joker.

Using this approach the joker tiles become "normal" tiles in the graph
(ie take their assumed values) when searching for liberation.  Then,
in the next step, thereare many possible graphs (one for each possible
value of the joker).

I currently don't see how to handle this explosion in the number of
graphs.

So I'm stuck. It seems like the colouring view doesn't reduce the
combinatorial complexity sufficiently.  Or doesn't allow for the
complexity to be reduced using a "natural" compromise.

Andrew