Huddled Masses
Posts Tagged ‘Recursion’
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 | 
Comments Closed
So, I posted a story about Fibonacci sequences and noticed that the recursion in PowerShell is really rather slow. But I also noticed something interesting — I had expected that recursing using a function would be a little cheaper (and faster) than recursing using the pipeline, and it turns out that it’s not. At all.
I’d love to hear some thoughts on why I got the speed results I got here. At first I thought it was something about type coercion, but as you can see, I tried casting everything to no avail. There’s no difference if I don’t output anything, and in fact, the non-recursive algorithm can trivially output every Fibonacci number in the sequence without affecting it’s time (I actually altered it so it didn’t to keep the output clean).
Obviously I expected the recursive algorithms to be slow and scale badly because of the amount of work involved, but how is it that the pipeline-recursive “filter” outperforms the plain old recursive function (albeit by an infinitesimal fraction)?
[08]: function fibfunction([int]$i){ if($i -lt 2) { 1 }else{ [int](fibfunction ($i-1)) + [int](fibfunction ($i-2)) } }
[09]: filter fibfilter{ if($_-lt2){1}else{[int]([int]$_-1|fibfilter)+[int]([int]$_-2|fibfilter)}}
[10]: [int]$size = 18
[11]: fibfunction $size
4181
[12]: $size | fibfilter
4181
[13]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
4181
[14]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : fibfunction $size
Duration : 00:00:02.4764040
CommandLine : $size | fibfilter
Duration : 00:00:02.2137255
CommandLine : [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0048825
[15]: [int]$size = 21
[16]: fibfunction $size
17711
[17]: $size | fibfilter
17711
[18]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
17711
[19]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : $null = fibfunction $size
Duration : 00:00:10.5764715
CommandLine : $null = $size | fibfilter
Duration : 00:00:09.6282900
CommandLine : $null = [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0058590
P.S.: The numbers in braces with the colon (like [18]: ... ) is my prompt.
Posted in Huddled |
Tags: Fibonacci, Performance, PowerShell, Recursion, Scripting, Timing |
4 Comments »