Simple grid placement puzzle

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Simple grid placement puzzle

Postby balr » Wed Sep 24, 2014 4:33 pm UTC

The challenge: Place the digits 1 through 9 into a 3x3 grid subject to two constraints:

1. No numbers that exactly divide each other can be in the same row, column, or long diagonal (1 doesn't count as a divisor for this puzzle)

2. No numbers that are +/-1 of each other can be adjacent vertically or horizontally. (Thus if top middle is 5, neither of the other two top cells nor the middle cell can be 4 or 6).

This isn't a solution:

Code: Select all

       2   3   5
       6   8   9
       1   7   4
Problems: 8 and 7 are adjacent; ditto 8 and 9; and 2 and 3. 2 and 6 are divisors as are 2, 4, 8. All the other cells are fine!


Find a solution, or prove it can't be done.

Krealr
Posts: 157
Joined: Wed Sep 09, 2009 8:22 pm UTC

Re: Simple grid placement puzzle

Postby Krealr » Wed Sep 24, 2014 5:17 pm UTC

I think I found a solution.
Spoiler:

Code: Select all

8 1 6
3 7 4
5 2 9


Edit: After some more checking I'm pretty sure it is the only solution. (Other that rotations/reflections)

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Simple grid placement puzzle

Postby curiosityspoon » Wed Sep 24, 2014 5:17 pm UTC

Label the grid as follows:

Code: Select all

A1 A2 A3
B1 B2 B3
C1 C2 C3

Spoiler:
Now the numbers 2, 4, and 8 all disqualify each other by factorization, so these numbers must be is separate rows and columns. With the long diagonals also serving as disqualifying lines, without loss of generality these numbers must occupy A2, B1, C3 in some order (rotating the grid if necessary to achieve this orientation).

If 2 occupies C3, then 6 is disqualified from all six remaining squares by factorization. Again without loss of generality, then, 2 occupies A2 (reflecting along the A1-C3 diagonal if necessary).

The center square B2 shares a row, column, or long diagonal with every other square, and cannot contain any number that's a part of any factorization constraint. The only numbers immune to such constraints are 1, 5, and 7; 1 is further disqualified by adjacency since it's known that 2 occupies a side square. Then B2 contains either 5 or 7.

By being adjacent to the 2 in A2, the squares A1, B2, and A3 exclude all of 1, 3, and 6; these numbers must then go in the only remaining squares: C1, C2, and B3. Additionally, 6 cannot go in C2 or B3, because those squares are adjacent to B2, and a 6 would disqualify both remaining candidates there, 5 and 7. So 6 goes in C1, and the rest of the squares now untangle themselves:
3 cannot go in C2 by factorization across row C, so C2 is 1, and B3 is 3.
4 cannot go in C3 by adjacency with the 3 in B3, so C3 is 8, and B1 is 4.
5 cannot go in A1 or B2 by adjacency with the 4 in B1, so 5 goes in A3, leaving 7 for B2 and 9 for A1.

Recap:

Code: Select all

9 2 5
4 7 3
6 1 8

and this solution is unique up to rotation and reflection.

thefargo
Posts: 33
Joined: Mon Jan 20, 2014 3:45 pm UTC

Re: Simple grid placement puzzle

Postby thefargo » Wed Sep 24, 2014 5:38 pm UTC

Spoiler:
there is only one unique solution
9 2 5
4 7 3
6 1 8

there are 8 possible transpositions/rotations of this matrix which also satisfy the solution



edit: Ninja'd by Krealr

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Simple grid placement puzzle

Postby Nitrodon » Wed Sep 24, 2014 6:58 pm UTC

Construction/proof of the unique solution:
Spoiler:
The number 2 is in the same row, column, or long diagonal as at most five other numbers. As such, it must be in the middle of an edge.

Code: Select all

.2.
...
...

Only three numbers (5, 7, and 9) can be adjacent to 2, and there are three tiles adjacent to 2, so these three numbers must all be adjacent to 2. Moreover, 9 cannot be placed in the center, since 3 divides it. Hence, 9 is in an adjacent corner. Without loss of generality:

Code: Select all

.29
...
...

As stated earlier, the center tile must be a 5 or 7. Hence, 6 cannot be adjacent to it, and must be in a bottom corner. If we place it in the bottom left corner, all tiles are in the same row, column, or long diagonal as either 6 or 9, so 3 cannot be placed anywhere. Hence 6 goes in the bottom right corner.

Code: Select all

.29
...
..6

From here, you can fill in 3, 4, 8, 1, 5, and 7 in that order. Each number will have only one space available to it when you get to it.

Code: Select all

529
374
816

Hence the solution is unique.

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Simple grid placement puzzle

Postby balr » Thu Sep 25, 2014 8:51 am UTC

That didn't last long!

curiosityspoon and nitrodon have both pretty much replicated the analysis I made to solve the puzzle, so I won't bother publishing that.

Now 4x4 with the same rules is a bit tougher to find a solution - there are quite a few. Can you find one of them?

How about the lowest solution (reading the grid as hex number left to right, top to bottom)?

Minor hint in a spoiler:
Spoiler:
A little bit of thought similar to the start of the 3x3 analysis gets you the first three cells easily. Then there is limited placement for multiples of 4.

thefargo
Posts: 33
Joined: Mon Jan 20, 2014 3:45 pm UTC

Re: Simple grid placement puzzle

Postby thefargo » Thu Sep 25, 2014 11:46 am UTC

By trial and error, I came up with:

Spoiler:
01 06 08 12
09 13 10 16
02 07 03 05
15 04 14 11

I started by placing the 1 in the top left corner (to shoot for the lowest value solution, then used nitrodon's logic for the 2, then crunched the rest.


edit: Never mind, this is an invalid solution. Error checking is hard on these things...

Krealr
Posts: 157
Joined: Wed Sep 09, 2009 8:22 pm UTC

Re: Simple grid placement puzzle

Postby Krealr » Thu Sep 25, 2014 4:20 pm UTC

balr wrote:Now 4x4 with the same rules is a bit tougher to find a solution - there are quite a few. Can you find one of them?


Am I missing something? This seems impossible.

Spoiler:
There are 16 total numbers. 7 of them are multiples of 2. (4, 6, 8, 10, 12, 14, 16) Which means after placing 2 I need at least 7 open spots.

With symmetry/rotation there are only 3 choices for placing the number 2 on a blank board.

- indicates no multiples of 2 can go in that spot

Code: Select all

2 - - -    - - o o    - - - o
- - o o    2 - - -    - 2 - -
- o - o    - - o o    - - - o
- o o -    - o - o    o - o -


So at most I have 6 empty slots, not enough to put the remaining multiples of 2

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Simple grid placement puzzle

Postby Nitrodon » Thu Sep 25, 2014 4:57 pm UTC

Krealr, the rules specify long diagonals (from one corner of the square to another), not all diagonals. The second option in your spoiler is possible.

Lunch Meat
Posts: 68
Joined: Fri Jun 20, 2008 6:30 am UTC

Re: Simple grid placement puzzle

Postby Lunch Meat » Thu Sep 25, 2014 6:06 pm UTC

How about this?

Spoiler:

Code: Select all

15 4  6  14
2  11 13 9
7  3  10 16
1  5  8  12

I pretty much figured it out through trial and error--placing 2, 4, 8, 16 in one of the possible configurations, then adding 3 and 6, then 9, 5, 10, and 15 until I got to something that didn't work and then going back a step.

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Simple grid placement puzzle

Postby balr » Sat Sep 27, 2014 9:55 am UTC

That looks good, lunch meat.

I think we followed similar logic paths to get there:

Spoiler:
2 has to go on a middle edge (not corner), so we can start with:

Code: Select all

    ?   2   ?   ?
    ?   ?   ?   ?
    ?   ?   ?   ?
    ?   ?   ?   ?

(in your case, you started with the bottom row. Same difference).

If we are aiming for the lowest solution, then top left has to be 5 and the other side of the 2 has to be 7:

Code: Select all

    5   2   7   ?
    ?   ?   ?   ?
    ?   ?   ?   ?
    ?   ?   ?   ?

Then, as you say, only 21 possible placements for 4, 8, 16. That brings it down to a brute search space solvable in minutes with Scilab or equivalent. Assuming of course that 5,2,7,... has any solutions (hint: it does).

I don't know if it is possible to eliminate any other possibilities by logic before going brute force. Other than the multiples of 3 that you used.

curiosityspoon
Posts: 35
Joined: Wed Sep 24, 2014 5:01 pm UTC

Re: Simple grid placement puzzle

Postby curiosityspoon » Sat Sep 27, 2014 10:12 am UTC

Spoiler:
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

1358      1358
P---  or  -G-C
--P-      P---
-2--      --P-

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

1358      1358
4---  or  G--C
--GC      --4-
-2--      -2--

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.

Code: Select all

1358
G-EC
6-4A
-2--

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:

Code: Select all

1358
GBEC
6D4A
F297


[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:

Code: Select all

GECF
D68B
3152
A497

balr
Posts: 54
Joined: Mon Dec 07, 2009 5:29 pm UTC

Re: Simple grid placement puzzle

Postby balr » Mon Sep 29, 2014 8:09 am UTC

Nice analysis!

I think we have a winner.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 12 guests