m x n grid with tiles of three different colours, you may select any two adjacent tiles, if their colours are different. These two tiles are then converted to the third colour, i.e., the one colour not represented by these two tiles. The puzzle is solved if all tiles have the same colour. Apparently, one can prove that this puzzle is always solvable, if neither
n are divisible by 3.
Of course, this begs for a solving algorithm. You will write a function or program that solves this puzzle. Note that functions with 'side effects' (i.e., the output is on
stdout rather than in some awkward data type return value) are explicitly allowed.
Input & Output
The input will be an
m x n matrix consisting of the integers
2 if convenient). You may take this input in any sane format. Both
>1 and not divisible by 3. You may assume the puzzle is not solved
You will then solve the puzzle. This will involve a repeated selection of two adjacent tiles to be 'converted' (see above). You will output the two coordinates of these tiles for each step your solving algorithm took. This may also be in any sane output format. You are free to choose between 0-based and 1-based indexing of your coordinates, and whether rows or columns are indexed first. Please mention this in your answer, however.
Your algorithm should run within reasonable time on the original 8x8 case. Brute-forcing it completely is explicitly disallowed, i.e. your algorithm should run under
k the number of steps needed for the solution. The solution however is not required to be optimal. The proof given in the linked question may give you an idea as to how to do this (e.g., first do all columns using only vertically adjacent tiles, and then do all rows)
In these test cases, the coordinates are 1-based and rows are indexed first (like MATLAB/Octave and probably many others).
Input: [1 2] Output: (result: all 3's) [1 1],[1,2] Input: [ 1 2 3 1 ] Output: (result: all 1's) [1 1],[2 1] (turn left column into 2's) [2 1],[2 2] (turn right column into 3's) [1 1],[1 2] (turn top row into 1's) [2 1],[2 2] (turn bottom row into 1's) Input: [1 2 3 2 3 2 1 1] Output: (result: all 3's) [1 1],[1 2] [1 3],[1 4] [1 2],[1 3] [1 1],[1 2] [1 2],[1 3] [1 1],[1 2] [1 3],[1 4] [2 1],[2 2] [1 1],[2 1] [1 2],[2 2] [1 3],[2 3] [1 4],[2 4]
If desired, I may post a pastebin of larger test cases, but I think this should be sufficient.