99 lines
No EOL
3.1 KiB
Python
99 lines
No EOL
3.1 KiB
Python
# Eight Queens
|
|
# a solution to the Eight Queens problem written in Python
|
|
# by Donald Burr <dburr@borg-cube.com>
|
|
#
|
|
# more on the Eight Queens problem:
|
|
# http://en.wikipedia.org/wiki/Eight_queens_puzzle
|
|
|
|
import cProfile
|
|
|
|
# a simple class to represent a Queen
|
|
class Queen:
|
|
def __init__(self, row):
|
|
self.row = row
|
|
self.column = 0
|
|
|
|
# Array to hold our 8 queens
|
|
# we're starting off by placing each queen on a separate row
|
|
queens = []
|
|
for row in range(8):
|
|
queens.append(Queen(row))
|
|
|
|
# some variables to keep some interesting statistics
|
|
solutions_found = 0
|
|
positions_checked = 0
|
|
|
|
# test the queen at a given row to see if it is safe at a given column
|
|
def is_safe(current_row, current_column):
|
|
global positions_checked
|
|
global queens
|
|
|
|
positions_checked = positions_checked + 1
|
|
|
|
for previous_row in range(current_row):
|
|
# check vertically: are we trying to place in the same column as a previously placed queen?
|
|
if queens[previous_row].column == current_column:
|
|
# bzzt - not safe!
|
|
return False
|
|
|
|
# now check diagonally
|
|
difference_in_rows = current_row - previous_row
|
|
difference_in_columns = current_column - queens[previous_row].column
|
|
if difference_in_rows == difference_in_columns or difference_in_rows == -difference_in_columns:
|
|
# bzzt, not safe!
|
|
return False
|
|
|
|
# we've compared against all queens, so we must be good
|
|
# place the queen and we're outta here!
|
|
queens[current_row].column = current_column
|
|
return True
|
|
|
|
# recursively try moving a queen across all columns
|
|
def move_queen_across_row(row):
|
|
global solutions_found
|
|
|
|
for column in range(8):
|
|
# move queen column by column, checking if it's safe
|
|
if is_safe(row, column):
|
|
# if we just placed the last queen, we've got a solution
|
|
if row == 7:
|
|
solutions_found = solutions_found + 1
|
|
print_answer()
|
|
else:
|
|
# recursive call - now move the queen to the NEXT row
|
|
move_queen_across_row(row+1)
|
|
|
|
# print out a solution once we've found it
|
|
def print_answer():
|
|
global solutions_found
|
|
global queens
|
|
|
|
print "SOLUTION #%d\n" % solutions_found
|
|
# rows are in reverse order
|
|
for current_row in reversed(range(8)):
|
|
# print row number (using chess numbering)
|
|
print "%d" % (current_row+1),
|
|
for current_column in range(8):
|
|
if queens[current_row].column == current_column:
|
|
print " Q ",
|
|
else:
|
|
print " . ",
|
|
|
|
print
|
|
|
|
print " A B C D E F G H \n\n"
|
|
|
|
##### end of functions
|
|
##### main code (such as it is) below here
|
|
##### putting it in a function so we can profile just for the halibut
|
|
|
|
def main():
|
|
# kick things off by trying to move the first queen
|
|
move_queen_across_row(0)
|
|
|
|
# all solutions have been found
|
|
print "POSITIONS CHECKED: %d\n\n" % positions_checked
|
|
|
|
# the REAL start of the code
|
|
# just profile it
|
|
cProfile.run('main()') |