5 queens
cf29
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.
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
> On Sat, 22 Dec 2007 11:36:07 -0800 (PST), cf29 <fcharlypil...@gmail.com>
> declaimed the following in comp.lang.python:
>
> > Greetings,
>
> > I designed in JavaScript a small program on my website called 5
> > queens.
>
> 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"
>
> > 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.
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.
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.
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>
cf29
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?
John Machin
> On Dec 23, 12:39 am, Jervis Liang <arc...@gmail.com> wrote:
>
> > On Dec 22, 2:36 pm, cf29 <fcharlypil...@gmail.com> wrote:
>
> > > 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
>
> 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)
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.
>
> problem:
>
> """
> 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[i][2]==0: # free square
solution.append(i) # a queen position
queenCtrl(board[i]) # 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
---
# 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[i][2]==0: # free square
solution.append(i) # a queen position
queenCtrl(board[i]) # the queen controls squares
Terry Reedy
"John Machin" <sjma...@lexicon.net> wrote in message
news:ad789176-3e76-411c...@s8g2000prg.googlegroups.com...
| 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
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.
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.
--
gra...@visi.com
Grant Edwards
Grant Edwards
Never mind. I just realized that you said 5-queens, not
8-queens.
--
cf29
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[i]]+cc
>>> for c in combinations(range(4), 3):
... print c
...
[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]
--
Steven
cf29
cybersource.com.au> wrote:
> 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[i]]+cc
>
> >>> for c in combinations(range(4), 3):
>
> ... print c
Thank you Steven, it works. I am so new to Python that I don't
understand fully how this function works to be able to adapt it to my
original problem. I wish I had a teacher :-)
Merry Xmas
Steven D'Aprano
(1) Read up on generators. Google is your friend.
(2) Experiment in an interactive Python session. For example, look at
this pair of functions:
>>> def function(x, y, z):
... L = []
... for i in (x, y, z):
... L.append(i)
... return L
...
>>> def generator(x, y, z):
... for i in (x, y, z):
... yield i
...
>>> print function(1, 2, 3)
[1, 2, 3]
>>> print generator(1, 2, 3)
<generator object at 0xb7f7ee8c>
>>>
>>>
>>> for i in function(1, 2, 3):
... print i
...
1
2
3
>>> for i in generator(1, 2, 3):
... print i
...
1
2
3
Now imagine, instead of returning three items, suppose you had a function
that needed to return millions of items. A function using return would
need to produce all of those items before it could make them available to
you. A generator using yield can feed them to you one at a time, as soon
as they're ready.
(3) Read up on recursion, when a function calls itself.
Hope that helps.
--
Steven
George Sakkis
> 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[i]]+cc
>
> >>> for c in combinations(range(4), 3):
>
> ... print c
> ...
> [0, 1, 2]
> [0, 1, 3]
> [0, 2, 3]
> [1, 2, 3]
Or if you only need to iterate over each combination once instead of
keeping around more than one of them, below is a more efficient
version that reuses the same list for all combinations. Also it
doesn't require the input sequence to implement slicing so it can be
used e.g. with xrange:
def itercombos(seq, n):
def ifill(combo, i, start, end=len(seq), seq=seq, n=n):
if i == n:
yield combo
else:
i1 = i+1
for j in xrange(start,end):
combo[i] = seq[j]
for combo in ifill(combo, i1, j+1):
yield combo
for combo in ifill(n*[None],0,0):
yield combo
>>> for c in itercombos(xrange(4), 3): print c
[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]
>>> for c in combinations(xrange(4), 3): print c
Traceback (most recent call last):
File "combs.py", line 54, in <module>
for c in combinations(xrange(4), 3): print c
File "combs.py", line 12, in combinations
for cc in combinations(seq[i+1:], n-1):
TypeError: sequence index must be integer, not 'slice'
George