5 queens
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On Dec 22, 11:05 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote: > 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On Dec 23, 12:39 am, Jervis Liang <[EMAIL PROTECTED]> wrote:
> On Dec 22, 2:36 pm, cf29 <[EMAIL PROTECTED]> 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.
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?
--
http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On Dec 23, 1:49 am, John Machin <[EMAIL PROTECTED]> wrote: > > > 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 ? -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On Dec 23, 2:04 pm, Steven D'Aprano <[EMAIL PROTECTED] 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 > 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 -- http://mail.python.org/mailman/listinfo/python-list
documentation
Which website would you recommend for a great documentation about Python? I am looking for a list of methods and properties of all the Python elements with syntax examples. -- http://mail.python.org/mailman/listinfo/python-list
TextWrangler and new Python version (Mac)
I installed Python 2.5 on my Mac (OS X Tiger). When running scripts with the TextWrangler Run command it is using the system installed version of Python (2.3). If I run the scripts with the Apple Terminal it uses the new version (2.5). Is there any way to ask TextWrangler to use the new version of Python? -- http://mail.python.org/mailman/listinfo/python-list
Re: TextWrangler and new Python version (Mac)
Thank you Jean, I could fix this problem. Creating the symbolic link wasn't really obvious though. They also say about the documentation: *Extract the documentation files, and place them in some suitable location, e.g. ~/Library/Python-Docs *Edit your "environment.plist" file, and create an environment variable PYTHONDOCS to the location of the folder which contains the Python documentation. Is that the html version of the Python documentation? Do you know more about this "environment.plist" file? Where is it supposed to be? I didn't find any. -- http://mail.python.org/mailman/listinfo/python-list
cannot execute binary file (Python 3.0.1)
Greetings, On Mac OS 10.5.6, I updated Python to version 3.0.1. When I want to run a py file, I get an error: xxx:~ xxx$ cd '/Users/xxx/Documents/programmingPractice/' && '/usr/ local/bin/python' '/Users/xxx/Documents/programmingPractice/ python_file.py' && echo Exit status: $? && exit 1 -bash: /usr/local/bin/python: cannot execute binary file This wasn't an issue with Python 2.6, please let me know how to solve this problem. Best regards Charly -- http://mail.python.org/mailman/listinfo/python-list
Re: cannot execute binary file (Python 3.0.1)
On Mar 1, 11:14 am, Chris Rebert wrote: > Detailing exactly how you upgraded Python would help immensely. > > Cheers, > Chris Thanks for your answer. I installed the package in python-3.0.1-macosx2009-02-14.dmg (downloaded from http://www.python.org/download/releases/3.0.1/) and runed the Update Shell Profile.command situated in the Python 3.0 folder. If I type python in the Terminal, it says: Python 3.0.1 (r301:69597, Feb 14 2009, 19:03:52). So it seems that it is working properly. If I use the Terminal and type: python myfile.py, it works as expected. The issue is when I want to run py file either with Python Launcher.app or directly from BBEdit (the text editor i use). I get the "cannot execute binary file" error. In /usr/local/bin/ the python symbolic link is connected to Python v3 Charly http://cf29.com/ -- http://mail.python.org/mailman/listinfo/python-list
Re: cannot execute binary file (Python 3.0.1)
On Mar 1, 12:52 pm, Ned Deily wrote: > It appears you are trying to run a python script by double-clicking on > it and that Python Launcher.app is the default application associated > with .py files. The default setting in Python Launcher is to use the > python linked to /use/local/bin/pythonw. By default, the OS X 3.0.1 > installer does not install or modify the links in /usr/local/bin/, > unlike 2.x installers. That is a problem for Python Launcher. Here are > a few options, assuming you used the 3.0.1 python.org installer: > > 1. You can start up the installer again, choose Customize, and then > select and install the "UNIX command-line tools" package. > /usr/local/bin/pythonw will now point out at python 3.0.1 rather than > python 2.6. > > -- > Ned Deily, > n...@acm.org Thank you Ned! The 1. did the trick. Actually I was using the open menu of Python Launcher to open my files. And now it works fine. Usually I use to run python scripts from BBEdit itself and this is now working as expected. What a great place to find answers! Thanks again. Charly http://cf29.com/ -- http://mail.python.org/mailman/listinfo/python-list
