7
$\begingroup$

I'm creating a puzzle based on the idea from this numberphile video: pebbling a chessboard.

You can see a working (yet unfinished) version here.

I would like to give the user a feedback of how well they solve the puzzle, so I need to compare the user's solution with the optimum (minimal).

I've published the same question on reddit, where a user suggested that if c(n) is that minimum in an nxn square, then $c(n+1) = 2 c(n) + 2$, with $c(2)=2$. But I've found a solution for the $4 \times 4$ case in 12 steps (it is incomplete, but you get the idea).

Do you think there is a way to know the general solution with minimum steps?

Improve this question
$\endgroup$
4
  • $\begingroup$ Interesting question. Can't answer it yet, however an upper bound for any n is c(n) = (S(n)-1)*2, where S(n) is the sum of the n'th row of pascals triangle. I.e. there will always be a solution where all positive /negative cancellation events happen along the main diagonal, with the number of cancellations in each square equal to the ith entry in that row of pascals triangle. However this is clearly not the minimum. Also the number of positive moves must equal the number of negative moves, so c(n) will always be even. $\endgroup$
    – astralfenix
    May 2, 2016 at 12:24
  • $\begingroup$ @astralfenix: The total number of moves of what you are describing is the same as what you get with the c(n+1) = 2*c(n)+2 recursive sequence, namely 2^n-2, and that is indeed an upper bound. $\endgroup$
    – Jaap Scherphuis
    May 2, 2016 at 13:23
  • 2
    $\begingroup$ With a computer search I have shown that for 4x4, 12 is indeed optimal. For 5x5 the original upper bound is 30 (=2^5-2), but by using the optimal 4x4 solution you get a better upper bound of 2*12+2 = 26. However, by computer search I have an 18 move optimal solution. It goes as follows, using zero-based coordinates: 04 03 02 40 30 31 21 11 22 23 14 13 23 22 21 41 33 42. I don't have an optimal 6x6 solution yet. $\endgroup$
    – Jaap Scherphuis
    May 2, 2016 at 13:28
  • 3
    $\begingroup$ Please include a description of the puzzle in your question. $\endgroup$
    – f''
    May 2, 2016 at 14:07

3 Answers 3

Reset to default
3
$\begingroup$

I have found a zig-zag move sequence, very similar to what astralfenix found, but which attains the lower bound that ffao proved, namely 6(n-2) for n>2. This shows that this general solution is an optimal one.

Let me first show you some diagrams of the move pattern for n=4,5,6,7. The first grid shows the set of squares where a positive particle is split, and the second grid the same for the negative particles. The last grid shows the net result of either of those, which is therefore the number of positive-negative annihilations for each square.

   ====    ====    ==== 
  |....|  |.---|  |1...|
  |+...|  |..--|  |.21.|
  |+++.|  |..-.|  |.1.1|
  |++..|  |....|  |..1.|
   ====    ====    ==== 

   =====    =====    ===== 
  |.....|  |...--|  |..1..|
  |..+..|  |.----|  |1..1.|
  |+.+..|  |..-.-|  |.2.2.|
  |++++.|  |..-..|  |.1..1|
  |++...|  |.....|  |..1..|
   =====    =====    ===== 

   ======    ======    ====== 
  |......|  |...---|  |..1...|
  |..+...|  |....--|  |...21.|
  |..+++.|  |.----.|  |1....1|
  |+.+...|  |..-.-.|  |.2.2..|
  |++++..|  |..-...|  |.1..1.|
  |++....|  |......|  |*.1...|
   ======    ======    ====== 

   =======    =======    ======= 
  |.......|  |.....--|  |....1..|
  |....+..|  |...----|  |..1..1.|
  |..+.+..|  |....-.-|  |...2.2.|
  |..++++.|  |.----..|  |1.....1|
  |+.+....|  |..-.-..|  |.2.2...|
  |++++...|  |..-....|  |.1..1..|
  |++.....|  |.......|  |..1....|
   =======    =======    =======

It is clear that the + pattern just extends by three squares for each increment in board size. The - pattern is the same as the + pattern, except rotated 180 degrees for odd n, and mirrored along the \ diagonal for even n.

