News for hackers. Stuff that matters.

A comment on The N-Queens completion problem is NP-hard. Parent comment

Re:The N-Queens completion problem is NP-hard by imaginenore on Monday September 04, 2017 @01:03PM (#15169456)
If you can solve it at all for even 50x50 would mean a revolution in certain algorithmic fields.
[ Parent | on HN ]
Re:The N-Queens completion problem is NP-hard by fooker on Tuesday September 05, 2017 @05:38PM (#15179342)
That is surprising.

Can you point me to a concrete reference about the 50x50 number?

Modern SAT solvers should be able to handle that, maybe with a few problem specific tweaks.

[ Parent | on HN ]
Re:The N-Queens completion problem is NP-hard by thomasahle on Monday September 04, 2017 @04:50PM (#15170783)
That's a bit too simply put, unfortunately. You could do that with an `e^{n/50}` solution. That wouldn't really be unexpected.
[ Parent | on HN ]