6.1 The Sixteen Puzzle

by Marko Riedel

6.1.1 Idea

The goal is to implement the sixteen puzzle. The classic version of this puzzle consists of fifteen pieces that are placed in a box that is four pieces wide and four pieces high. There is one empty slot. Pieces in the same row as the empty slot can move horizontally and those in the same column can move vertically. The pieces are scrambled and the goal is to restore the start position, which lists the pieces sequentially, starting from the top row. There seems to be some confusion as to whether this puzzle should be called the fifteen puzzle or the sixteen puzzle, we choose the latter. The start position is shown in Fig. 8.






1 2 3 4




5 6 7 8




9 101112




131415





Figure 8: Start configuration for the sixteen puzzle.


We will let the user choose how many pieces there should be to a single row or column. The user can pick any TIFF image she likes to use as the content of the pieces. These parameters are passed in via the command line.

6.1.2 Implementation

There are two components to this application. There is a view that displays the pieces and a controller that creates auxiliary objects like the main menu and the window that holds the view.

Start by declaring some constants: the minimum and maximum number of pieces per row/column and the minimum width and height of a single piece.

 
#import <Foundation/Foundation.h> 
#import <AppKit/AppKit.h> 
 
#define MINDIM 3 
#define MAXDIM 24 
 
#define PIECEMIN 20

The class SixteenView implements a view that draws all the pieces (a different approach might use one view for every piece). This view has two states: either scrambled or not scrambled. It displays the source image as is when it is in the latter state, otherwise it displays the individual pieces. It must also react to mouse clicks and move pieces accordingly.

Now discuss the variables. The view must remember the state of the board. It stores the state in the two-dimensional array board, where the first index determines the row and the second the column. The entries are integers where the integer m represents the piece that sits in row m∕d, where d is the size, and column m%d in the source image. The value -1 represents the blank. The variable bdim is used to store the number of pieces per row or column. We record the position of the blank in the variables blankX and blankY. There is a flag that indicates whether the view is scrambled or not. We store the source image in the variable image and the dimensions of the individual pieces in the variable pieceSize. We’ll be copying rectangular portions of the source image whose size is given by pieceSize in order to construct the image of the scrambled board.

 
@interface SixteenView : NSView 
{ 
    int board[MAXDIM][MAXDIM]; 
    int bdim; 
    int blankX, blankY; 
 
    BOOL scrambled; 
 
    NSImage *image; 
    NSSize pieceSize; 
}

There are only a few methods to SixteenView. There is an initializer that is invoked with the origin of the view, the source image, and the number of pieces per row and column.

We implement acceptsFirstResponder so that the board can be scrambled with a click on the application’s main menu. The method totalPositioned tells us how many pieces are in the right position. It will help us determine when the board is properly scrambled and when the user has solved the puzzle.

The method doMoveX:Y: is used to move pieces in response to clicks and while we scramble the pieces. Suppose the user clicks on a piece anywhere in the same row or column as the blank. The pieces move so that the blank is in the position that the user clicked on (there is only one way for them to go). The method scramble: scrambles the pieces. The last two methods are important: drawRect: must draw the view according to its internal state and mouseDown: processes mouse clicks by the user.

 
- initAtPoint:(NSPoint)loc withImage:(NSImage *)img 
 andDimension:(int)dim; 
 
- (BOOL)acceptsFirstResponder; 
 
- (int)totalPositioned; 
- doMoveX:(int)xpos Y:(int)ypos; 
- scramble:(id)sender; 
 
- (void)drawRect:(NSRect)aRect; 
- (void)mouseDown:(NSEvent *)theEvent; 
 
@end

The first thing the initializer does is to compute the frame of the view. It is determined by the position that was passed in as an argument and the size of the image. The width and the height of the image may not always be divisible by the number of rows and columns. Any leftover at the right or at the top will not be displayed, hence we reduce the frame size by those leftover amounts. We then invoke NSView’s method initWithFrame: as required to initialize the view.

 
@implementation SixteenView 
 
