5 queens

[cf29]

Greetings,

I designed in JavaScript a small program on my website called 5
queens.
(http://www.cf29.com/design/dame5_eng.php)

The goal is to control all the chess board with five queens that do
not attack each other. I found "manually" many solutions to this
problem (184 until now) and wanted to create a Python script to find
them all. As I am new to Python, I struggle a lot.

I found a way to create:
- a board where each square is defined by its row, column and if it is
controlled or not
- a function that tells which squares are controlled by a queen on a
particular square
- a function that counts how many squares are controlled
- a function that can reset all squares control to 0
- a function that can place 5 queens safely on the board
- I can find the first solution and register it in a list

My problem starts now. How can I find the next solution and append it
to the list? Has anyone tried to do a such script? If anyone is
interested to help I can show what I've done so far.

 

[Dennis Lee Bieber]

Greetings,

I designed in JavaScript a small program on my website called 5
queens.

Only 5? The classic algorithm is 8-queens on a standard 8x8 board,
as I recall...

http://en.wikipedia.org/wiki/Eight_...ens_puzzle_as_an_exercise_in_algorithm_design

My problem starts now. How can I find the next solution and append it
to the list? Has anyone tried to do a such script? If anyone is
interested to help I can show what I've done so far.

None of your problems are Python related. This is an exercise in
designing an algorithm -- algorithms are language neutral.

The brute force approach is an 8-level (for 8 queens) loop. Each
level loops over each square of the board; if the queen can be safely
placed in that square, place it and descend one level to the next queen.
When the last queen is placed safely, the bottom level records the
success configuration, then moves on to the attempt the next square.
When all squares have been tried at a given level, it returns up one
level, and that higher level moves to its next square and repeats with
the lower level.

def placeQueen(board, lvl):
for sqr in board:
if sqr.empty():
if not sqr.endangered():
sqr.addQueen()
if lvl == 8:
reportSuccess(board)
else:
placeQueen(board, lvl+1)

board = newBoard()
placeQueen(board, 1)

This will NOT detect rotations or mirror solutions.
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Michael Spencer]

Greetings,

I designed in JavaScript a small program on my website called 5
queens.

...

Has anyone tried to do a such script? If anyone is

interested to help I can show what I've done so far.

Tim Peters has a solution to 8 queens in test_generators in the standard library
test suite (see: Lib/test/test_generators.py)

HTH

Michael

 

[John Machin]

Only 5? The classic algorithm is 8-queens on a standard 8x8 board,
as I recall...

The classic *problem* is "8 queens don't attack each other".

http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puz...

and then type Ctrl-F followed by domination. As the OP says, his "goal
is to control all the chess board with five queens that do
not attack each other"

None of your problems are Python related. This is an exercise in
designing an algorithm -- algorithms are language neutral.

Indeed. The Wikipedia article has several clues on how to avoid a
brute-force solution to the classic problem -- some of these should be
applicable to the OP's problem.

 

[cf29]

        Only 5? The classic algorithm is 8-queens on a standard 8x8 board,
as I recall...

This is a different problem. You have to control all the squares with
only 5 queens.
In the 8 queens problem you have to put 8 "safe queens".
I also have it on my website at http://www.cf29.com/design/dame_eng.php

I know about the Wikipedia 8 queens solution and it is how I
discovered Python. I wanted to learn more about it to try to modify
this script for the 5 queens problem. It helped me to go as far as I
did with my 5 queens script but the 8 queens script only considers a
number of queens equal to the number of rows. In the 5 queens problem,
there are 8 rows and 3 of them are empty.

It may be not particularly related to Python so may be my message is
misplaced. Thanks for the help anyway.

 

[Fredrik Lundh]

Tim Peters has a solution to 8 queens in test_generators in the standard library
test suite (see: Lib/test/test_generators.py)

and for a more straightforward and perhaps more grokkable
implementation, see Guido's original Python demo code in
Demo/scripts/queens.py

</F>

 

[Jervis Liang]

The goal is to control all the chess board with five queens that do
not attack each other. I found "manually" many solutions to this
problem (184 until now)

How did you find 184 solutions? Wolfram says there are 91 distinct
solutions for 5-queens on an 8x8 board with no two queens attacking
each other.

http://mathworld.wolfram.com/QueensProblem.html

 

[cf29]

How did you find 184 solutions? Wolfram says there are 91 distinct
solutions for 5-queens on an 8x8 board with no two queens attacking
each other.

http://mathworld.wolfram.com/QueensProblem.html

