My Functional Programming Solution to the N Queens Problem
The N-Queens problem is an interesting exercise when learning any new programming language. I am learning F# these days and more importantly I am learning how to think functionally.
The concepts of functional programming which I really like are
- Write everything as small functions
- Avoid imperative style like heavily nested "if conditions" and "for loops"
- Write concise code which is easy to understand
Here is the code which I wrote. Let me know if you can further make it more "functional"
01.let isAllowed c = function
02. | [] -> true
03. | list -> List.forall (fun p -> (fst c) <> (fst p) && (snd c) <> (snd p) && abs((fst c) - (fst p)) <> abs((snd c) - (snd p))) list;;
04.
05.let solve board =
06. let rec moveQueen board pos list =
07. match pos with
08. | (row, col) when row >= board && List.isEmpty list -> []
09. | (row, col) when row < board && col < board && isAllowed pos list -> moveQueen board (0, col + 1) (pos :: list)
10. | (row, col) when row < board && col < board && isAllowed pos list = false -> moveQueen board (row + 1, col) list
11. | (row, col) when row >= board && col < board -> moveQueen board (fst (List.head list) + 1, (snd (List.head list))) (List.tail list)
12. | (row, col) when col >= board -> list::moveQueen board (fst (List.head list) + 1, (snd (List.head list))) (List.tail list)
13. | (_, _) -> failwith "unknown combination"
14. moveQueen board (0, 0) [];;
15.
16.let solutions = solve 8;;
17.printfn "%d" solutions.Length;;
One thing you will instantly recognize is the power of F#. I remember back in the day when this assignment was given in college even the most bright students wrote this in 100s of line of imperative code. We had lot of nested loops and if conditions which made the code harder to understand.
F# uses functional concepts like pattern matching, recursion and Lists to ensure that the resulting solution is concise and flat.
F# also makes it possible to write very powerful data processing logic in a neat and concise way. Suppose we want to confirm that the solutions found by the above program are unique. To prove this, we need to remove duplicates from a Lists of Lists which contains Tuples.
It make look intimidating at first, but the F# Lists and recursion make it quite easy to do
01.let isAllowed c = function
02. | [] -> true
03. | list -> List.forall (fun p -> (fst c) <> (fst p) && (snd c) <> (snd p) && abs((fst c) - (fst p)) <> abs((snd c) - (snd p))) list;;
04.
05.let comparePoints p1 p2 =
06. match p1, p2 with
07. | p1, p2 when (fst p1 > fst p2) -> 1
08. | p1, p2 when (fst p1 < fst p2) -> -1
09. | p1, p2 when (fst p1 = fst p2) && (snd p1 > snd p2)-> 1
10. | p1, p2 when (fst p1 = fst p2) && (snd p1 < snd p2) -> -1
11. | p1, p2 when (fst p1 = fst p2) && (snd p1 = snd p2) -> 0
12. | _, _ -> failwith "unknown pattern";;
13.
14.let rec compareLists l1 l2 =
15. match l1, l2 with
16. | [], [] -> 0
17. | l1, [] -> 1
18. | [], l2 -> -1
19. | (hd1::tl1), (hd2::tl2) ->
20. match (comparePoints hd1 hd2) with
21. | 1 -> 1
22. | 0 -> compareLists tl1 tl2
23. | -1 -> -1
24. | _ -> failwith "Unknown return code";;
25.
26.let rec deduplicateList = function
27.| [] -> []
28.| [x] -> [x]
29.| hd1 :: (hd2 :: tl) when compareLists hd1 hd2 = 0 -> deduplicateList (hd2 :: tl)
30.| hd1 :: (hd2 :: tl) when compareLists hd1 hd2 <> 0 -> hd1 :: (deduplicateList (hd2 :: tl))
31.| _ -> failwith "unknown pattern";;
32.
33.let solve board =
34. let rec moveQueen board pos list =
35. match pos with
36. | (row, col) when row >= board && List.isEmpty list -> []
37. | (row, col) when row < board && col < board && isAllowed pos list -> moveQueen board (0, col + 1) (pos :: list)
38. | (row, col) when row < board && col < board && isAllowed pos list = false -> moveQueen board (row + 1, col) list
39. | (row, col) when row >= board && col < board -> moveQueen board (fst (List.head list) + 1, (snd (List.head list))) (List.tail list)
40. | (row, col) when col >= board -> list::moveQueen board (fst (List.head list) + 1, (snd (List.head list))) (List.tail list)
41. | (_, _) -> failwith "unknown combination"
42. moveQueen board (0, 0) [];;
43.
44.let uniqueSolutions = solve 8 |> List.map (List.sortWith comparePoints) |> List.sortWith compareLists |> deduplicateList;;
45.printfn "%d" uniqueSolutions.Length;;