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.