Description Each row (not just horizontal, but also diagonal) add up to 38? There are 15 rows in all directions to complete, each made up of 3, 4 or 5 pieces. This brilliant concept allows you to complete the puzzle by using every number from 1 – 19. (professorpuzzle.com)
There are 121,645,100,408,832,000 permutations for this puzzle. Certainly not something you want to brute force.
Write a program that doesn't take a month of 24/7 calculating to find all the possible answers.
Using permutations and process of elimination, the program starts from the outer ring and works its way to the center in a spiral fashion.
If you go by the image above, it calculates the pieces in the following order:
- Tiles 9, 11, & 18
- Tiles 17 & 3
- Tiles 19 & 16
- Tiles 12 & 10
- Tiles 13 & 15
- Tile 14
- Tiles 8 & 6
- Tile 1
- Tile 7
- Tile 2
- Tile 4
- Tile 5
On my laptop, I'm able to get 12 solutions in ~13s +/- 1s.
I won't post the answers here, but if you really want to know the answers, you can obviously just run the program using python main.py
How do I run this?
- Clone this repository
- In the directory, run
pip install -r requirements.txt - Run main.py from your command line using
python main.py
Depending on the specifications of the computer you are using, the code may take a few seconds to run. The output shows a list of arrays contained valid solutions.
Why did you do this? Someone gave me this puzzle as a present, and I thought it was an interesting challenge.
- Most numpy functions compile to C.
- You can do static typing with numpy.
- Loops kill your performance. Use list comprehensions instead.
- Use iterators and generators.
- Use an efficient algorithim. If one doesn't exist, create one.