It is a simple matter to check that these patterns result in the number of particles shown in the third grid, and therefore will annihilate everything. It is not so obvious that there actually exists a sequence of moves in the game that does this. This is because the actual game has the restriction that there cannot be two or more particles with the same charge in any square. It turns out however that it is fairly easy:

1) Perform the positive moves along the spine of the pattern, i.e. a zig-zag pattern with two steps in each direction. These moves are shown here with the letters a-j. The asterisks are places where a move is still to be performed later. This takes 2(n-2) moves.

   Moves      Result
   =======    ======= 
  |.......|  |....+.-|
  |....j..|  |.....+.|
  |..*.i..|  |..++.+.|
  |..fgh*.|  |.....+.|
  |*.e....|  |++.+...|
  |bcd*...|  |...+...|
  |a*.....|  |.+.....|
   =======    =======

2) Then perform the same zig-zag pattern for the negative particles. Note however that to get the first change of direction working you will need to split the other particle that resulted from the first move (the extra move is shown as c here). I'll leave off the final move of the zig-zag, so this is another 2(n-2) moves.

   Moves      Result
   =======    ======= 
  |.....ca|  |.......|
  |...*edb|  |...-...|
  |....f.*|  |..+...-|
  |.*ihg..|  |.-...+.|
  |..j.*..|  |+...-..|
  |..*....|  |..-+...|
  |.......|  |.+.....|
   =======    =======

3) You are then left with n-2 positive-negative particle pairs which takes another 2(n-2) moves to clear.

The example shown here is for n=7, so the two zig-zags are merely 180 degree rotations of each other. It is fairly obvious that the same pattern will therefore work for all odd n. For a complete proof a similar demonstration is needed for even n, where the two zig-zags are mirror images of each other, but this post is long enough as it is.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks @Jaap, so optimal solution for 8x8 chessboard is 36. Maybe next question could be to find the maximum number of movements. It could probably follow a predictable pattern. $\endgroup$
    – Edgar G.
    May 3, 2016 at 14:51
  • $\begingroup$ The maximum happens when all the annihilations are on the centre diagonal. This gives the old upper bound of 2^n-2 moves. $\endgroup$
    – Jaap Scherphuis
    May 3, 2016 at 15:23
  • $\begingroup$ Well I was thinking of max movements allowed by rules but not necessarily solving the puzzle (sorry). Sometimes you end up with an unsolvable configuration of particles, but you can still continue cloning pieces. $\endgroup$
    – Edgar G.
    May 3, 2016 at 16:21
  • 1
    $\begingroup$ Computer search gives 3x3:6; 4x4:16; 5x5:37, but runs out of memory on 6x6. $\endgroup$
    – Jaap Scherphuis
    May 4, 2016 at 5:07
  • $\begingroup$ Great! This seems to be more difficult than the original puzzle goal! I will contemplate creating an alternative version of the brain teaser, specially because it is so hard to solve by computer. Thanks again @Jaap! $\endgroup$
    – Edgar G.
    May 4, 2016 at 7:22
4
$\begingroup$

partial answer:

I still don't have a full proof of the minimum, but there is an algorithm which has a better bound than 2*c(n)+2. The algorithm is essentially the one used in your solution for n=4, generalised for higher n. Namely:

  1. At the beginning there is a +ve square at (1,1) and a -ve square at (n,n). select (1,1), then the one above it (1,2), then the one to the right, and so on in a zig-zag pattern until you have made a total of 2(n-2) moves.
  2. Now select (n,n) then (n-1,n). This eliminates the two +ve squares closest to the top right corner.
  3. select (n,n-1), then (n-1,n-1). Now all the right-most +ve squares are eliminated
  4. select (n-2,n-1), then the square below, then the square to the left, and so on in a zig-zag pattern until the last square selected was (2,3).
  5. select (2,1). Now only one +ve square is left (at 3,1) and only one -ve square is left (at n, n-2). This situation is equivalent to solving an (n-2, n-2) square, we already know the answer to that from previous iterations.

So, this is in effect a recurrence relation with the equation c(n) = 4n -6 + c(n-2)

The following diagram illustrates this for n=6. The big dots are the only non-empty squares remaining after the algorithm above has finished, and this is equivalent to solving n=4 enter image description here

edit: Below is how the algo compares to 2c(n)+2. It doesn't find the minimum though, as Jaap Scherphuis found that c(5)=18 using a computer.