- initAtPoint:(NSPoint)loc withImage:(NSImage *)img 
 andDimension:(int)dim 
{ 
    NSRect frame; 
    int x, y; 
 
    frame.origin = loc; 
    frame.size = [img size]; 
 
    frame.size.width -= ((int)frame.size.width)%dim; 
    frame.size.height -= ((int)frame.size.height)%dim; 
 
    [super initWithFrame:frame];

The initializer stores the source image in the instance variable and computes the width and height of the individual pieces. It raises an exception if either is too small. We may store the dimension if there was no problem.

 
    image = img; 
 
    pieceSize.width = frame.size.width/dim; 
    pieceSize.height = frame.size.height/dim; 
 
    if(pieceSize.width<PIECEMIN ∣∣ 
       pieceSize.height<PIECEMIN){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”image_to_small_for_a_%dx%d”, 
                      dim, dim]; 
    } 
 
    bdim = dim;

Next we indicate that a new SixteenView is not in the scrambled state and initialize the board accordingly. The blank goes in the last column of the bottom row.

 
    scrambled = NO; 
    for(y=0; y<bdim; y++){ 
        for(x=0; x<bdim; x++){ 
            board[y][x] = y*bdim+x; 
        } 
    } 
    board[0][bdim-1] = -1; 
    blankX = bdim-1; blankY = 0; 
 
    return self; 
}

We implement acceptsFirstResponder so that the view may respond to action messages.

 
- (BOOL)acceptsFirstResponder 
{ 
    return YES; 
}

The method totalPositioned iterates over all positions on the board and records the number of pieces that are in the correct position.

 
- (int)totalPositioned 
{ 
    int x, y, count = 0; 
 
    for(y=0; y<bdim; y++){ 
        for(x=0; x<bdim; x++){ 
            if(board[y][x] == y*bdim+x){ 
                count++; 
            } 
        } 
    } 
 
    return count; 
}

The method doMoveX:Y: responds to a click at the position that is given by the two arguments. There are four cases. There is nothing to do if the user has clicked on the blank or on a piece that shares neither row nor column with the blank. The interesting cases occur when the user clicks on a piece in the same row or column as the blank. We move the pieces that lie between the click position and the blank, each piece by one position. They move down, if the user clicked above the blank, up, if the user clicked below, right, if the user clicked to the left and finally, left, if the user clicked to the right. These four cases are handled by loops that shift the pieces. We update the position of the blank.

 
- doMoveX:(int)xpos Y:(int)ypos 
{ 
    int mv; 
 
    if(xpos==blankX && ypos==blankY){ 
        NSBeep(); 
    } 
    else if(xpos==blankX){ 
        if(ypos>blankY){ // down 
            for(mv=blankY; mv<ypos; mv++){ 
                board[mv][xpos] = board[mv+1][xpos]; 
            } 
        } 
        else{ // up 
            for(mv=blankY; mv>ypos; mv--){ 
                board[mv][xpos] = board[mv-1][xpos]; 
            } 
        } 
        board[ypos][xpos] = -1; blankY = ypos; 
    } 
    else if(ypos==blankY){ 
        if(xpos>blankX){ // left 
            for(mv=blankX; mv<xpos; mv++){ 
                board[ypos][mv] = board[ypos][mv+1]; 
            } 
        } 
        else{ // right 
            for(mv=blankX; mv>xpos; mv--){ 
                board[ypos][mv] = board[ypos][mv-1]; 
            } 
        } 
        board[ypos][xpos] = -1; blankX = xpos; 
    } 
    else{ 
        NSBeep(); 
    } 
 
    return self; 
}

