I blogged about my old Java Applet for the chess minimum attack (dominance) puzzle previously here.
I’ve been writing some code (in Java) to solve this fun puzzle. I’ve played the puzzle for many years – it’s part of the excellent and free Simon Tatham’s Portable Puzzle Collection which has been available on many platforms for ages and has recently been ported to Android too. Untangle was inspired by Planarity, written by John Tantalo.
My first effort modelled the puzzle as a physical system. The links between points are elastic bands, where the attractive force is proportional to the cube of their length. The points have an electric charge which produces a repulsive force between all points in line with Coulomb’s inverse square law. The whole thing is submerged in a viscous fluid so that things don’t move too fast.
It solves many puzzles just using those rules but sometimes, especially with puzzles with a large number of vertices, it gets stuck in ‘a knot’ or takes too long to stabilize. Also, if it happens to ‘choose’ an outer face with a large number of vertices, then some inner vertices can be pushed out by the repulsive force so that they cross the ‘perimeter line’.
I’m now working on a faster and guaranteed-to-work algorithm – though it may not be as interesting to watch in action. Stay tuned for an update…
Above is a snapshot image. Here’s the real thing.
It works for any size of cube from 2 x 2 x 2 up to 11 x 11 x 11. Actually, 11 is an arbitrary limit – the same code would work for any size of cube. Use the little + and – buttons up in the top left hand corner to select the size of the cube.
Turning a face or slicing a layer is pretty intuitive – just click somewhere on the cube, hold down the mouse button and drag.
Turning the whole cube around is the same but you have to double-click, hold the mouse button down on the second click and then drag.
There’s a bug in the turning of the whole cube which causes the orientation to jump occasionally. I think I can fix it by using quaternions to do the whole-cube rotation, but with the demise of Flash I’m thinking this would be a good project to migrate to HTML5 – and then I could patch in the quaternion stuff at the same time.
You can also use the keyboard to turn layers (there’s a sort of agreed way of doing this among speed-cubers, and the simulation mostly uses the agreed keys),
Place five queens on a chess board so that every square on the board is attacked. It’s an old and famous problem; there are lots of solutions and it’s pretty easy to find one. Try it for yourself and see!
Now try using just three queens and two rooks. Not so easy this time; the solution is unique if you ignore trivial rotations and reflections of the whole board. What about other attacking forces? Four queens and two pawns maybe?
The image above is a snapshot of my solver. Click here to go to the solver itself. I wrote it over ten years ago when Java applets were flavor of the month. Most modern computers and tablets don’t have Java available by default and most tablets won’t let you install Java at all; you can still install Java as a free plug-in in most PC browsers though.