from Hacker News

How wooden puzzles can destroy dev teams

by johncs on 7/6/15, 10:59 PM with 9 comments

• by ChrisLomont on 7/7/15, 7:21 PM

  Interestingly, when I run this through an old Dancing Links [1] based solver I wrote a while back for solving general puzzles, it solves the first one in 0.04 seconds, uses 65 columns, 242 rows, does 181510 de-queues, and finds a unique solution.

  The same solver on the hard version runs in 0.01 seconds, 67 columns, 272 rows, 245626 de-queues, and finds no solutions.

  So as others have noted, the hard puzzle solution must be some weird rotation, and/or not spaced on "integral" coordinates.

  Since I don't have time to write such a solver, I will leave it for now :)

  Note: if you have not looked at the Dancing Links paper by Knuth and learned how to use it to solve backtracking problems, you should. It's amazingly useful for solving such problems, for enumerating all solutions, and it is fast and completely general.

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

• by shard on 7/7/15, 12:00 AM

  Assuming the solvers that they wrote searched the problem space correctly, the hard side probably violates some assumption. My guess would be that on the hard side the pieces can lock into some sort of 3D structure.

• by fsk on 7/6/15, 11:55 PM

  What makes this a HARD puzzle is that the pieces don't completely fill the area. That dramatically increases the solution search space.

• by 0x0 on 7/6/15, 11:57 PM

  Any hints for the solution, then?

• by fredgrott on 7/7/15, 12:07 AM

  if they ever read Penrose it would have taken less time :)