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
Re: 5 queens
On Mon, 24 Dec 2007 00:18:29 -0800, cf29 wrote: 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 :-) (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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
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 -- 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 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On Dec 23, 8:05 am, Dennis Lee Bieber [EMAIL PROTECTED] wrote: On Sat, 22 Dec 2007 11:36:07 -0800 (PST), cf29 [EMAIL PROTECTED] 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_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. -- 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 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
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 -- 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, 10:18 am, cf29 [EMAIL PROTECTED] wrote: 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. 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 queensnxn 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, er, the same way as you found the first one? record it in my solutions list solutions_list.append(solution) -- 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
John Machin [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] | 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: 5 queens
On 2007-12-23, Grant Edwards [EMAIL PROTECTED] wrote: On 2007-12-22, cf29 [EMAIL PROTECTED] wrote: 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. -- -- http://mail.python.org/mailman/listinfo/python-list
