1.6 Backtracking I: The n-queens problem

by Marko Riedel

1.6.1 Idea

The n-queens problem consists in placing n non-attacking queens on an n-by-n chess board. A queen can attack another queen vertically, horizontally, or diagonally. E.g. placing a queen on a central square of the board blocks the row and column where it is placed, as well as the two diagonals (rising and falling) at whose intersection the queen was placed.

The algorithm to solve this problem uses backtracking, but we will unroll the recursion. The basic idea is to place queens column by column, starting at the left. New queens must not be attacked by the ones to the left that have already been placed on the board. We place another queen in the next column if a consistent position is found. All rows in the current column are checked. We have found a solution if we placed a queen in the rightmost column. A solution to the five-queens problem is shown in Figure 4.


PIC

Figure 4: Solution to the five-queens problem.


Recursion is the obvious choice to implement this algorithm. We have an additional requirement, however. The user should be able to run the search step by step as well as automatically. E.g. she may want to halt the search at the middle column and observe how subsequent queens are placed. We would have to somehow stop and restart a sequence of nested calls if recursion were used. We record the state of the search instead. First, we record where queens have so far been placed on the board. Second, we record which row of the rightmost column we are currently checking.

The GUI is simple. We draw the board and the queens that have so far been placed. Placed queens are drawn in black. The board is drawn in blue during backtracking and in green if a solution was found. The queen that we are currently trying to place is drawn in red. The application’s menu lets the user single-step through the search or choose to run it automatically. The algorithm returns to the initial position after all positions have been searched.

The application’s structure is straightforward. There are two classes: a controller and a subclass of NSView. The controller is the application’s delegate. It parses command-line arguments, sets up and responds to the main menu and controls the timer that is used during automated searches. The view draws the board and knows how to move from one state of the search to the next.

1.6.2 Implementation

We start by including the usual headers and define a constant that determines the width in pixels of a single cell of the board. The class QView:NSView represents and draws the board. Its instance variables store the size of the board, the number of solutions found during the current run and the state of the search. The latter is determined by the array board, whose indices correspond to columns and values to rows. It records where queens have been placed. The value of candidate records where in the rightmost empty column we are trying to place the next queen.

 
#include <Foundation/Foundation.h> 
#include <AppKit/AppKit.h> 
 
#define CELLSIZE 60 
 
@interface QView : NSView 
{ 
    int d; 
    NSMutableArray *board; 
    int candidate; 
    int solCount; 
}

There are only a few methods in the implementation of QView. The initializer creates a view of the right size for the given dimension (width/height). The method drawRect: is where the view draws itself. The most important method is next, which advances from one state of the search to the next. There is a method that returns a boolean that indicates whether the current state of the board represents a solution.

 
- initWithDimension:(int)dim; 
- (void)drawRect:(NSRect)aRect; 
 
 
- next; 
 
- (BOOL)isSolution; 
 
@end

The initializer is straighforward. It invokes the initializer of its superclass NSView with a rectangle of the appropriate dimensions. It creates the mutable array that holds the board. It is empty because initially there is no queen on the board. We start at column zero, with the bottom position being the first of d positions that must be checked, hence the value of candidate is zero. The counter for the number of solutions that have been found is set to zero.

 
@implementation QView 
 
- initWithDimension:(int)dim 
{ 
    d = dim; 
    [super initWithFrame:NSMakeRect(0, 0, d*CELLSIZE, d*CELLSIZE)]; 
 
    board = [NSMutableArray arrayWithCapacity:d]; 
    [board retain]; 
 
    candidate = 0; 
 
    solCount = 0; 
 
    return self; 
}

