zsmb's prog site

Queens

  2015.08.28.

Introduction

The  eight queens puzzle is a classic mathematical puzzle on a chessboard - your goal is to place 8 queens on the 8x8 board so that no two of them can attack each other (i.e. no two are in the same row, column, or diagonal). It was also  featured around the end of my second semester programming course as an example of backtrack algorithms. After the recent  Numberphile video, I felt like making a quick program for solving the problem.

Usage

The executable solves the 8 by 8 board, when it's done, you can press any key (or close the SDL window) to exit the program.

Description

The Board class has the board size as a template parameter so that you can use this to get a solution for an arbitrary N by N board with N queens on it, the graphics should adjust appropriately if you create smaller and larger boards. Be aware of runtimes for large boards though, the 8 by 8 board with 50ms delay between the algorithm's steps (for drawing) solves in about 45 seconds.

If you disable the drawing for every step, you can get near instantaneous solutions up to about a 28 by 28 board or so.

Note that there are no solutions for the problem for the 0, 2, and 3 values of N (the SDL window does not tell you this, I was a bit lazy with the edge cases).

Development

I'm fairly content with the code in this one, the only thing that bothers me is the method by which the user closing the SDL window exits the program with the bool return values and such. The other way to do it would've been to throw an exception to get back to the main function, maybe this is a nicer solution. Still feels clunky though.

I did start this out trying to program it with an N by N matrix of bools instead of just keeping a list of the queens, but that turned out to be  quite tedious with all the loops.

Downloads

Downloading the zip file that contains the executable results in a warning (at least in Chrome) as a security measure, but you can choose to "Keep" it.