It is different from generating polyminos, but it is NP-hard problem too. I'm given polyminos with size 4, 5, 6, as an array.
'F':{'num':0b011110010,'width':3} #will be mutated to polymino as
((0,1,1),(1,1,0),(0,1,0)) #as printed
(0,1,1)
(1,1,0)
(0,1,0)
And I have a 2D array which is known for having at least one way to tile it full with the given polymino set.
The problem is to find the ways of tiling the array.
To solve the problem I made algorithm as,
A1. reverse the binary of all the possible rotation of given chips and add to dictionary,
Solver.keyset[tupleall(reverse_binary(objs.rotate(rots).shape))] = [[objs.name, rots, (0,0)]]
A2. check if the given array is in the dictionary
A3a. divide the array to solve by x,y axis, and solve for the smaller ones
A3b. add arrays which has solution, from the dictionary and solve for it
It works very well for small arrays,
a = Solver(((0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)))
a.chips(5,6) #chip sized for 5-6
a.solver()
a.info
[['6C', 3, (0, 0), '6D', 1, (0, 1)], ['6C', 1, (0, 1), '6D', 3, (0, 0)], ['6A', 2, (0, 0), '6A', 0, (1, 0)], ['6A', 3, (1, 0), '6A', 1, (0, 0)], ['6A', 0, (1, 0), '6A', 2, (0, 0)], ['6A', 1, (0, 0), '6A', 3, (1, 0)], ['6D', 3, (0, 0), '6C', 1, (0, 1)], ['6D', 1, (0, 1), '6C', 3, (0, 0)]]
(Well, I need to rip out some polyminos which has duplicated by rotation)
But for larger arrays, it costs excessive times.
1 - Does my algorithm worth to do it? - do I have alternative algorithms to solve it better? I tried for brute-force, adding all the possible ways, but it took too much time so that I still didn't get the answer for (8,6) array.
2 - Will allowing only one answers from each division would help? - It will numerously speed up to find few answers, but its diversity will lessens.
