logical deduction - What is the minimum number of steps to solve this cloning particles on chessboard puzzle?

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?

Answer

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.