4 ms·
> While, I haven’t found a similar recursive solution for N-Queens, I know there’s a polynomial solution out there. How do you know that?
by ggchappell 14y ago
> While, I haven’t found a similar recursive solution for N-Queens, I know there’s a polynomial solution out there.
How do you know that?
- xiaoma 14y agoI saw some research talking about polynomial complexity for N-Queens come up in a google search. If someone has published a paper about a problem like this generally means that the time-complexity they're writing about doable but very hard. I didn't click any of the links though, since I wanted to keep working the problem.
- Someone 14y ago"A polynomial time algorithm for the N-Queens problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4685 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.4... (haven't completely read it, but I think they waive their hands too much when argumenting that their algorithm will not get stuck too often) Also: "Explicit solutions to the N-queens problem for all N": http://dl.acm.org/citation.cfm?id=122322 http://dl.acm.org/citation.cfm?id=122322 (paywalled) Haskell code for a (that?) closed-form solution: https://gist.github.com/IanCal/1858601 https://gist.github.com/IanCal/1858601