A general solution of Eight Queens (Python recipe) by Alec Jang

ActiveState Code (http://code.activestate.com/recipes/475145/)

# !/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()