8queens.py

#
# 8queens.py - 8 queens problem
#
# 2014-02-05 Steven Wart created this file
#

from sys import stdout

# Print out an 8x8 chessboard showing the positions of the pieces
def draw_board(board):
	stdout.write("   ")
	for col in range(8):
		stdout.write(" %d  " % col)

	for cell in range(64):
		if ((cell % 8) == 0):
			stdout.write('\n')
			stdout.write("  +")
			for col in range(8):
				stdout.write("---+")
			stdout.write('\n')
			stdout.write("%d |" % (cell / 8))

		if (board[cell]):
			stdout.write(" Q |")
		elif is_under_attack(cell, board):
			stdout.write(" x |")
		else:
			stdout.write("   |")

	stdout.write('\n')
	stdout.write("  +")
	for col in range(8):
		stdout.write("---+")
	stdout.write('\n')

def initialize_rook_moves(board):
	rook_moves = [[] for x in range(len(board))]

	for target in range(len(board)):
		for cell in range(len(board)):
			if (target % 8 == cell % 8) or (target / 8 == cell / 8):
				rook_moves[cell].append(target)

	return rook_moves

def append_move(col, row, moves):
	if row >= 0 and row <= 7 and col >= 0 and col <= 7:
		moves.append(row * 8 + col)

def initialize_bishop_moves(board):
	bishop_moves = [[] for x in range(len(board))]

	for row in range(8):
		for col in range(8):
			target = col * 8 + row
			for neighbor in range(1,8):
				append_move(row + neighbor, col - neighbor, bishop_moves[target])
				append_move(row - neighbor, col - neighbor, bishop_moves[target])
				append_move(row + neighbor, col + neighbor, bishop_moves[target])
				append_move(row - neighbor, col + neighbor, bishop_moves[target])

	return bishop_moves

def is_under_attack(target, board):
	for index in range(len(board)):
		if board[index] and (target in rook_moves[index] or target in bishop_moves[index]):
			return True
	return False

# return the next board position greater than or equal to start 
# where the queen can be placed
# if no spaces are available, return -1
def placeQueenAfter(start, board):
	for index in range(start, len(board)):
		if not board[index] and not is_under_attack(index, board):
			return index
	return -1

arrangements = 0

#
# queens - how many queens to place
# board - a list of 64 cells containing True or False indicating the presence of a queen
#
# Attempt to place the first queen in the list. If this cannot be done, return False
# Then attempt to place the rest of the queens in the list. If those cannot be placed,
# attempt to place the queen at the next candidate position in the board.
#
# If this fails return False
# Otherwise, return True.
#
# From http://en.wikipedia.org/wiki/Eight_queens_puzzle
#
# The problem can be quite computationally expensive as there are 4,426,165,368 (i.e., 64 C 8)
# possible arrangements of eight queens on a 8x8 board, but only 92 solutions.
#
# It is possible to use shortcuts that reduce computational requirements or rules of thumb but
# that avoids brute-force computational techniques. For example, just by applying a simple rule
# that constrains each queen to a single column (or row), though still considered brute force,
# it is possible to reduce the number of possibilities to just 16,777,216 (that is, 88) possible
# combinations. Generating permutations further reduces the possibilities to just 40,320 (that is, 8!),
# which are then checked for diagonal attacks
#
# The above heuristic allows the 8 queen solution to be found within a few seconds on a modern PC.
# Otherwise the calculation will not complete for 8 queens in a reasonable time period.
#
def placeQueens(queens, board, startingAt = 0):

	global arrangements

	if queens == 1:
		arrangements = arrangements + 1
		if arrangements % 10000 == 0:
			print "Examined %d arrangements" % arrangements

	# no queens to place? trivial!
	if queens <= 0:
		return True

	for col in range(8):
		# optimization: only examine row number = number of queens to place - 1
		row = queens - 1
		candidate = row * 8 + col
		pos = placeQueenAfter(candidate, board)
		if pos >= 0:
			board[pos] = True
			if placeQueens(queens - 1, board, row * 8):
				return True
			else:
				board[pos] = False
		else:
			return False

	return False

# board keeps track of where the queens are placed
board = [False for x in range(64)]

rook_moves = initialize_rook_moves(board)
bishop_moves = initialize_bishop_moves(board)

placeQueens(8, board)
draw_board(board)