Wednesday, September 17, 2008

Minimization Maze Game

Two players, A and B.
Take an n-by-n grid, for n = fixed positive integer.
Player A fills in the grid with the integers 1 to n^2, one integer per
grid-square, such that each integer k is adjacent
(below/above/right/left) to (k+1) (for 1 <= k <= n^2 -1), placing the
1 anywhere and finishing anywhere.
Player B then draws a line from upper-left square, taking any path
from square to square (visiting each square AT MOST once) and moving
down/up/right/left, and finishing at lower-right square.
Player B attempts to have the sum of each square she/he passes over
with her/his line be as small as possible.
Then the players switch, player B fills in another n-by-n grid and
player A draws the line.
The player with the lowest score wins.

Thanks,
Leroy Quet

No comments: