# Anaphylactic Worm Game

"Cliff Pickover ", 914 945-3630 cliff at WATSON.IBM.COM
Wed Mar 23 17:30:58 EST 1994

```Anaphylactic Worm Game

(I'd be interested in any obvservations you have.  Thanks,
cliff at watson.ibm.com)

Imagine a species of worm that becomes seriously allergic to a
substance the second time it is exposed to it.  This is similar to real
alleric reactions where the immune system becomes hyper-senstive to an
antigen upon re-exposure.  (This sensitivity is sometimes known as
anaphylaxis.)  Therefore, as the worm wanders around its world it tries
to avoid those allergens it has encountered previously -- otherwise it
dies.  You don't have to get dirty digging in your garden to study these
worms.  Rather the simple thought exercises should have you wriggling
with delight without ever leaving your office.

The game I designed to simulate the above process is called the
Anaphylactic Worm Game.  It's played on a chessboard which is filled with
random numbers having values from 0 to 24.  These 25 possible values
represent 25 different allergens.  Worms start on any square and find
the longest possible path through the board by moving horizontally or
vertically (not diagonally).  Each number along a worm-path must be
different, or the worm dies.

I am curious to know the longest path you can find in any of the
following three problems.  I would be happy to mention "winner's names"
in an article I'm writing if you write to me at cliff at watson.ibm.com.
(Winners are the first people who tell me the longest possible path.)

I would be interested in roughly how long it took you to determine your
solution.  In addition, here is a mathematical question to ponder:
Given Worm Boards constructed randomly in this manner, what is the
average "largest worm path" you would expect to find?  In the boards
below, I would also be interested in people who can find the shortest
worm path in each.  That is, given a particular starting cell, are there
only extremely short paths possible?  In general, do you think that
certain starting squares in the chess board have a higher probability of
yielding longer paths than others?  For example, do interior squares
generally yield longer possible worm paths than border squares because
they have more neighbors?  Any other observations?

Worm Grid 1:
0  0  2 21  2 23 15 18
4 22 24 17 12  4 11 19
3  3 11 15  5 12  6  8
18 23  6 12 18 24 15 11
9  7 19 18 16 18 14 18
2 17 10  6  5  7 20  7
5 24  5 24 18  0  1  3
24 21  6  8 21 23 18 13

Worm Grid 2:
12  7 11  4 22 22 17  6
15 24  2  1  9  8 16 20
11 23 15  9 17  6 24  4
23 21  3  4  8 17 22 17
6  6 22 16  2  5  8  1
11 10 17  2  8 18 14 10
7 11 24  3 13 10 15  7
20 20  3  1  9  7 10  6

Worm Grid 3:
2 13 20  9 19  8 16 12
22 15 16 14 14 11 12  5
13 12  3  6  4 12  8 15
4  21  8 18 17 13  5  1
9  14 15 19 15  4  4  2
16  6 16  4 11 16  3 17
3  15 15  3 15 14  8 21
22 19 16 24  0 19  8 22

```