Difference between revisions of "CSC352 multiprocessingNQueens.py"

From dftwiki3
Jump to: navigation, search
(→‎Output)
(→‎Source)
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] 01:49, 11 February 2010 (UTC)
 
--[[User:Thiebaut|D. Thiebaut]] 01:49, 11 February 2010 (UTC)
 
----
 
----
 +
__TOC__
 +
 
==Source==
 
==Source==
−
<source lang="python">
+
The code relating to the multiprocessing feature is highlighted in yellow.
 +
<br>
 +
<source lang="python"  highlight="18,103,104,105,106,107,108,109,110,111,125,126,127,128,130,131,132,133,135,136,138,141,142,146,147">
 
#! /usr/bin/python
 
#! /usr/bin/python
 
# D. Thiebaut
 
# D. Thiebaut
Line 41: Line 45:
  
 
def displaySolution( board ):
 
def displaySolution( board ):
 +
  """Display the solution as a list of column indexes"""
 
   list = []
 
   list = []
 
   for i in range( len( board ) ):
 
   for i in range( len( board ) ):
Line 152: Line 157:
  
 
</source>
 
</source>
 +
 +
==Unformatted Source==
 +
 +
<code><pre>
 +
#! /usr/bin/python
 +
# D. Thiebaut
 +
# This is the multiprocessing version of the N-Queens problem.
 +
# It uses the multiprocessing module available starting with Python 2.6
 +
# Usage:
 +
#    python multiprocessingNQueens.py  N
 +
# or
 +
#  time python multiprocessingNQueens.py  N
 +
# or
 +
#  /usr/bin/time python multiprocessingNQueens.py N
 +
#
 +
# where N is the number of queens wanted, i.e. the dimension
 +
# of the board.
 +
#
 +
 +
import sys
 +
import time
 +
import multiprocessing
 +
 +
QUEEN = -10
 +
EMPTY = 0
 +
 +
 +
 +
