Minesweeper (Part 1)

Let’s do a multi-day project: Let’s build Minesweeper for the iPhone. This should be pretty straight-forward, especially if we cut out a bell or whistle here and there. Let’s get started with some data structures.

Quick Design

As we move forward, we’ll need to make design choices specific to our platform, but for now we can simply take the Windows version of Minesweeper as a reference. This is sufficient to design our puzzle data structure.

Our app will allow the player to create, play, and review any number of minesweeper puzzles. A puzzle is defined by these data:

  • Dimensions (width and height)
  • Mine count and position
  • Position of uncovered squares


After a fair bit of mucking about with object models, I decided to model a puzzle (largely) with a simple array of bytes. The coding is pretty simple:

  • The cell at (x,y) is represented by a byte at offset width*y+x
  • Bits 0-3 store the number of mines neighboring the cell (0-8)
  • Bit 4 is set iff the cell is mined
  • Bit 5 is set iff the cell has been revealed

The rationale behind the choice of a byte array is that if we hold puzzle density fixed, the relationship between the memory use of a dense representation and a sparse representation will be a constant factor for any puzzle size. Since puzzle density is likely to remain relatively constant (due to playability considerations), and since the memory use of a dense representation compares favorably to that of a sparse representation at the 15%-20% densities we’re likely to see in practice, there’s no real advantage to a sparse representation. And a dense representation is much easier to work with.


If you’d like to see them, you can download the complete Puzzle header and implementation files.

The class declaration is pretty simple:

@interface Puzzle : NSObject
	NSUInteger		w;
	NSUInteger		h;
	NSUInteger		m;
	char*			cells;

@property (nonatomic, assign, readonly) NSUInteger w;
@property (nonatomic, assign, readonly) NSUInteger h;
@property (nonatomic, assign, readonly) NSUInteger m;

- (id)initWithWidth:(NSUInteger)w height:(NSUInteger)h mines:(NSUInteger)m;

- (void)generate;
- (BOOL)isMinedAtX:(NSUInteger)x andY:(NSUInteger)y;
- (NSUInteger)neighborsAtX:(NSUInteger)x andY:(NSUInteger)y;


In the implementation file, we begin with some constants:

const static NSUInteger MAX_EDGE_SIZE	= 500;
const static char BIT_REVEALED		= (1<<5);
const static char BIT_MINED		= (1<<4);
const static char NEIGHBOR_MASK		= 0xf;

We then add some helper functions:

static inline char get_record(char* d, int w, int h, int x, int y)
	return ((x>=0)&&(x<w)&&(y>=0)&&(y<h))?d[w*y+x]:0;

static inline char is_mined(char* d, int w, int h, int x, int y)
	return (get_record(d, w, h, x, y)&BIT_MINED)?1:0;

We define a lazy getter for our internal data storage:

- (char*)cells
	if (!cells)
		cells = (char*) malloc(w*h);
	return cells;

and methods for initialization:

- (id)initWithWidth:(NSUInteger)iw height:(NSUInteger)ih mines:(NSUInteger)im
	if (self = [super init])
		w = MIN(MAX(iw, 2), MAX_EDGE_SIZE);
		h = MIN(MAX(ih, 2), MAX_EDGE_SIZE);
		m = MIN(im, (w-1)*(h-1));
	return self;

… debugging:

- (NSString*)description
	char symbols[2*w+1];
	memset(symbols, ' ', 2*w+1);
	symbols[0] = '\n';
	symbols[2*w] = '\0';
	NSMutableArray* a = [NSMutableArray arrayWithCapacity:h];

	char* d = self.cells;
	for (int y = 0; y < h; y++)
		for (int x = 0; x < w; x++)
			char cell = d[w*y+x];
			symbols[2*x+1] = (cell&BIT_MINED)?'X':('0'+(cell&NEIGHBOR_MASK));
		[a addObject:[NSString stringWithCString:symbols encoding:NSASCIIStringEncoding]];
	return [a componentsJoinedByString:@""];

… puzzle generation:

- (void)generate
	char* d = self.cells;
	int size = w*h;
	// To keep things reasonable, add or remove cells depending on density
	if (m > size/2)
		// More than 50% mined: remove mines
		memset(d, BIT_MINED, size);
		for (int nmines=size; nmines>m;)
			int idx = rand()%size;
			if (d[idx] & BIT_MINED)
				d[idx] &= ~BIT_MINED;
		// Less than 50% mined: add mines
		memset(d, 0, size);
		for (int nmines=0; nmines<m;)
			int idx = rand()%size;
			if (!(d[idx] & BIT_MINED))
				d[idx] |= BIT_MINED;
	// Calculate neighbors
	for (int x = w-1; x >= 0; x--)
		for (int y = h-1; y >= 0; y--)
			d[w*y+x] |= (is_mined(d,w,h,x-1,y-1) +
				     is_mined(d,w,h,x+0,y-1) +
				     is_mined(d,w,h,x+1,y-1) +
				     is_mined(d,w,h,x-1,y+0) +
				     is_mined(d,w,h,x+1,y+0) +
				     is_mined(d,w,h,x-1,y+1) +
				     is_mined(d,w,h,x+0,y+1) +
				     is_mined(d,w,h,x+1,y+1) );

… and a public interface:

- (BOOL)isMinedAtX:(NSUInteger)x andY:(NSUInteger)y
	return is_mined(self.cells, w, h, x, y);

- (NSUInteger)neighborsAtX:(NSUInteger)x andY:(NSUInteger)y
	return get_record(self.cells, w, h, x, y)&NEIGHBOR_MASK;

Finally, I clean up:

- (void)dealloc
	if (cells) free(cells);
	[super dealloc];
Share and Enjoy:
  • Twitter
  • Facebook
  • Digg
  • Reddit
  • HackerNews
  • del.icio.us
  • Google Bookmarks
  • Slashdot
This entry was posted in iPhone, Projects. Bookmark the permalink.

One Response to Minesweeper (Part 1)

  1. Jordan says:

    Wow! I like the concept and all of the bit math. Needed to study it a while. Great stuff, looking forward to reading the next two articles.