Message Boards Message Boards

Solving the Queens Puzzle with Graph Theory

5 Replies

Cool idea! The post left me wondering what the complexity of finding a solution is. After some detective work, I have found this:

Bell, J., & Stevens, B. (2009). A survey of known results and research areas for n-queens. Discrete mathematics, 309(1), 1-31.

Check out Theorem 3 - would be sweet to implement one of these, and have it as a WFR!

Apparently, the n-queens completion puzzle is NP-hard, see:

Gent, I. P., Jefferson, C., & Nightingale, P. (2017). Complexity of n-queens completion. Journal of Artificial Intelligence Research, 59, 815-848.

Would it be difficult to allow for pre-set placements, per the completion puzzle?

Hi Alejandra! Did you know we also solved this as an example for WFR`DepthFirstSearch? The code is under "Neat Examples", and I reproduce it here for purpose of a timing test:

The time for System is only $3$ to $4\times$ faster than WFR, when the compile advantage could very well be $10\times$ or more. Time can depend on a lot of things, including optimization mistakes made by the programmer. Instead, we can just trace the computation and ask how many nodes did the search tree have? Answers to this question are typically order-dependent, and search trees can be minimized through heuristics. There's a sizeable literature on this. For example, I'm sure that Donald Knuth has written about it in connection with exact cover problems.

Unfortunately, we don't know much what's going on under the hood of FindIndependentVertexSet, so it's not possible presently to compare the search trees directly. Maybe you can ask Charles or Yan if they know how to trace search trees or at least output statistics about vertex count per level.

If you want to be more "independent", you can also try to write your own search code starting from the queen graph and iterating through successive placements by deleting vertices. This could be done depth-first using DepthFirstSearch, or breadth-first using NestWhileGraph. Right away there is an issue, should the first choice have a branching ratio $8$ or $8^2$ or something else?

If you can figure out how to compare search trees, and potentially minimize them, that would make an interesting chapter in our upcoming book about game theory.

POSTED BY: Brad Klee

Hi Brad! Yes! I actually got the inspiration from your post "Analyzing a Competitive New Method for GenerateTiling," so thank you for the idea!

I agree with you that the compile advantage could be 10× or more by optimizing the code. It would be really cool to know how many nodes the search tree has. I can totally ask about it and check if it's possible to compare the search trees directly or at least output statistics about vertex count per level based on the algorithm to see if there is an interesting result for the chapter in your upcoming book about game theory. I will definitely get back to you, hopefully with some helpful results!

In your other recent post, there's now some competitive timing statistics, where it looks like DancingLinksX (DLX) wins the race. A similar approach is possible for the queens problem, but it looks like DLX is not especially fast in this case. Then it occurred to me that QueenGraph could be used with an n-tier level structure, and indeed this appears to lead to a faster time with DepthFirstSearch. I have an idea how to keep going with this calculation, and I will contact you about that soon. Calculations are included here:

POSTED BY: Brad Klee

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract