Probably two weeks have passed since the initial failure of the original code logic to find a solution to fit all 12 Pentominoes into a 12 by 5 space. After ironing out a few bugs in the initial code, it did manage to find solutions for 5,8,10 and one time 11 pieces. However, even after running overnight, it failed to find a solution to the full 12 piece problem. I think the code is sound, it’s just that it relies on chance to find a solution and with the large number of iterations required to solve for 12 pieces it is just very unlikely to randomly be selected. Eventually it should work – I might run this exe on an AWS cloud based PC which can easily be left to run for a week if required.
The following modifications in the logic resulted in success (and some very spaghetti like code.)
- The piece order can now be read in from data statements, and in the future can be made random. Normally I start off with the “X” pentomino since there are fewer possible starting solutions (this piece has no reflections or rotations).
- For a given starting position for piece1 the code evaluates all possible legal positions for piece2,3,4…and so on until no more solutions are found. It then moves back onto the next position of the previous piece until a full solution is found for all 12 pieces. This way ensures that the solutions tested run from left to right, so this algorithm has a kind of natural packing whilst still being a brute force search. If left to run “forever” this code should eventually find all 1010 possible solutions for the 12×5 fitting problem.
This version of the code has already produced two out of the 1010 solutions with the same starting position for the X piece. I’m happy that my initial goal has been achieved, within the timeframe assigned. Remaining tasks (which probably do not merit further posts) are:
- truly random piece order, starting with user decided starting piece.
- bring in piece reflections
- Only reflect or rotate pieces which need it (at the moment all pieces are rotated which is a bit wasteful.
- Simplify code logic and introduce more subroutines to reduce duplicated code.
- More advanced “hole checking” routines to reduce some spurious interim solutions
- Algorithm to weight solutions to proceed to faster convergence.
- Version which will find all possible solutions.
- Bring in some AI algorithms
- Recode in Python or something other than BASIC.
Watch this space for any progress reported !