14
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Yeah, my intuition and scratch work seems to suggest that it s impossible. But how would you give a formal proof of its impossibility? $\endgroup$
    – Enigma
    Dec 7, 2014 at 1:58
  • $\begingroup$ No, it was a question suggested by a professor. $\endgroup$
    – Enigma
    Dec 7, 2014 at 2:01
  • $\begingroup$ 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, $\endgroup$
    – JMoravitz
    Dec 7, 2014 at 2:08
  • $\begingroup$ 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. $\endgroup$
    – ml0105
    Dec 7, 2014 at 2:53

3 Answers 3

21
$\begingroup$

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.

Addendum: For your viewing pleasure:

enter image description here

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Dec 7, 2014 at 2:28
  • $\begingroup$ @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? $\endgroup$ Dec 7, 2014 at 2:32
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Dec 7, 2014 at 4:29
  • $\begingroup$ 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? $\endgroup$
    – Enigma
    Dec 7, 2014 at 4:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – JMoravitz
    Dec 7, 2014 at 4:53
12
$\begingroup$

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, dolphintour

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.

another dolphin tour

$\endgroup$
3
  • $\begingroup$ Very nice :) I imagine this is the exceptional case, and most blue squares are not the starting point of tours. $\endgroup$ Dec 7, 2014 at 8:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Dec 7, 2014 at 12:49
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 28, 2023 at 7:36
3
$\begingroup$

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.

Solutions 8x8

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.add_patch(plt.Circle(coords[-1], 0.15))
        ax.arrow(*(p-0.1*dp for p,dp in zip(self.pos, dr)), *(0.2*p for p in dr),
                shape='full', lw=0, length_includes_head=True,
                head_width=0.3)
        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:
                print("{} -> Not found".format((i,j)))
                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: 2x2 board

3x3 board

4x4 board

5x5 board

6x6 board

Solutions

$\endgroup$
5
  • 1
    $\begingroup$ Why are your boards 7x7 instead of 8×8? $\endgroup$ Jul 28, 2023 at 8:18
  • 2
    $\begingroup$ Also, can you detail how you "exhausted" searching for ways (for the blue squares which you claim don't tour) $\endgroup$ Jul 28, 2023 at 8:23
  • $\begingroup$ @DavidRaveh Sorry about that, I put the wrong figure! Here it is. For the algorithm, I just used a simple depth-first search. $\endgroup$ Jul 28, 2023 at 13:46
  • $\begingroup$ 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)? $\endgroup$ Jul 28, 2023 at 17:21
  • 1
    $\begingroup$ @DavidRaveh I've added the code of the program which computes the tours and plots the result. $\endgroup$ Jul 31, 2023 at 12:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .