11
$\begingroup$

I have enjoyed playing a puzzle game called "Cats & Boxes" published by Smart Games.

Briefly, the way the game is played is:

  1. Place $5$ cat pieces and $4$ box pieces (one of which has $2$ boxes) onto a $5\times5$ grid. The game comes with $60$ initial puzzle setups, ranging in difficulty. The cats are always unboxed in each initial configuration.
  2. Move the box pieces one at a time until each cat is in a box. See the images below for an example setup and eventual solution.
  3. (An edit for clarity) The box pieces are rigid, each consisting of $1$ or $2$ boxes that may or may not be placed over a cat, as well as $3$ flat "carpet" squares. The carpet squares must be placed flat on the board and cannot go onto a cat or any part of another box piece. See this video that shows an example.

enter image description here

enter image description here

Some actions are specifically not allowed.

  • You may not move any of the cats.
  • You may not overlap any pieces, i.e. each box piece needs to be placed flat on the grid (whether or not it holds a cat) before moving another box piece. The cats are $3$ dimensional, so the only part of a box piece that can go on a cat square is a box itself.

The minimum number of moves required to solve a puzzle is $4$, since there are $4$ box pieces. The easiest puzzles in the game can be solved in $4$ moves.

Harder puzzles require more moves. The fun of the game comes from figuring out how exactly to move the pieces around until all the cats are boxed.

The puzzle booklet tells the minimum number of moves needed to solve each puzzle. Easy puzzles can be done in about $4$ to $7$ moves at a minimum. Mid-level puzzles take about $8$ to $13$ moves at a minimum. The "hardest" puzzle in the booklet is the last one, puzzle $60$. It takes a minimum of $33$ moves to complete, as indicated in the booklet.

enter image description here

$33$ moves seems to me like an outlier, when compared with the rest of the puzzles. The next highest is $26$ moves, and those are the only two puzzles requiring $>20$ moves.

I expect that computers were very much involved in coming up with initial puzzle configurations, and their optimal solutions. My own programming skills are not up to the task of writing code to answer my question.

I know that many initial configurations of cats are impossible to cover with the box pieces. One restriction comes from the piece with $2$ boxes that are a chess knight's move apart. So, having all $5$ cats in a single row, column, or diagonal will be impossible to cover. I know there are other restrictions due to the shapes of the box pieces.

My specific question is the one in the title. It could be that $33$ moves is the greatest minimum possible, but I'd like to know for sure!

$\endgroup$
11
  • $\begingroup$ Do the blue tiles move during a puzzle or are they fixed? Must the boxes stay on blue tiles unless they are trapping a cat? Are the cats always not on blue tiles? What are the rules for trapping cats in the double box? How does the double box move? $\endgroup$ Commented Nov 22, 2024 at 21:03
  • 1
    $\begingroup$ Sorry it wasn't clear. Each box piece is rigid. Each has 1 or 2 boxes, as well as 3 of what I'll call "carpet" squares. Their shapes are shown in the setup for puzzle 60. This video may also help: youtube.com/watch?v=rCmbVHndzhQ $\endgroup$ Commented Nov 22, 2024 at 21:10
  • 1
    $\begingroup$ I think the following algorithm should be viable: First ignore the cats and construct a graph of possible configurations of the box pieces (vertices) and moves (edges). Now for each $\binom{25}{5} \approx 50\,000 $ choice of cat positions, you have a set of valid vertices where the carpets do not hit the cats and a subset of marked vertices where the boxes are exactly on the cats, and you want to calculate the maximum distance between a pair of marked vertices that only go through valid vertices, which can be found by running a BFS starting at each marked vertex. $\endgroup$ Commented Nov 25, 2024 at 15:17
  • 2
    $\begingroup$ And a correction, you don't want the longest path between two marked vertices, you want $\max_{v \text{ valid}} \min_{w \text{ marked}} d(v, w)$ which can be found by running a BFS starting at each valid vertex $v$. $\endgroup$ Commented Nov 25, 2024 at 15:25
  • 1
    $\begingroup$ @DreiCleaner: I guess you might as well wait it out here. (Perhaps someone can flesh-out the algorithm more mathematically anyway.) If you don't get a satisfactory response, cross-post to StackOverflow, but be sure to include a description of the algorithm itself. ... In every incarnation of the question, I recommend moving all clarifications you've provided in comments (as well as the how-to-play video link) to the body of the question itself. Comments are easily overlooked and may be hidden. ... Good luck! $\endgroup$ Commented Dec 4, 2024 at 17:25

