N Queens Puzzle Algorithm

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AaronAlfer
Posts: 4
Joined: Sat Nov 25, 2017 10:45 am
Location: Minsk, Belarus

N Queens Puzzle Algorithm

Post by AaronAlfer » Fri Dec 15, 2017 12:00 pm

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
Posts: 927
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: N Queens Puzzle Algorithm

Post by AlvaroBegue » Fri Dec 15, 2017 3:09 pm

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
Posts: 4
Joined: Sat Nov 25, 2017 10:45 am
Location: Minsk, Belarus

Re: N Queens Puzzle Algorithm

Post by AaronAlfer » Fri Dec 15, 2017 4:18 pm

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
Posts: 2226
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: N Queens Puzzle Algorithm

Post by Gerd Isenberg » Fri Dec 15, 2017 5:13 pm

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

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

AaronAlfer
Posts: 4
Joined: Sat Nov 25, 2017 10:45 am
Location: Minsk, Belarus

Re: N Queens Puzzle Algorithm

Post by AaronAlfer » Fri Dec 15, 2017 6:44 pm

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 :D

AlvaroBegue
Posts: 927
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: N Queens Puzzle Algorithm

Post by AlvaroBegue » Fri Dec 15, 2017 7:02 pm

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.
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
Posts: 211
Joined: Fri Aug 12, 2016 6:43 pm

Re: N Queens Puzzle Algorithm

Post by Fulvio » Sat Dec 16, 2017 1:39 am

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
Interesting problem.
This is my simple algorithm:
https://wandbox.org/permlink/HB2biLawqMOAGdC6

IanO
Posts: 486
Joined: Wed Mar 08, 2006 8:45 pm
Location: Portland, OR
Contact:

Re: N Queens Puzzle Algorithm

Post by IanO » Sat Dec 16, 2017 5:17 am

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
Posts: 4
Joined: Sat Nov 25, 2017 10:45 am
Location: Minsk, Belarus

Re: N Queens Puzzle Algorithm

Post by AaronAlfer » Sat Dec 16, 2017 12:22 pm

Fulvio wrote: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
Posts: 927
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: N Queens Puzzle Algorithm

Post by AlvaroBegue » Sat Dec 16, 2017 1:38 pm

AaronAlfer wrote:
Fulvio wrote: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.

Post Reply