fork download
copy 
  1. open System
  2.  
  3. let [<Literal>] N = 8
  4.  
  5. let solve() = 
  6.     let q = Array.create N 0
  7.     let rec succ h = function
  8.         | -1 -> true
  9.         | x when q.[x] = q.[h] || abs(q.[x] - q.[h]) = abs(x - h) -> false
  10.         | x  -> succ h (x - 1)
  11.     let acc = ref []
  12.     let rec back x y = 
  13.         match x , y with
  14.         | N, N  -> ()
  15.         | N , _ -> if succ (N - 1) (N - 2) 
  16.                    then acc := Array.map id q :: !acc 
  17.                    //else ()
  18.         | -1, _ -> ()
  19.         | _ , N -> q.[x] <- 0 
  20.         | x , y -> q.[x] <- y
  21.                    if succ x (x - 1)
  22.                    then back (x + 1) 0 
  23.                         back x (y + 1) 
  24.                    else back (x) (y + 1) 
  25.     back 0 0
  26.     !acc
  27.  
  28. let rec gen list n = 
  29.     if n=N then[list] else
  30.         let n'=n+1
  31.         [0..(N-1)] |> List.filter (fun c -> 
  32.             let rec chk lst l r = 
  33.                 let l',r'=l-1,r+1
  34.                 match lst with
  35.                 | [] -> true
  36.                 | x::_ when x=c || x=l' || x=r' -> false 
  37.                 | _::t -> chk t l' r'
  38.             chk list c c)
  39.         |> List.map (fun i -> gen (i::list) n') |> List.concat
  40.  
  41. let solve1 () = gen [] 0
  42.  
  43. let show res =
  44.     for b in res do
  45.         for e in b do
  46.             String.replicate e ". " + "W " + String.replicate (7 - e) ". "
  47.             |> printfn "%s"
  48.     printfn ""
  49.  
  50. let bench f =
  51.     let stopWatch = System.Diagnostics.Stopwatch.StartNew()
  52.     Seq.length (f ()) |> ignore
  53.     stopWatch.Stop()
  54.     stopWatch.Elapsed.TotalMilliseconds
  55.  
  56. let rec benchTest cnt t0 t1 =
  57.     if cnt=100 then (t0,t1) 
  58.     else let t0n=t0 + bench solve
  59.          let t1n=t1 + bench solve1
  60.          benchTest (cnt+1) t0n t1n
  61.  
  62. let res0,res1=benchTest 0 0.0 0.0
  63. printfn "pycture        :  %f mS" res0
  64. printfn "KolodeznyDiver :  %f mS" res1
  65.  
  66.  
Success #stdin #stdout 0.56s 24592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
pycture        :  108.224300 mS
KolodeznyDiver :  377.349700 mS
https://ideone.com/AdRwzU
language:
F# (mono 4.1)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!