CSC231: N-Queens Problem: interpreted vs compiled
--D. Thiebaut 14:44, 1 December 2010 (UTC)
Contents
the C Version of the N-Queens Problem
/* queensdemo.c D. Thiebaut Position N queens on an NxN chess board Typical output: +--------------------------------+ | Q | | . . Q | | . . . . Q | | . Q . . . . | | . . . . . . Q | | . . . . . . . . Q . . . | | . . . . . . . . . . Q . | | . . . . . . . . . . Q . . . .| | . . . . . . . . . . . . Q .| | . . . . Q . . . . . . . . .| | . . . . . . . . . . . . . . Q| | . . . . . . Q . . . . . . . .| | . . . Q . . . . . . . . . . .| | . . . . . . . . . Q . . . . .| | . . . . . . . Q . . . . . . . .| | . . . . . . . . . Q . . . . . .| +--------------------------------+ solution 0: 0 2 4 1 12 8 13 11 14 5 15 6 3 10 7 9 The dots represent position in the 16x16 board where a queen would be taken, if positioned at that place. This version is animated and shows all the backtracking of the recursive search function (which is not optimized). */ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MAXN 25 #define EMPTY 0 #define TAKEN 1 #define QUEEN -1000 /* ---- prototoype ---- */ void clrscr(void); void gotoxy(int, int); void Display(int Chessboard[][MAXN], int); int AddQueen(int, int Chessboard[][MAXN], int); void Init(int CHessboard[][MAXN]); int Syntax(int argc, char *argv[]); void Print(int Chessboard[][MAXN], int N); /* ------------------------------------------------------- */ main(int argc, char *argv[]) { int N; int Chessboard[MAXN][MAXN]; N=Syntax(argc, argv); Init(Chessboard); Display(Chessboard,N); if (AddQueen(/* row */ 0, Chessboard, N)) printf("N=%d solution found!",N); else printf("N=% no solutions found!",N); } int AddQueen(int row, int Chessboard[][MAXN], int N) { int col, r, c; for (col=0; col<N; col++) if (Chessboard[row][col]==EMPTY) { /*--- put a queen on board ---*/ Chessboard[row][col]=QUEEN; Display(Chessboard, N); /*--- mark lower diagonals ---*/ for (r=row+1, c=col+1; r<N && c < N; r++, c++) Chessboard[r][c]++; /* mark cells on the diagonal as taken */ for (r=row+1, c=col-1; r<N && c >=0; r++, c--) Chessboard[r][c]++; /* mark cells on other diag. as taken */ for (r=row+1; r<N; r++) Chessboard[r][col]++; /*--- if on last row, then we found a solution! ---*/ if (row==N-1) { Print(Chessboard, N); return 1; } else /*--- otherwise, add another queen ---*/ if (AddQueen(row+1, Chessboard, N)) return 1; /*--- we're now backtracking. Remove present queen ---*/ /*--- put a queen on board ---*/ Chessboard[row][col]=EMPTY; /*--- mark lower diagonals ---*/ for (r=row+1, c=col+1; r<N && c < N; r++, c++) Chessboard[r][c]--; /* unmark cells on the diagonal */ for (r=row+1, c=col-1; r<N && c >=0; r++, c--) Chessboard[r][c]--; /* unmark cells on other diag */ for (r=row+1; r<N; r++) Chessboard[r][col]--; } Display(Chessboard, N); return 0; } /* ------------------------------------------------------- */ void Print(int Chessboard[][MAXN], int N) { static int count=0; int r, c; printf("solution %2d: ",count++); for (r=0; r<N; r++) for (c=0; c<N; c++) if (Chessboard[r][c]==QUEEN) printf("%d ",c); printf("\n"); } /* ------------------------------------------------------- */ void Display(int Chessboard[][MAXN], int N) { int r, c; gotoxy(1,1); printf("+"); for (c=0; c<N; c++) printf("--"); printf("+\n"); for (r=0; r<N; r++) { printf("|"); for (c=0; c<N; c++) if (Chessboard[r][c]==QUEEN) printf(" Q"); else if (Chessboard[r][c]==EMPTY) printf(" "); else printf(" ."); printf("|\n"); } printf("+"); for (c=0; c<N; c++) printf("--"); printf("+\n"); } /* ------------------------------------------------------- */ void Init(int Chessboard[][MAXN]) { int row,col; for (row=0; row <MAXN; row++) for (col=0; col<MAXN; col++) Chessboard[row][col]=EMPTY; } /* ------------------------------------------------------- */ int Syntax(int argc, char *argv[]) { if (argc <= 1) { fprintf(stderr,"Syntax: queens N\n"); fprintf(stderr,"where N is the size of the chessboardn"); exit(1); } return atoi(argv[1]); } /* ------------------------------------------------------- */ void gotoxy(int x, int y) { printf("%c[%d;%dH",27,x,y); } /* ------------------------------------------------------- */ void clrscr(void) { gotoxy(1,1); printf("%c[J",27); }
Python Version
#! /usr/bin/python # D. Thiebaut # Usage: # nqueens.py N # where N is the number of queens wanted, i.e. the dimension # of the board. # import sys import time QUEEN = -10 EMPTY = 0 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 self.clockEnd = 0 self.timeStart = 0 self.timeEnd = 0 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" 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 ): 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, 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 board[row][col] == EMPTY: # put a queen here board[ row ][ col ] = QUEEN markLowerBoard( board, row, col, +1 ) ok = tryRow( board, row+1, N, display ) if not ok: # backtrack board[ row ][ col ] = EMPTY markLowerBoard( board, row, col, -1 ) else: return True return False def main(): if len( sys.argv ) < 2: print "Syntax: nqueens.py N" print " where N is the # of queens" return #--- start measurement --- perf = timePerfClass() perf.start() #--- get dimension, create board, and solve! --- N = int( sys.argv[1] ) board = makeBoard( N ) # set bool to True to display progress... ok = tryRow( board, 0, N, False ) #--- stop measurement --- perf.stop() #perf.printElapsed() if ok: print "N = %d: Success!" % N #displayBoard( board ) if __name__=="__main__": main()
Comparison of the Execution times
- The two versions above are modified so that they do not display any information until they have found a solution. Also, the dimension of the board can be passed directly on the command line, as a simple number following the name of the executable.
- For the C program we compile two versions of the executable, both with gcc. One version is not optimized, the other optimized with -O3 (see man page for gcc for more information).
Python execution
% time for N in {10..25} ; do > python nqueens.py $N > done N = 10: Success! N = 11: Success! N = 12: Success! N = 13: Success! N = 14: Success! N = 15: Success! N = 16: Success! N = 17: Success! N = 18: Success! N = 19: Success! N = 20: Success! N = 21: Success! N = 22: Success! N = 23: Success! N = 24: Success! N = 25: Success! real 0m47.959s user 0m47.785s sys 0m0.131s
It takes 48 seconds for the python program to find the first solution for boards of size 10 to 25.
Compiled C-Program, no optimization
time for N in {10..25} ; do queensFirst_notOptimized $N done N=10 solution found! N=11 solution found! N=12 solution found! N=13 solution found! N=14 solution found! N=15 solution found! N=16 solution found! N=17 solution found! N=18 solution found! N=19 solution found! N=20 solution found! N=21 solution found! N=22 solution found! N=23 solution found! N=24 solution found! N=25 solution found! real 0m1.365s user 0m1.097s sys 0m0.032s
It takes 1.3 seconds to the executable program to find the same solutions for boards of dimensions 10 to 25
Optimized C Program
time for N in {10..25} ; do queensFirst_optimized $N done N=10 solution found! N=11 solution found! N=12 solution found! N=13 solution found! N=14 solution found! N=15 solution found! N=16 solution found! N=17 solution found! N=18 solution found! N=19 solution found! N=20 solution found! N=21 solution found! N=22 solution found! N=23 solution found! N=24 solution found! N=25 solution found! real 0m0.399s user 0m0.356s sys 0m0.031s
- It takes 0.4 seconds to the optimized program to find all 15 solutions.
Summary
Language | Execution Time |
---|---|
Python | 48 sec |
C | 1.4 sec |
C with -O3 optimization | 0.4 sec |