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. 18  4059 
cf29 wrote:
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
On Dec 23, 8:05 am, Dennis Lee Bieber <wlfr...@ix.netcom.comwrote:
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.
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_q...ght_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.
On Dec 22, 11:05*pm, Dennis Lee Bieber <wlfr...@ix.netcom.comwrote:
* * * * 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.
On Dec 22, 2:36 pm, cf29 <fcharlypil...@gmail.comwrote:
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
Michael Spencer wrote:
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>
On Dec 23, 12:39*am, Jervis Liang <arc...@gmail.comwrote:
On Dec 22, 2:36 pm, cf29 <fcharlypil...@gmail.comwrote:
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.
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?
On Dec 23, 10:18 am, cf29 <fcharlypil...@gmail.comwrote:
On Dec 23, 12:39 am, Jervis Liang <arc...@gmail.comwrote:
On Dec 22, 2:36 pm, cf29 <fcharlypil...@gmail.comwrote:
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)
On Dec 23, 1:49*am, John Machin <sjmac...@lexicon.netwrote:
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.
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[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 ?
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[i][2]==0: # free square
solution.append(i) # a queen position
queenCtrl(board[i]) # 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
"John Machin" <sj******@lexicon.netwrote in message
news:ad**********************************@s8g2000p rg.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
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.
On 2007-12-22, cf29 <fc***********@gmail.comwrote:
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.
-- gr****@visi.com
Grant Edwards
On 2007-12-23, Grant Edwards <gr****@visi.comwrote:
On 2007-12-22, cf29 <fc***********@gmail.comwrote:
>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.
--
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.
On Sun, 23 Dec 2007 02:22:38 -0800, cf29 wrote:
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
On Dec 23, 2:04*pm, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.auwrote:
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
Steven
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
On Mon, 24 Dec 2007 00:18:29 -0800, cf29 wrote:
On Dec 23, 2:04Â*pm, Steven D'Aprano <st...@REMOVE-THIS-
cybersource.com.auwrote:
>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
Steven
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 :-)
(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
On Dec 23, 7:04 am, Steven D'Aprano 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
...
[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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Andreas |
last post by:
Hi!
does anybody know an algorithm to solve the 8-queens-problem in PHP?
|
by: cfanatic |
last post by:
Hey all, I been reading through these forums for a long time but have
never posted. Well, I got a dillema. I have a program of the Eight
Queen's program and I have to make it work without...
|
by: Matt |
last post by:
I will be grateful if someone explians this part
colfree = FALSE;
upfree = FALSE;
downfree = FALSE;
of the code below. I don't understand how this marks the downward and
upward diagonals....
|
by: totalgeekdom |
last post by:
Background:
The problem I'm trying to solve is.
There is a 5x5 grid.
You need to fit 5 queens on the board such that when placed there are
three spots left that are not threatened by the queen.
...
|
by: Idea |
last post by:
hi guys m new out here and need help with an assignment due next week.The assignmnet is some what related to eight queens problem but not fully, you can say the basic is taken from that problem....
|
by: angel120 |
last post by:
Since this is my first post, allow me to introduce myself. My name is Angel, and I'm a 3rd year student at Queens College. I currently am taking CS211, which is the second level of C++, CS212 which...
|
by: angel120 |
last post by:
So my second hw is to solve the 8 queens problem using a 1D array. The professor gave us a code that outputs the following (labeled as q):
0 2 5 7 6 3 1 4
The spaces 0-7 refer to the column #,...
|
by: AZRebelCowgirl73 |
last post by:
I am trying to develop an 8 queens program, and currently it is working however it is printing 87222211 which is obviously wrong, I am trying to print the row of the queen in order from...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
