aboutsummaryrefslogtreecommitdiff
path: root/sample/nqueen.in
diff options
context:
space:
mode:
Diffstat (limited to 'sample/nqueen.in')
-rw-r--r--sample/nqueen.in141
1 files changed, 0 insertions, 141 deletions
diff --git a/sample/nqueen.in b/sample/nqueen.in
deleted file mode 100644
index dd50ad1..0000000
--- a/sample/nqueen.in
+++ /dev/null
@@ -1,141 +0,0 @@
-// N-Queen
-//
-// The original is written as a Lisp program in the following file:
-// https://www.istc.kobe-u.ac.jp/activity/mage/m27/27_Lisp.pdf
-
-
-/**
- * member
- * r, done << member(m, list)
- * return
- * r: 1 if m occurs in list
- * done: the same to `list'
- */
-// fun member x [] = false
-// | member x (y::ys) = if x=y then true else (member x ys);
-
-member(r, list, int x) >< [] =>
- r~0, list~[];
-member(r, list, int x) >< (int y):ys
-| x==y =>
- r~1, list~y:ys
-| _ =>
- list~y:cnt, member(r, cnt, x)~ys;
-
-
-/**
- * len_list (stream version)
- * len, done << len_list(list)
- * return
- * len: length of `list'
- * done: the same to `list'
- */
-
-len_list(len, done) >< [] =>
- len~0, done~[];
-len_list(len, done) >< x:xs =>
- done~x:cnt,
- len_list_(len, cnt, 1)~xs;
-
-len_list_(len, done, int ct) >< [] =>
- len~ct, done~[];
-len_list_(len, done, int ct) >< x:xs =>
- done~x:cnt,
- len_list_(len, cnt, ct+1) ~ xs;
-
-/**
- * len (non-stream version)
- * ret << len(list)
- * return
- * ret: length of `list'
- */
-
-len(ret) >< [] =>
- ret~0;
-len(ret) >< x:xs =>
- len_list(ret, Eraser)~x:xs;
-
-
-
-/**
- * threat (stream version)
- * check for (0,q) and (k, qpos[col=k]) where k=1...
- * http://www.nct9.ne.jp/m_hiroi/func/haskell06.html
- 0 1 2 -->
- +-------------
- 1| . . . . . .
- 2| . . . -3. . 5 - 3 = 2
- 3| . . -2. . . 5 - 2 = 3
- 4| . -1. . . . 5 - 1 = 4
- 5| Q . . . . . Q position is 5
- 6| . +1. . . . 5 + 1 = 6
- 7| . . +2. . . 5 + 2 = 7
- 8| . . . +3. . 5 + 2 = 8
- +-------------
- * r, done << threat(k,m, board)
- * return
- * r: 1 if threat conditions are satisfied
- * done: the same to `board'
- */
-// fun threat k m [] = false
-// | threat k m (x::xs) =
-// if (k = x-m) orelse (k = x+m) then true
-// else (threat (k+1) m xs);
-
-threat(r, done, int k, int q)><[] =>
- r~0, done~[];
-threat(r, done, int k, int q)><(int x):xs
-| (k == x-q) or (k == q-x) =>
- r~1, done~(x:xs)
-| _ =>
- done~x:cnt, threat(r, cnt, k+1, q)~xs;
-
-
-
-// fun queen1 b n 0 = []
-// | queen1 b n m =
-// if (member m b) orelse (threat 1 m b) then (queen1 b n (m-1))
-// else if (length b) = (n-1) then (m::b)::(queen1 b n (m-1))
-// else (queen1 (m::b) n n) @ (queen1 b n (m-1));
-// fun queen n = queen1 n [] n;
-
-queen(ret) >< (int n) => queen_(ret, [], n)~n;
-
-queen_(r, b, int n) >< (int m)
-| m==0 =>
- r~[], Eraser~b
-| _ =>
- mem_ret, done_b << member(m,b),
- queen__chk_m_in_b(r, done_b, n, m)~mem_ret;
-
-queen__chk_m_in_b(r, b, int n, int m) >< (int mem_ret)
-| mem_ret == 1 =>
- queen_(r, b, n)~(m-1)
-| _ =>
- th_ret, done_b << threat(1, m, b),
- queen__chk_threat(r, done_b, n, m)~th_ret;
-
-queen__chk_threat(r, b, int n, int m) >< (int threat_ret)
-| threat_ret == 1 =>
- queen_(r, b, n)~(m-1)
-| _ =>
- len_ret, done_b << len_list(b),
- queen__chk_lastelem(r, done_b, n, m)~len_ret;
-
-queen__chk_lastelem(r, b, int n, int m) >< (int len_ret)
-| len_ret == n-1 =>
- b1, b2 << Dup(b),
- r~(m:b1):cnt, queen_(cnt, b2, n)~(m-1)
-| _ =>
- b1, b2 << Dup(b),
- r << Append(cnt1, cnt2),
- queen_(cnt1, m:b1, n)~n, queen_(cnt2, b2, n)~(m-1);
-
-
-
-// ----------------------------------------------------------
-// main
-// ----------------------------------------------------------
-const N=8;
-queen(ret)~N, len(count)~ret;
-count; // count ->92