Hello, everyone. I think many of you have heard about the N queens puzzle. So, purely out of interest, I decided to write a program that can solve the puzzle on a scalable board. It incorporates the same techniques that are applied in chess engines. To me it was just fun to play around with, and after I finished this small project I figured why not share it with you guys.
You can check it out here: https://github.com/AaronAlfer/NQueensMagic
The source code is available (I documented it), and also you can download the executable and try it out yourself. I wrote a more in-depth description in the README file (go by the link). Please let me know what you think. Cheers!
Images:
https://drive.google.com/open?id=1uqJg3 ... xHstzvWU_p
https://drive.google.com/open?id=1qFx8S ... nIfXHIJTm-
N Queens Puzzle Algorithm
Moderators: hgm, Rebel, chrisw
-
- Posts: 4
- Joined: Sat Nov 25, 2017 11:45 am
- Location: Minsk, Belarus
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: N Queens Puzzle Algorithm
This took me about 5 minutes to put together. It uses a single core and it's about as fast as your program.
Code: Select all
#include <iostream>
int const N = 16;
unsigned a[N];
unsigned long n_solutions(unsigned n) {
if (n == N)
return 1u;
unsigned available = (1u << N) - 1ul;
for (unsigned i = 0; i < n; ++i)
available &= ~((a[i] << (n - i)) | a[i] | (a[i] >> (n - i)));
unsigned long result = 0ul;
for (; available; available &= available - 1) {
a[n] = available & -available;
result += n_solutions(n + 1);
}
return result;
}
int main() {
std::cout << n_solutions(0) << '\n';
}
-
- Posts: 4
- Joined: Sat Nov 25, 2017 11:45 am
- Location: Minsk, Belarus
Re: N Queens Puzzle Algorithm
Great job. It would be nice if it also yielded the combinations. Now, I doubt that it actually took you 5 minutes. Well, to write the code - sure, but you're obviously more experienced than I am in this kind of thing. I didn't spend much time on this particular part either - there's much more to that: different modes (to me the interesting mode was Completion, not this one), pre-calculations, serialization, UI, git, etc. I'm still a learner, and all of that was good experience for me. Anyway, thanks for your code.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: N Queens Puzzle Algorithm
Mine, Marcel van Kervinck's and Tony Lezard's 8Q approaches:
https://chessprogramming.wikispaces.com ... 0Bitboards
https://chessprogramming.wikispaces.com ... 0Bitboards
-
- Posts: 4
- Joined: Sat Nov 25, 2017 11:45 am
- Location: Minsk, Belarus
Re: N Queens Puzzle Algorithm
Oh I missed that article on CPW! Thanks. Besides, when I was studying the topic I found this site, and those guys basically search for a single solution for N ranging from 1 to 50. And their algorithm runs literally for weeks! I don't know why it takes them so long, and I honestly don't see the point because if you need just 1 solution, there are explicit solutions that don't involve any combinatorics. So if you wanna talk about my program's performance issues, now you see that I'm not that bad
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: N Queens Puzzle Algorithm
It took me 5 minutes because I've done this before (or very similar things), and because when I was in college I participated in programming contests with similar challenges.AaronAlfer wrote:Great job. It would be nice if it also yielded the combinations. Now, I doubt that it actually took you 5 minutes. Well, to write the code - sure, but you're obviously more experienced than I am in this kind of thing. I didn't spend much time on this particular part either - there's much more to that: different modes (to me the interesting mode was Completion, not this one), pre-calculations, serialization, UI, git, etc. I'm still a learner, and all of that was good experience for me. Anyway, thanks for your code.
Anyway, I wasn't trying to take away from what you wrote. I just saw the challenge and I went for it.
-
- Posts: 395
- Joined: Fri Aug 12, 2016 8:43 pm
Re: N Queens Puzzle Algorithm
Interesting problem.AaronAlfer wrote:Hello, everyone. I think many of you have heard about the N queens puzzle. So, purely out of interest, I decided to write a program that can solve the puzzle on a scalable board. It incorporates the same techniques that are applied in chess engines. To me it was just fun to play around with
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6
-
- Posts: 496
- Joined: Wed Mar 08, 2006 9:45 pm
- Location: Portland, OR
Re: N Queens Puzzle Algorithm
This is an entire topic on the Rosetta Code wiki, where you can see it implemented in a variety of algorithms in a hundred different programming languages.
http://rosettacode.org/wiki/N-queens_problem
http://rosettacode.org/wiki/N-queens_problem
-
- Posts: 4
- Joined: Sat Nov 25, 2017 11:45 am
- Location: Minsk, Belarus
Re: N Queens Puzzle Algorithm
Nice. I tested it, and I have to say that with 8Q it's fine but as soon as N gets any bigger, the algorithm gets really slow. The sorting part causes major slowdown.Fulvio wrote:Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: N Queens Puzzle Algorithm
It's instructive to understand where this code is getting slow: It is looping through every permutation, so even if there is a conflict between the first queen and the second queen, it will cycle through the (N-2)! ways of rearranging the other queens. If you use backtracking, you can skip all those possibilities in a single step.AaronAlfer wrote:Nice. I tested it, and I have to say that with 8Q it's fine but as soon as N gets any bigger, the algorithm gets really slow. The sorting part causes major slowdown.Fulvio wrote:Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6