# Chess board combinatorics

STATEMENT: A dolphin is a special chess piece that can move one square up, OR one square right, OR one square diagonally down and to the left. Can a dolphin, starting at the bottom-left square of a chessboard, visit each square exactly once?

QUESTION: How would one approach this type of problem. It seems that whatever way the dolphin moves the maximum moves always involve the dolphin to traverse an 6x8 square.

• Yeah, my intuition and scratch work seems to suggest that it s impossible. But how would you give a formal proof of its impossibility? Dec 7, 2014 at 1:58
• No, it was a question suggested by a professor. Dec 7, 2014 at 2:01
• I have a path it can follow that hits all but one square, so the question becomes then how can we be sure that it can't hit all, Dec 7, 2014 at 2:08
• I would hint at looking at this from a graph theory intuition. The related Knight's Tour asks the question if there is a Hamiltonian Circuit on the board based on using a Knight. So we use a Dolphin and seek to find a Hamiltonian Circuit. Dec 7, 2014 at 2:53

Hint: Instead of the usual black/white pattern, color the square $(a,b)$ either green, blue, or yellow, according to the remainder of $a+b$ (mod $3$). Each color forms a diagonal stripe going from the upper left to the lower right, with the stripe pattern going green, blue, yellow, $\dots$ as you move up or to the right. Think about how this coloring relates to a Dolphin's movement, and what a tour of the board would look like in terms of these colors.

• Very nice. To complete the proof then will also require noting that the starting square matters. If you were to start on one of the blue squares it is indeed possible to hit every space. Dec 7, 2014 at 2:28
• @JMoravitz At least, the coloring argument would not preclude the existence of a tour. Have you found a Dolphin tour starting at, say, the lower right blue square? Dec 7, 2014 at 2:32
• Was working on something else entirely. Yes, in fact, there is a path starting from the lower right blue, assuming your definition is that it need not be a closed walk or need to "arrive at" the starting square (having begun there is good enough). Posted below. Dec 7, 2014 at 4:29
• I still can't completely formulate the final argument. Using this coloring we see that for every diagonal movement it has to be superseded by a right movement and two up movements. This give us a 2-2-1 choice of colors. I also know that there is 20-21-22 groupings of distinct colors Green-Yellow-Blue. But what is the contradiction I am supposed to arrive at? Dec 7, 2014 at 4:47
• @S.S See below for the punchline to the proof. In fact there are 21 green, 21 yellow, and 22 blue spaces. Regardless which move is chosen, you will move $g\to b$, from $b\to y$, and from $y\to g$. The contradiction is that having started on a green (or yellow) square, you will not have the ability to continue movement after having reached the 21st blue (or green resp.) you come to. Dec 7, 2014 at 4:53

In response to Mike Earnest's question regarding the existence of a Dolphin Tour from alternate starting points: If we started at a blue square, say for example the bottom right corner instead,

The punchline of the proof is that there are in fact 21 yellow, 21 green, and 22 blue squares. Any sequence of moves will be (...,green,yellow,blue,...) repeated. Having started from a green square, after reaching the 21st blue, you will no longer have another green square to go to, and so you cannot continue until reaching the 22nd blue.

In a similar fashion, it is then impossible to reach every square having started at a yellow square either.

Having started at a blue however, as shown above, can be possible (depending on the square), and if is impossible for a specific starting square, would require a different argument.

• Very nice :) I imagine this is the exceptional case, and most blue squares are not the starting point of tours. Dec 7, 2014 at 8:01
• After playing with it for a while, I have in fact found dolphin tours starting from each of the blues from the bottom two rows and haven't yet checked the others. I'm not yet convinced if any blues don't have a dolphin tour. Dec 7, 2014 at 12:49
• After a (not so quick) computational search, in fact most of the blue squares do start dolphin tours, but not all of them. 6 of them do not, mostly on the top right part of the board. Jul 28, 2023 at 7:36

Here are all the starting points which would allow for a complete dolphin tour, with examples (these are not unique) of such tours for each one.

These solutions were obtained by exhaustively searching tours, starting from the blue cells in Mike's answer, using a simple depth-first search. One can speedup the process by noting the symmetry across the bottom-left / top right diagonal, and stopping the search when some cells become unattainable. Here is the python code which was used:

