N-Queens

In a recent workshop, the presenter challenged the attendees to place 8 queens on a chessboard such that none of them could take another. Nobody managed within the allotted time, and then he showed us the solution, which he implemented by memorizing the “magic” number corresponding to the distance of each piece from the x-axis.

This seemingly random arrangement was dissatisfying to the point of distraction. I spent the next half and hour of the workshop pondering it, and came up with a slightly more pleasing way of encoding the solution:

Pen and paper solution

If we call the closest side of the board South (S) and the furthest side of the board North (N), then counting from the N or S side of the board respectively, we can notice the following pattern in the arrangement:

Of course, this numerical pattern differs according to the board rotation.

I was excited about this so I shared it with the group, and then the presenter challenged me to come up with 2 additional solutions before the next session.

Excel

Back at my computer later, I opened Excel and after entering my previous solution I started to look for other patterns.

I found that the squares with Queens on them fell on the extremities of T-shapes drawn within squares of dimensions 5×5, 3×3, and the square 1×1, starting in the corners of the board, one at the base of each T and one at the end of the cross.

But the remaining squares didn’t seem to fit the pattern (a T within a 7×7 square starting at the top right but oriented in an upright position overlapping the 5×5 square did catch one Queen square at it’s base, but since it didn’t also encompass a second square at one end of the cross piece, I don’t think it counts.)

But, then I noticed:

• if we replace the right half of the board with a mirror image of the left side of the board,
• transpose the top and bottom quadrants on the right,
• and then superimpose the original positions of the Queens (Q)

well, let’s see what happens…

1. Mirror

2. Transpose

3. Superimpose

 
It’s a fit!

Of course, in both of those solutions I was working backwards from the solution, and only with a standard 8×8 chessboard. Surely there must be a way to derive a general rule. Right?

I racked my brains for a while, fiddled in Excel and PHP, but couldn’t come up with anything elegant. In the end I searched online and found a few programmatic solutions, all of which used a recursive (i.e. brute force) approach.

A web-based solution in PHP

I found a functional example that encompassed an N-Queens approach, where N is the number of Queens / dimensions of the board. The one I chose was an approach by rcammisola that solves the N-Queens problem in PHP with recursion.

The original class printed a text-based grid like this:

	|Q| | | | | | | |
	-----------------
	| | | | |Q| | | |
	-----------------
	| | | | | | | |Q|
	-----------------
	| | | | | |Q| | |
	-----------------
	| | |Q| | | | | |
	-----------------
	| | | | | | |Q| |
	-----------------
	| |Q| | | | | | |
	-----------------
	| | | |Q| | | | |
	-----------------

My Changes

My changes are mainly cosmetic:

• A select box from where you can choose the grid size (number of queens)
• Added an alternative output style: an HTML table. You can still output a text-based board by passing anything to the print_board method, e.g. $q->print_board(1);
• A bit of Bootstrap for its grids, navs, and button styles (chosen because it’s the CSS framework with which I’m most familiar). Thanks to Bootstrap and a teeny bit of extra CSS, the chess board should fit to the screen without any overflow on any size of device.
• An SVG queen: queen by Dolly Holmes from the Noun Project
• Wrapped text-based board in a pre tag so it aligns nicely.

Other changes include:

• Modifying how default values are handled (construct/solve methods)
• Splitting the methods that construct the output from the ones that actually display it
• PHP formatting changes (based upon my own personal preference, which stems from working with WordPress). Mostly this means: curly braces open on the same line but close on a new line, and there are spaces inside parenthesis and around operators / operands.

Demo

See it in action here or fork the code on Github.