The Eight Queens Problem in Chess

[bloodhound]

Hi, me and my mate were talking about uni and stuff. he does computer science at imperial. and this came up. its the famous eight queen problem

 

"All you have to do is put eight queens on a chess board so that none of them are attacking each other."

 

sounds easy rite. but believe me, i can manage only 7. apparently he had to write a program to find a solution to this problem. and yes there are solutions.

 

So now, I dont want anyone to cheat or look it up on the web. I would just like to know how a mathematician would go about solving this. I was thinking about using matrices. a 8by8 matrice. but then i dont know what to do with it. anyway if anyone can find a solution, post it. and tell us how u went about finding it. cheers. ill have more go at it.

[Dave]

Sounds like a brute-force question to me.

[bloodhound]

i am sure there is a really neat way to do it, but i wont give up and look it up on the web just yet.

[wolfson]

If all sixty-four squares of the chess board are numbered consecutively from one to sixty-four, all 92 distinct solutions can be represented by 92 integer sequences, where each queen placement represents a term.

 

See: http://en.wikipedia.org/wiki/8_queens_problem

 

6, 9, 21, 26, 40, 43, 55, 60.

 

Since each queen must belong to one and only one row and column (and diagonal), and there are the same number of queens as there are rows and columns, the sum of any such sequence must be fixed. With the integer sequence representation above, the sum must be 8 + sum(1..7) + 8 * sum(1..7) = 260, the magic constant of Eight queens puzzle, for all 92 distinct solutions

 

 

Thus:

 

# Return a list of solutions to the n-queens problem on an

# n-by-width board. A solved board is expressed as a list of

# column positions for queens, indexed by row.

# Rows and columns are indexed from zero.

def n_queens(n, width):

if n == 0:

return [[]] # one solution, the empty list

else:

return add_queen(n-1, width, n_queens(n-1, width))

 

# Try all ways of adding a queen to a column of row new_row, returning

# a list of solutions. previous_solutions must be a list of new_row-queens

# solutions.

def add_queen(new_row, width, previous_solutions):

solutions = []

for sol in previous_solutions:

# Try to place a queen on each column on row new_row.

for new_col in range(width):

# print 'trying', new_col, 'on row', new_row

if safe_queen(new_row, new_col, sol):

# No interference, so add this solution to the list.

solutions.append(sol + [new_col])

return solutions

 

# Is it safe to add a queen to sol at (new_row, new_col)? Return

# true if so. sol must be a solution to the new_row-queens problem.

def safe_queen(new_row, new_col, sol):

# Check against each piece on each of the new_row existing rows.

for row in range(new_row):

if (sol[row] == new_col or # same column clash

sol[row] + row == new_col + new_row or # diagonal clash

sol[row] - row == new_col - new_row): # other diagonal

return 0

return 1

 

for sol in n_queens(8, 8):

print sol

 

(APP (MATHS) 2000-2004 ©)

[bloodhound]

thanks for that . forget the computer code stuff. just want some mathematical ideas

[wolfson]

My favourite solution (there are quite a few) has 180degrees rotational symmetry

[bloodhound]

cool. is there a way to find solutions witought brute forcing it?

[Radical Edward]

how about minimising the number of new squares covered on each queen placement?

[wolfson]

If we label the columns and rows from 0 to 7, then we have queen at position (i,j), where

j = (3 + 2i) mod 8, for 0 _< < 4

_

 

j = (2i - 2) mod 8, for 4 _< i

 

 

Hope that helps

chess.zip

[winfred01]

The only way (I know) to solve this problem is by backtracking (with ordinary computers)... unless your friend is using a computer with "special" CPU, I think that's the only way.

The Eight queen's problems is a typical demo for backtracking.

 

I will have a go using a matix ( i , j ) and some linear equations y=ax+b...(a = 1,-1)

 

btw, I put Imperial as my insurance so I might be asked to solve this question in the future...um...

[Tesseract]

I did this problem before and memorized it, it took a while for me to figure out where each queen goes ine each column though.

[Sayonara]

I used an Excel sheet to work it out visually

 

Only found 1 solution (well, four really as you can get different orders if you rotate it about the board) out of a possible 92 though.

 

Not that this has anything to do with the maths issue ofc.