Back to Questions
1.0k
views4
comments
Knight's tour Problem
f#

Hi im looking for Code that solves the knight tour problem. The knight should move to every space on the chess board (but each space only once). Im hoping somebody has allready solved this using F# and could post me the code.

Here is a solution in Scala: [link:gist.github.com]

Greetings,

Daniel

.

This is not exactly an answer but check this link

[link:fsharpnews.blogspot.com]

You may be able to buy a reprint of the article from Flying Frog; it's worth asking.

By on 12/30/2010 1:54 PM ()

Hi Thanks for the Link, but I was hoping not to spend any money ;)

I got the n Queens problem solved but still having trouble with the knight tour problem :O

By on 1/2/2011 4:53 AM ()

For problems like this one, I like using recursive sequences. Inside the sequence I either
- yield a good solution
- do nothing when I'm in an illegal position
- yield! remaining good solutions starting from the one I'm currently in

So for the knight's tour a good solution means
- I have visited (rows*cols) squares in total
- I haven't stepped on a previously visited square.

This means that the recursive function needs to remember previously visited squares (A set of int*int) and the number of moves. In the code below you can see that I collect each move in a buffer (called acc) and only cough up a buffer of moves when the conditions are met. When I'm mid-way inside my calculation I use yield! to keep visiting possible next moves, and passing the set of visited squares along.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

let tours rows cols (startx,starty) =
    let jumps = [(1, 2); (-1, 2); (1, -2); (-1, -2); (2, 1); (-2, 1); (2, -1); (-2, -1)]
    
    let withinboard (x,y) = x >= 0 && x < cols && y >= 0 && y < rows
    
    let rec aux acc seen nvisited curpos = seq {
        if withinboard curpos && not (Set.contains curpos seen) then
            if nvisited = rows * cols then
                yield (curpos::acc) |> List.rev
            else
                let (x,y) = curpos
                for (dx,dy) in jumps do
                    let newpos = (x + dx, y + dy)
                    yield! aux (curpos::acc) (Set.add curpos seen) (nvisited+1) newpos
        }
    
    aux [] Set.empty 1 (startx,starty)


// a sanity check: is every square visited exactly once?
let check solution = 
    solution |> Seq.distinct |> Seq.length = List.length solution

Example:

1
2
3
4
5
6
7
8
9

> tours 5 5 (2,2) |> Seq.head;;
Real: 00:00:00.362, CPU: 00:00:00.359, GC gen0: 22, gen1: 1, gen2: 0
val it : (int * int) list =
  [(2, 2); (3, 4); (4, 2); (3, 0); (1, 1); (0, 3); (2, 4); (4, 3); (3, 1);
   (1, 0); (0, 2); (1, 4); (3, 3); (4, 1); (2, 0); (0, 1); (1, 3); (2, 1);
   (4, 0); (3, 2); (4, 4); (2, 3); (0, 4); (1, 2); (0, 0)]
> check it;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = true

Warning: this code generates ALL possible tours, that's why I only wanted the first solution. This solution is far from optimal, but it's just a demonstration of how to use recursive sequences for these kind of (is it depth-first or breadth-first?) searches.

If you want to excercise your recursive thinking, try solving some (or more?) project Euler problems. That's how I learned this.

By on 1/3/2011 2:15 AM ()

Hi cfern,

thanks alot this is exactlly what I was looking for.

Ill look into the project Euler problems, thanks for this tip

By on 1/3/2011 4:41 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