0 people like it.
Like the snippet!

one to nine puzzle

Solve the one to nine puzzle with a utility function that handles the depth first search. First saw the puzzle here: http://msdn.microsoft.com/en-us/vcsharp/ee957404

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32:

/// Helper to manage depth first search of a problem.
/// next_f generates new states, and done_f test for the 
/// end of the search.
let solve next_f done_f initial =
    let rec go state =
        seq {
            if done_f state then
               yield state
            else
               for state' in next_f state do
                   yield! go state'
            }
    go initial


let one_to_nine () =
    let next_f (number, digits, idx) =
        let idx' = idx + 1
        seq {
            for d in digits do
               let number' = number * 10 + d
               if number' % idx' = 0 then
                   yield number', Set.remove d digits, idx'
            }

    let done_f (_, _, idx) = idx = 9

    solve next_f done_f (0, Set.ofList [1..9], 0)
    |> Seq.map (fun (num, _, _) -> num)
    |> Seq.head

printfn "solution: %A" (one_to_nine())

val solve : next_f:('a -> #seq<'a>) -> done_f:('a -> bool) -> initial:'a -> seq<'a>

Full name: Script.solve

Helper to manage depth first search of a problem.
next_f generates new states, and done_f test for the
end of the search.

val next_f : ('a -> #seq<'a>)

val done_f : ('a -> bool)

val initial : 'a

val go : ('a -> seq<'a>)

val state : 'a

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

val state' : 'a

val one_to_nine : unit -> int

Full name: Script.one_to_nine

val next_f : (int * Set<int> * int -> seq<int * Set<int> * int>)

val number : int

val digits : Set<int>

val idx : int

val idx' : int

val d : int

val number' : int

Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
  interface IComparable
  interface IEnumerable
  interface IEnumerable<'T>
  interface ICollection<'T>
  new : elements:seq<'T> -> Set<'T>
  member Add : value:'T -> Set<'T>
  member Contains : value:'T -> bool
  override Equals : obj -> bool
  member IsProperSubsetOf : otherSet:Set<'T> -> bool
  member IsProperSupersetOf : otherSet:Set<'T> -> bool
  ...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>

val remove : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.remove

val done_f : ('a * 'b * int -> bool)

val ofList : elements:'T list -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofList

module Seq

from Microsoft.FSharp.Collections

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val num : int

val head : source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.head

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

Raw view Test code New version

More information

Link:	http://fssnip.net/6m
Posted:	13 years ago
Author:	dave jones
Tags:	puzzle