Fun chess problem

[Tazo]

i dont get it 

[R.a.B.B.i.T]

Cause Blaze sucks at explaining things.

[Hdx]

Code Select Expand


00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000
A friend of mine came up with this.
~-~(HDX)~-~

[CrAzY]

Code Select Expand


00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000
A friend of mine came up with this.
~-~(HDX)~-~

Funny it comes out to be eight '0's and '1's.
Haha, byte it up!

Code Select Expand


01
10
80
20
40
02
08


Excuse me if I did that wrong.  Its been a while since I've converted.

[Yoni]

I will define a Valid Queen Placement and a Correct Queen Placement on an n*n chessboard:

Valid Queen Placement (VQP):
A placement of n queens on an n*n chessboard such that there are no 2 queens on the same row and no 2 queens on the same column.

Correct Queen Placement (CQP):
A VQP, where no 2 queens are on the same diagonal.

The problem is finding a CQP.

Encoding a VQP mathematically

As Nate noted, the set of VQPs is isomorphic to the set of permutations of (0, 1, 2, ..., n - 1).
The isomorphism:
Given a VQP, the i'th row has a queen only on the j'th column (where the j of each i is unique). Therefore, the permutation (j1, j2, ..., jn) uniquely describes the VQP.

Example:

x.......
..x.....
...x....
....x...
.......x
.x......
......x.
.....x..

This VQP matches the permutation: 0, 2, 3, 4, 7, 1, 6, 5.

Therefore, there are n! possible VQPs on an n*n board (since there are n! isomorphic permutations).

Determining whether a VQP is a CQP

Given some VQP, we need to determine that no 2 queens are on the same diagonal.
When are 2 queens on the same diagonal?

Proposition 1: Two queens are on the same diagonal if and only if, when you draw a rectangle such that the 2 queens are on opposite corners of the rectangle, this rectangle is a square.

This is true because the diagonal that they are on is one of the diagonals of the square I defined.

Proposition 2: Two queens are on the same diagonal if and only if their horizontal distance is equal to their vertical distance.

This follows directly from proposition 1.

Proposition 3: Given the permutation (A[0], A[1], ..., A[n-1]) of the VQP, the queens "i" and "j" are on the same diagonal if and only if |i - j| = |A - A[j]|.

This is gained by applying the isomorphism on the result of Proposition 2.
From this, we can isolate all CQPs:

A VQP (A[0], A[1], ..., A[n - 1]) is a CQP if and only if for all pairs i, j where i != j:
|i - j| != |A - A[j]|

Finding a better representation

Working algebraically:

|i - j| != |A - A[j]|
i - j != A - A[j]     and     j - i != A - A[j]
A - i != A[j] - j     and     A + i != A[j] + j

The last line is the key.
If we build 2 alternate arrays,
B = A - i for all i
C = A + i for all i

This translates to:

B != B[j]     and     C != C[j]

Therefore, we can determine whether a given VQP is a CQP in O(n log n) time. (Why?)

Finding all CQPs
Python:

Code Select Expand


def PermutationFix(number, pivot):
if number < pivot:
return number
return number + 1

def Permutations(n):
if n < 1:
return
if n == 1:
yield [0]
return

for initial in xrange(n):
for perm in Permutations(n - 1):
yield [initial] + [PermutationFix(number, initial) for number in perm]

def TestCQP(VQP):
n = len(VQP)
Plus = [VQP[i] + i for i in xrange(n)]
Minus = [VQP[i] - i for i in xrange(n)]
if len(set(Plus)) == n and len(set(Minus)) == n:
return True
return False

def AllCQPs(n):
return filter(TestCQP, Permutations(n))


[Ban]

Or you could just whip out a chess board and do it there. I'll do it when I get home.

[disco]

Id do it that way but i dont have 8 queens .

[MyndFyre]

Id do it that way but i dont have 8 queens .

Huh.  Well.... maybe you could put other pieces on the board and just *say* they're queens?

[R.a.B.B.i.T]

He has ADHD.