The method drawRect is NSView’s designated draw method where the view draws itself. The background of the board is green if the current state of the board represents a solution and blue otherwise. The variable mx holds the width and height of the view in pixels.

 
- (void)drawRect:(NSRect)aRect 
{ 
    int mx = d*CELLSIZE; 
 
    [([self isSolution] ? 
      [NSColor greenColor] : [NSColor blueColor]) set]; 
    PSrectfill(0, 0, mx, mx);

The next step is to draw the grid, which consists of 2n + 2 lines, n + 1 horizontal ones and n + 1 vertical ones. The loop draws the lines in pairs, moving in parallel from bottom to top and from left to right.

 
    [[NSColor blackColor] set]; 
    PSsetlinewidth(2.0); 
    int l; 
    for(l=0; l<=mx; l+=CELLSIZE){ 
        PSmoveto(0, l); 
        PSlineto(mx, l); 
        PSmoveto(l, 0); 
        PSlineto(l, mx); 
    } 
    PSstroke();

We now draw the queens using the data stored in the array board. A queen is represented by a black filled circle whose radius is a quarter of the cell size. The queen is centered in the respective cell.

 
    int col, placed = [board count]; 
    for(col=0; col<placed; col++){ 
        PSarc(col*CELLSIZE+ 
              CELLSIZE/2, 
              [[board objectAtIndex:col] intValue]*CELLSIZE+ 
              CELLSIZE/2, 
              CELLSIZE/4, 0, 360); 
        PSfill(); 
    }

It remains to draw the queen that is currently being checked. It is farthest to the right and hence its column index is the number of queens already placed. The value of candidate determines the row.

 
    if(placed<d){ 
        [[NSColor redColor] set]; 
        PSarc(placed*CELLSIZE+ 
              CELLSIZE/2, 
              candidate*CELLSIZE+ 
              CELLSIZE/2, 
              CELLSIZE/4, 0, 360); 
        PSfill(); 
    } 
}

We move on to the most important part of this recipe, i.e. the method that takes the search from one state to the next. We first extract the number of queens that have been placed on the board. The current candidate resides in the column to the right of the rightmost queen, where candidate determines in what row the candidate is placed. The latter value increases during the search. It starts at the bottom row and is incremented until the top row is reached, one increment per state change.

 
- next 
{ 
    int placed = [board count];

The candidate is admissible only if it is consistent with the queens that are already on the board, i.e. if it is not attacked by/does not attack any of these queens. We check each of them in turn. If the candidate is in the same row or column or diagonal then the position is not consistent. Rows and columns are easy to check. Use the following observation for diagonals. A falling diagonal has the equation y = -x + p. Two queens that lie on the same falling diagonal have the same value for y + x. A rising diagonal has the equation y = x + p. Two queens that lie on the same rising diagonal have the same value for y - x. A candidate is consistent if it passes the check for all queens that are already on the board.

 
    BOOL consistent = YES; 
    int col; 
    for(col=0; col<placed; col++){ 
        int row = [[board objectAtIndex:col] intValue]; 
        if(row==candidate ∣∣ 
           col==placed ∣∣ 
           row+col == candidate+placed ∣∣ 
           row-col == candidate-placed){ 
            consistent = NO; 
            break; 
        } 
    }

If the candidate’s position is consistent, then we place a queen on the board and position the next candidate at the very bottom of the next column. The consistency check is also run if a solution has been found. It fails in this case because all available rows are blocked. Hence no new extra queen is ever added to the right of the right side of the board, and a solution leads to the else clause, where we increment the solution count, remove the rightmost successfully placed queen and make the cell just above it the new candidate we must check. We move the candidate up one cell otherwise, i.e. when the position is not consistent.

 
    if(consistent==YES){ 
        [board addObject:[NSNumber numberWithInt:candidate]]; 
        candidate = 0; 
    } 
    else{ 
        if(placed==d){ 
            candidate = [[board lastObject] intValue]+1; 
            [board removeLastObject]; 
            solCount++; 
        } 
        else{ 
            candidate++; 
        }

We backtrack to the rightmost column that has not been checked completely. A row value of d indicates that a column has been checked. We move backwards from the right to the left, eliminating columns that we have checked. The new candidate position in a given column is one cell above the previous position, hence the increment.

 
        while(candidate==d && [board count]){ 
            candidate = [[board lastObject] intValue]+1; 
            [board removeLastObject]; 
        }

There remains some housekeeping to do. We can detect the transition from the last state to the first by checking whether the previous state was the top position of the first column. If this is the case, then we can output the number of solutions found and reset the solution counter to zero.

 
        if(![board count] && candidate==d){ 
            candidate = 0; 
            NSLog(@”found_%d_solutions_to_the_%d-queens_problem”, 
                   solCount, d); 
            solCount = 0; 
        } 
    }

The method triggers a redisplay at the end since the state of the board has certainly changed.

 
    [self display]; 
    return self; 
}

