algorithm - How to solve 5 * 5 Cube in efficient easy way -

there 5*5 cube puzzle named happy cube problem given mat , need make cube . http://www.mathematische-basteleien.de/cube_its.htm#top

its like, 6 blue mats given-

from following mats, need derive cube -

these way has 3 more solutions. first cub

for such problem, easiest approach imagine recursion based each cube, have 6 position , , each position try check other mate , fit, go again recursively solve same. finding permutations of each of cube , find fits best.so dynamic programming approach.

but making loads of mistake in recursion , there better easy approach can use solve same?

i made matrix out of each mat or diagram provided, rotated them in each 90 clock-wise 4 times , anticlock wise times . flip array , did same, each of above iteration have repeat step other cube, again recursion .

 0 0 1 0 1  1 1 1 1 1  0 1 1 1 0  1 1 1 1 1  0 1 0 1 1 -------------  0 1 0 1 0  1 1 1 1 0  0 1 1 1 1  1 1 1 1 0  1 1 0 1 1 -------------  1 1 0 1 1  0 1 1 1 1  1 1 1 1 0  0 1 1 1 1  0 1 0 1 0 -------------  1 0 1 0 0  1 1 1 1 1  0 1 1 1 0  1 1 1 1 1  1 1 0 1 0 -------------  1st - block diagram 2nd - rotate clock wise 3rd - rotate anti clockwise 4th - flip 

still struggling sort out logic .

i can't believe this, wrote set of scripts in 2009 brute-force solutions exact problem, simple cube case. put code on github: https://github.com/niklasb/3d-puzzle

unfortunately documentation in german because that's language team understood, source code comments in english. in particular, check out file puzzle_lib.rb.

the approach indeed straightforward backtracking algorithm, think way go. can't it's easy though, far remember 3-d aspect bit challenging. implemented 1 optimization: find symmetries beforehand , try each unique orientation of piece. idea more characteristic pieces are, less options placing pieces exist, can prune early. in case of many symmetries, there might lots of possibilities , want inspect ones unique symmetry.

basically algorithm works follows: first, assign fixed order sides of cube, let's number them 0 5 example. execute following algorithm:

def check_slots():     each edge e:         if slot adjacent e filled:             if 1-0 patterns of piece edges (excluding corners)                    have xor != 0:                 return false             if corners not "consistent":                 return false     return true  def backtrack(slot_idx, pieces_left):     if slot_idx == 6:         # finished, found solution, output or whatever         return     each piece in pieces_left:         each orientation o of piece:             fill slot slot_idx piece in orientation o             if check_slots():                 backtrack(slot_idx + 1, pieces_left \ {piece})             empty slot slot_idx 

the corner consistency bit tricky: either corner must filled 1 of adjacent pieces or must accessible yet unfilled slot, i.e. not cut off assigned pieces.

of course can ignore drop or of consistency checks , check in end, seeing there 8^6 * 6! possible configurations overall. if have more 6 pieces, becomes more important prune early.