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[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';
}

[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.