On the metric of minimizing the value, start in the corner square A1. The lowest candidate for that square is obviously 1, so plug it in. The only constraint that's placed on 1 is that it cannot be adjacent to 2, so the lowest number which can potentially occupy A2 is 3, so plug that in. Now both 2 and 4 are disqualified from A3 by adjacency, so plug in a 5 there.
Now by previously-demonstrated results, 2 must go in an edge square but not a corner. Whichever square that might be, imagine the 3x3 grid that's obtained by removing the 2 along with its row and column. Clearly this grid must contain all seven remaining even numbers, and only has space for two odd numbers. This means that if the trial grid which begins 1-3-5 is in fact legal, 2 can't possibly go in column 4, because the submatrices on either B4 or C4 already contain three odd numbers across row A. Furthermore, A4 must be even, because whichever one of 1, 3, or 5 happens to share a column with 2, the others account for both permissible odd numbers in the 3x3. 2 obviously doesn't go in the corner, and both 4 and 6 are excluded from A4 by adjacency to 5, so the lowest theoretical value on the top row is 1-3-5-8.
If all assignments so far are legal, the 8 in the corner constrains the 2, 4, and G (16) to six possible squares. Since those three numbers all have factorization constraints on each other, those 6 squares can be divided into two mutually exclusive groups of 3, in which unknown powers of 2 are marked as P:
Code: Select all
P--- or -G-C
Note that in the first case, 2 itself can be uniquely placed, since it requires a location on the edge which is non-adjacent to 1. In the second case, G can be placed in B2 because either 2 or 4 would fall afoul of adjacency to 3. Furthermore, both 2 and 4 place factorization constraints on C (12) which would lock it out of rows C and D, and columns 1 and 3, forcing it to appear in B4.
In fact, those constraints in the second case prove inescapable. Consider what happens now when attempting to place a 6 in that grid: by factorization, it's locked out of column 2 (with 3) and 4 (with C), as well as row B (also with C), leaving only C3 and D1. However, the 2 must occupy either C1 or D3, and each one shares a row or column with both remaining candidate cells. So the second configuration is impossible, and the first configuration is the only chance if 1-3-5-8 is indeed the lowest possible value for the top row.
Again there are two cases, and again placing G will automatically restrict C to one legal candidate, allowing it to be filled in along with the powers of 2:
Code: Select all
4--- or G--C
In case 1, factorization constraints lock the 6 out of rows C and D, as well as columns 2 and 4. This leaves only B3, but that, too is restricted by adjacency to the 5 at A3. Then case 1 is impossible and case 2 is the last remaining possibility to check before backtracking to something larger than 1-3-5-8 in the top row.
In case 2, the 6 is still locked out of columns 2 and 4, and this time rows B and D. But there is still one cell remaining for it, C1, where it can and must go.
Two even numbers remain to be placed: A (10) and E (14). Factorization with 5 blocks A from column 3, so E goes at B3, leaving A to go in C4.
With only the remaining odd numbers left to place, E blocks 7 by factorization along the row (B2), column (D3), and diagonal (C2 and D1), leaving D4 as the last safe spot for it.
F (15) is blocked from columns 2 and 3 by factorization with 3 and 5, forcing it to go in D1. Likewise, 9 is blocked from the 3 in column 2, and now the last remaining choice is D3.
Now only B (11) and D (13) need placing. Both are prime, so there are no factorization contraints to worry about, but E blocks D from B2 by adjacency. Thus 1-3-5-8 in the top row admits exactly one solution to the remainder of the grid; since it's clearly impossible to make the lexical ordering any smaller than that, this solution is hereby minimal:
[EDIT] Similarly, optimizing for the maximal lexical grid ordering can start by assuming the head out to 16-14-12-15-13, which uniquely specifies everything except the 7 and 9, and then simply place those in the order that yields a greater result, leaving: