Counting Games:Relative-Primality & Grids

[Leroy Quet]

Posted to sci.math and rec.puzzles:
(Don't confuse this with the grid-puzzle I posted yesterday...)


Take the following game:

There are m players, m = any positive integer.

Take an n-by-n grid, where n is such that m divides n^2.

Players take turns placing the integers 1 to n^2 (in order) into the
grid, if possible, such that player-k places those integers congruent
to k(mod m) into the grid, such that:
the integer, j, is placed into a cell where all adjacent (up, down,
left, right) cells (which already contains integers) contain only
integers which are relatively prime to j.

The last player who is able to place an integer somewhere into the
grid is the winner.
(If the grid is filled in completely, then player m wins.)


A sample game:

1  4  5

2  7  3

*  6  *

(The player placing the 7 has won.)

-

So...
What are the number of possible games for an n-by-n grid?
(The number of players is insignificant, right?)


If this number is G(n), then (obviously):
g(n) <= G(n) <= (n^2)!,
where g(n) is the number of games where the grid is filled in
completely.

 g(n) can be just thought of as the number of ways to fill in a grid
(with 1 to n^2) so that all adjacent integers are coprime -- without
thinking of it as a "game".

Also, I wonder how to calculate the g(n) sequence also.

Thanks,
Leroy Quet