## 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

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:

AlvaroBegue
Posts: 927
Joined: Tue Mar 09, 2010 2: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&#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

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

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

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

### Re: N Queens Puzzle Algorithm

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

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:

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

### 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

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

### Re: N Queens Puzzle Algorithm

Fulvio wrote:Interesting problem.
This is my simple 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.

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

### Re: N Queens Puzzle Algorithm

AaronAlfer wrote:
Fulvio wrote:Interesting problem.
This is my simple algorithm: