4 × 4 Torus Puzzle
Time limit5sMemory limit256 MB
Find the fewest cyclic row or column shifts on the 4 by 4 torus grid that turn the given color layout into four solid color rows.
- Level
Hard8 of 10
- Topics
- BFS, Graph, Brute force
- Solved
- No attempts yet
Problem
You are given a puzzle drawn as a 4 × 4 grid of colored cells. Each cell is red (R), green (G), blue (B), or yellow (Y), and each color appears exactly four times.
The puzzle is solved in exactly one arrangement:
RRRR
GGGG
BBBB
YYYY
Only that arrangement counts. A grid whose rows read GGGG, BBBB, YYYY, RRRR from top to bottom has one color per row but is not solved.
The grid is not flat. It is stretched over a torus, a donut with a hole in the middle. The top row is joined to the bottom row, and the leftmost column is joined to the rightmost column.
One move shifts a single row one cell left or right, or shifts a single column one cell up or down. A cell pushed off an edge reappears at the opposite edge.
The figure below solves one state in three moves.
Given a state of the puzzle, find the smallest number of moves that solves it. Every state can be solved in fewer than 13 moves.
Input
The input has exactly four lines, and each line has four characters from R, G, B, Y. The input describes a state the puzzle can actually reach, so each color appears exactly four times.
Output
Print the smallest number of moves that solves the given puzzle.