Sometimes the controller needs to know whether the current state of the board represents a solution or not. This is the purpose of isSolution. We have a solution if the number of queens on the board equals the number of rows/columns of the board.

 
- (BOOL)isSolution 
{ 
    return([board count]==d); 
} 
 
@end

We are now ready to move on to the controller. Recall that the user may step through a search or run it automatically. The latter case requires a timer. We define two constants that determine how much time elapses between firings of the timer. It fires quickly (after 0.15 seconds) if the current position does not represent a solution, and waits a full five seconds otherwise.

 
#define FAIL_PAUSE 0.15 
#define SOL_PAUSE 5

The controller obviously needs to keep track of the QView. It also stores whether the search is currently running automatically or not. There is an invocation for use with the timer (we use the same invocation again and again). The controller also stores the timer.

 
@interface Controller : NSObject 
{ 
    QView *qv; 
 
    BOOL running; 
 
    NSInvocation *inv; 
    NSTimer *tm; 
}

The controller is the application’s delegate and applicationDidFinishLaunching: is its most important method, where it initializes the menu, creates the window with the board and prepares for use of the timer. The three methods runSearch:, haltSearch: and next: are invoked through clicks on the application’s main menu. They run the search, halt it or advance it by a single step, respectively. The method validateMenuItem: enables and disables the corresponding entries on the main menu according to the run state of the application. The method tick is invoked when the timer fires.

 
- (void)applicationDidFinishLaunching:(NSNotification *)notif; 
 
- runSearch:(id)sender; 
- haltSearch:(id)sender; 
- next:(id)sender; 
 
- (BOOL)validateMenuItem:(NSMenuItem*)anItem; 
 
- tick; 
 
@end

The method validateMenuItem: recognizes menu items by tags. This is recommended for large applications where internationalization plays a role; i.e. we do not want to depend on the title of an item, as it may change. (Thanks Fabien Vallon for the hint.)

 
typedef enum { 
    MENU_START, 
    MENU_STOP, 
    MENU_NEXT, 
    MENU_QUIT 
} MENU_TAG;

The first thing applicationDidFinishLaunching: does is to query the command line arguments. The second argument contains the size of the board.

 
@implementation Controller 
 
- (void)applicationDidFinishLaunching:(NSNotification *)notif 
{ 
    NSProcessInfo *procInfo = [NSProcessInfo processInfo]; 
    NSArray *args = [procInfo arguments];

The next step is to build the application’s menu and set the tags of each item. There are three entries to control the search: run, halt and next. The fourth entry of the menu quits the application. We assign and display the menu.

 
    NSMenu *menu = [NSMenu new]; 
 
    [[menu addItemWithTitle: @”Run” 
           action:@selector(runSearch:) 
           keyEquivalent:@””] setTag:MENU_START]; 
    [[menu addItemWithTitle: @”Halt” 
           action:@selector(haltSearch:) 
           keyEquivalent:@””] setTag:MENU_STOP]; 
    [[menu addItemWithTitle: @”Next” 
           action:@selector(next:) 
           keyEquivalent:@””] setTag:MENU_NEXT]; 
    [[menu addItemWithTitle: @”Quit” 
           action:@selector(terminate:) 
           keyEquivalent:@”q”] setTag:MENU_QUIT]; 
 
    [NSApp setMainMenu:menu]; 
 
    [menu display];

We require exactly one argument, namely the size of the board.

 
    if([args count]!=2){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”usage:_%@_<n>, 
                      [procInfo processName]]; 
    }

