N-Queens ([H]ard|forum)

[sedarious]

There is a challenge up at hardforum for the N-Queens problem. It was posted by DrPizza who also posts on these boards at times. Anyway, just posting if anyone was interested...

[Strike]

I posted this answer a long time ago on the CCAE:

http://www.codeexamples.org/cgi-bin/c2h/hl.cgi?filename=queens.lisp&type=HTML-detail

[Tarkus]

Perhaps we should one up them and make a program which solves for any type of peice... Hmmm, maybe I'll start coding.

[Dru Lee Parsec]

There is a concept used in chess playing programs called "Bit Boards". Essentially this is a 64 bit piece of data that tells us things like "What squares have white pieces on them?", "What squares is the queen attacking?", etc. For example. If there is a Queen in theupper right hand corner of a chess board (square a8 in algebraic notation) then the Bit Board for "What squares is this Queen attacking" would look like this:



11111111
11000000
10100000
10010000
10001000
10000100
10000010
10000001


The Bit Board for a Queen on b2 would be this:


01000001
01000010
01000100
01001000
01010000
11100000
11111111
11100000


Now, there are also Bit Boards for things like "What square is my queen on?" So the Bit board for the Queen at a8 would be this:


10000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000


The reason this is significant is because if you take the Bit Board with the one square set (My queen is on a8 ) and you XOR it with the Bit Board for "What squares is my Queen on b2 attacking?" then if they are not attacking each other the XOR result is 0. If it's anything other than 0 then there is an overlap and one queen is attacking the other. Therefore it seems that by building a set of bit boards and using XOR you could solve the 8 Queens problem for any piece.

In fact, I would expect that there would be a solution for 8 rooks or 14 Bishops or 24 Knights. (How I arrived at these numbers is left as an exercise for the student;) )

Could be an interesting challenge. Do Bit Boards sound like a useful technique?

[stuka]

Dru Lee: does sound like a useful technique, but wouldn't the AND be a better/simpler technique? That way, you just take the full Bit Board for the queens, and any nonzero bits would indicate a conflict. Of course, I think there's a slight problem here - there are 64C8 possible configurations for the 8 queens problem, which is pretty large - I'm sure other algorithms are better.

[Strike]

Yeah, what the program I linked to above does (which is really my extending an implementation solving the less generic 8 queens problem to n-queens) is actually walk through all the possible solutions, if I recall correctly.

Side note - the solution space for a given n doesn't correlate well with n itself, which I find odd. Here are the number of solutions for n from 0 to 12 (okay so 0, 1, 2, and 3 are corner cases that maybe should be ignored).


0: 0
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
11: 2680
12: 14200

[stuka]

Strike: 2 queens == no solutions?

[Strike]

Originally posted by Stuka
Strike: 2 queens == no solutions?
2 queens on a 2x2 board, nope

I didn't check the hardocp forums, but my understanding of the problem is N queens on an NxN board

[Strike]

I just thought of something else:

Stuka: anything more than 8 queens on an 8x8 board is impossible, silly :)

[stuka]

oh - heh, I forgot the problem was N on NXN (guess I oughta read 'em before I talk, eh?)

[sedarious]

Strike,

Do you test ALL possibilities??? Even like all 8 queens on the same row? Or are you using permutations? Testing ALL possibilities is rather exhaustive. All solutions lie in the permutations of the string 1->N (N! permutations)...

Dru,
Using a bitboard seems like a good amount of work to test for collisions. I use a permutation array to go through possibilities. This ensures that there are no Horizontal or Vertical collisions. Here is my phpcode (that is broken and I don't know why right now) for solving the system...


//removed

[Strike]

sedarious, I'm pretty sure the algorithm I use (I didn't even write it, it came from my textbook at the time) uses a less naive approach than exhausting everything now that I've thought about it some. I'm quite sure that it doesn't even attempt placing another queen in the same column and also rather sure that it doesn't try doing so in the same row either. So, it'd really be (8^2 * 7^2 * 6^2 * ... * 2^2 * 1) instead of (64!/(64-8)!), which is more believable.

[Dru Lee Parsec]

Strike: Are you checking for diagonal collisions as well?
If Queen a is at aX, aY and queen b is at bX, bY then deltaX = aX-bX and deltaY = aY-bY. If ABS(deltaX) == ABS(deltaY) then they're on the same diagonal.

Damn, I wish I had time to code for fun. I'd love to write this program just for fun.

[Strike]

Yeah, it checks for diagonals as well, I'm just not sure if it pre-emptively throws those out when constructing a new move to try.

[sedarious]

Here is some code that actually works (C++). I am trying to work on a few more eliminations...

[bwkaz]

The ncurses .tar.gz package has a version written in C that works just fine, as well. I could post it, but that wouldn't be very original, now, would it? ;)