ThreadedNQueens.py
--D. Thiebaut 16:06, 24 January 2010 (UTC)
#! /usr/bin/python
# D. Thiebaut
# Usage:
# nqueens.py N
# where N is the number of queens wanted, i.e. the dimension
# of the board.
#
# to kill a program that doesn't want to stop:
# kill `ps | grep threaded | grep -v idle | grep -v grep | cut -d' ' -f 1`
import sys
import time
import threading
QUEEN = -10 # marker for a queen in 2D integer array
EMPTY = 0 # marker for empty cell (no queen, no coverage by a queen)
class timePerfClass:
"""A class to keep track of processor and user time.
use by first calling start(), then stop(), then
printElapsed()"""
def __init__(self):
self.clockStart = 0 # beginning processor time
self.clockEnd = 0 # ending processor time
self.timeStart = 0 # beginning user time
self.timeEnd = 0 # ending user time
def start( self ):
self.clockStart = time.clock()
self.timeStart = time.time()
def stop( self ):
self.clockEnd = time.clock()
self.timeEnd = time.time()
def printElapsed( self ):
print "processor time: ", (self.clockEnd-self.clockStart), "sec"
print "user time : ", (self.timeEnd-self.timeStart), "sec"
class queenThread( threading.Thread ):
"""
a thread for searching for a solution to the N-Queens problem
starting from a given location on the top row. The location is
stored in self.col. The thread then tries to place N-1 queens
on the remaining N-1 rows.
run() is the main core of the thread
self.timeToStop set to True by main to force the thread to quit
self.ok True if thread found a solution
self.N the dimension of the board
self.board the NxN board used by thread to find solution
self.doneEvent an Event shared by all theads and main. cleared
by main() which bock-waits on it until a thread
finds a solution and sets the event, which awakens
main().
"""
def __init__( self, N, col, doneEvent ):
"""constructor. Initializes parent class and set all local members"""
threading.Thread.__init__( self )
self.col = col
self.N = N
self.doneEvent = doneEvent
self.board = self.makeBoard( N )
self.ok = False
self.timeToStop = False
def run( self ):
"""will be called by start(), automatically. The workhorse member function
that does all the work"""
self.board[ 0 ][ self.col ] = QUEEN
self.markLowerBoard( self.board, 0, self.col, 1 )
self.ok = self.tryRow( self.board, 1, self.N )
#--- tell main program if we've found a solution ---
if self.ok:
self.doneEvent.set()
def stop( self ):
"""call this member function to tell the thread to stop running. Another thread
has found a solution."""
self.timeToStop = True
def getStatus( self ):
"""returns whether the thread was successful (ok=true) or not finding
a solution """
return self.ok
def getBoard( self ):
"""return the current board with the queens positions"""
return self.board
def makeBoard( self, N ):
"""create a 2-D array of ints with dimension N
Returns the 2D array"""
board = []
for i in range( N ):
board.append( [] )
for j in range( N ):
board[i].append( EMPTY )
return board
def markLowerBoard( self, board, row, col, offset ):
"""Once a queen is positioned at location (row,col),
all the cells on a lower diagonal and lower vertical
of this queen must be marqued as unavailable so that
another queen cannot be put in this place"""
N = len( board )
diagleft = col-1
diagright = col+1
# mark all lower rows on diagonals and vertical
for r in range( row+1, N ):
if diagleft >=0: board[r][diagleft] += offset
if diagright <N: board[r][diagright] += offset
board[r][col] += offset
diagleft -= 1
diagright += 1
def tryRow( self, board, row, N ):
""" put a queen on give row, and recursively try all queens
on successive rows"""
if row >= N:
return True #we found a solution!
for col in range( N ):
if self.timeToStop:
return False
if board[row][col] == EMPTY:
# put a queen here
board[ row ][ col ] = QUEEN
self.markLowerBoard( board, row, col, +1 )
ok = self.tryRow( board, row+1, N )
if not ok:
# backtrack
board[ row ][ col ] = EMPTY
self.markLowerBoard( board, row, col, -1 )
else:
return True
return False
def goHome():
"""on terminals supporting ANSI chars, puts cursor top left of screen"""
sys.stderr.write( "\x1b[0;0H" )
def displaySolution( board ):
"""displays the series of column indexes where the Queens reside"""
list = []
for i in range( len( board ) ):
for j in range( len( board ) ):
if board[ i ][ j ]==QUEEN:
list.append( str( j ) )
print "Solution = ", ','.join( list )
def displayBoard( board, home=False ):
"""display the 2D array, showing empty cells as .
and queens as Q"""
if home: goHome()
for i in range( len( board ) ):
for j in range( len( board ) ):
if board[i][j]==QUEEN:
print 'Q',
else:
print '.',
print
displaySolution( board )
#------------------------------------------------------------------------
def main():
"""
Finds the solution to the N-Queens by launching N threads, each
one assuming the first queen is located on the Nth column of the
first row of the board.
"""
if len( sys.argv ) < 2:
print "Syntax: threadedNQueens.py N"
print " where N is the # of queens"
return
#--- start measuring execution time ---
perf = timePerfClass()
perf.start()
#--- get dimension of board ---
N = int( sys.argv[1] )
#--- create an event that will enable a thread to signal main() ----
doneEvent = threading.Event()
doneEvent.clear()
#--- create N threads and keep them in a list ---
threadList = []
for col in range( N ):
newThread = queenThread( N, col, doneEvent ) # new thread
threadList.append( newThread ) # add to list
newThread.start() # start it
print "all threads started!"
#--- wait for first successful thread to issue a notify on cond ---
print "blocking and waiting for a thread to succeed..."
doneEvent.wait()
print "Solution found!"
#--- stop timing and display execution times ---
perf.stop()
perf.printElapsed()
#--- find (a) thread with a solution and display it---
for threadQ in threadList:
if threadQ.getStatus() == True:
displayBoard( threadQ.getBoard() )
break
#--- tell all threads to stop ---
print "notifying threads to stop"
for threadQ in threadList:
threadQ.stop()
#---waiting for threads to finish ---
while len( threading.enumerate() ) > 1: # 1 because main is still running
time.sleep( 0.5 )
if __name__=="__main__":
main()
