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