The method scramble: scrambles the board. It makes maxIter valid moves, where maxIter is the total number of pieces and checks that at most a quarter of the pieces are in the correct position. The process repeats if this is not the case (too many pieces placed correctly).

 
- scramble:(id)sender 
{ 
    int maxInPlace = bdim*bdim/4, maxIter = bdim*bdim, i;

There is an outer loop that checks the number of correctly placed pieces and an inner loop that carries out maxIter moves. Moves are determined as follows: first flip a coin to decide whether to move horizontally or vertically. Then pick a random position that is not equal to the position of the blank and carry out the move. How to avoid the position of the blank? First pick a position that is not the last position, then add one if it is larger than or equal to the blank’s position. This guarantees a uniformely random choice between the available positions, which exclude the blank.

 
    do { 
        for(i=0; i<maxIter; i++){ 
            BOOL horizontal = lrand48()%2; 
            int mv = lrand48()%(bdim-1); 
 
 
            if(horizontal==YES){ 
                if(mv>=blankX){ 
                     mv++; 
                } 
 
                [self doMoveX:mv Y:blankY]; 
            } 
            else{ 
                if(mv>=blankY){ 
                     mv++; 
                } 
 
                [self doMoveX:blankX Y:mv]; 
            } 
        } 
    } while([self totalPositioned]>maxInPlace);

The last thing scramble: does is to record the fact that the view has been scrambled and mark it for display.

 
    scrambled = YES; 
    [self setNeedsDisplay:YES]; 
 
    return self; 
}

The method drawRect: is important. It draws the view according to its internal state. Almost everything is done by compositing rectangular portions of the source image. The easy part is first. Simply composite the rectangle that needs drawing when the view is not scrambled, and draw a boundary around the entire image.

 
- (void)drawRect:(NSRect)aRect 
{ 
    int x, y; 
 
    [[NSColor blueColor] set]; 
 
    if(scrambled==NO){ 
        [image compositeToPoint:aRect.origin 
               fromRect:aRect 
               operation:NSCompositeCopy]; 
        [NSBezierPath strokeRect:[self bounds]]; 
        return; 
    }

It stays quite simple even when the view is scrambled. Iterate over the positions of the board. The current row and column tell us where content of the piece should go. The actual value of the board at that position tells us where in the source image the piece is to be found. We do not draw the blank.

We compute the source rectangle (where the piece resides in the source image) and the destination rectangle (where it is on the board) for each position of the board, do the composite operation and draw a boundary around the piece; there is nothing to draw for the blank.

 
    for(y=0; y<bdim; y++){ 
        for(x=0; x<bdim; x++){ 
            int val = board[y][x], 
                px = val%bdim, py=val/bdim; 
            NSRect src, dest; 
 
            if(val==-1){ 
                continue; 
            } 
 
            src.origin.x = px*pieceSize.width; 
            src.origin.y = py*pieceSize.height; 
            src.size = pieceSize; 
 
            dest.origin.x = x*pieceSize.width; 
            dest.origin.y = y*pieceSize.height; 
            dest.size = pieceSize; 
 
 
            [image compositeToPoint:dest.origin 
                    fromRect:src 
                    operation:NSCompositeCopy]; 
            [NSBezierPath strokeRect:dest]; 
        } 
    } 
}

The last method of SixteenView is the method mouseDown:. It must respond to clicks by the user and reposition pieces accordingly. The first step is to compute the location of the click in the view’s coordinate system (not essential here, but good practice). Next we determine what piece has been clicked. There is nothing to do when the user clicks and the view is not scrambled; the same goes for clicks that are not in the same row/column as the blank. If the click makes sense then we process it.

 
- (void)mouseDown:(NSEvent *)theEvent 
{ 
    NSPoint loc; 
    int x, y; 
 
    loc = [theEvent locationInWindow]; 
    loc = [self convertPoint:loc fromView: nil]; 
 
    x = loc.x/pieceSize.width; y = loc.y/pieceSize.height; 
 
    if(scrambled==NO ∣∣ (x!=blankX && y!=blankY)){ 
        NSBeep(); 
        return; 
    } 
 
    [self doMoveX:x Y:y];

The last step is to check whether the user has solved the puzzle, which occurs when there are as many pieces in place as there are positions on the board, minus the blank. In this case display the complete image right away and congratulate the user, otherwise mark the view as needing display.

 
    if([self totalPositioned]==bdim*bdim-1){ 
        scrambled = NO; 
        [self display]; 
        NSRunAlertPanel(@”Congratulations!”, @”Puzzle_solved.”, 
                         @”Ok”, nil, nil); 
    } 
    else{ 
        [self setNeedsDisplay:YES]; 
    } 
} 
 