+----+------------+-------------+----------------+
| n  | 2*c(n-1)+2 | 4n-6+c(n-2) | actual minimum |
+----+------------+-------------+----------------+
|  2 |          2 |           2 | 2              |
|  3 |          6 |           6 | 6              |
|  4 |         14 |          12 | 12             |
|  5 |         30 |          20 | 18             |
|  6 |         62 |          30 | ?              |
|  7 |        126 |          42 |                |
|  8 |        254 |          56 |                |
|  9 |        510 |          72 |                |
| 10 |       1022 |          90 |                |
| 11 |       2046 |         110 |                |
| 12 |       4094 |         132 |                |
| 13 |       8190 |         156 |                |
| 14 |      16382 |         182 |                |
+----+------------+-------------+----------------+
Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting, so the puzzle could be solved recursively, this time making annihilations occur on the line connecting the two initial particles for each sub-puzzle. I like the idea of annihilations along the line connecting points because they don't expand too much as trees. $\endgroup$
    – Edgar G.
    May 2, 2016 at 14:09
  • $\begingroup$ I think an extra optimization for your algorithm could be achieved by looking at the intersection of sub-puzzles. If you first solve for nxn and then you solve the resulting (n-2)x(n-2), there are grid cells that are visited several times and maybe could be exploited to minimize the global solution. $\endgroup$
    – Edgar G.
    May 2, 2016 at 15:22
4
$\begingroup$

Looking at this from a lower bound perspective:

If we give the square $(i,j)$ the energy value $\frac{1}{2^{i+j}}$, then the energy of the positive particles is always 1. Thus, the set of reachable positions for the positive particles is a subset of the positions with sum 1.

As the particles always annihilate themselves on the same square, the final position must be reachable both for the negative particles and for the positive ones. So we can look for a lower bound on the number of moves by looking at the positions with the smallest amount of particles that have energy sum 1 from both starting positions.

By noting that all positions in the same diagonal have the same energy, we can specify the energy of a position by noting how many pieces are on each diagonal. I used this fact to write a computer program to brute force the following lower bound table:

+----+-------------+-------------------------------------+----------------+
| n  | lower bound | pieces annihilated on each diagonal | actual minimum |
+----+-------------+-------------------------------------+----------------+
|  2 |           2 |                               0 2 0 |              2 | 
|  3 |           6 |                           0 0 4 0 0 |              6 | 
|  4 |          12 |                       0 0 2 3 2 0 0 |             12 | 
|  5 |          18 |                   0 0 2 3 0 3 2 0 0 |             18 |
|  6 |          24 |               0 0 2 3 0 3 0 3 2 0 0 |              ? |
|  7 |          30 |           0 0 2 3 0 3 0 3 0 3 2 0 0 |                |
|  8 |          36 |       0 0 2 3 0 3 0 3 0 3 0 3 2 0 0 |                |
+----+-------------+-------------------------------------+----------------+

While this doesn't show that those numbers of moves are reachable, it does show that you can't do better.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting! You are using the same invariant from numberphile's video. As the positive particle clones, its energy remains constant. But it may happen that one positive particle annihilates with one negative. And by cloning other positive particle, the sum of positive energy is no more 1. How do you combine positive-negative energies in order to obtain an invariant? I cannot see how it is done. $\endgroup$
    – Edgar G.
    May 3, 2016 at 8:17
  • $\begingroup$ @Edgar G.: What ffao is doing is essentially this simplification: imagine every square can contain any number of positive and negative particles, and that all annihilations are paused until you press a button. Then you can first do all the moves that clone positive particles, then all the moves that clone negative particles, and then all the squares should have the same number of positive as negative particles so everything will annihilate when you press the button. At that moment the positive particles will still have total energy 1, but so will the negative ones which have the same pattern. $\endgroup$
    – Jaap Scherphuis
    May 3, 2016 at 8:29
  • $\begingroup$ Ok! I was confused by the rule that doesn't allow the same particle to be multiple times on one cell. Then, if the final number of positive particles is P, there are also P negatives, and as each click adds one particle, you need at least 2*P-2 steps (lower bound column values). $\endgroup$
    – Edgar G.
    May 3, 2016 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.