1 Answer 1

Reset to default
6
+100
$\begingroup$

Since the cats don't move, we can start there. There are ${{25}\choose{5}}=53130$ ways to place the cats on the board. Because the entire puzzle is invariant under rotations (though not reflections), we can treat cat placements related by a rotation as equivalent. This leaves us with $13302$ (equivalence classes of) cat placements. Call this set $\mathcal{C}$.

We can also enumerate all the legal ways to place the four box pieces on the board, such that they don't overlap each other. Call this set $\mathcal{P}$. I find $|\mathcal{P}|=8020$ (which is slightly fewer than the $8256$ implied by one of the comments).

Now, each cat placement $c \in \mathcal{C}$ is consistent with some subset of the legal placements of the four box pieces, $\mathcal{P}(c) \subseteq \mathcal{P}$. Among these placements (and contingent on $c$), some may be legal start states for a puzzle (because no cats are in boxes), and some may be legal end states (because all the cats are in boxes) -- call these sets $S(c)$ and $E(c)$, respectively. We can find $S(c)$ and $E(c)$ for each $c$, and then eliminate cat placements for which either set is empty. This leaves us with $556$ cat placements $c$ that might be used for solvable puzzles. The number of potentially solvable puzzles (again, modulo rotations of the cat placements) is $\sum_c |S(c)| = 3048$.

Finally, for each potentially solvable puzzle $\langle c, p_s \in S(c)\rangle$, we form an undirected graph whose nodes are $\mathcal{P}(c)$, and where there is an edge $\langle q, q' \rangle$ whenever box piece placements $q$ and $q'$ differ by exactly one box piece's location. (Note that these graphs are all subgraphs of a much larger graph whose nodes are all of $\mathcal{P}$.) We then find the minimum graph distance from $p_s$ to $E(c)$ in the usual way. (If no node in $E(c)$ is reachable from $p_s$, then in fact this puzzle is not solvable.)

Carrying out this procedure finds $1727$ solvable puzzles, with difficulty (= minimum path length) ranging from $4$ to $33$. A single puzzle has the maximum difficulty of $33$, and a single puzzle has the next-highest difficulty of $26$. There are only six puzzles with difficulty greater than $20$, so the choice to include only two of them may just have been a design preference.

Update:

Here is a link to a file containing all 1727 solvable puzzles. The first column is the initial layout (print the five strings in order to get an ASCII representation -- '#' is a cat, and the four box pieces are 'A' through 'D'); the second column is the difficulty; and the third column lists the shortest distances to all reachable end states from the given start state. In particular, the first entry in the file, which corresponds to the most difficult puzzle, is:

('#BbB-', '-D#B#', 'DdaA-', '#DCAa', 'CCcA#') 33 [33]

So the ASCII representation of the puzzle's initial layout is:

#BbB- -D#B# DdaA- #DCAa CCcA#

This corresponds exactly to the card image posted in the question.

$\endgroup$
5
  • 1
    $\begingroup$ Thank you for this! What did you use to carry out the procedure? Are you able to provide the $1727$ solvable puzzles you found (in some format)? I agree that not including too many puzzles with difficulty $>20$ was probably a design preference. $\endgroup$ Commented Dec 9, 2024 at 15:55
  • $\begingroup$ Thanks again for providing the puzzles. They'll keep me busy for a while! $\endgroup$ Commented Dec 10, 2024 at 14:07
  • $\begingroup$ in your list of puzzles, some of them have multiple values in brackets. For example the 16th puzzle from the top says [17, 20, 32, 32]. So, 17 is the shortest among these, but what is the meaning of the others? That there are other finish states (cats in different boxes) that take longer? I scrolled through and noticed some puzzles have up to 30 different numbers in brackets. $\endgroup$ Commented Dec 10, 2024 at 19:38
  • 1
    $\begingroup$ Yes, exactly ... there are other finish states (a cat in a different box, or in the same box with the piece rotated around it) reachable from the same starting state, and these take at least as many moves to reach as the listed difficulty. $\endgroup$ Commented Dec 10, 2024 at 21:24
  • 2
    $\begingroup$ I gave up trying to track down errors in my magma script and rewrote it, using a different way of representing the pieces' positions. The rewritten script finds only $2005$ inequivalent ways of fitting the box pieces onto the board, thus now agreeing with your $\ |\mathcal{P}|=8020\ .$ $\endgroup$ Commented Dec 11, 2024 at 6:21

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.