If we accept that there exist a number of squares we can't fill completely
with different squares...
How can we cover as much as possible of the square puzzle surface?
Of course we prefer a perfect fit, but this seems impossible with smaller puzzles (below 110 x 110).
In the beginning we hardly believed this could be such a big problem.
It turned out to be one of the thoughest mathemetical jigsaw puzzles we met!
Who can solve it?
The three of us have puzzled and programmed on this isue with a lot of pleasure:
- Ed van Eersel
- Bart te Molder
- Pascal Huybers
This hobby started with a programming contest by Prospero,
but the original idea is much older. We found a perfect solution (no open space!) of the puzzle of 175 in a
book issued in 1956. This has been a great thinking job! They found it (and some perfect rectangles) by using mathematical graphs.
Our algorithm is a special type of
backtracking : e.g. depth-first traversal.
This means that we firstly try a square on every possible place, before you replace it for another one.
We believe the current super computers (using backtracking algorithms)
are still not able to solve the 175 puzzle within 10 years.
We met a surprising link with the Fibonacci numbers!
Still many questions remain open:
1) What is the smallest perfect solution?
2) What is the largest puzzle with no perfect solution? (if it exist)
What can be proved on a mathemetical way on this jigsaw puzzle?
Our programs have gone through all squares upto N=96, and are still
running on some larger puzzles, we did not find any perfect solution yet this way.
If you know something more (or just interested) you are welcome to contact us,
All solutions of puzzles 2 upto 100
How to write a computer program that solves this puzzle?
We used backtracking.
Reactions are welcome - mail to: