Given a standard 8x8 chess board, find the positions of 8 queens such that no queen threatens any other.  I have a very systematical (and non bruteforcing) way of solving it, I'll post the solution in a few days.

[quote author=nslay link=topic=11700.msg113693#msg113693 date=1116997847]
Given a standard 8x8 chess board, find the positions of 8 queens such that no queen threatens any other.  I have a very systematical (and non bruteforcing) way of solving it, I'll post the solution in a few days.
[/quote]

This was a fun relational programming exercise in my programming languages course. We were using Mozart-Oz as the language. Wonder if I can find the code...bah can't access blackboard :(

I don't know about a systematical way, but I did it intuitively in one shot:
[pre]
-----------------
|X| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |X| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
[/pre]
I'm interested to see what the systematical way is.  Obviously there are other ways to do this -- I *believe* can think of at least 7 other positions that would do this.  *shrug*

How do you play chess?

[quote author=UserLoser link=topic=11700.msg113743#msg113743 date=1117066270]
How do you play chess?
[/quote]

http://www.google.com/search?hl=en&q=how+to+play+chess

To whom was that question directed?

[quote author=MyndFyre link=topic=11700.msg113745#msg113745 date=1117066615]
[quote author=UserLoser link=topic=11700.msg113743#msg113743 date=1117066270]
How do you play chess?
[/quote]

http://www.google.com/search?hl=en&q=how+to+play+chess

To whom was that question directed?
[/quote]

Probably you. There is a flaw in your logic. Note the two c's conflict.

[pre]
-----------------
|c| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |c| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
[/pre]

[quote author=dxoigmn link=topic=11700.msg113772#msg113772 date=1117074902]
[quote author=MyndFyre link=topic=11700.msg113745#msg113745 date=1117066615]
[quote author=UserLoser link=topic=11700.msg113743#msg113743 date=1117066270]
How do you play chess?
[/quote]

http://www.google.com/search?hl=en&q=how+to+play+chess

To whom was that question directed?
[/quote]

Probably you. There is a flaw in your logic. Note the two c's conflict.

[pre]
-----------------
|c| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |c| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
[/pre]

[/quote]

Alright, stop drawing chess boards.  To make this efficient, I have found this problem is analogous to finding a sequence of numbers using 12345678 in which no countings may overlap.

Consider
24683571

Notice if I count from 1
I get 654321
which overlaps at 6 despite 8357 in between
this means if you position a queen in the last column in the 1st row, it will conflict with a queen in 3rd column positioned in the 6th row.

12345678
draws a perfectly diagonal line of queens.
Basically, the columns are the index of the digits, the digits themselves are the rows of placement.

So this should be easier to write numerically than drawing strange figures of chess boards with the ascii characters.  It is also easy to verify if you don't have a chess board.

[quote author=dxoigmn link=topic=11700.msg113772#msg113772 date=1117074902]
Probably you. There is a flaw in your logic. Note the two c's conflict.
[/quote]
Oooh good eye.  I need to go home and look at an actual board.  Doing this in Notepad doesn't work.  ;)

[quote author=MyndFyre link=topic=11700.msg113781#msg113781 date=1117076512]
[quote author=dxoigmn link=topic=11700.msg113772#msg113772 date=1117074902]
Probably you. There is a flaw in your logic. Note the two c's conflict.
[/quote]
Oooh good eye.  I need to go home and look at an actual board.  Doing this in Notepad doesn't work.  ;)
[/quote]

Pen and paper seem to work fine for me. Alternatively, you could write a program :P

[quote author=dxoigmn link=topic=11700.msg113782#msg113782 date=1117076548]
[quote author=MyndFyre link=topic=11700.msg113781#msg113781 date=1117076512]
[quote author=dxoigmn link=topic=11700.msg113772#msg113772 date=1117074902]
Probably you. There is a flaw in your logic. Note the two c's conflict.
[/quote]
Oooh good eye.  I need to go home and look at an actual board.  Doing this in Notepad doesn't work.  ;)
[/quote]

Pen and paper seem to work fine for me. Alternatively, you could write a program :P
[/quote]

Or you could numerically analyze it :P  It might be easier :D

No really, how do you play.  I never played it in my life (and don't want to learn so google link no bueno), just saying that I don't know how because sometimes I am random like that

Basicly you have two rows of pieces. The people in the front are called Pawns. Then you have several different pieces in the back row:
[quote]
Pawn   Pawn    Pawn    Pawn   Pawn  Pawn  Pawn  Pawn
Rook   Knight   Bishop  Queen  King  Bishop  Knight  Rook
[/quote]

Pawns can move forward 1 space or 2 on its first move. The Pawn can only attack diagonally 1 space.

The Rook looks like a tower. It can move straight left or right as many spaces as it can without hitting any other pieces.

The Knight can move in an L shape. Example: forward 2, left 1. backwards 2, right 1. Left two, left one. Right two, left one.
The knight can also jump over pieces.

The Bishop can move diagonally.

The Queen can move in any direction. This is one of the most useful pieces.

The king is the most important piece. It can move in any direction 1 space. If the king is in a position that it can be attacked, its called Check. The player who owns the king must either move the king so it isn't in attack range of any opponents pieces, kill the attacking piece, or move something infront of it. If it cannot it is called Checkmate and the attacking player has won.

The board is a grid of black and white squares. The queen show be on the same colour square of what she is.  If your black, the queen should also be on black square, and the king on the white. The board is a grid of 8x8.

Here is an example of a set up board.

[quote]
Rook  Knight   Bishop   King   Queen  Bishop Knight  Rook
Pawn  Pawn   Pawn      Pawn  Pawn   Pawn  Pawn  Pawn





Pawn   Pawn    Pawn    Pawn   Pawn  Pawn  Pawn  Pawn
Rook   Knight   Bishop  Queen  King  Bishop  Knight  Rook
[/quote]

Well, I think that is the basics of the game, if you are still interested go buy a book on the game, they can give you some good pointers and good strategy's to help you on your chess carrear.

I think you screwed up your knight examples.

Left two, left one. That would be convenient in some cases.

[quote]
[ ] [X] [ ]
[ ] [ ]  [ ]
[X][ ]  [ ]
[/quote]
You could from from X to X

i dont get it  ;D

Cause Blaze sucks at explaining things.

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

[quote author=HdxBmx27 link=topic=11700.msg113925#msg113925 date=1117219501]
[code]
00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000[/code]
A friend of mine came up with this.
~-~(HDX)~-~
[/quote]
Funny it comes out to be eight '0's and '1's.
Haha, byte it up!

[code]
01
10
80
20
40
02
08
[/code]

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

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.
[hr]
[u]Encoding a VQP mathematically[/u]

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:
[pre]
x.......
..x.....
...x....
....x...
.......x
.x......
......x.
.....x..
[/pre]
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).
[hr]
[u]Determining whether a VQP is a CQP[/u]

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[i] - 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[i] - A[j]|
[hr]
[u]Finding a better representation[/u]

Working algebraically:

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

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

This translates to:

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

Therefore, we can determine whether a given VQP is a CQP in O(n log n) time. (Why?)
[hr]
[u]Finding all CQPs[/u]
Python:
[code]
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))
[/code]

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

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

[quote author=Disco link=topic=11700.msg114412#msg114412 date=1117652754]
Id do it that way but i dont have 8 queens :(.
[/quote]

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

He has ADHD.