I just found a puzzle that kept me wondering. The prompt:
Given a map M composed of N*N tiles (N can be as large as 1000), consider an operation R such that R{x,y,t} rotates a tile from M, at coordinates [x,y], t times - a 90 degree clockwise rotation.
Calculate the set of R operations that produce a map containing no cycles and no dangling tiles (for each tile, it links to its neighbours in at least one edge).
As a example: Input:
┛┃╻┗╺╺┏╻
┣╹╺╋┫┓┃╹
┏┏┓┏━╻━━
╹┳┳╻╹━┣┛
━╻┻┣╻┳┣╺
┏┓┃┓┫┻╹╺
┗┳┳┓┛╋┓━
╻┗┓╺╸┗━┏
Can be rearranged to:
┏━╸┏╸╻┏╸
┣╸╺╋┳┛┃╻
┗┓┏┛┃╻┃┃
╻┣┫╻╹┃┣┛
┃╹┣┫╻┣┻╸
┗┓┃┗┻┫╻╻
┏┫┣┓┏╋┛┃
╹┗┛╹╹┗━┛
Which is a modified map that doesn't contain cycles nor dangling pieces.
The set of possible tiles includes:
"╸" and rotations: "╺", "╻", "╹"
"━" and rotation: "┃"
"┓" and rotations: "┛", "┏", "┗"
"┣" and rotations: "┳", "┻", "┫"
"╋"
Of course the brute-force solution (rotate every piece, check for correctness) is not viable, as the map can be big.
Every solution I can think of (graph with spanning tree, DP, even a genetic algorithm, recursive backtracking - can we even prune anything?) turns out to be as inefficient as the brute-force one. If the set is unique, does that change anything?
Best,