7
$\begingroup$

I'm implementing a Douglas Engel's puzzle, Color Wheels (reproduced with permission) and now I would like to check solutions of users.

For those of you that don't know the puzzle, here you can see that it consists of two intersecting wheels with three common pieces. The wheels can rotate so there is an interchange of pieces. As you can imagine, after mixing the pieces, the objective is to rearrange to original position, pretty much the same as in Rubik's Cube.

Picture from Douglas Engel page

I have two problems:

  1. I am mixing the pieces with 90 alternative random movements (45 each wheel). But, is there any state beyond that? I mean, is any valid state reachable with these 90 movements?

  2. I want to give 3 stars to those who solve the puzzle with optimal solution. I've mixed pieces randomly so I don't know the optimal (and solving the puzzle with javascript would require an algorithm and an implementation of it). What I would like is to know if there is a "God number" for this puzzle, a minimum number of steps to solve any configuration (like in Rubik's Cube)*.

(Please note that my implementation takes into account the orientation of pieces, but the original puzzle "Color Wheels" doesn't. By now, I am interested in the version without orientations, like in the image above).

*This means that sometimes I will give 3 stars to solutions that are not truly optimal, but that's ok.

$\endgroup$
8
  • $\begingroup$ Off hand, I'd suggest randomly varying the choice of 90 times, if for no other reason than 90 is a multiple of the primes I see in the layout: 2, 3 and 5. Nice puzzle, by the way, and well implemented already with intuitive controls. $\endgroup$
    – humn
    Mar 15, 2016 at 12:58
  • 1
    $\begingroup$ I selected 90 randomly, so I can change it and make it dynamic. Thanks for the suggestion, I'm glad you like it! $\endgroup$
    – Edgar G.
    Mar 15, 2016 at 13:03
  • $\begingroup$ If I get it right, your state space size is at most N! (where N is the number of pieces), because that's how many ordered assignments you can get. If your N is small enough (say around 10) you should be able to do a BFS graph exploration from your scrambled configuration in a short-ish time to compute the minimum number of moves for any configuration. $\endgroup$ Mar 15, 2016 at 15:32
  • $\begingroup$ Yes it could be implemented an algorithm to check optimal, but I would have to check it again at server side (to avoid cheating), and that's too time consuming. I would prefer simply compare against an optimal solution length. $\endgroup$
    – Edgar G.
    Mar 15, 2016 at 17:22
  • 1
    $\begingroup$ It reminds me a lot of the Kangoeroe Puzzler, and is actually equivalent to the 'Puzzler - Advenger' by mr. Engel as well. A solution of it can be found on Jaapsch' Puzzle Page. Jaapsch Puzzle Pages usually also include God's numbers and number of possible configurations, so perhaps it might be of use to you. $\endgroup$ Mar 16, 2016 at 13:09

1 Answer 1

6
$\begingroup$

As you say, you are implementing a type of Douglas Engel's puzzle, an "Enigma". Given the colour set and the fact that you are ignoring the orientation of the triangular wedges ("corners" in twisty puzzle lingo) in your implementation makes it a either a "Turnstile" or "Avenger" (I believe one with orientations is called a "Puzzler"). Since, in your implementation, the colours must be placed in triples separated by uncoloured edges, with one triple in the intersection, but the permutation of the triples amongst these locations is not a constraint makes it an Avenger.

In any of these three cases there are $21$ placeable pieces: $11$ edges - $6$ of no colour, and then $1$ of each of $5$ colours; and $10$ corners - $2$ of each of the same $5$ colours.

During a solve the state may be changed by turning either the left wheel or the right wheel in increments of $\frac16$ of a rotation. If we measure any amount of consecutive $\frac16$ turns of the same wheel as a single move (like the Rubik's cube's "Half Turn Metric") then after we have turned one wheel the next move may only be the other wheel (otherwise we could concatenate it with our previous move). A full turn of either wheel would be the identity, not changing the state, so there are 5 ways we can change the state at any move; and before any move is made there is the choice of with which wheel to start.

A sequence of such moves may then be written out in a similar fashion to Singmaster notation as a string of symbols of the form: W[n][']. For example L3 would represent turning the left wheel $\frac36$, or R2' would represent turning the right wheel $\frac26$ anti-clockwise. We may leave out the 1 when n is 1 for brevity (we could leave 1 in and leave out W for all but the first turn, but for ease of reading I have not done so). Thus the set of symbols is {L, R, L', R', L2, R2, L2', R2', L3, R3}.

Some sequences produce the same permutation as others of the same length or less - for an Avenger this happens for the first turn, since the order of the colours is disregarded; but for a turnstile it first occurs at a move depth of $4$ (e.g. L2' R2 L2 R2 = R2' L2' R2' L2), so we cannot use the count of possible sequences to yield God's number, however we can use it to put a lower bound on God's number. With $0$ turns only a single sequence (doing nothing) is possible, with exactly $1$ turn there are $2*5=10$ sequences, with exactly $2$ turns there are $2*5^2=50$ and so on. With up to $N$ turns there are $S(N)=1+2\times\sum_{i=1}^N{5^i}$ sequences.

What about the total possible states? Putting the puzzle together, starting with the coloured edges, there are $11$ places we could place the first coloured edge, then $10$ we could place the second and so on until we have placed all $5$. After that's been done, whichever way we place the $6$ uncoloured edges makes no difference. There are thus $11*10*9*8*7=55,440$ ways to place the edges ($\frac{11!}{6!}$).

Moving on to place the corners there are $10$ places we could place the first corner and $9$ we could place the second, etc. However, swapping $2$ corners of the same colour makes no difference to the state and there are $5$ different colours for which this is possible, so there are $\frac{10!}{2^5} = 113,400$ ways to place the corners.

Since, disregarding specific locations of uncoloured edges, we can:

  • swap two coloured edges independently - e.g. L3 R L3 R2 L3 R3 L' R L' R2 L' R3; and
  • swap two corners independently - e.g. R3 L' R' L2 R' L' R L' R L R3

there are $\frac{11!\times10!}{2^5\times6!}=6,286,896,000$ states.

The Turnstile then has $1$ state that is the solved state.
The Avenger has $5!=120$ solved states (As there are $5!$ ways to permute $5$ colours).

Since $S(13)<\frac{11!\times10!}{2^5\times6!}<S(14)$ we know God's number for the Turnstile is at least $14$.

Since $S(10)<\frac{11!\times10!}{2^5\times6!\times5!}<S(11)$ we know God's number for the Avenger is at least $11$.

As per Kevin Cruijssen's comment Jaap Scherphuis has a page dedicated to this puzzle where he shows results from brute-forcing God's number for two simpler versions - "Novice" and "Challenger", both having a God's number of $13$, so the Avenger will almost certainly have a God's number of at least $13$ too.

Maybe someone will post a group theory based proof or solver, but until then I have created a brute-force solver which finds optimal solutions. It works by brute-forcing and cacheing state-sequence pairs up to some move length from the goal state, then when presented with a scramble it first looks to see if its cache contains that state, and if not it starts brute-forcing another set of state-sequence pairs this time starting at the provided scramble rather than the completed state (up to some maximal depth) when this yields a state that is in its cache it then prefixes the cached sequence with this on demand sequence, which is an optimal solution for the scramble (since all reachable states in the cache are paired with optimal solutions and the solver is completing the on demand search at depth n prior to considering any at depth n+1). Code for this is here.

I have found many Turnstile scrambles that require $16$ moves
Plus some that require $17$ moves, such as these:

enter image description here
Turnstile solve: R' L2 R2 L' R2' L R' L2 R3 L3 R L3 R' L2' R' L2' R (17)
Avenger solve: L R' L' R' L3 R2' L R2 L3 R2 L2 R2 L R (14)


enter image description here
Turnstile solve: R L2 R2 L' R L' R' L3 R' L2 R2' L R L2 R2 L R2' (17)
Avenger solve: R L2 R3 L R2' L2' R2' L2' R3 L3 R2' L (12)


enter image description here
Turnstile solve: L2 R2 L R L' R L2' R2' L2 R2' L' R3 L R2 L2 R3 L3 (17)
Avenger solve: R L3 R L R3 L R' L R3 L' R' L3 R L (14)


(I changed the colours of Jaap's applet to be in line with your goal state picture.)

Creating an AvengerSolver with $15$ or more moves cached finds all $\frac{11!\times10!}{2^5\times6!\times5!}=52,390,800$ states (and the entries for $16$ or more moves have no state-sequence pairs).

So, God's number for the Avenger is $15$.

The break down of Avenger states by optimal solution length is:

Avenger solution lengths

Creating a solver (and persisting the cache to disk) with 15 cached moves took 65 minutes for me and used 13.8GB RAM* (2.6GB when persisted to disk), however a solver with 8 cached moves and 7 on demand moves works quickly (sub-second solves), only takes 3 seconds to initialise with file creation and only uses 55MB of RAM (7.8MB persisted to disk, allowing for sub-second start up).

* I am using a 64-bit system, it will use considerably less on a 32 bit system.

I made some attempts to reduce memory footprint by compressing states to integers representing the permutation (rather than a length 21 tuple of integers as it uses now) which should have saved almost 80% of the memory, but so far, for the methods I've implemented, the cost in terms of calculation time are too great and they only seem to save about 50%; furthermore an implementation in a statically typed language could certainly be made more lightweight.

So far I have not seen a Turnstile that requires $18$ wheel turns, but there could only be one, so I would not rule out $18$ for God's number for a Turnstile, but I think $19$ or more is unlikely.

So, to directly answer your other specific question, $90$ random turns of alternating wheels will certainly cover the space for an Avenger and almost certainly will for a Turnstile (and probably for a Puzzler too), however it is unnecessary to worry about that since an alternative approach would be to put the puzzle together as I described. Another way is to do what I did in my code, in Turnstile.scramble(), and simply shuffle the edges and shuffle the corners - since every permutation thereof is a solvable state (at least for the Avenger or Turnstile).

You could also retry if you happen to scramble to a state that you know is solvable in less than some number of turns (i.e. is considered too easy).


Since it wont fit here I have made my Python code for brute force evaluation available on github.

$\endgroup$
5
  • $\begingroup$ First of all, wow! Great amount of info! I've replicated jaap's values for novice version also and tried to brute force Avenger as well. I think I would need to leave alone my laptop two days calculating (or I would need to optimize my algorithm). Thanks for your answer. I'm gonna look at your code :) I'm surprised to see that Python can solve such problems (13GB is quite respectable). I'll change my scramble function then. $\endgroup$
    – Edgar G.
    Apr 4, 2016 at 14:31
  • $\begingroup$ The code should be well documented by the docstrings, let me know if anything doesn't make sense. As for the memory footprint - each of the tuples representing a state is 192 bytes, plus the dict overhead for O(1) time lookups all adds up - this could be much lower I'm sure. $\endgroup$ Apr 4, 2016 at 18:58
  • $\begingroup$ I've quickly looked over but I have to dive in the code to understand what is the algorithm doing. I was trying bruteforce: breadth-first search. My performance problem, I think, is it revisits each state too many times. I'm not so concerned with memory performance as with speed or algorithm performance, which I think yours is truly superior to BFS. I'm glad you posted the code! (I don't speak python but I think it's not a problem.) $\endgroup$
    – Edgar G.
    Apr 5, 2016 at 7:18
  • $\begingroup$ It is a BFS - the root is a state; children are states yielded by making a turn of the other wheel (to the last turned). It visits every state and checks if it has already been found at the same or lower depth (the state-path pairs are in dictionaries, 1 per depth). The path is an integer which may be parsed to produce an instruction [boolean(isFirstWheelLeft), list(nClockwiseSixtys for move in moves)]. The path from the cache must be inverted when appended to the end of an onDemand path (since the cache's root is a solved state whereas the onDemand's root is the scrambled state). $\endgroup$ Apr 6, 2016 at 0:15
  • $\begingroup$ (...and the first depth after the 0 move depth has both wheel turns) $\endgroup$ Apr 6, 2016 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.