Comment from Hugo van der Sanden, Jun 12 2005: "Consider n=2: renumbering doesn't affect the result, so we can fix row A at (1, 2, 3, 4) and multiply the result by 4!. Once rows B and C are chosen, there is only one option for row D. Row B must have (3, 4) or (4, 3) followed by (1, 2) or (2, 1).
"Rows C and D can be swapped without affecting validity, so we can fix column 1 of row C to be the lower of the two options and multiply the results by 2.
"That leaves at most 4 options for row C (2 choices in each of the remaining 3 positions, of which one must have our selected number as one of the choices); that leaves 16 options to check for rows B and C, the result to be multiplied by 48.
"Checking, we find just 6 of the 16 grids are valid:
1234/3412/2143/4321 1234/3412/2341/4123 1234/3421/2143/4312
1234/4312/2143/3421 1234/4321/2143/3412 1234/4321/2413/3142
so a(2) = 6 * 48 = 288."
An example of a sudoku of size 9 X 9:
124567893
378294516
659831742
++
987123465
231456978
546789321
++
863972154
495618237
712345689
See A114288 for the lexicographically earliest 9 x 9 solution, which is the analog of the first of the 4 x 4 grids given at the end of van der Sanden's comment.  M. F. Hasler, Mar 29 2013
