Welcome, guest | Sign In | My Account | Store | Cart

This is a general method to figuren out all solutions of eight queens. Certainly, it can also solve any number of queens. It's very fast.

Python, 92 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92``` ```# !/usr/bin/env python # A general solution of Eight Queens # Copyright (C) 2006 Alec Jang # # This program is free software, you can redistribute it # with or without any modifications. It may be interesting or # even useful, but without any warranty. # # Description: # This is a general method to figuren out all solutions of # eight queens. Certainly, it can also solve any number of queens. # Each solution is a list, and each value of the list represents # the column number, at the same time the index of this value # represents it's row number. # For instance, list [5,0,4,1,7,2,6,3] means that the first # queen is at (0,5), the second queen is at (1,0), etc. # It runs very fast. In my window box, it need within 4 seconds # to make all solutions and print them to a file. # Only tested at python 2.41 # # Usage: # python queens.py >queens.txt # # if you want to get only one solution , or solve other number of # queens solution, you can do it like this: # # >>>import queens # >>>q=queens.queens(8) # >>>queens.print_solution(q.next()) # # Alec Jang 3/18/2006 import sys def check_safe(lst): """Check if any two elements of lst can form a line, if so, there will be: abs(value2-value1)/(index2-index1)==1 """ for i in range(len(lst)): for j in range(i+1, len(lst)): if abs((lst[j]-lst[i])*1.0/(j-i))==1: return False return True def print_solution(lst): """Print a solution to stdout The argument lst is a nested list """ for i in range(len(lst)): stars=['.']*len(lst) stars[lst[i]]='Q' print stars def list_mutation(n): """Generate all posible layouts of n queens """ if n==0: yield [n] else: for lst in list_mutation(n-1): for i in range(n): yield lst[0:n-1-i]+[n-1]+lst[n-1-i:n-1] def queens(n): """Find all solutions of queens. For each layout generated by list_mutation(n), chech if it's safe. The augument n is the number of queens. Certainly it can be altered to meet your own needs. """ print "N queens solutions" print "By Alec Jang" for q in list_mutation(n): if check_safe(q): yield q def test(): """Test 8 queens. """ N=8 import time start=time.time() count=0 for q in queens(N): count+=1 print "solution: ", count, q print_solution(q) print "Solution count:", count print "time: ", time.time()-start if __name__=="__main__": test() ```

Rade Drmic 16 years, 4 months ago

Thanx! I'm a newbie and I also made a script for this problem some time ago, but my was far too complicated, and slow :)

In windows box 10 queens was calculating 43 hours!!! on Celeron 2,66 (and without preview - only displaying the sum of combinations at the end), so I stoped it without finding a solution...

So I started to ask myself: IS PYTHON JUST TOO SLOW? :)

Now I can learn how to do such things better!!!

Thanx!

Alec Jang (author) 16 years, 4 months ago

I am very happy on hering that. I am very happy that this little program can help you a little. Python is really a very powerful and interesting programming language.

Uwe Zeisberger 16 years, 2 months ago

far from optimal. I removed all output of the solutions from the suggestion and got

solutions: 92

time: 0.502584934235

Then I hacked an other version with

solutions: 92

time: 0.0768530368805

I currently fail to list my script here in this html form, it gets mangled somehow. I uses in-situ permutation and skips permutations that don't resolve the left-most conflict.

 Created by Alec Jang on Fri, 17 Mar 2006 (PSF)