Solution to: Cat & Mouse
White can always win if it employs a good strategy (which was not the case in the game you just played in the puzzle). You can experience this yourself by playing the game against the computer here (click on the square where you want to move the black piece).
Below is an explanation. There are three possible outcomes:
- Yes, the game is computable and white can always win.
- Yes, the game is computable and black can always win.
- No, the game is not computable.
We first define Wwhite(game situation) and Wblack(game situation) which indicate whether a player has won in a certain game situation:
- Wwhite(game situation) holds if and only if white has won in the game situation (meaning black is completely blocked).
- Wblack(game situation) holds if and only if black has won in the game situation (meaning black has reached the other side).
We further define Cwhite(player to move, game situation) and Cblack(player to move, game situation).
Cwhite(player to move, game situation) indicates whether white can always win in a game situation where a certain player is to move:
- Cwhite(white, game situation) holds if and only if Wblack(game situation) does not hold and there exists a white move m in the game situation for which Cwhite(black, "game situation after move m") holds.
- Cwhite(black, game situation) holds if and only if Wwhite(game situation) holds or for all possible black moves m in the game situation, Cwhite(white, "game situation after move m") holds.
Cblack(player to move, game situation) indicates whether black can always win in a game situation where a certain player is to move:
- Cblack(white, game situation) holds if and only if Wblack(game situation) holds or for all possible white moves m in the game situation, Cblack(black, "game situation after move m") holds.
- Cblack(black, game situation) holds if and only if Wwhite(game situation) does not hold and there exists a black move m in the game situation for which Cblack(white, "game situation after move m") holds.
Now it holds that:
- The game is computable and white can always win if Cwhite(black, initial situation).
- The game is computable and black can always win if Cblack(black, initial situation).
- The game is not computable if both Cwhite(black, initial situation) and Cblack(black, initial situation) do not hold.
With five game pieces and 32 squares, there are at most 32 × 31 × 30 × 29 × 28 = 24,165,120 possible game situations. A computer program can therefore calculate all possible game progressions in a short time and determine Cwhite(player to move, game situation) and Cblack(player to move, game situation) for each game situation. Using such a program, it can be determined that Cwhite(black, initial situation) holds, and thus white can always win. Below is an example of a Python program that can be used for this purpose.
It is even possible to calculate how long black can hold out: if white plays smart, the game will be over after a maximum of 44 moves.
# BSD 3-Clause License
#
# Copyright 2025 RJE-Productions and E.R. van Veldhoven
#
# Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
# following conditions are met:
#
# 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following
# disclaimer.
#
# 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
# following disclaimer in the documentation and/or other materials provided with the distribution.
#
# 3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote
# products derived from this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
# INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
# SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
# USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
from enum import Enum
# We define a board of 10 by 10 fields as shown in the figure below. This board consists of an actual 8 by 8
# chessboard, surrounded by an outer ring of 'invalid' fields. The black fields of the chessboard are not used.
# In the figure, both the 'invalid' and the 'unused' fields have their numbers surrounded by brackets.
#
# +----+----+----+----+----+----+----+----+----+----+
# | (0)| (1)| (2)| (3)| (4)| (5)| (6)| (7)| (8)| (9)|
# +----+----+----+----+----+----+----+----+----+----+
# |(10)| 11 |(12)| 13 |(14)| 15 |(16)| 17 |(18)|(19)|
# +----+----+----+----+----+----+----+----+----+----+
# |(20)|(21)| 22 |(23)| 24 |(25)| 26 |(27)| 28 |(29)|
# +----+----+----+----+----+----+----+----+----+----+
# |(30)| 31 |(32)| 33 |(34)| 35 |(36)| 37 |(38)|(39)|
# +----+----+----+----+----+----+----+----+----+----+
# |(40)|(41)| 42 |(43)| 44 |(45)| 46 |(47)| 48 |(49)|
# +----+----+----+----+----+----+----+----+----+----+
# |(50)| 51 |(52)| 53 |(54)| 55 |(56)| 57 |(58)|(59)|
# +----+----+----+----+----+----+----+----+----+----+
# |(60)|(61)| 62 |(63)| 64 |(65)| 66 |(67)| 68 |(69)|
# +----+----+----+----+----+----+----+----+----+----+
# |(70)| 71 |(72)| 73 |(74)| 75 |(76)| 77 |(78)|(79)|
# +----+----+----+----+----+----+----+----+----+----+
# |(80)|(81)| 82 |(83)| 84 |(85)| 86 |(87)| 88 |(89)|
# +----+----+----+----+----+----+----+----+----+----+
# |(90)|(91)|(92)|(93)|(94)|(95)|(96)|(97)|(98)|(99)|
# +----+----+----+----+----+----+----+----+----+----+
#
# The figure below only shows the numbers of the 32 used fields:
#
# +----+----+----+----+----+----+----+----+----+----+
# | | | | | | | | | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 11 | | 13 | | 15 | | 17 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 22 | | 24 | | 26 | | 28 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 31 | | 33 | | 35 | | 37 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 42 | | 44 | | 46 | | 48 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 51 | | 53 | | 55 | | 57 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 62 | | 64 | | 66 | | 68 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 71 | | 73 | | 75 | | 77 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 82 | | 84 | | 86 | | 88 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | | | | | | | | |
# +----+----+----+----+----+----+----+----+----+----+
#
# White starts on the fields 11, 13, 15, and 17. We store the positions of the white pieces in the 'whitePositions'
# array. Black starts on field 84, and we store its position in the 'blackPosition' variable.
#
# White can make the following two moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
#
# Black can make the following four moves:
# 1. one field diagonally down to the left: this corresponds to an increase of the field number by 9.
# 2. one field diagonally down to the right: this corresponds to an increase of the field number by 11.
# 3. one field diagonally up to the left: this corresponds to a decrease of the field number by 11.
# 4. one field diagonally up to the right: this corresponds to a decrease of the field number by 9.
#
# A move is only valid if there is not already a piece on the destination field and the destination field is not on
# the outer ring. A field lies on the outer ring if any of the following conditions hold:
# - the field number is less than 10;
# - the field number is at least 90;
# - the field number modulo 10 equals 0;
# - the field number modulo 10 equals 9.
#
# We store the result for each game situation in the variable "outcomes". This variable contains the outcome for
# each combination (player to move, position of black, positions of white pieces 1 to 4). We map the 32 possible
# field numbers to the range [0..31] as follows:
#
# +----+----+----+----+----+----+----+----+----+----+
# | | | | | | | | | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 0 | | 1 | | 2 | | 3 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 4 | | 5 | | 6 | | 7 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 8 | | 9 | | 10 | | 11 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 12 | | 13 | | 14 | | 15 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 16 | | 17 | | 18 | | 19 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 20 | | 21 | | 22 | | 23 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | 24 | | 25 | | 26 | | 27 | | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | 28 | | 29 | | 30 | | 31 | |
# +----+----+----+----+----+----+----+----+----+----+
# | | | | | | | | | | |
# +----+----+----+----+----+----+----+----+----+----+
NR_OF_POSITIONS = 32 # There are 32 fields on which the pieces can be positioned.
POSSIBLE_MOVES = [9, 11, -11, -9]
# Define a mapping of the 32 usable field numbers in the range [0..99] to the range [0..31].
MAPPING = [
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, 1, -1, 2, -1,
3, -1, -1, -1, -1, 4, -1, 5, -1, 6, -1, 7, -1, -1, 8, -1, 9, -1,
10, -1, 11, -1, -1, -1, -1, 12, -1, 13, -1, 14, -1, 15, -1, -1,
16, -1, 17, -1, 18, -1, 19, -1, -1, -1, -1, 20, -1, 21, -1, 22, -1,
23, -1, -1, 24, -1, 25, -1, 26, -1, 27, -1, -1, -1, -1, 28, -1,
29, -1, 30, -1, 31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
]
class Player(Enum):
BLACK = 0
WHITE = 1
class Outcome(Enum):
NOT_CALCULATED = 0
BLACK_CAN_ALWAYS_WIN = 1
WHITE_CAN_ALWAYS_WIN = 2
BEING_CALCULATED = 3
class CatAndMouseGame:
def __init__(self):
# 'outcomes' corresponds to C_white(player whose move it is, game situation)
# and C_black(player whose move it is, game situation) in the puzzle explanation.
self.outcomes = [[[[[[Outcome.NOT_CALCULATED for _ in range(NR_OF_POSITIONS)]
for _ in range(NR_OF_POSITIONS)]
for _ in range(NR_OF_POSITIONS)]
for _ in range(NR_OF_POSITIONS)]
for _ in range(NR_OF_POSITIONS)]
for _ in range(2)]
self.black_position = 0 # Initialize with a default value
self.white_positions = [0] * 4
self.total = 0
self.initialize_piece_positions()
def initialize_piece_positions(self):
self.black_position = 84
self.white_positions = [11, 13, 15, 17]
def show_progress(self):
self.total += 1
if self.total % 10000 == 0:
print(self.total, end='\r')
def is_usable_field(self, field_number):
if field_number < 10 or field_number >= 90 or field_number % 10 == 0 or field_number % 10 == 9:
# The field is on the outer ring
return False
else:
# Check if in this row the usable fields have odd numbers (this holds for rows 2, 4, 6, and 8)
odd_row = (field_number // 10) % 2 == 1
return (odd_row and field_number % 2 == 1) or (not odd_row and field_number % 2 == 0)
def is_move_allowed(self, piece_position: int, move: int) -> bool:
new_piece_position = piece_position + move
if not self.is_usable_field(new_piece_position):
# A move outside the chessboard is not allowed
return False
if new_piece_position == self.black_position:
# Black is on the new field, therefore the move is not allowed
return False
for white in range(4):
if new_piece_position == self.white_positions[white]:
# A white piece is on the new field, therefore the move is not allowed
return False
return True
def black_has_won(self) -> bool:
return self.black_position in [11, 13, 15, 17]
def white_has_won(self) -> bool:
# White wins if it blocks black in such a way that black cannot make any move anymore
return not (self.is_move_allowed(self.black_position, POSSIBLE_MOVES[0]) or
self.is_move_allowed(self.black_position, POSSIBLE_MOVES[1]) or
self.is_move_allowed(self.black_position, POSSIBLE_MOVES[2]) or
self.is_move_allowed(self.black_position, POSSIBLE_MOVES[3]))
def white_can_make_a_move(self) -> bool:
return (self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[0]) or
self.is_move_allowed(self.white_positions[0], POSSIBLE_MOVES[1]) or
self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[0]) or
self.is_move_allowed(self.white_positions[1], POSSIBLE_MOVES[1]) or
self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[0]) or
self.is_move_allowed(self.white_positions[2], POSSIBLE_MOVES[1]) or
self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[0]) or
self.is_move_allowed(self.white_positions[3], POSSIBLE_MOVES[1]))
def get_outcome(self, player: Player, black_position: int, white_positions: list) -> Outcome:
# Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
sorted_white_positions = sorted(white_positions)
return self.outcomes[player.value][
MAPPING[black_position]][
MAPPING[sorted_white_positions[0]]][
MAPPING[sorted_white_positions[1]]][
MAPPING[sorted_white_positions[2]]][
MAPPING[sorted_white_positions[3]]]
def set_outcome(self, player: Player, black_position: int, white_positions: list, outcome: Outcome):
# Because the white pieces are interchangeable, we can sort their positions for more efficient calculation
sorted_white_positions = sorted(white_positions)
self.outcomes[player.value][
MAPPING[black_position]][
MAPPING[sorted_white_positions[0]]][
MAPPING[sorted_white_positions[1]]][
MAPPING[sorted_white_positions[2]]][
MAPPING[sorted_white_positions[3]]] = outcome
def white_move(self):
self.show_progress()
white_can_win = False
black_can_win = False
if self.white_can_make_a_move():
for piece in range(4):
for move in range(2):
if self.is_move_allowed(self.white_positions[piece], POSSIBLE_MOVES[move]):
# Perform the white move
tmp_position = self.white_positions[piece]
self.white_positions[piece] += POSSIBLE_MOVES[move]
# Now black is to move
outcome = self.get_outcome(
Player.BLACK, self.black_position, self.white_positions)
if outcome == Outcome.NOT_CALCULATED:
# This game situation has not been calculated yet
if self.white_has_won():
self.set_outcome(Player.BLACK, self.black_position,
self.white_positions, Outcome.WHITE_CAN_ALWAYS_WIN)
else:
self.black_move()
outcome = self.get_outcome(
Player.BLACK, self.black_position, self.white_positions)
if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
white_can_win = True
elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
black_can_win = True
# Restore the game situation
self.white_positions[piece] = tmp_position
else:
# If white cannot move, it must skip a turn
# Now black is to move
outcome = self.get_outcome(
Player.BLACK, self.black_position, self.white_positions)
if outcome == Outcome.NOT_CALCULATED:
# Prevent endless loops
self.set_outcome(Player.BLACK, self.black_position,
self.white_positions, Outcome.BEING_CALCULATED)
self.black_move()
outcome = self.get_outcome(
Player.BLACK, self.black_position, self.white_positions)
if outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
white_can_win = True
elif outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
black_can_win = True
if white_can_win:
self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
Outcome.WHITE_CAN_ALWAYS_WIN)
elif black_can_win:
self.set_outcome(Player.WHITE, self.black_position, self.white_positions,
Outcome.BLACK_CAN_ALWAYS_WIN)
def black_move(self):
self.show_progress()
black_can_win = False
white_can_win = False
for move in range(4):
if self.is_move_allowed(self.black_position, POSSIBLE_MOVES[move]):
# Perform the black move
tmp_position = self.black_position
self.black_position += POSSIBLE_MOVES[move]
# Now white is to move
outcome = self.get_outcome(
Player.WHITE, self.black_position, self.white_positions)
if outcome == Outcome.NOT_CALCULATED:
# This game situation has not been calculated yet
if self.black_has_won():
self.set_outcome(Player.WHITE, self.black_position,
self.white_positions, Outcome.BLACK_CAN_ALWAYS_WIN)
else:
self.white_move()
outcome = self.get_outcome(
Player.WHITE, self.black_position, self.white_positions)
if outcome == Outcome.BLACK_CAN_ALWAYS_WIN:
black_can_win = True
elif outcome == Outcome.WHITE_CAN_ALWAYS_WIN:
white_can_win = True
# Restore the game situation
self.black_position = tmp_position
if black_can_win:
self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
Outcome.BLACK_CAN_ALWAYS_WIN)
elif white_can_win:
self.set_outcome(Player.BLACK, self.black_position, self.white_positions,
Outcome.WHITE_CAN_ALWAYS_WIN)
print("Creating game object...")
game = CatAndMouseGame()
print("Running game...")
game.black_move()
print(game.total)
game.initialize_piece_positions()
print(game.get_outcome(Player.BLACK, game.black_position, game.white_positions).name)
Back to the puzzle