Solving a wooden puzzle using Haskell

_ache_

I did the exact same thing in C++ 10 years ago ! Same puzzle. :D

I wonder if I can still find the source code. (Found it! Source code was in French and not very elegant but it works, glorified brute force aka Backtracking).

I'm eager to improve it to find ALL solutions, not just the first one.

https://ache.one/polycube.cpp

gerdesj

Good job. When you said "in French" ... well, "IS_VALIDE" is quite something to see!

It seems you are fluent in Franglais - https://en.wikipedia.org/wiki/Franglais. I have only respect for someone who can flit between languages with that facility.

fjfaase

Solving this kind of puzzles is equal to solving an exact cover. Exact cover is known to be NP-complete.

OskarS

Indeed it is, and Donald Knuth spends a substantial part of the latest volume (4B) of The Art of Computer Programming on solving exact cover problems like this using Dancing Links! He presented an earlier version of the algorithm in this legendary article [1], but as good as that article is, the book is even better (and the algorithm improved!). It also has tons of exercises like this. Cannot recommend it highly enough.

[1]: https://arxiv.org/abs/cs/0011047

kqr

I have a 2D variant of this puzzle and got curious about the solvability of various starting positions so I made this graphical tool: https://xkqr.org/info/tetrispuzzlesolver.html

Being able to solve starting from various constraints have turned out really useful for building an intuition for the puzzle.

asplake

I missed any link to the puzzle itself. Does anyone here know where you might get one from?

_ache_

Here is the one from the article.

https://linsoluble-casse-tete.fr/products/25-y-constantin

HN

Solving a wooden puzzle using Haskell

Solving a wooden puzzle using Haskell