35
10
Over at our friends at Puzzling.SE, the following puzzle was posted: Is this chromatic puzzle always solvable? by Edgar G. You can play it here.
Puzzle explanation
Given a 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 m
nor 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 1
, 2
and 3
(or 0
, 1
, 2
if convenient). You may take this input in any sane format. Both m
and n
are >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 O(k^[m*(n-1)+(m-1)*n])
with 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)
Test cases
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.
I'd love to see a code challenge version of this, where the goal is to solve a set of puzzles with the least total moves. – Mego – 2016-07-05T08:55:41.023
@Mego I definitely considered this. However, I'm afraid that this will turn into a DFS or BFS which will take forever to run; or, to prevent this, a set of vague restrictions (like 'must run within an hour' which favors people with a massive computer, or which will require me to test all solutions). And furthermore, the current challenge has zero answers spare mine, so I doubt that an even more difficult version requiring heuristics etc. will prove to be more popular... But perhaps if this challenge picks up momentum I may post a sibling challenge like you describe. – Sanchises – 2016-07-05T09:04:29.487
I think I'll try to do that in Lua, but it may be longer than your 324 Bytes solution ^^ – Katenkyo – 2016-07-07T11:25:17.253
@Katenkyo Only one way to find out! I'm looking forward to seeing your solution. – Sanchises – 2016-07-07T12:06:12.213
You'll have to wait a little bit sadly, you prevented brute-force solution so I have to find a solution that's short in lua :p – Katenkyo – 2016-07-07T12:08:53.973
Is the output sane if it is as in the op to solve all rows, then an extra new line, and then a set of moves that you'll have to repeat for each column ? something like [x 1],[x 2] – Maliafo – 2016-07-09T11:41:12.073
@Maliafo No, every step needs to be printed. – Sanchises – 2016-07-09T11:53:06.523