Dumb Eight Queen Solution in Python

eightqueen.py

#!/usr/bin/env python2.7

# Solving the 8-queen problem.
# Written by Asad ur Rehman <asad.rehman@gmail.com>
#
# Slight optimizations with the help of @jibz and @atharhameed
#
# real	0m23.248s
# user	0m21.840s
# sys	0m0.085s
#
# Finds all 92 solutions
#
# Mon Mar 12 00:43:29 PKT 2012
#

MAX_X = 8
MAX_Y = 8
NUM_QUEENS = 8

def insert_queen(board, x, y):
	if board[x][y] != '.':
		return False

	for i in xrange(MAX_Y):
		for j in xrange(MAX_X):
			if x == i and y == j:
				board[x][y] = 'X'	# mark queen at this location

			# mark diagonals and straights as occupied
			elif i == x or j == y or (x-y) == (i-j) or (x+y) == (i+j):
				board[i][j] = 'O'

	return True

def available_coords(board):
	ret = []
	for i in xrange(MAX_Y):
		for j in xrange(MAX_X):
			if board[i][j] == '.':
				ret.append( [i,j] )

	return ret

def print_board(board):
	q = 0
	for i in xrange(MAX_Y):
		for j in xrange(MAX_X):
			print board[i][j],
			if board[i][j] == 'X':
				q = q + 1

		print ""
	print "--- %d queens" % q

processed = set()

def try_putting_queens(orig_board, num):
	global processed
	
	if ''.join([c for r in orig_board for c in r]) in processed:
		return

	available = available_coords(orig_board)
	for (x,y) in available:
		board = [row[:] for row in orig_board]
		insert_queen(board, x, y)
		try_putting_queens(board, num+1)
	else:
		if num == 8:
			print_board(orig_board)

	processed.add(''.join([c for r in orig_board for c in r]))

if __name__ == "__main__":
	board = [['.' for x in xrange(MAX_X)] for y in xrange(MAX_Y)]
	try_putting_queens(board, 0)