4 Queens Problem with Continuation-Passing Style
(This is post #2 of the Continuations Explained with Ruby Series)
In post #1 of this series, I showed you how to save the computations of a factorial and how to manipulate the base condition. As I said, we can’t do much with that, but it is the basis for what we’re going to be looking at in this post.
4 Queens Problem
The problem we’re going to solve in this post is the 4 Queens problem, which is just a simplified version of the 8 Queens problem. The idea is that we have a 4×4 chess table, and 4 Queen chess pieces. We now have to position those 4 Queens in such a way that there is only one queen per line and none of them are able to capture any other using standard chess moves.
Detecting Collisions
To detect a collision between Queens, we need to check the columns and the diagonals. Collisions can be easily checked if we assign index positions to chess board matrix and keep 3 separate collision lists: one for columns and two for the diagonals. We update the collision lists whenever a Queen is placed. For the column list, we simply add the Queen’s column position; for one diagonal, we add the sum of the Queen’s line with the Queen’s column to the list (called Diag+); and for the other diagonal, we add the subtraction of the line and column position to the list (called Diag-).
For example, take a look at the above image. Lines and columns are labeled from 1 to 4. The Diag+ elements are in the lower triangle in dark grey, and the Diag- elements are in the upper triangle in white. In table (b), the Queen on line 1 can capture the Queen on line 2 because summing their line and column position both result in the same number (4). Queen on line 2 collides with Queen on line 3 because of Diag-: subtract their line and column positions and you get the same value (0). Queen in line 1 and line 3 also collide because they have the same column position.
Recursion
One way to solve this problem is to employ backtracking depth first search. Think of backtracking as being just like recursion, except that you’re not sure if the path you took is the right one, so you need to be able to go backwards and take another path if need be.
Here’s a possible recursive solution to this problem:
def queens_collide?(i, j, col, diag_plus, diag_minus)
col.include?(j) || diag_plus.include?(i + j) || diag_minus.include?(i - j)
end
def place_queens(n, i, j, col, diag_plus, diag_minus)
if i.zero?
col
elsif j.zero?
false
elsif queens_collide?(i, j, col, diag_plus, diag_minus)
place_queens(n, i, j - 1, col, diag_plus, diag_minus)
else
queen_placed_ok = place_queens(
n, i - 1, n,
col + [j],
diag_plus + [i + j],
diag_minus + [i - j]
)
if queen_placed_ok
queen_placed_ok
else
place_queens(n, i, j - 1, col, diag_plus, diag_minus)
end
end
end
def queens(n)
place_queens(n, n, n, [], [], [])
end
puts queens(4).inspect
# >> [3, 1, 4, 2]
I Want More
The code I just presented to you works fine, but what if we didn’t like that answer? What if we wanted to compute another solution? And another one after that?
The key here is line 13, which represents the backtracking checkpoint. It’s the point of the algorithm where, if the path taken by the recursion leads to a wrong answer (collision or if the end of the table is reached), then it has to backtrack up until that deciding point and choose another path. Also notice that the code in the line I mentioned is a non tail-recursive call, meaning that the line is a dependency which uses the stack to store intermediate results.
CPS FTW
The idea here is to make the dependencies explicit and thus avoid the usage of the stack, because once the method finishes it’s computation, all the intermediate results disappear along with the call stack. And we want access to those saved computations, so we can use them to calculate other possible solutions. To do that, we’ll transform the place_queens recursive function into a tail-recursive one using the Continuation-Passing Style technique by making the implicit computations, which are stored in the stack, explicit using anonymous functions (lambdas):
$queens_continuation = nil
def queens_collide?(i, j, col, diag_plus, diag_minus)
col.include?(j) || diag_plus.include?(i + j) || diag_minus.include?(i - j)
end
def place_queens(n, i, j, col, diag_plus, diag_minus, continuation)
if i.zero?
$queens_continuation = continuation
continuation.call([])
elsif j.zero?
continuation.call(false)
elsif queens_collide?(i, j, col, diag_plus, diag_minus)
place_queens(n, i, j - 1, col, diag_plus, diag_minus, continuation)
else
queen_placed_ok = place_queens(
n, i - 1, n,
col + [j],
diag_plus + [i + j],
diag_minus + [i - j],
lambda do |r|
if r
continuation.call(r + [j])
else
place_queens(n, i, j - 1, col, diag_plus, diag_minus, continuation)
end
end
)
end
end
def queens(n)
place_queens(n, n, n, [], [], [], lambda { |r| r })
end
puts queens(4).inspect
# >> [2, 4, 1, 3]
This code still produces a correct answer, even if it’s not the same as the 1st recursive version.
Now for the fun part. The global variable $queens_continuation contains the final continuation of the method. In other words, after calling the function, not only do we get the results like normal, but we now have access to the computations that were performed to reach it.
Therefore, if we call the continuation passing an empty array, we’ll get the same answer:
puts $queens_continuation.call([]).inspect # >> [2, 4, 1, 3]
If you take a look at the continuation we create at line 21, more specifically the if statement, we check if the argument r is true, in which case the lambda just calls the previous continuation with a list to be concatenated as the result. But if it’s false, then it’s because it hasn’t gotten to a valid result yet, so it continues to calculate Queen positions.
So, with access to the final continuation when the function call finished, we can do some interesting stuff. Say that you don’t like the first result and want another one. We just need to call the continuation with false and it’ll think that it the Queens have collided and will calculate another solution for us:
puts $queens_continuation.call(false).inspect # >> [3, 1, 4, 2]
And once again, when it returns, we have our solution plus access to its computations in $queens_continuation. So if we’re still not happy with the result, we can call the continuation again with false. Although, this time we ran out of solutions:
puts $queens_continuation.call(false).inspect # >> false
But if we had initially called queens(8), we’d have more solutions to go through. But I’ll leave that for you to try: fire up IRB, copy-and-paste the above code, invoke queens(8), and see how many possible solutions exist by passing false to the continuation lambda in $queens_continuation.
Moral of the Story
By making the dependencies of a normal recursive function explicit and removing the usage of the stack, we have the capacity to reutilize the previous computations and calculate more results, just like Prolog. If the compiler/interpreter is sufficiently smart to optimize tail-recursive functions, we also gain a performance boost! The only problem is Tail Call Optimization (TCO) is only done in some Ruby implementations: JRuby (limited) and YARV (not enabled by default).
I hope you found this as interesting as I did when my teacher explained it to the class. I don’t know if I’ll ever need to do something like this again, but I found it really cool and wanted to share this with you all (even if I’m the only reader of my blog =).
If you have any questions, please, don’t hesitate and drop me a comment.