import numpy as np
import matplotlib.pyplot as plt
from enum import Enum

class Moves(Enum):
UP = (0,1)
RIGHT = (1,0)
DOWNLEFT = (-1,-1)

class State:
def __init__(self, grid, pos, moves=[]):
self.size = 1
for s in grid.shape:
self.size *= s
self.grid = grid
self.pos = pos
self.moves = moves

@classmethod
def new(cls, size, init_pos):
state = np.full((size,size), True)
state[init_pos] = False
return cls(state, init_pos)

def is_done(self):
return len(self.moves)+1 == self.size

def is_impossible(self):
if len(self.moves) == 0:
# Check if the starting point is in a "blue" cell
cnts = [0,0,0]
for i,j in np.ndindex(self.grid.shape):
cnts[(i+j)%3] += 1
i,j = self.pos
for c in cnts:
if c > cnts[(i+j)%3]:
return True
# Check if the last move did block a cell
for dx,dy in ((-2,-1),(-1,-2),(-1,1),(1,-1),(2,1),(1,2)):
x,y = (self.pos[0]+dx,self.pos[1]+dy)
if self.is_valid((x,y)):
blocked = True
for move in Moves:
npos = (x-move.value[0], y-move.value[1])
if self.is_valid(npos):
blocked = False
break
if blocked:
return True
return False

def is_valid(self, pos):
for v in pos:
if v < 0 or v >= len(self.grid):
return False
return self.grid[pos]

def plot(self, ax, *args, **kwargs):
start = self.pos
coords = [start]
for m in self.moves[::-1]:
start = tuple(s-d for s,d in zip(start,m.value))
coords.append(start)
nx,ny = self.grid.shape
ax.set_xlim(-0.5, nx-0.5)
ax.set_ylim(-0.5, ny-0.5)
ax.set_aspect("equal")
dr = self.moves[-1].value
ax.arrow(*(p-0.1*dp for p,dp in zip(self.pos, dr)), *(0.2*p for p in dr),
return ax.plot(*zip(*coords[::-1]), *args, **kwargs)

def move(self, move):
newpos = tuple(x+dx for x,dx in zip(self.pos,move.value))
if self.is_valid(newpos):
newgrid = self.grid.copy()
newgrid[newpos] = False
return self.__class__(newgrid, newpos, self.moves+[move])
return None

def avail_moves(self):
avail = {}
for move in Moves:
moved = self.move(move)
if moved is not None:
avail[move] = moved
return avail

def find_solution(self):
if self.is_done():
return self
if self.is_impossible():
return None
for move,res in self.avail_moves().items():
sol = res.find_solution()
if sol is not None:
return sol
return None

def make_sym(self):
def tr(c):
a,b = c
return b,a
tr_m = {
Moves.UP : Moves.RIGHT,
Moves.RIGHT : Moves.UP,
Moves.DOWNLEFT : Moves.DOWNLEFT,
}
return State(self.grid.T, tr(self.pos), [tr_m[m] for m in self.moves])

def plot_grid(n):
fig, axes = plt.subplots(n,n, sharey=True, sharex=True, figsize=(n,n))
for i in range(n):
for j in range(i+1):
ax = axes[-j-1][i]
ax_t = axes[-i-1][j]
ms = State.new(n,(i,j))
sol = ms.find_solution()
if sol:
print("{} -> Found".format((i,j)))
sol.plot(ax)
if i != j:
sol.make_sym().plot(ax_t)
else:
ax.set_aspect("equal")
ax_t.set_aspect("equal")
ax.set_xticks([])
ax.set_yticks([])

plot_grid(8)
plt.show()


To be exhaustive, and as there are some nice patterns, here are the solutions for smaller boards:

• Why are your boards 7x7 instead of 8×8? Jul 28, 2023 at 8:18
• Also, can you detail how you "exhausted" searching for ways (for the blue squares which you claim don't tour) Jul 28, 2023 at 8:23
• @DavidRaveh Sorry about that, I put the wrong figure! Here it is. For the algorithm, I just used a simple depth-first search. Jul 28, 2023 at 13:46
• Thank you for clarifying. If it isn't too inconvenient, would you be able to include your code (and what software you run it on)? Jul 28, 2023 at 17:21
• @DavidRaveh I've added the code of the program which computes the tours and plots the result. Jul 31, 2023 at 12:18