Huddled Masses
February 18th, 2008 | 
Author: Well … my brother called me with an odd compiler problem with his C++ homework today (he’s working on another degree, and taking some programming courses) ... but the homework problem he was working on was the infamous N Queens problem:
Given a chess board of N x N squares, place N queens on the board in such a way than none threatens the others. In chess, a queen can move diagonally or horizontally, so solving this requires placing each queen on her own row and column, and ordered such that none of them are on the same diagonal in either direction.
The problem is solvable using a backtracking recursive algorithm: the program must place a queen on the first row and then find a spot that works for the next row, and continue for each row. If it can’t find a spot for a row, it backtracks to the previous row and uses the next legal spot on that row, and if there is none, it backtracks to the previous row, and so on.
Anyway. There’s lots of information about this stuff out there on the ‘net, including dozens of slides shows and lecture notes from dozens of schools, so I’m just going to move on to the fun part: my solution in PowerShell. I wrote it just to make sure I understood the algorithm correctly, without giving away the C++ answer as much as a quick web search would. In fact, I followed the restrictions my brother’s professor had placed on them to break it up into a specific set of functions…
## N-Queens problem using backtracking
################################################################################
## Backtracking is a problem-solving strategy that, when it reaches an impasse,
## retraces its steps in reverse order before trying a new sequence of steps.
param($size=8) # By default, we use a board of size 8
function Check-Queen($r1,$c1,$r2,$c2) {
return -not (
# they can't be on the same column
($c1 -eq $c2) -or
# nor on the same row
($r1 -eq $r2) -or
# nor on the same diagonal
([Math]::Abs($r1-$r2) -eq [Math]::Abs($c1-$c2)));
}
function Out-Board($board){
foreach($c in $board) {
switch(0..($board.Count-1)) {
{$_-eq$c} { write-host "Q" -fore red -nonew }
default { write-host "#" -nonew}
}
Write-Host
}
}
function Set-Queen($board,$row,$column) {
# Set the queen location for this row
$board[$row]=$column;
# if this is the last row, then we're done
if($row+1 -eq $board.Count) { return $true }
# place the queen in the next row
# try every column ....
for($c=0;$c -lt $board.Count; $c++) {
$clean = $true
# check it against every prior row
for($r=0; $r -le $row; $r++) {
$clean = $clean -and (Check-Queen $r $board[$r] ($row+1) $c)
if(!$clean) { break; }
}
# if we found the spot, recurse the next row...
if($clean -and( Set-Queen $board ($row+1) $c )) {
return $true;
}
}
return $false
}
$board = new-object int[] $size
# if starting in 0,0 doesn't work 0,1 will
if(Set-Queen $board 0 0){
Out-Board $board
}elseif(Set-Queen $board 0 1){
Out-Board $board
}
Posted in Huddled | 
Tags: Algorithms, Backtracking, Challenges, PowerShell, Programming, Recursion, Scripting