Back to Questions
1.2k
views3
comments
backtrack n queens.
f#

So I have this function:

let rec any j n f =

let s = f j

if s <> [] then s else

if j = n then [] else any (j+1) n f

It tries every value from j to n and returns the first solution it finds. I can use it to find a solution to the n-queen's problem by passing this function:

let tryqueen n place i j =

if attacks i j place then [] else

let newplace = (i,j) :: place

if i = n then newplace else

addqueen (i+1) n newplace

which attempts to place a queen on the i, j square if possible, returns [] if unsuccessful or adds a queen on that square and moves to the next row. It has to be defined in within the scope of this function

let rec addqueen i n place =

let tryqueen ....

any 1 n ( tryqueen n place i )

which is simply attempting to place any queen somewhere on the i-th row. So to find a solution to the n-queens problem, I simply call addqueen 1 n [] and it returns one solution to the problem.

I would like to write a function "all" that can be used similarly like "any", but instead of simply returning the first solution to the problem, it continues to add solutions to a list of solutions. I'd like to keep the current functions I have to solve the problem, but just simply return all possible configurations instead of just the first one it finds that works. I'm not having much luck though. I like to see what it would look like though if possible with the current scheme.

.

Try using a seq{} expressions - you should be able to yield each solution you find:

[link:msdn.microsoft.com]

By on 6/10/2010 7:44 PM ()

This is a (rather inefficient) implementation using lazy sequences. It works by generating n branches, each corresponding to placing a queen in each column on the first row, and by trying to extend each partial solution with a queen on the next row.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

let testAttack partialPlace r c =
    if Seq.exists (fun (pr, pc) -> pr = r || pc = c || pr + pc = r + c || pr - pc = r - c) partialPlace
    then Seq.empty else Seq.append partialPlace (Seq.singleton (r, c))


let generateRow r n partialPlaces =
    partialPlaces |> Seq.collect (fun partial -> { 1..n } (* Cols *) |> Seq.map (testAttack partial r) |> Seq.filter (Seq.isEmpty >> not))


let queens n =
    { 2..n } (* Rows *) |> Seq.fold (fun partialPlaces row -> generateRow row n partialPlaces) (Seq.init n (fun c -> Seq.singleton (1, c + 1)))


(queens 4);;
(queens 8);;
By on 6/16/2010 9:49 AM ()

A variation with sequence expressions:

1
2
3
4
5
6
7
8
9

let queensSE n = seq {
    let rec solve partials = seq {
        for partial in partials do
            let lastRow = Seq.length partial
            if lastRow = n then yield partial
            else yield! solve ( { 1..n } (* Cols *) |> Seq.map (testAttack partial (lastRow + 1)) |> Seq.filter (Seq.isEmpty >> not) )
    }
    yield! solve (Seq.init n (fun c -> Seq.singleton (1, c + 1)))
}
By on 6/16/2010 10:38 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper