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 47 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.
