Mazes. & Coprime Grids

[Giovanni Resta]

Leroy Quet wrote:

> 2) What is the array where b(m,n) is the number of ways 1 through m*n can 
> be put into an m-by-n grid, one integer per grid-square, so that every 
> immediately adjacent pair of integers (adjacent in the directions of up, 
> down, left, or right) are coprime?
> (And more specifically, what is the sequence where b(n) is for the n-by-n 
> grid?)

If I'm correct, here are some values for you, other values may take some time
(or need a smarter program...)
The first column (or row) is A076220.
b(n)= 1, 8, 2016, 19611648, ... does not appear in OEIS, nor
1,2,2,6,8,6,12,16,16,12,72,432,2016,432,72,...
bye,
giovanni.

(use a fixed font like courier to preserve alignment)

   |    1       2        3         4       5     6       7        8
--------------------------------------------------------------------
1 |    1        2       6        12      72    72     864     1728
2 |    2        8      16       432    2784 35712 2121984 34069248
3 |    6       16    2016     23904 7102656
4 |   12      432   23904  19611648
5 |   72     2784 7102656
6 |   72    35712
7 |  864  2121984
8 | 1728 34069248
=====================================================================

The 16 configuration 3x2 are the following
------------------------------------------------
  1 2 3   2 5 6   3 4 1   4 5 6   6 1 2   6 5 4
  6 5 4   3 4 1   2 5 6   3 2 1   5 4 3   1 2 3
------------------------------------------------
  1 4 3   3 2 1   3 4 5   5 2 3   6 1 4
  6 5 2   4 5 6   2 1 6   6 1 4   5 2 3
------------------------------------------------
  2 1 6   3 2 5   4 1 6   5 4 3   6 5 2
  3 4 5   4 1 6   3 2 5   6 1 2   1 4 3
------------------------------------------------