CSC231: N-Queens Problem: interpreted vs compiled

--D. Thiebaut 14:44, 1 December 2010 (UTC)

---

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