Spot Colour Puzzle

By: on December 19, 2018

I failed to solve the Spot Colour Puzzle at a recent team-building event. Time to revisit state space search and have some fun with Elixir.

The puzzle consists of seven discs, each of which has six coloured spots.

One disc is to be placed at the center and the remaining six discs have to be arranged around it so that opposing spots have matching colours. The solution to the example set of discs is as follows:

State space search is an appropriate technique for solving such puzzles by computer. State space search systematically examines different states of a problem until a target state is found or the state space is exhausted. Each state may lead to zero or more successor states through the application of problem-specific actions.

For the Spot Colour Puzzle, the target state is one where all seven discs have been placed and the colour matching constraints are satisfied. The constraints are illustrated below:

The initial state is one where none of the discs have been placed yet. In the initial state, there are seven unused discs and each one can be placed in the centre (action), leading to seven distinct successor states. Further successor states are generated by placing an unused disc into the next satellite position, but only if the relevant colour matching constraints are satisfied by the disc in question.

The remainder of this text will describe how the Spot Colour Puzzle can be solved in Elixir.

defmodule Discs do

A disc is represented as a tuple comprising an id and a colour sequence. The sequence is obtained by enumerating the disc’s colours in a clockwise manner. As discs can be rotated, it does not matter which particular spot the sequence starts with. Our example set of discs is represented as follows:

  @discs [
    {:d1, 
     [:blue, :yellow, :red, :white, :black, :green]},
    {:d2, 
     [:yellow, :red, :white, :green, :black, :blue]},
    {:d3, 
     [:white, :blue, :green, :red, :black, :yellow]},
    {:d4, 
     [:white, :red, :green, :yellow, :black, :blue]},
    {:d5, 
     [:black, :white, :green, :yellow, :blue, :red]},
    {:d6, 
     [:black, :red, :white, :blue, :yellow, :green]},
    {:d7, 
     [:red, :white, :blue, :black, :yellow, :green]}
  ]

Solving the puzzle means generating the seven centre disc states from @discs and then calling the state space search procedure with those seven states as the initial agenda (to-do list).

  def solve() do
    @discs
    |> initialize_agenda()
    |> search()
  end

Each state in the agenda is a four-tuple comprising:

  1. the centre disc
  2. the remainder of the centre disc’s colour sequence to which no satellites are attached yet — initially this is the full colour sequence.
  3. the sequence of satellite discs attached to the centre, initially empty. Here, each satellite disc is represented as a four-tuple comprising:
    • the target colour, i.e. the colour of the centre disc’s spot that the satellite disc is attached to
    • the id of the satellite disc
    • l, the colour preceding (left of) the target colour in the satellite’s colour sequence
    • r, the colour following (right of) the target colour in the satellite’s colour sequence

    The colours l and r are needed for checking the constraints between the satellite discs.

  4. the remaining, unattached discs — initially a list of six.
  def initialize_agenda(discs), do:
    Enum.map(
      discs,
      fn {_, colour_seq} = centre_disc ->
        {centre_disc, 
         colour_seq, 
         [], 
         List.delete(discs, centre_disc)}
      end
    )

The search will terminate unsuccessfully if the agenda becomes empty:

defp search([]), do: :no_solution

While the agenda is non-empty, the search procedure removes the first state from the agenda and examines it. If the state is a solution (i.e. the target state), the search has been successful and the target state is returned as the result. Otherwise, the successor states are generated, added to the agenda, and the search continues.

  defp search([state | more_states]) do
    if is_solution(state) do
      state
    else
      agenda = successors(state, more_states)
      search(agenda)
    end
  end

A state is the target state if the constraints are satisfied; this corresponds closely to the constraint illustration shown earlier.

  defp is_solution({{_, [c1, c2, c3, c4, c5, c6]}, [], 
                  [ {c6, _, l1, l2},
                    {c5, _, l2, l3},
                    {c4, _, l3, l4},
                    {c3, _, l4, l5},
                    {c2, _, l5, l6},
                    {c1, _, l6, l1} ], []}), do: true

  defp is_solution(_), do: false

The successors of a non-target state are generated by trying to attach each of the uncommitted satellite discs to the next spot of the centre disc.

  defp successors({centre_disk, 
                   [next_colour | remaining_colours], 
                   committed, 
                   uncommitted}, agenda) do
    uncommitted
    |> Enum.flat_map(
         fn candidate_disc -> 
           maybe_attach(next_colour, 
                        committed, 
                        candidate_disc) 
         end
       )
    |> Enum.map(
         fn {_, chosen_disc_id, _, _} = chosen_disc -> 
           {centre_disk,
            remaining_colours,
            [chosen_disc | committed],
            remove(uncommitted, chosen_disc_id)} 
         end
       )
    |> Enum.into(agenda)
  end

  defp successors(_, agenda), do: agenda

  defp remove(uncommitted, disc_id), do: 
    Enum.filter(uncommitted, 
      fn {n, _} -> n != disc_id end
    )

The very first satellite can always be attached.

  defp maybe_attach(target_colour, 
                    [], 
                    {disc_id, colour_seq}) do
    {l, r} = neighbours(target_colour, colour_seq)
    [{target_colour, disc_id, l, r}]
  end

Each subsequent satellite can only be attached if its r-colour matches the previous satellite’s l-colour.

  defp maybe_attach(target_colour, 
                    [{_, _, left, _} | _], 
                    {disc_id, colour_seq}) do
    {l, r} = neighbours(target_colour, colour_seq)
    if left == r do
      [{target_colour, disc_id, l, r}]
    else
      []
    end
  end

  defp neighbours(col, [col, r, _, _, _, l]), do: {l, r}
  defp neighbours(col, [l, col, r, _, _, _]), do: {l, r}
  defp neighbours(col, [_, l, col, r, _, _]), do: {l, r}
  defp neighbours(col, [_, _, l, col, r, _]), do: {l, r}
  defp neighbours(col, [_, _, _, l, col, r]), do: {l, r}
  defp neighbours(col, [r, _, _, _, l, col]), do: {l, r}

end

Running the program yields the solution shown earlier:

iex(1)> Discs.solve()
{{:d2, [:yellow, :red, :white, :green, :black, :blue]}, [],
 [
   {:blue, :d1, :green, :yellow},
   {:black, :d4, :yellow, :blue},
   {:green, :d3, :blue, :red},
   {:white, :d6, :red, :blue},
   {:red, :d5, :blue, :black},
   {:yellow, :d7, :black, :green}
 ], []}

Now, here is a picture I took of the puzzle we had on our table at the team-building event.

This instance of the Spot Colour Puzzle can be represented as follows:

  @discs [
    {:d1, 
     [:black, :red, :white, :blue, :yellow, :green]},
    {:d2, 
     [:green, :blue, :yellow, :red, :white, :black]},
    {:d3, 
     [:red, :white, :blue, :black, :yellow, :green]},
    {:d4, 
     [:black, :yellow, :white, :blue, :green, :red]},
    {:d5, 
     [:blue, :green, :red, :black, :yellow, :white]},
    {:d6, 
     [:white, :green, :black, :blue, :yellow, :red]},
    {:d7, 
     [:black, :yellow, :green, :red, :white, :blue]}
  ]

And the result of the search is:

:no_solution

It seems likely that the discs from at least two puzzles got mixed up during a previous event. The spell is broken and I can finally let go.

Share

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*