N Queens Puzzle Algorithm

[AaronAlfer]

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-

[AlvaroBegue]

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&#91;N&#93;;

unsigned long n_solutions&#40;unsigned n&#41; &#123;
  if &#40;n == N&#41;
    return 1u;
  unsigned available = &#40;1u << N&#41; - 1ul;
  for &#40;unsigned i = 0; i < n; ++i&#41;
    available &= ~(&#40;a&#91;i&#93; << &#40;n - i&#41;) | a&#91;i&#93; | &#40;a&#91;i&#93; >> &#40;n - i&#41;));
  unsigned long result = 0ul;
  for (; available; available &= available - 1&#41; &#123;
    a&#91;n&#93; = available & -available;
    result += n_solutions&#40;n + 1&#41;;
  &#125;
  return result;
&#125;

int main&#40;) &#123;
  std&#58;&#58;cout << n_solutions&#40;0&#41; << '\n';
&#125;

[AaronAlfer]

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.

[Gerd Isenberg]

Mine, Marcel van Kervinck's and Tony Lezard's 8Q approaches:

https://chessprogramming.wikispaces.com ... 0Bitboards

[AaronAlfer]

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

[AlvaroBegue]

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.

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.

Anyway, I wasn't trying to take away from what you wrote. I just saw the challenge and I went for it.

[Fulvio]

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

Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6

[IanO]

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

[AaronAlfer]

Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6

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.

[AlvaroBegue]

Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6

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.

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.