The command line argument is a string. We require a scanner to retrieve the integer value from the string. We throw an exception if the scanner fails or the board is to small (min. is a two by two).

 
    NSScanner *scn = 
        [NSScanner scannerWithString:[args objectAtIndex:1]]; 
    int dim = -1; 
    if([scn scanInt:&dim]==NO ∣∣ dim<2){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”integer_board_size_>=_2,_please;_” 
                      @”got_%d”, dim]; 
    }

The intial state is step mode, i.e. we are not running.

 
    running = NO;

We are ready to instantiate the QView that will perform the search and display the board.

 
    qv = [[QView alloc] initWithDimension:dim];

The next step is to build the window. The size of the content rectangle is equal to the size of the view, since it will be the content view of the window. We allocate and initialize the window, which is titled, but not resizable. The title of the window indicates what size of queens problem we are solving.

 
    NSWindow *qWin; 
    NSRect winRect; 
 
    winRect.origin = NSMakePoint(0, 0); 
    winRect.size = [qv bounds].size; 
 
    qWin = [[NSWindow alloc] 
                initWithContentRect:winRect 
                styleMask:NSTitledWindowMask 
                backing:NSBackingStoreBuffered 
                defer:NO]; 
    [qWin 
        setTitle: 
            [NSString stringWithFormat:@”%d_queens_problem”, dim]];

We place the view in the window, center it and make it appear on screen.

 
    [qWin setContentView:qv]; 
 
    [qWin center]; 
    [qWin makeKeyAndOrderFront:nil];

The last step is to create the one invocation that will be used with all timers. It captures the target object (the controller) and the selector (tick). It is retained because it must persist throughout the lifetime of the application.

 
    inv = [NSInvocation 
              invocationWithMethodSignature: 
                   [self methodSignatureForSelector: 
                             @selector(tick)]]; 
    [inv setSelector:@selector(tick)]; 
    [inv setTarget:self]; 
    [inv retain]; 
}

The method runSearch: is invoked via the main menu. It sets the internal state to “running” and schedules a timer that fires at FAIL_PAUSE intervals.

 
- runSearch:(id)sender 
{ 
    running = YES; 
    tm = [NSTimer scheduledTimerWithTimeInterval:FAIL_PAUSE 
                   invocation:inv 
                   repeats:YES]; 
 
    return self; 
}

The method haltSearch: resets the internal state to “halted” and invalidates the timer, which stops firing and is autoreleased.

 
- haltSearch:(id)sender 
{ 
    running = NO; 
    [tm invalidate]; 
 
    return self; 
}

The method next: is invoked from the menu and advances the search one step.

 
- next:(id)sender 
{ 
    [qv next]; 
    return self; 
}

The method validateMenuItem: is invoked by the application object. It checks for three cases when a menu item should be disabled: the “stop” item when we are not running, the “start” item when we are running and the “next” item when we are running.

 
- (BOOL)validateMenuItem:(NSMenuItem*)anItem 
{ 
    MENU_TAG tag = [anItem tag]; 
 
    if((tag==MENU_STOP && !running) ∣∣ 
       (tag==MENU_START && running) ∣∣ 
       (tag==MENU_NEXT && running)){ 
        return NO; 
    } 
 
    return YES; 
}

The last method is called tick and it is invoked by the timer. It advances the search by a single step and checks whether a solution has been found, in which case the timer is set to fire after SOL_PAUSE seconds, so that the user has time to inspect the structure of the solution.

 
- tick 
{ 
    [qv next]; 
    if([qv isSolution]){ 
        [tm setFireDate: 
                [NSDate dateWithTimeIntervalSinceNow:SOL_PAUSE]]; 
    } 
 
    return self; 
} 
 
@end

The function main concludes the recipe. It sets up an autorelease pool, creates the application object and makes the controller be its delegate. It then runs the application. The autorelease pool is released on exit.

 
int main(int argc, char** argv, char **env) 
{ 
    NSAutoreleasePool *pool = [NSAutoreleasePool new]; 
 
    NSApplication *app; 
 
    app = [NSApplication sharedApplication]; 
    [app setDelegate:[Controller new]]; 
    [app run]; 
 
    [pool release]; 
    exit(0); 
}