def makeBoard( 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 goHome():
 +
    sys.stderr.write( "\x1b[0;0H" )
 +
 +
def displaySolution( board ):
 +
  """Display the solution as a list of column indexes"""
 +
  list = []
 +
  for i in range( len( board ) ):
 +
      for j in range( len( board ) ):
 +
          if board[ i ][ j ]==QUEEN:
 +
              list.append( str( j ) )
 +
  print "Solution (%2d queens): " % len( list ), ','.join( list ), ' '*20
 +
 +
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 markLowerBoard( 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( board, row,  N, foundOne, queue, display=False ):
 +
    """ put a queen on give row, and recursively try all queens
 +
    on successive rows"""
 +
    if row >= N:
 +
      return True #we found a solution!
 +
 +
    if display:
 +
        displayBoard( board, True )
 +
 +
    for col in range( N ):
 +
        # if a solution has been found, stop
 +
        if foundOne.value == 1:
 +
            return False
 +
        if board[row][col] == EMPTY:
 +
            # put a queen here
 +
            board[ row ][ col ] = QUEEN
 +
            markLowerBoard( board, row, col, +1 )
 +
            ok = tryRow( board, row+1, N, foundOne, queue, display )
 +
            if not ok:
 +
                # backtrack
 +
                board[ row ][ col ] = EMPTY
 +
                markLowerBoard( board, row, col, -1 )
 +
            else:
 +
                return True
 +
    return False         
 +
 +
def firstQueenAt( col, N, foundOne, queue ):
 +
    board = makeBoard( N )
 +
    board[0][col] = QUEEN
 +
    markLowerBoard( board, 0, col, +1 )
 +
    ok = tryRow( board, 1, N, foundOne, queue, False )
 +
    if ok:
 +
        foundOne.value = 1
 +
        queue.put( board )
 +
        #displayBoard( board )
 +
 +
 +
def main():
 +
    if len( sys.argv ) < 2:
 +
        print "Syntax: nqueens.py N"
 +
        print "        where N is the # of queens"
 +
        return
 +
 +
    #--- get dimension, create board, and solve! ---
 +
    N = int( sys.argv[1] )
 +
 +
    # set bool to True to display progress...
 +
    list = []
 +
    foundOne = multiprocessing.Value( 'i', 0 ) # create shared memory value
 +
                                          # containing an int and set it
 +
                                          # to false   
 +
    queue = multiprocessing.Queue()
 +
 +
    for i in range( N ):
 +
        p = multiprocessing.Process( target=firstQueenAt, args=( i, N, foundOne, queue ) )
 +
        p.start()
 +
        list.append( p )
 +
 +
    while foundOne.value == 0:
 +
        time.sleep( 0.1 )
 +
 +
    board = queue.get()
 +
    displayBoard( board )
 +
 +
    for p in list:
 +
        p.join()
 +
   
 +
    print "\nDone!"
 +
 +
if __name__=="__main__":
 +
    main()
 +
</pre></code>
  
 
==Output==
 
==Output==

Latest revision as of 11:37, 22 April 2010

--D. Thiebaut 01:49, 11 February 2010 (UTC)

Source

The code relating to the multiprocessing feature is highlighted in yellow. 

#! /usr/bin/python
# D. Thiebaut
# This is the multiprocessing version of the N-Queens problem.
# It uses the multiprocessing module available starting with Python 2.6
# Usage:
#    python multiprocessingNQueens.py  N
# or
#   time python multiprocessingNQueens.py  N
# or
#   /usr/bin/time python multiprocessingNQueens.py N
#
# where N is the number of queens wanted, i.e. the dimension
# of the board.
#

import sys
import time
import multiprocessing 

QUEEN = -10
EMPTY = 0



def makeBoard( 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 goHome():
    sys.stderr.write( "\x1b[0;0H" )

def displaySolution( board ):
  """Display the solution as a list of column indexes"""
  list = []
  for i in range( len( board ) ):
      for j in range( len( board ) ):
          if board[ i ][ j ]==QUEEN:
              list.append( str( j ) )
  print "Solution (%2d queens): " % len( list ), ','.join( list ), ' '*20

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 markLowerBoard( 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( board, row,  N, foundOne, queue, display=False ):
    """ put a queen on give row, and recursively try all queens
    on successive rows"""
    if row >= N:
       return True #we found a solution!

    if display:
        displayBoard( board, True )

    for col in range( N ):
        # if a solution has been found, stop
        if foundOne.value == 1:
            return False
        if board[row][col] == EMPTY:
            # put a queen here
            board[ row ][ col ] = QUEEN
            markLowerBoard( board, row, col, +1 )
            ok = tryRow( board, row+1, N, foundOne, queue, display )
            if not ok:
                # backtrack
                board[ row ][ col ] = EMPTY
                markLowerBoard( board, row, col, -1 )
            else:
                return True
    return False           

def firstQueenAt( col, N, foundOne, queue ):
    board = makeBoard( N )
    board[0][col] = QUEEN
    markLowerBoard( board, 0, col, +1 )
    ok = tryRow( board, 1, N, foundOne, queue, False )
    if ok:
        foundOne.value = 1
        queue.put( board )
        #displayBoard( board )


def main():
    if len( sys.argv ) < 2:
        print "Syntax: nqueens.py N"
        print "        where N is the # of queens"
        return

    #--- get dimension, create board, and solve! ---
    N = int( sys.argv[1] )

    # set bool to True to display progress...
    list = []
    foundOne = multiprocessing.Value( 'i', 0 ) # create shared memory value
                                           # containing an int and set it
                                           # to false    
    queue = multiprocessing.Queue()

    for i in range( N ):
        p = multiprocessing.Process( target=firstQueenAt, args=( i, N, foundOne, queue ) )
        p.start()
        list.append( p )

    while foundOne.value == 0:
        time.sleep( 0.1 )

    board = queue.get()
    displayBoard( board )

    for p in list:
        p.join()
    
    print "\nDone!"

if __name__=="__main__":
    main()

Unformatted Source

#! /usr/bin/python
# D. Thiebaut
# This is the multiprocessing version of the N-Queens problem.
# It uses the multiprocessing module available starting with Python 2.6
# Usage:
#    python multiprocessingNQueens.py  N
# or
#   time python multiprocessingNQueens.py  N
# or
#   /usr/bin/time python multiprocessingNQueens.py N
#
# where N is the number of queens wanted, i.e. the dimension
# of the board.
#

import sys
import time
import multiprocessing 

QUEEN = -10
EMPTY = 0



def makeBoard( 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 goHome():
    sys.stderr.write( "\x1b[0;0H" )

def displaySolution( board ):
  """Display the solution as a list of column indexes"""
  list = []
  for i in range( len( board ) ):
      for j in range( len( board ) ):
          if board[ i ][ j ]==QUEEN:
              list.append( str( j ) )
  print "Solution (%2d queens): " % len( list ), ','.join( list ), ' '*20

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 markLowerBoard( 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( board, row,  N, foundOne, queue, display=False ):
    """ put a queen on give row, and recursively try all queens
    on successive rows"""
    if row >= N:
       return True #we found a solution!

    if display:
        displayBoard( board, True )

    for col in range( N ):
        # if a solution has been found, stop
        if foundOne.value == 1:
            return False
        if board[row][col] == EMPTY:
            # put a queen here
            board[ row ][ col ] = QUEEN
            markLowerBoard( board, row, col, +1 )
            ok = tryRow( board, row+1, N, foundOne, queue, display )
            if not ok:
                # backtrack
                board[ row ][ col ] = EMPTY
                markLowerBoard( board, row, col, -1 )
            else:
                return True
    return False           

def firstQueenAt( col, N, foundOne, queue ):
    board = makeBoard( N )
    board[0][col] = QUEEN
    markLowerBoard( board, 0, col, +1 )
    ok = tryRow( board, 1, N, foundOne, queue, False )
    if ok:
        foundOne.value = 1
        queue.put( board )
        #displayBoard( board )


def main():
    if len( sys.argv ) < 2:
        print "Syntax: nqueens.py N"
        print "        where N is the # of queens"
        return

    #--- get dimension, create board, and solve! ---
    N = int( sys.argv[1] )

    # set bool to True to display progress...
    list = []
    foundOne = multiprocessing.Value( 'i', 0 ) # create shared memory value
                                           # containing an int and set it
                                           # to false    
    queue = multiprocessing.Queue()

    for i in range( N ):
        p = multiprocessing.Process( target=firstQueenAt, args=( i, N, foundOne, queue ) )
        p.start()
        list.append( p )

    while foundOne.value == 0:
        time.sleep( 0.1 )

    board = queue.get()
    displayBoard( board )

    for p in list:
        p.join()
    
    print "\nDone!"

if __name__=="__main__":
    main()

Output

Command to invoke the program: 

 chmod +x multiprocessingNQueens.py
 time ./multiprocessingNQueens.py 18

Output: 

. . . . . . . . . . . . . . . . . Q
Q . . . . . . . . . . . . . . . . .
. . Q . . . . . . . . . . . . . . .
. . . . Q . . . . . . . . . . . . .
. Q . . . . . . . . . . . . . . . .
. . . . . . . Q . . . . . . . . . .
. . . . . . . . . . Q . . . . . . .
. . . . . . . . . . . . . . Q . . .
. . . . . . Q . . . . . . . . . . .
. . . . . . . . . . . . . . . Q . .
. . . . . . . . . . . . . Q . . . .
. . . . . . . . . . . . . . . . Q .
. . . Q . . . . . . . . . . . . . .
. . . . . Q . . . . . . . . . . . .
. . . . . . . . Q . . . . . . . . .
. . . . . . . . . . . Q . . . . . .
. . . . . . . . . Q . . . . . . . .
. . . . . . . . . . . . Q . . . . .
Solution (18 queens):  17,0,2,4,1,7,10,14,6,15,13,16,3,5,8,11,9,12                     

Done!

real	0m3.074s
user	0m4.872s
sys	0m1.024s






Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC352_multiprocessingNQueens.py&oldid=7048"