Last active
April 3, 2016 02:55
-
-
Save cympfh/700f77492f99c6059ffc0d590e227a79 to your computer and use it in GitHub Desktop.
8 queens puzzle
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
(* | |
8-queen puzzle | |
8x8上にクイーンを8つ置く. | |
R・バード著「関数プログラミング」にあったのを思い出しつつ | |
書いた.同じ行にはひとつしかクイーンが無いのは自明で、 | |
ということは1行にちょうど1つだけあることになる. | |
それを利用したデータ構造を用いる.つまり、0行目から順に、 | |
クイーンが何列目にあるか、というリストを一つの候補とし、 | |
複数の候補をリストによって持っておき、それをmainに渡す. | |
0..i行目までの候補からi+1行目の候補を列挙して(sel)それを | |
候補の後ろに付け足したもの(1つ以上の候補になる)を | |
新たに0..i+1行目までの候補とし、また再帰的にmainに渡す. | |
初めは0..(-1)行目までの候補として[[]]を渡している. | |
*) | |
open System;; | |
module List = | |
(* lsからxを除いたリストls'を返す. | |
lsには高々1つのxしか含まれていないと決めてる *) | |
let rec diff x = function | |
| [] -> [] | |
| y::ys when x=y -> diff x ys | |
| y::ys -> y::diff x ys | |
let rec sel ls cand = | |
match ls with | |
| [] -> cand | |
| x::xs -> | |
let len = List.length ls in | |
cand |> List.diff x |> List.diff (x-len) |> List.diff (x+len) | |
|> sel xs | |
let rec main lss = | |
match lss with | |
| ls::lss when List.length ls = 8 -> lss | |
| _ -> [for ls in lss do | |
let cand = sel ls [0..7] in | |
for x in cand -> ls @ [x]] | |
|> main | |
let ls = [[]] in | |
printfn "%A" <| main ls | |
(* vim:set ft=fs: *) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment