- Traden4Alpha
**Posts:**23951**Joined:**

Our town has a puzzle maker that specializes in puzzles with whimsy pieces such as these:

Liberty Puzzles? I always think that calling things "Liberty This" and "Freedom That" as Americans are wont to do is virtually communist. It's the sort of thing the Russians and Chinese do.

Cool, does he have Escher tilings?

- Traden4Alpha
**Posts:**23951**Joined:**

There are no Eschers that I know of but there is a Pieter Bruegel (one of my favorite artists) puzzle of "Children's Games" in which many of the whimsey pieces are children playing which makes it hard to spot the painted bits of children playing.

- Traden4Alpha
**Posts:**23951**Joined:**

Yes, {Liberty, Freedom, Patriot} are magic incantations that if repeated often enough become true or at least they seems that way.Liberty Puzzles? I always think that calling things "Liberty This" and "Freedom That" as Americans are wont to do is virtually communist. It's the sort of thing the Russians and Chinese do.

But aren't all countries forged from a combination of iron will and ironic slogans?

And we used to use Imperial a lot! The default should be to name things after people, ideally me...something I practice!

At those prices you aren't going to give up too soon!There are no Eschers that I know of but there is a Pieter Bruegel (one of my favorite artists) puzzle of "Children's Games" in which many of the whimsey pieces are children playing which makes it hard to spot the painted bits of children playing.

- Traden4Alpha
**Posts:**23951**Joined:**

Indeed! Yet they are really nice puzzles made of laser-cut 1/4" wood.At those prices you aren't going to give up too soon!There are no Eschers that I know of but there is a Pieter Bruegel (one of my favorite artists) puzzle of "Children's Games" in which many of the whimsey pieces are children playing which makes it hard to spot the painted bits of children playing.

And they are far cheaper on a $/hour basis than theatre tickets or Michelin-starred restaurants.

Here is a thought:

One possible puzzle is little rectangular tiles of various sizes that only fit in the square in one way (and its mirrors). This is probably equivalent to "bin packing" which is an NP-complete problem. Another classic NP-complete problem is 3SAT which is about finding boolean values for variables (x1=true, x2=true, x3=false) such that a sequence of clauses involving those variables are all true. This can likely be translated into puzzle shapes that have to match.

All these NP-complete problems are equivalently hard with no known polynomial time algorithm (only exponential). There will always be special cases that require exponential time'and If you can solve any NP-complete problem in polynomial time then you can solve *all* of then in polynomial time.

So IMO jigsaw is NP-complete and you won't be able to find a polynomial time algorithm.

One possible puzzle is little rectangular tiles of various sizes that only fit in the square in one way (and its mirrors). This is probably equivalent to "bin packing" which is an NP-complete problem. Another classic NP-complete problem is 3SAT which is about finding boolean values for variables (x1=true, x2=true, x3=false) such that a sequence of clauses involving those variables are all true. This can likely be translated into puzzle shapes that have to match.

All these NP-complete problems are equivalently hard with no known polynomial time algorithm (only exponential). There will always be special cases that require exponential time'and If you can solve any NP-complete problem in polynomial time then you can solve *all* of then in polynomial time.

So IMO jigsaw is NP-complete and you won't be able to find a polynomial time algorithm.

- Traden4Alpha
**Posts:**23951**Joined:**

Standard jigsaws only become NP-complete if the solver cannot reject a prospective solution with bounded M<<N pieces. That is, the solver faces a non-zero chance of placing N-1 pieces in what seems like a valid configuration only to find that the last piece fails to fit.

For most jigsaw puzzles, however, the piece shape and color patterns across the boundary are so unique that it's virtually impossible to incorrectly put even two pieces together.

That said, I have seen puzzles with identically-shaped innie & outie tabs (and large expanses of uniform color) where one can get trapped and have to undo a set of pieces that seemed to go together.

For most jigsaw puzzles, however, the piece shape and color patterns across the boundary are so unique that it's virtually impossible to incorrectly put even two pieces together.

That said, I have seen puzzles with identically-shaped innie & outie tabs (and large expanses of uniform color) where one can get trapped and have to undo a set of pieces that seemed to go together.

Last edited by Traden4Alpha on January 11th, 2017, 10:33 pm, edited 1 time in total.

Yes, good insight, the common puzzles are incrementally solvable and way to easy, there is an opportunity here!

this fractal puzzle looks difficult, very confusing.

this fractal puzzle looks difficult, very confusing.

- Traden4Alpha
**Posts:**23951**Joined:**

Love that fractal puzzle!Yes, good insight, the common puzzles are incrementally solvable and way to easy, there is an opportunity here!

this fractal puzzle looks difficult, very confusing.

One of the ancient versions of the Macintosh OS (maybe System 8. something?) came with a simple digital jigsaw puzzle that let one pick N. These days, with multi-finger touchscreen UIs and data logging systems, one could create an even better digital jigsaw puzzle system and gather empirical data on solver performance as a function of N.

GZIP: On