Category Archives: Games’n’Puzzles

Box Shift Puzzle

Posted on by
Reply

While thinking about simple “puzzles” that seem hard at a first glance, but have not enough rules and structural constraints that make it easy to prove that they are NP-complete, I designed the following game (but perhaps it has already a name … let me know if you know it 🙂 ):

  • a $N \times N$ grid contains $S \times S$ blue boxes in the upper left area, the home area; each box occupies a cell;
  • a column (or row) that contains at least one box is picked at random and it is shifted downward (or rightward). If a box exits from one border it re-enters on the opposite site;
  • the random shift is repeated maxmoves times (e.g. $maxmoves = S^2$);
  • the aim of the game is to repack the boxes in the upper left home area, using at most maxmoves upward column shifts or leftward row shifts.

A simple javascript version of the game can be played here.

Can the blue boxes be packed in the upper-left 4×4 yellow area using at most 16 moves?

The rules are simple, but even in a small game with a 4×4 home area it’s hard to find the correct shift sequence …

Continue reading →

Subway Shuffle is PSPACE-complete

Posted on by
Reply

Abstract: Subway shuffle is an addicting puzzle game created by Bob Hearn. It is played on a graph with colored edges that represent subway lines; colored tokens that represent subway cars are placed on the nodes of the graph. A token can be moved from its current node to an empty one, but only if the two nodes are connected with an edge of the same color of the token. The aim of the game is to move a special token to its final target position. We prove that deciding if the game has a solution is PSPACE-complete even when the game graph is planar.

Subway Shuffle Level 14

Continue reading →

IcoSoKu solver

Posted on by
38

margin-left: 30px;

Faces example

I wrote a simple javascript IcoSoKu solver. You can enter the configuration of the 12 yellow pins in the text boxes and click “Solve IcoSoKu” to calculate the solution. For example if you have the yellow pin 5 on vertex A (the top vertex), you must type 5 in the Pin A text box. The faces are identified with their three yellow pins (see a small example on the right).

The 20 white tiles are identified with their black dots; for example (2,2,0) represents the tile with two black dots in the first and second corner and zero dots on the third.If the solution says put tile (1,2,3) on face [11,12,7], then you must put the white tile on the bottom-left face, and rotate it until 1 black dot is on yellow pin 11, 2 black dots are on yellow pin 12 and 3 black dots are on yellow pin 7. You can also generate a random yellow pins configuration clicking “Random IcoSoKu”.

Continue reading →