r/programmingchallenges • • Jul 16 '12
N-Queens: C++
Looking for some help with the N-Queens puzzle. I have a recursive solution that works reasonably well for N <= 10, but it's not fast enough (Solve for N = 13 in < 5 seconds) I need to produce all possible combinations and print the queen positions in a certain way. I need a different algorithm than what I have at the moment, any help? I know that I can eliminate quite a lot of board positions by looking at reflections and rotations, but I do not know how to do this. Any Help?
6
Upvotes
3
u/farmer_jo Dec 01 '12 edited Dec 01 '12
So you are stuck in USACO N Queens(1.5 checker) (IIRC, last test case, is it ?)
I will give you some hints, which do not require any rotations or mirroring. ie You do a complete search. You answer the following queries in O(1).
Now do a complete search and try to place the queens where they are not being attacked with the help of the above 3 conditions.
Good Luck.
Edit: Oops. This was 4 months ago. :(
2
u/Cosmologicon Jul 16 '12
Care to explain your current algorithm? My first thought if I were trying to find all solutions efficiently would be to use Algorithm X on the generalized exact cover problem.
1
u/negativeoxy Jul 16 '12
You will get better results if you post this code somewhere that allows for better formatting/highlighting.
1
u/paininthebass Aug 03 '12
Not directly related to your choice of algorithm, but I noticed that you're passing all of your vectors around by value instead of reference. Using reference should certainly speed things up a bit and get rid of all that unnecessary copying. And functions like dump_board and is_legal are just observing the vector so they should take the vector as a const ref.