If I am not mistaken, the 92 solutions are for 8 queens on a 8x8 board
with no queen attacking each other.
On the same page they say that for 5 queens controlling all the board
the number of solutions is 4860 but it is in the case that "every
queen is attacked ("protected") by at least one other". The picture
above shows a position where all queens are "safe" though.

So my problem is how to find the solutions for 5 (FIVE) queens
controlling ALL the board with NO queen being under attack. I think
that a short visit to the problem at (http://www.cf29.com/design/
dame5_eng.php) will make it crystal clear.
And more precisely as I did already a part of the job (see the
original post). How can I record solutions in a way that the function
goes to the NEXT possible valid position? It is probably a basic thing
but I am new to programming and it is not obvious for me. If squares
are indexed from 0, the first solution I found is [0, 10, 20, 25, 35]
and now how can I look for the next one, record it in my solutions
list until there is no more?

 

[Dennis Lee Bieber]

<mumbling to myself, it seems>

The brute force approach is an 8-level (for 8 queens) loop. Each
level loops over each square of the board; if the queen can be safely
placed in that square, place it and descend one level to the next queen.
When the last queen is placed safely, the bottom level records the
success configuration, then moves on to the attempt the next square.
When all squares have been tried at a given level, it returns up one
level, and that higher level moves to its next square and repeats with
the lower level.

Once you understand /that/ slow scheme, the first optimization is to
realize that, with a single queen per row, one can use the "level" to
determine which row the queen in question is to be placed, and only
examine the 8 squares on that row. Associated with this is that the
"danger" test needs to only check diagonals and column for rows less
than the current row.

A potential second optimization is in the danger test -- you can
either scan each diagonal and column when attempting to place a queen,
OR when you /do/ place a queen you flag the squares in the column and
diagonals below the current row. Then the test simply becomes "is the
square flagged". However, as you need to "unflag" when unrecursing a
level, and you must not unflag a square that is covered by one or more
OTHER queens you have a choice: Either start each attempt by making a
(deep)copy of the board; that way you can unset the flags by just making
a fresh copy... OR you use a counting flag (say -1 for Queen, 0 for
empty, >0 for #of queens threatening this square); this means setting
the flag is done by adding 1, and clearing by subtracting 1.

A third optimization: once a solution is found, you generate the
mirror and rotation solutions: If you find a solution with a queen in
(1,1), you will also find mirror solution (1, 8) [left-right], (8, 1)
[top-bottom], and (8, 8) [left-right & top-bottom]. Furthermore, you
have three rotations for each [taking the initial as 0deg]: +90, +180,
+270... (some rotations may match some mirrors)

For each solution you can create a tuple/list specifying the column
the queen is in (the subscript is the row). Keeping a list of these
would allow for duplicate checking...

--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[John Machin]

If I am not mistaken, the 92 solutions are for 8 queens on a 8x8 board
with no queen attacking each other.

It's *91* distinct solutions to what appears to be *exactly* your
problem:

"""
Dudeney (1970, pp. 95-96) also gave the following results for the
number of distinct arrangements N_u(k,n) of k queens attacking or
occupying every square of an nxn board for which no two queens attack
one another (they are "not protected").
k queens nxn N_u(k,n)
1 2 1
1 3 1
3 4 2
3 5 2
4 6 17
4 7 1
5 8 91
"""

On the same page they say that for 5 queens controlling all the board
the number of solutions is 4860 but it is in the case that "every
queen is attacked ("protected") by at least one other". The picture
above shows a position where all queens are "safe" though.

So my problem is how to find the solutions for 5 (FIVE) queens
controlling ALL the board with NO queen being under attack. I think
that a short visit to the problem at (http://www.cf29.com/design/
dame5_eng.php) will make it crystal clear.
And more precisely as I did already a part of the job (see the
original post). How can I record solutions in a way that the function
goes to the NEXT possible valid position? It is probably a basic thing
but I am new to programming and it is not obvious for me. If squares
are indexed from 0, the first solution I found is [0, 10, 20, 25, 35]
and now how can I look for the next one,

ermmmm, the same way as you found the first one?

record it in my solutions
list

solutions_list.append(solution)

 

[Dennis Lee Bieber]

This is a different problem. You have to control all the squares with
only 5 queens.

OK, I seem to have missed that aspect...

In the 8 queens problem you have to put 8 "safe queens".
I also have it on my website at http://www.cf29.com/design/dame_eng.php

Well... Look at it this way -- if 5 queens control the entire board,
there is no place to put a 6th queen... Uhh... I'm presuming you are
still following the 8-queen type of "no overlap" coverage... (that is,
no valid solution has multiple queens on the same row/column/diagonal)

Though obviously my second post of optimizations falls out as you DO
have to scan all the rows, not just one row per "level"... (that is, you
may have to skip rows to find a solution [as you do mention later in the
trimmed])

Brute force ideas, off the top of my head, and taking into account
that with five queens, any solution only has three open rows/columns...

First queen can be placed anywhere in rows 1..4 (I'm not sure, at this
stage, if one can limit to column 1..4, possibly anything in 5..8 would
be a rotation/mirror of a solution found if using just 1..4 for first)
Second queen can be placed somewhere in rows 2..5 (same uncertainty re
columns)
Third ... 3..6
Fourth ... 4..7
Fifth ... 5..8

So in the recursion, any of the five queens is restricted to a
maximum range of four rows, and subsequent queens don't have to explore
rows prior to the previously placed queen. So if the first queen is in
row four, the second can only be in row five, third in six, etc.

Suggest using the counting method when placing a queen, and upon
fifth queen placement, scan the board for any cell that has a zero count
-- which is /not/ a solution <G>
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Dennis Lee Bieber]

