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 <alec.jang@gmail.com>
# 
# 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()

3 comments

Rade Drmic 18 years ago  # | flag

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!

Rade

Alec Jang (author) 17 years, 12 months ago  # | flag

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 17 years, 10 months ago  # | flag

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.