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 from: nslay on May 25, 2005, 12:10 AM
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.
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:
-----------------
|X| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |X| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
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 from: UserLoser on May 25, 2005, 07:11 PM
How do you play chess?
http://www.google.com/search?hl=en&q=how+to+play+chess
To whom was that question directed?
Quote from: MyndFyre on May 25, 2005, 07:16 PM
Quote from: UserLoser on May 25, 2005, 07:11 PM
How do you play chess?
http://www.google.com/search?hl=en&q=how+to+play+chess
To whom was that question directed?
Probably you. There is a flaw in your logic. Note the two c's conflict.
-----------------
|c| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |c| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
Quote from: dxoigmn on May 25, 2005, 09:35 PM
Quote from: MyndFyre on May 25, 2005, 07:16 PM
Quote from: UserLoser on May 25, 2005, 07:11 PM
How do you play chess?
http://www.google.com/search?hl=en&q=how+to+play+chess
To whom was that question directed?
Probably you. There is a flaw in your logic. Note the two c's conflict.
-----------------
|c| | | | | | | |
-----------------
| | | | | | |X| |
-----------------
| | | | |X| | | |
-----------------
| | |X| | | | | |
-----------------
| | | | | | | |X|
-----------------
| | | | | |c| | |
-----------------
| | | |X| | | | |
-----------------
| |X| | | | | | |
-----------------
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 from: dxoigmn on May 25, 2005, 09:35 PM
Probably you. There is a flaw in your logic. Note the two c's conflict.
Oooh good eye. I need to go home and look at an actual board. Doing this in Notepad doesn't work. ;)
Quote from: MyndFyre on May 25, 2005, 10:01 PM
Quote from: dxoigmn on May 25, 2005, 09:35 PM
Probably you. There is a flaw in your logic. Note the two c's conflict.
Oooh good eye. I need to go home and look at an actual board. Doing this in Notepad doesn't work. ;)
Pen and paper seem to work fine for me. Alternatively, you could write a program :P
Quote from: dxoigmn on May 25, 2005, 10:02 PM
Quote from: MyndFyre on May 25, 2005, 10:01 PM
Quote from: dxoigmn on May 25, 2005, 09:35 PM
Probably you. There is a flaw in your logic. Note the two c's conflict.
Oooh good eye. I need to go home and look at an actual board. Doing this in Notepad doesn't work. ;)
Pen and paper seem to work fine for me. Alternatively, you could write a program :P
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
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
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][ ] [ ]
You could from from X to X
i dont get it ;D
Cause Blaze sucks at explaining things.
00000001
00010000
10000000
00100000
00000100
01000000
00000010
00001000
A friend of mine came up with this.
~-~(HDX)~-~
Quote from: HdxBmx27 on May 27, 2005, 01:45 PM
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!
01
10
80
20
40
02
08
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.
Encoding a VQP mathematicallyAs 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 CQPGiven 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 representationWorking 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 CQPsPython:
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))
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 from: Disco on June 01, 2005, 02:05 PM
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?
He has ADHD.