6
|
3056 Views
|
5 Replies
|
10 Total Likes
View groups...
Share
GROUPS:

# Solving the Queens Puzzle with Graph Theory

Posted 9 months ago
5 Replies
Sort By:
Posted 8 months ago
 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?
Posted 9 months ago
 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 9 months ago
 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!
Posted 9 months ago
 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 9 months ago
 -- you have earned Featured Contributor Badge Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!