threatless_queens.py

#!/usr/bin/env python
#
# Find positions of queens on chess-board so they will not threaten each other
#
# Author:  Yotam Medini  [email protected] -- Created: 2006/June/18
#

import sys
import string


def next_permutation(a):
    n = len(a)
    # Find last increasing pair
    i = n - 2
    while i >= 0 and a[i] >= a[i+1]:
        i -= 1
    if i < 0:
        a = None  # a is decreasing, no more permutations
    else:
        # Find last greater than a[i].
        # There must be one! since a[i] < a[i+1].
        j = n - 1
        while a[i] >= a[j]:
            j -= 1
        # and swap
        t = a[i];  a[i] = a[j];  a[j] = t

        # Mirror the tail.
        tail = a[i + 1:]
        tail.reverse();  # Python is strong
        a = a[: i + 1] + tail
    return a


# Check if (x0,y0) and  (x1,y1)  squares  on same '/' diagonal
def same_diagonal_SW2NE(x0, y0, x1, y1):
    same = (x0 - y0) == (x1 - y1)
    return same


# Check if (x0,y0) and  (x1,y1)  squares  on same '\' diagonal
def same_diagonal_SE2NW(x0, y0, x1, y1):
    same = (x0 + y0) == (x1 + y1)
    return same


# Check if (x0,y0) and  (x1,y1)  squares  on common diagonal
def same_diagonal(x0, y0, x1, y1):
    same = (same_diagonal_SW2NE(x0, y0, x1, y1) or
            same_diagonal_SE2NW(x0, y0, x1, y1))
    return same


# Assume  a  holds a permutation of chess rows.
# If a = [a0, a1, a2, ..., a{n-1}]  then the squares are:
# (0,a0),  (1,a1), (2,a2) ..., (n-1,a{n-1})
# The function checks if there are no pair of squares that
# queens would threaten each other.
def is_queen_solution(a):
    no_threat = True
    size = len(a)
    xShva = 0 # First queen
    while no_threat and xShva < size:
        yShva = a[xShva]
        xEster = xShva + 1  # Second queen
        while no_threat and xEster < size:
            yEster = a[xEster]
            no_threat = not same_diagonal(xShva, yShva, xEster, yEster)
            xEster += 1
        xShva += 1
    return no_threat


# Assume rows is a sequence of rows for each column.
# Return string of chess squares
# For example:  if  rows = [0, 2, 1] v then we will return  "a1 b3 c2"
def rows2chess_str(rows):
    abc = string.ascii_lowercase;  # "abc...z"  but I am lazy
    nlc = len(abc);                # This is 26 duh! but let Python count...
    s = ""
    size = len(rows)
    if size < nlc:  #  8 < 26   So the default case will be nice
        for c in range(0, size):
            colrow = "%s%d" % (abc[c], rows[c] + 1)
            s += colrow + ' '  #  add square
    else:
        # We give up letter notation
        for c in range(0, size):
            s += "(%d,%d) " % (c, rows[c])
    s = s[:-1]  # Remove last unwanted space
    return s


# main
size = 8; # default
if len(sys.argv) == 2:
    size = int(sys.argv[1])
n_solutions = 0
permutation = range(0, size);  # 1st increasing permutation - I like Python
while permutation != None:
    if is_queen_solution(permutation):
        chess_squares = rows2chess_str(permutation)
        sys.stdout.write("[%3d]:  %s\n" % (n_solutions, chess_squares))
        n_solutions += 1
    permutation = next_permutation(permutation)
sys.stdout.write("Total: %d solutions\n" % n_solutions)
sys.exit(0)