@end

The controller is very simple. It builds the window and the view once the application has been launched, sets the main menu and processes command line arguments.

 
@interface Controller : NSObject 
 
- (void)applicationDidFinishLaunching:(NSNotification *)notif; 
 
@end

We need to get at the arguments, so we obtain them from the process info object. One of these is the path to the source image, which is a string and will be stored in the variable imgPath. There is the variable img that holds the image itself. We also obtain the number of pieces per row or column from the command line: this is recorded in the variable size. We declare variables to hold the window, the main menu, the SixteenView and the content rectangle of the window.

 
@implementation Controller 
 
- (void)applicationDidFinishLaunching:(NSNotification *)notif 
{ 
    NSProcessInfo *procInfo = [NSProcessInfo processInfo]; 
    NSArray *args = [procInfo arguments]; 
 
    NSString *imgPath; 
    NSImage *img; 
    int size; 
    SixteenView *sv; 
 
    NSMenu *menu = [NSMenu new]; 
 
    NSWindow *stWin; 
    NSRect winRect;

The first action is to seed the random number generator so that we get different results from a scramble operation every time the program is run. We build the main menu with two entries, one to scramble the view and another to quit the application, and display it right away.

 
    srand48(time(NULL)); 
 
    [menu addItemWithTitle: @”Scramble” 
          action:@selector(scramble:) 
          keyEquivalent:@””]; 
    [menu addItemWithTitle: @”Quit” 
          action:@selector(terminate:) 
          keyEquivalent:@”q”]; 
    [NSApp setMainMenu:menu]; 
 
    [menu display];

The arguments are processed next. There must be three of them: the application binary, the size and the image. We raise an exception when we do not have the right number of arguments or when the size is to small for a meaningful game or too large for the board.

 
    if([args count]!=3){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”args_are:_<size>_<image>]; 
    } 
 
    size = [[args objectAtIndex:1] intValue]; 
    if(size<MINDIM ∣∣ size>MAXDIM){ 
        [NSException raise:NSRangeException 
                      format:@”size_out_of_range_(%d_-%d):_%d”, 
                      MINDIM, MAXDIM, size]; 
    }

We try to read the image from the file and raise an exception if there is a problem.

 
    imgPath = [args objectAtIndex:2]; 
    img = [[NSImage alloc] initWithContentsOfFile:imgPath]; 
    if(img==nil){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”no_image_in_%@”, imgPath]; 
    }

We allocate the instance of SixteenView next. The initializer of the view computes the size of the view from the size of the image and we use this value as the size of the window’s content rectangle.

 
    sv = [[SixteenView alloc] 
             initAtPoint:NSMakePoint(0, 0) 
             withImage:img andDimension:size]; 
 
    winRect.origin = NSMakePoint(0, 0); 
    winRect.size = [sv bounds].size;

Finally we allocate the window, set its title, make the SixteenView the content view and the initial first responder, center the window and order it to the front.

 
    stWin = [[NSWindow alloc] 
                initWithContentRect:winRect 
                styleMask:NSTitledWindowMask 
                backing:NSBackingStoreBuffered 
                defer:NO]; 
    [stWin setTitle:@”sixteen_puzzle”]; 
 
    [stWin setContentView:sv]; 
    [stWin setInitialFirstResponder:sv]; 
 
    [stWin center]; 
    [stWin makeKeyAndOrderFront:nil]; 
} 
 
@end

The function main is the same as in the df frontend recipe: it allocates the application and the controller and runs the application.

 
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); 
}