Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @VizGhar,validated by @cedricdd,@Timinator and @yhuberla.
If you have any issues, feel free to ping them.
I don’t understand how to solve the last two tests (“Empty board L” and “Empty board J”). The search space is really huge to place the 15 tetrasticks on an empty board. Even after 100 million backtracking iterations I’ve still searched only tiny fraction of the search space. Any hints?
What programming language are you using? Have you tried any optimisation on backtracking? For example, the order in exploring the search space?
Trying it in Perl at the moment. No, I’m not using any special optimization, just brute-force backtracking testing all tetrastick positions with all of the (non-equivalent) flip/rotation combinations in the order given in the puzzle.
Do you have any suggestions for optimizing the backtracking?
I understand that the order of placing the tetrasticks on the board doesn’t matter (I just need to output them in the desired order when a solution is found). Which order is the best? Using the “biggest” tetrasticks first (the ones with the biggest area)?
Minimum Remaining Values (MRV) works well for this puzzle. This file contains an overview of some heuristics that can be used, and MRV is mentioned on page 19. You may also try other heuristics mentioned in the file.
Hmm. trying to estimate the total search space. I think it’s C(29,15)*15!*C(16,15)=16,219,346,721,177,600,000,000. The reasoning: There’s 60 segments and each letter is 4 segments. And out of the 36 positions only 29 can be the upper/left origin of a letter blit pattern. So only 15 of the 16 can be chosen to fill the board which is 16 ways. And there’s 15! ways of ordering the 15 into the chosen cells. it’s just an estimate, but it’s actually smaller than i thought by about 8 digits. It should be even smaller, who has a better estimate? here’s some heuristics of an empty board:
Possibles count by location on empty board (upper/left letter origin):
0 1 2 3 4 5
0: 88 88 87 75 32 1
1: 88 88 87 75 32 1
2: 87 87 86 74 31 0
3: 75 75 74 62 19 0
4: 32 32 31 19 1 0
5: 1 1 0 0 0 0
Total fits: 1529
Fits per Letter: F=160 H=160 I=24 J=160 L=120 N=120 O=25 P=160 R=128 T=64 U=80 V=64 W=64 X=16 Y=120 Z=64 combos=1.1673330234144E+29
Orientations per letter: F=8 H=8 I=2 J=8 L=8 N=8 O=1 P=8 R=8 T=4 U=4 V=4 W=4 X=1 Y=8 Z=4
scale size: F=1200 H=1200 I=108 J=1200 L=1260 N=1260 O=112.5 P=1200 R=1600 T=800 U=600 V=800 W=800 X=200 Y=1260 Z=800
sorted: R L N Y F H J P T V W Z X U O I
maybe a screwed it up. mult by 88/16 avg. orientations = 95,153,500,764,241,920,000,000
I can solve the puzzle. However I did a little extra. trying to see what other empty boards are solvable given other Missing pieces. So out of the 16, I find solutions when the missing piece is J H N L or Y. but none of the others. As if the 11 are necessary for any proper solution of an empty board. Has anyone else found any of the solutions where the missing piece is one of the other 11? the solutions found take <1s, but the unfound take awhile to quit even at 350k nodes/s (throttled).
Nice puzzle again !
As for polyominoes I think it is an hard one.
The transformation from polyominoes is quite still a challenge with multiple ways to fall in issues as multiple transformations of coordinates and datas are needed to set correctly each figure and its transformations.
MAy my code is more complicated than it would need but anyway, the optimization matters.
Special thanks to @PatrickMcGinnisll for the optimal sorting, even with it I’m not able to pass all the tests + validators. ‘I’ and ‘O’ needs to be swapped for the test 7.