Following is the OCaml code I wrote yesterday to solve the 8-queen puzzle. I have presented a solution in Python in an earlier post for the same purpose. However, there's a key difference. This solution is purely functional programming. This means that we do a completely side-effect free computing here. Therefore, we don't have assignments, mutable types, and of course, no loops. Once I got the code in place, I re-implemented the whole thing using loops. For the benefit of those accustomed to a procedural way of programming (me included), I have included that code too here.
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | module EightQueen = struct let conflict a b diff = (a = b) || (abs (a - b) = diff) let emptyList = [];; let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];; let maxlength = List.length allValues;; let shuffle d = let nd = List.map (fun c -> (Random.bits (), c)) d in let sond = List.sort compare nd in List.map snd sond let rec checkConflict newList = let rec check i = let c = conflict (List.nth newList 0) (List.nth newList i) i in if c then false else if i = (List.length newList - 1) then true else check (i + 1) in if List.length newList < 2 then true else check 1 let rec solve pos = if checkConflict pos = false then emptyList else if List.length pos = maxlength then pos else let rec loop lst allowedValues = if allowedValues = emptyList then emptyList else let head = List.hd allowedValues and tail = List.tl allowedValues in let extendedList = head::pos in let answer = solve extendedList in if answer <> emptyList then answer else loop lst tail in loop pos (shuffle allValues) end;; let rec printList lst = match lst with [] -> () | e::l -> print_int e ; print_string " " ; printList l ;; let lst = EightQueen.solve EightQueen.emptyList in printList lst; print_string "\n";; |
And here follows pretty much the same code using imperative style:
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | let conflict a b diff = (a = b) || (abs (a - b) = diff) ;; let emptyList = [];; let allValues = [ 0; 1; 2; 3; 4; 5; 6; 7 ];; let maxlength = List.length allValues;; let rec print_list = function [] -> () | e::l -> print_int e ; print_string " " ; print_list l ;; let shuffle d = let nd = List.map (fun c -> (Random.bits (), c)) d in let sond = List.sort compare nd in List.map snd sond let rec checkConflict newList = let result = ref true in for i = 1 to ((List.length newList) - 1) do if !result = true then if conflict (List.nth newList 0) (List.nth newList i) i then result := false done; !result ;; let rec solve pos = if checkConflict pos = false then emptyList else if List.length pos = maxlength then pos else let result = ref emptyList in for i = 0 to ((List.length allValues) - 1) do if !result = emptyList then let value = (List.nth allValues i) in let extendedList = value::pos in let answer = solve extendedList in if answer <> emptyList then result := answer done; !result ;; let lst = solve emptyList in print_list lst; print_string "\n";; |