And more precisely as I did already a part of the job (see the
original post). How can I record solutions in a way that the function
goes to the NEXT possible valid position? It is probably a basic thing
but I am new to programming and it is not obvious for me. If squares
are indexed from 0, the first solution I found is [0, 10, 20, 25, 35]
and now how can I look for the next one, record it in my solutions
list until there is no more?

Off-hand, same recursion scheme as the 8-queens... Probably same for
mirror/rotation solutions... Use a structure of [r1, r2, r3, r4, r5, r6,
r7, r8], initialize with a None in each position, then store the column
in the appropriate position when a solution is found...
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[cf29]

It's *91* distinct solutions to what appears to be *exactly* your
problem:

"""
k queens        nxn     N_u(k,n)
5       8       91

Sorry I missed that. Anyway I found 192 solutions now, they include
rotations and mirroring so that gives 24 "unique" solutions. May be
there is a total of 91 unique solutions that would give 91x8 = 728
distinct solutions. I don't know yet.

Sorry for any misunderstanding as English is not my native language.
I'll include my script so you may understand my code better than my
English and tell me where I went wrong. Thanks a lot to everyone for
your patience and kind help to a such newbie I am. I am learning a
lot, I started to learn Python 3 days ago.

the code I wrote so far
-----
# Solutions to the 5 queens problem
# Control all the board with five queens
# that do not attack each other

board = [] # squares list
nbRows = 8 # number of rows
nbCols = 8 # number of columns

# create 64 squares definied by their row, column
# and a 0 meaning that they aren't controlled yet
# ie the 1st square board[0] is [0,0,0], the last one board[63] is
[7,7,0]
for r in range(nbRows):
for c in range(nbCols):
board.append([r,c,0])

# control done by a queen on square (sq)
def queenCtrl(sq):
for c in range(len(board)):
if (board[c][0] == sq[0] or # same row
board[c][1] == sq[1] or # same col
(board[c][0] + board[c][1]) == (sq[0] + sq[1]) or # diagonal1
(board[c][0] - board[c][1]) == (sq[0] - sq[1])): # diagonal2
board[c][2] = 1 # the square is controlled

# count the number of controlled squares
def calcCtrl():
nbCtrl = 0 # number of controlled squares
for c in range(len(board)):
if board[c][2] == 1:
nbCtrl += 1
return nbCtrl

# reset controlled squares
def resetCtrl():
for c in range(len(board)):
board[c][2] = 0

# all the solutions list
allSolutions = []

# add nbQueens (5) new queens on safe squares
def newQueens(nbQueens=5):
solution = [] # one solution
for i in range(len(board)): # 64 squares
if len(solution) < nbQueens: # 5 queens
if board[2]==0: # free square
solution.append(i) # a queen position
queenCtrl(board) # the queen controls squares
resetCtrl() # reset the controled squares
allSolutions.append(solution) # add this solution to the list

# testing
newQueens()

for s in allSolutions:
print s

# this gives me the first solution

# please tell me
# how can I ask newQueens() to find the next new solution
# and add it to the allSolutions list until there is no more ?

 

[cf29]

Sorry again I forgot a part of the function in my previous post:
---
# add nbQueens (5) new queens on safe squares
def newQueens(nbQueens=5):
solution = [] # one solution
for i in range(len(board)): # 64 squares
if len(solution) < nbQueens: # 5 queens
if board[2]==0: # free square
solution.append(i) # a queen position
queenCtrl(board) # the queen controls squares
if calcCtrl() == len(board): # whole board controlled
allSolutions.append(solution) # add this solution to the list
resetCtrl() # reset the controled squares

 

[Terry Reedy]

| It's *91* distinct solutions to what appears to be *exactly* your
| problem:
|
| """
| Dudeney (1970, pp. 95-96) also gave the following results for the
| number of distinct arrangements N_u(k,n) of k queens attacking or
| occupying every square of an nxn board for which no two queens attack
| one another (they are "not protected").
| k queens nxn N_u(k,n)
| 1 2 1
| 1 3 1
| 3 4 2
| 3 5 2
| 4 6 17
| 4 7 1
| 5 8 91
| """

If you don't want to work out everything for yourself, I would go to the
Wolffram site and find the Dudeney reference and see if it has an algorithm
or merely a list of solutions (even that would help).

A brute force search off the top of my head goes as follows:
The 'topmost' queen can potentially be in any column of rows 0 to 3;
The second queen in the next row to 4, any column;
Etc.
r8 = range(8)
for i0 in range(0, 4):
for j0 in r8:
for i1 in range(i0+1,5):
for j1 in r8:
for i2 in range(i1+1, 6):
for j2 in r8:
for i3 in range(i2+1,7):
for ji in r8:
for i4 in range(i3+1):
for j4 in r8:
test_position:

Optimizations: test non-attacking property as add each queen.
Change range of j0 to range(4) to delete reflections about vertical axis.

To detect all duplicates by reflection and rotation, one needs a
'canonical' form for each position. With that, I think one could do much
better in not generating duplicates.

Terry Jan Reedy

 

[subeen]

Hi,

The problem you are trying to solve is a very famous and common
problem which can be solved by backtracking. Please try google with 8
queens problem or n queens problem.

I designed in JavaScript a small program on my website called 5
queens.
(http://www.cf29.com/design/dame5_eng.php)

The goal is to control all the chess board with five queens that do
not attack each other. I found "manually" many solutions to this
problem (184 until now) and wanted to create a Python script to find
them all. As I am new to Python, I struggle a lot.

I found a way to create:
- a board where each square is defined by its row, column and if it is
controlled or not
- a function that tells which squares are controlled by a queen on a
particular square
- a function that counts how many squares are controlled
- a function that can reset all squares control to 0
- a function that can place 5 queens safely on the board
- I can find the first solution and register it in a list

My problem starts now. How can I find the next solution and append it
to the list? Has anyone tried to do a such script? If anyone is
interested to help I can show what I've done so far.

Try to generate the next permutation and check if it's a valid
solution. Need to use recursion for this.

regards,
Subeen.

 

[Grant Edwards]

The goal is to control all the chess board with five queens that do
not attack each other. [...]
My problem starts now. How can I find the next solution and
append it to the list? Has anyone tried to do a such script?

ftp://ftp.visi.com/users/grante/python/queens.py

It's a pretty standard depth-first search of the solution space.

 

[Grant Edwards]

The goal is to control all the chess board with five queens that do
not attack each other. [...]
My problem starts now. How can I find the next solution and
append it to the list? Has anyone tried to do a such script?

ftp://ftp.visi.com/users/grante/python/queens.py

It's a pretty standard depth-first search of the solution space.

Never mind. I just realized that you said 5-queens, not
8-queens.


--

 

[cf29]

To make it simple and not have to deal with the 8 queens problem that
is different with the 5 queens one, I'll ask in a different way.

I am not familiar with implementing in Python such terms as "standard
depth-first search of the solution space", "permutation", "recursion",
"'canonical' form", ... I couldn't find the "Wolffram site's Dudeney
reference".

How would you write a function that will populate a list with a list
of numbers with all the possibilities? For example a list of 3 numbers
taken among 4 [0,1,2,3] without duplicates. The result should be:
[0,1,2]
[0,1,3]
[0,2,3]
[1,2,3]

I would apply this to my problem by adding conditions.
Thanks again for your help.

 

[Steven D'Aprano]

How would you write a function that will populate a list with a list of
numbers with all the possibilities? For example a list of 3 numbers
taken among 4 [0,1,2,3] without duplicates. The result should be:
[0,1,2]
[0,1,3]
[0,2,3]
[1,2,3]

What you are asking for is the combinations of the list, taking 3
elements at a time. Try using this generator:

def combinations(seq, n):
if n == 0:
yield []
else:
for i in xrange(len(seq)):
for cc in combinations(seq[i+1:], n-1):
yield [seq]+cc

.... print c
....
[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]