How to tell if a Mathematical Rubiks puzzle is solvable

Question

I recently came up with a series of mathematical puzzles based loosely on Rubik's puzzles(or should I say combination puzzles). They go like this: you have an n x n group of numbers where you can shift either a row or a column in any cardinal direction(left,right,up, or down) however you must increment every number involved by one. I am simply calling these Curtesian Objects and they are solved when all of the elements equal the same number. Curtesian Objects can also be described as tuples ex. x = 2x2 (1,2,3,4) where the (1,2) and (3,4) are the rows of x and (1,3) and (2,4) are the columns. An example of shifting would be shifting the top row of x left making x = (3,2,3,4). Keep in mind it only looks like switching because both n's are 2.

Hopefully I explained Curtesian Objects well enough and if so lets describe my problem. A Curtesian Object is solvable if all of its elements can become the same. An example is x (1,2,3,4) which is solvable to 5 and the steps are:

I omitted the directions due to it being obsolete when n = 2

1. Left Column Shift(or 1L for 1 shift) to (4,2,2,4)
2. Bottom Row Shift(or 1B) to (4,2,5,3)
3. Double Right Column Shift(or 2R and adds 2 to both elements) to (4,4,5,5)
4. Top Row Shift (or 1T) to (5,5,5,5)

The puzzle is how can you tell if a Curtesian Object is solvable and if so to what number? I've had some success using algebra since it helps in finding patterns of solvable puzzles but not in solving puzzles that I can't prove are unsolvable. Also looking into how changing n and the number of dimensions changes the problem would prove interesting. As a side question what do you call a problem that is hard to solve and hard to verify?

Answer 1

Every move adds 1 to N tiles, so the total sum of all the tiles increases by N each time. The total sum mod N therefore remains constant. When it is solved, the total sum is a multiple of N (or in fact of N^2), so a prerequisite for the puzzle to be solvable is that the total is a multiple of N cause it stays so throughout.

Now it remains to be proven that any board where the sum is a multiple of N can be solved.

For this we need to a useful move sequence.

 A0 B0 C0 D0
 E0 F0 G0 H0
 I0 J0 K0 L0
 M0 N0 O0 P0
 
 Shift row r to the right: (e.g. r=2)
 
 A0 B0 C0 D0
 H1 E1 F1 G1
 I0 J0 K0 L0
 M0 N0 O0 P0
 
 Shift column c down:  (e.g. c=2)
 
 A0 N1 C0 D0
 H1 B1 F1 G1
 I0 E2 K0 L0
 M0 J1 O0 P0
 
 Shift everything except row r to the right:
 
 D1 A1 N2 C1
 H1 B1 F1 G1
 L1 I1 E3 K1
 P1 M1 J2 O1
 
 Shift everything except column c+1 down:
 
 P2 M2 N2 O2
 D2 A2 F1 C2
 H2 B2 E3 G2
 L2 I2 J2 K2
 
 Shift everything up:
 
 D3 A3 F2 C3
 H3 B3 E4 G3
 L3 I3 J3 K3
 P3 M3 N3 O3
 
 Shift everything left:
 
 A4 F3 C4 D4 
 B4 E5 G4 H4 
 I4 J4 K4 L4 
 M4 N4 O4 P4 

Almost everything has stayed in place, and increased by 4. The only exceptions are the three tiles {B, E, F} which have undergone a 3-cycle, and E has increased and F decreased (relative to the rest).

This move sequence allows you to increase one tile and decrease an adjacent tile relative to the rest of the board.

If N is odd, you can fairly easily make any two tiles adjacent without changing the relative values. If you shift one row/column (N-1)/2 steps in one direction, and all the other rows/columns the same amount in the other direction, then that chosen row/column has been moved a single step relative to the rest (and all values have increased by the same amount).

This means that for odd N we can solve any board that has a total that is a multiple of N as follows:

1. Make the board's total sum a multiple of N^2, simply by doing any moves until that is the case.
2. Find a tile with a below average value, and a tile with an above average value.
3. Make the two tiles adjacent without changing the relative values on the board.
4. Apply the move sequence to increase the low tile and decrease the high tile.
5. Repeat steps 2-4 until all tiles have the same value.

--

If N is even there is a complication.

Consider the board coloured like a chess board, the squares alternating white and black. Whenever any tile is moved one step, it changes colour from white to black or vice versa. It will also change value from odd to even or vice versa. Let's call a tile that has a even value on a white square (or an odd value on a black square) an e-tile. A tile that has an odd value on a white square (or even on a black square) is a o-tile. Note that an e-tile never changes to an o-tile and an o-tile never changes to an e-tile.

When the board is solved there are obviously the same number of e-tiles as there are o-tiles. Therefore for a scrambled board to be solvable, there must also be the same number of each type.

If there are the same number of each type, then the solution method we already have almost works. The problem lies in step 3 - we can't make any two tiles adjacent without changing their relative values, but we can do it if the two tiles are on different coloured squares. So in step 2, you must choose the low-value and high-value tiles to be of different colours, e.g. take the lowest valued white square and highest valued black square or vice versa.

This brings the values closer together until the differences between the two colours are at most 1. At that point the fact that the amount of the two tile types are equal and that the total is a multiple of N^2 means that it is already solved.
--

The solving method above is obviously not efficient. In the final solved state the tiles will have reached quite a high value. It is trivial to increase the final value more just by shifting all the rows one step. To get a lower final value however you need to solve it in a more efficient manner, preferably optimally. This is usually a very hard mathematical problem. The general statement is - Given a set of generators for a mathematical group, find the shortest way to express any element of that group as a product of the given generators. Often the only way to do this is essentially by brute force, trying all move sequences of increasing lengths until you find a solution (combined with some pruning techniques to speed it up). For larger puzzles this is intractable.

I have not yet considered what happens in boards that are not square.