Created
June 11, 2015 20:39
-
-
Save joshuashaffer/571583c47841a2392663 to your computer and use it in GitHub Desktop.
8 queens
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| let empty_board = Array2D.init 8 8 (fun i j -> 0) | |
| let check_board (board : int[,]) = | |
| let queens = [for idx_i in 0..7 do | |
| for idx_j in 0..7 do | |
| if(board.[idx_i,idx_j] > 0) then | |
| yield idx_i,idx_j] | |
| //printfn "%A" queens | |
| let z = List.length(queens) | |
| if (z < 2) then | |
| // Single Queen | |
| true | |
| else | |
| let mutable return_value = true | |
| for queen1 in queens do | |
| let queen1_x, queen1_y = queen1 | |
| for queen2 in queens do | |
| let queen2_x, queen2_y = queen2 | |
| // Are they different queens? | |
| if (queen1_x <> queen2_x || queen1_y <> queen2_y) then | |
| // Check up/down | |
| if(queen1_x = queen2_x || queen1_y = queen2_y) then | |
| return_value <- false | |
| else | |
| // Check Diagonals | |
| let delta_y = (queen2_y-queen1_y) | |
| let delta_x = (queen2_x-queen1_x) | |
| if(delta_x = delta_y || delta_x = -delta_y) then | |
| return_value <- false | |
| return_value | |
| let rec search_solution (board : int[,]) (level : int) = | |
| if (level = 0) then | |
| //printfn "%A" board | |
| board, true | |
| else | |
| let mutable found_flag = false | |
| let mutable solution_board = Array2D.copy board | |
| for idx_i in 0..7 do | |
| for idx_j in 0..7 do | |
| if (found_flag = false) then | |
| if(board.[idx_i,idx_j] = 0) then | |
| let mutable board_temp = Array2D.copy board | |
| let next_level = level - 1 | |
| board_temp.[idx_i,idx_j] <- 1 | |
| if(check_board board_temp) then | |
| let ret_board, ret_found = search_solution board_temp next_level | |
| if(ret_found) then | |
| found_flag <- true | |
| solution_board <- Array2D.copy ret_board | |
| if (found_flag) then | |
| solution_board, true | |
| else | |
| board, false | |
| [<EntryPoint>] | |
| let main argv = | |
| let board = empty_board | |
| let queens = search_solution board 8 | |
| let o = check_board board | |
| printfn "%A" queens | |
| 0 // return an integer exit code | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
8 queens in f#