Queen for a day

I was reading the Pure manual (“Pure is a modern-style functional programming language based on term rewriting”) trying to learn the basics of functional programming (which, for some reason, I find very difficult) and saw this nice solution to the Queens N puzzle (Wikipedia article with a nice animation of the backtracking algorithm):

queens n       = search n 1 [] with
search n i p = [reverse p] if i>n;
= cat [search n (i+1) ((i,j):p)
| j = 1..n; safe (i,j) p];
safe (i,j) p = ~any (check (i,j)) p;
check (i1,j1) (i2,j2) = i1==i2 || j1==j2 ||
i1+j1==i2+j2 || i1-j1==i2-j2;
end;

Your basic brute force algorithm:

  • Put a queen in the first row
  • Put a queen in the next row, where it isn’t attacked
  • Continue until there is a queen on every row
  • Otherwise, backup one row and try the next column

q11

For example, here a failure on a 4×4 board (BTW, 4×4 is smallest size with a solution (there are 2), other than a 1×1 board)

For the first row, there can be a queen in every column, I’ll pick column 1 (1,1).
q12For the second row, there two possibilities: (2,3) and (2,4). If (2,3) is used, all of row 3 is under attack so there is no solution using these two positions. We would then try (2,4) (which also isn’t in a solution). Then back up the first row and try a queen in the second column (which does have a solution).

Ok, can I duplicate this algorithm in zkl? Well, no, I don’t have list comprehensions,  so I have to figure out how to fake around that.

But first, some simple things:
A queen attacks a square if they are on same row, column or diagonal. The diagonal is the interesting part: A diagonal is 45º so the line formula y = mx+b is y = ±1x + b –> y ± x = b. If a queen at (u,v) is on the same line then u ± v = b –> y ± x = u ± v, which is the “checks” code.
A square is “safe” if isn’t being attacked, for us, that means checking every square in a row to see it is being attacked and, if it isn’t, it is safe. My code (in zkl) is:
   not qs.filter1(isAttacked,a,b)
where qs is a list of queens in (row,col) pairs (eg L(L(1,1),L(2,3)) for two queens), a,b is the square in question and isAttacked is a function of three parameters: a queen pair, an x and a y and returns True if the queen attacks the square (kinda bass-ackwards but fits the data formats). So, anyway, filter1 checks each queen in qs to see if it attacks (a,b) (and stops at the first positive (the 1 in filter1)).

Now the hard part, the decent. What I do is build a row by putting a queen on every safe square:
   [1..N].filter(isSafe.fpM(“101”,row,queens))
.apply(fcn(c,r,qs){qs+T(r,c)},row,queens);

The first line generates a list of safe squares by column and the second line converts the column into a (row,column) pair and adds it to the list of queens already on the board. From the above picture, the second row would be: L(L(1,1),L(2,3)) and L(L(1,1),L(2,4)). Filter removes all the unsafe columns and safe.fpM builds a version of safe (call it isSafe’) that takes one parameter, the column. This is partial function application; I “fix” the first and third parameters so that a call to isSafe’(1) is actually isSafe(row,1,queens). (I have to do this because lambda functions are not lexically scoped and thus don’t see variables that are next to them).

If the row I just built is the last row, it is a solution and I’m done. Otherwise, I have to look at the next row:
   qs.apply(self.fcn.fp(N,row+1))
Here, for each set of queens, I recurse to the next row. Again, .fp builds a new function such that f’(queens) is actually f(N,row+1,queens). This results in a list of [partial] solutions and empty lists if there isn’t a solution.

Now that I have a list (of lists) of solutions (and empty lists for non-solutions) for each set of queens, distill that down to a single list of solutions and backtrack:
  .flatten()
And we are done.

fcn isAttacked(q,a,b)
{ x,y:=q; (x==a or y==b or x+y==a+b or x-
y==a-b) }
fcn isSafe(a,b,qs){(not qs.filter1(isAttacked,a,b))}
fcn queensN(N=8,row=1,queens=T){
qs := [1..N].filter(isSafe.fpM(“101”,row,queens))
.apply(fcn(c,r,qs){qs+T(r,c)},row,queens);
if (row == N) return(qs);
return(qs.apply(self.fcn.fp(N,row+1)).flatten());
}

queens := queensN(4);
println(queens.len(),” solution(s):”);
queens.apply2(Console.println);

2 solution(s):
L(L(1,2),L(2,4),L(3,1),L(4,3))
L(L(1,3),L(2,1),L(3,4),L(4,2))

___________________________________________________________________

Here is the second solution. After the first row, there is only one possibility for each subsequent row.

q31  q32  q33  q34

____________________________________________________________________________

What if we want only one solution? Again, borrowing from the Pure examples, it is easiest (and simpler and way faster) just to avoid the backtracking headaches altogether by throwing an exception with the first solution:

fcn queensN1(N=8,row=1,queens=T){
if (row > N) throw(Exception.Msg(queens));
[1..N].filter(isSafe.fpM(“101”,row,queens))
.apply(fcn(c,r,qs){qs+T(r,c)},row,queens)
.apply2(self.fcn.fp(N,row+1));
}
reg queens;
try {queensN1(8)}catch(Msg){queens=__exception.payload}
println(“A solution: “,queens);

A solution: L(L(1,1),L(2,5),L(3,8),L(4,6),L(5,3),L(6,7),L(7,2),L(8,4))

(apply2() is the same as apply but throws away the results, which we don’t care about as we are just using apply to loop/recurse over the sets of queens)

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s