Update for n-queens

14 files changed, 425 insertions, 5 deletions

diff --git a/comparison/Haskell/Makefile b/comparison/Haskell/Makefile
index 13a1b83..ee4e347 100644
--- a/comparison/Haskell/Makefile
+++ b/comparison/Haskell/Makefile
@@ -1,7 +1,7 @@
 CC      = stack ghc
 CFLAGS  = -O2
 BENCHMARK  = bash ../tools/sptest_commands.sh
-TARGET  = ack3-11 fib38 bsort-20000 isort-20000 qsort-260000 msort-260000
+TARGET  = nqueen-12 ack3-11 fib-38 bsort-20000 isort-20000 qsort-260000 msort-260000
 LOG = log.txt
 
 
@@ -12,10 +12,13 @@ all: $(LOG)
 $(LOG): $(TARGET)
 	$(BENCHMARK) $(TARGET)
 
+nqueen-12: nqueen-12.hs
+	$(CC) -- $(CFLAGS) $<
+
 ack3-11: ack3-11.hs
 	$(CC) -- $(CFLAGS) $<
 
-fib38: fib38.hs
+fib-38: fib-38.hs
 	$(CC) -- $(CFLAGS) $<
 
 bsort-20000: bsort-20000.hs
diff --git a/comparison/Haskell/fib-38.hs b/comparison/Haskell/fib-38.hs
new file mode 100644
index 0000000..658d228
--- /dev/null
+++ b/comparison/Haskell/fib-38.hs
@@ -0,0 +1,6 @@
+fib 0 = 0
+fib 1 = 1
+fib n = fib (n - 2) + fib (n - 1)
+
+
+main = print $ fib 38
diff --git a/comparison/Haskell/nqueen-12.hs b/comparison/Haskell/nqueen-12.hs
new file mode 100644
index 0000000..1efb57b
--- /dev/null
+++ b/comparison/Haskell/nqueen-12.hs
@@ -0,0 +1,21 @@
+member x [] = False
+member x (y:ys)
+  | x==y = True
+  | otherwise = member x ys
+
+threat k m [] = False
+threat k m (x:xs)
+  | (k == x-m) || (k == m-x) = True
+  | otherwise = threat (k+1) m xs
+
+
+queen1 0 b n = []
+queen1 m b n
+  | (member m b) || (threat 1 m b) = (queen1 (m-1) b n)
+  | (length b) == (n-1) = [m:b] ++ (queen1 (m-1) b n)
+  | otherwise = (queen1 n (m:b) n) ++ (queen1 (m-1) b n)
+
+queen n = queen1 n [] n
+
+n=12
+main = print $ (length (queen n))
diff --git a/comparison/Inpla/main.sh b/comparison/Inpla/main.sh
index 13502b9..c3ba3b3 100644
--- a/comparison/Inpla/main.sh
+++ b/comparison/Inpla/main.sh
@@ -1,5 +1,8 @@
 #!/bin/bash
 
+bash ./sptestInpla.sh src/nqueen-12.in '-Xmt 6'
+bash ./sptestInpla.sh src/nqueen-12-reuse.in '-Xmt 6'
+
 bash ./sptestInpla.sh src/fib-38.in
 bash ./sptestInpla.sh src/fib-38-reuse.in
 
@@ -17,3 +20,9 @@ bash ./sptestInpla.sh src/qsort-260000-reuse.in '-Xms 17 -Xmt 0'
 
 bash ./sptestInpla.sh src/msort-260000.in
 bash ./sptestInpla.sh src/msort-260000-reuse.in '-Xms 18 -Xmt 0'
+
+bash ./sptestInpla.sh src/qsort-800000.in
+bash ./sptestInpla.sh src/qsort-800000-reuse.in '-Xms 18 -Xmt 0'
+
+bash ./sptestInpla.sh src/msort-800000.in
+bash ./sptestInpla.sh src/msort-800000-reuse.in '-Xms 18 -Xmt 0'
diff --git a/comparison/Inpla/src/nqueen-12-reuse.in b/comparison/Inpla/src/nqueen-12-reuse.in
new file mode 100644
index 0000000..4e5a6b6
--- /dev/null
+++ b/comparison/Inpla/src/nqueen-12-reuse.in
@@ -0,0 +1,141 @@
+// 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~(*R)[];
+member(r, list, int x) >< (int y):ys
+| x==y =>
+        r~1, list~(*R)(y:ys)
+| _ =>
+        list~(*R)(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~(*R)[];
+len_list(len, done) >< x:xs => 
+        done~(*R)(x:cnt), 
+        len_list_(len, cnt, 1)~xs;
+
+len_list_(len, done, int ct) >< [] =>
+        len~ct, done~(*R)[];
+len_list_(len, done, int ct) >< x:xs => 
+        done~(*R)(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)~(*R)(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~(*R)[];
+threat(r, done, int k, int q)><(int x):xs
+| (k == x-q) or (k == q-x) =>
+        r~1, done~(*R)(x:xs)
+| _ =>
+        done~(*R)(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~[], (*L)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 =>
+        (*L)queen_(r, b, n)~(m-1)
+| _ =>
+        th_ret, done_b << threat(1, m, b), 
+	(*L)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 =>
+        (*L)queen_(r, b, n)~(m-1)
+| _ =>
+        len_ret, done_b << len_list(b), 
+	(*L)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, (*L)queen_(cnt, b2, n)~(m-1)
+| _ =>
+        b1, b2 << Dup(b),
+        r << Append(cnt1, cnt2),
+        (*L)queen_(cnt1, m:b1, n)~n, queen_(cnt2, b2, n)~(m-1);
+
+
+
+// ----------------------------------------------------------
+// main
+// ----------------------------------------------------------
+const N=12;
+queen(ret)~N, len(count)~ret;
+count;   // count ->14200
diff --git a/comparison/Inpla/src/nqueen-12.in b/comparison/Inpla/src/nqueen-12.in
new file mode 100644
index 0000000..18f3a64
--- /dev/null
+++ b/comparison/Inpla/src/nqueen-12.in
@@ -0,0 +1,141 @@
+// 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=12;
+queen(ret)~N, len(count)~ret;
+count; // count ->14200
diff --git a/comparison/OCaml/Makefile b/comparison/OCaml/Makefile
index 9db7726..18c1eda 100644
--- a/comparison/OCaml/Makefile
+++ b/comparison/OCaml/Makefile
@@ -1,7 +1,7 @@
 CC      = ocamlopt
 CFLAGS  = 
 BENCHMARK  = bash ../tools/sptest_commands.sh
-TARGET  = ack3_11 fib38 bsort20000 isort20000 qsort260000 msort260000
+TARGET  = nqueen12 ack3_11 fib38 bsort20000 isort20000 qsort260000 msort260000
 LOG = log.txt
 
 
@@ -12,6 +12,9 @@ all: $(LOG)
 $(LOG): $(TARGET)
 	$(BENCHMARK) $(TARGET)
 
+nqueen12: nqueen12.ml
+	$(CC) $(CFLAGS) $< -o $@
+
 ack3_11: ack3_11.ml
 	$(CC) $(CFLAGS) $< -o $@
 
diff --git a/comparison/OCaml/nqueen12.ml b/comparison/OCaml/nqueen12.ml
new file mode 100644
index 0000000..fc56542
--- /dev/null
+++ b/comparison/OCaml/nqueen12.ml
@@ -0,0 +1,23 @@
+let rec member x alist =
+  match alist with
+    []    -> false
+  | y::ys -> if x=y then true else (member x ys);;
+
+let rec threat k m alist =
+  match alist with
+    []    -> false
+  | x::xs ->  if (k = x-m) || (k = m-x) then true
+              else (threat (k+1) m xs);;
+
+let rec queen1 m b n =
+  match m with
+    0 -> []
+  | m ->
+    if (member m b) || (threat 1 m b) then (queen1 (m-1) b n)
+    else if (List.length b) = (n-1) then [m::b]@(queen1 (m-1) b n)
+         else (queen1 n (m::b) n) @ (queen1 (m-1) b n);;
+
+let queen n = queen1 n [] n;;
+
+let n = 12;;
+let () = print_int (List.length (queen n));
diff --git a/comparison/Python/Makefile b/comparison/Python/Makefile
index c77d677..5dd95fd 100644
--- a/comparison/Python/Makefile
+++ b/comparison/Python/Makefile
@@ -1,5 +1,5 @@
 COMMAND = python3
-TARGET  = dummy.py ack3-11.py fib38.py bsort-20000.py isort-20000.py qsort-260000.py msort-260000.py
+TARGET  = dummy.py nqueen-12.py ack3-11.py fib-38.py bsort-20000.py isort-20000.py qsort-260000.py msort-260000.py
 BENCHMARK  = bash ../tools/sptest_scripts.sh
 LOG = log.txt
 
diff --git a/comparison/Python/fib-38.py b/comparison/Python/fib-38.py
new file mode 100644
index 0000000..efa5380
--- /dev/null
+++ b/comparison/Python/fib-38.py
@@ -0,0 +1,8 @@
+def fib(n):
+    if n == 0:
+        return 0
+    elif n == 1:
+        return 1
+    else:
+        return fib(n-1) + fib(n-2)
+print(fib(38))
diff --git a/comparison/Python/nqueen-12.py b/comparison/Python/nqueen-12.py
new file mode 100644
index 0000000..494131f
--- /dev/null
+++ b/comparison/Python/nqueen-12.py
@@ -0,0 +1,27 @@
+def threat(k, m, alist):
+    if alist == []:
+        return False
+    else:
+        x = alist[0]        
+        if (k == x-m) or (k == m-x):
+            return True
+        else:
+            return threat(k+1, m, alist[1:])
+        
+def queen1(m, b, n):
+    if m == 0:
+        return []
+    else:
+        if (m in b) or threat(1, m, b):
+            return queen1(m-1, b, n)
+        elif len(b) == n-1:
+            return [[m]+b] + (queen1(m-1, b, n))
+        else:
+            return queen1(n, [m]+b, n) + (queen1(m-1, b, n))
+
+
+def queen(n):
+    return queen1(n,[],n)
+
+n=12
+print(len(queen(12)))
diff --git a/comparison/SML/Makefile b/comparison/SML/Makefile
index 14dca02..5e89840 100644
--- a/comparison/SML/Makefile
+++ b/comparison/SML/Makefile
@@ -1,5 +1,5 @@
 COMMAND = sml
-TARGET  = dummy.sml ack3-11.sml fib38.sml bsort-20000.sml isort-20000.sml qsort-260000.sml msort-260000.sml
+TARGET  = dummy.sml nqueen-12.sml ack3-11.sml fib-38.sml bsort-20000.sml isort-20000.sml qsort-260000.sml msort-260000.sml
 BENCHMARK  = bash ../tools/sptest_scripts.sh
 LOG = log.txt
 
diff --git a/comparison/SML/fib-38.sml b/comparison/SML/fib-38.sml
new file mode 100644
index 0000000..504d4ac
--- /dev/null
+++ b/comparison/SML/fib-38.sml
@@ -0,0 +1,5 @@
+fun fib 0 = 0
+| fib 1 = 1
+| fib n = (fib (n-1)) + (fib (n-2));
+
+fib 38;
diff --git a/comparison/SML/nqueen-12.sml b/comparison/SML/nqueen-12.sml
new file mode 100644
index 0000000..9605312
--- /dev/null
+++ b/comparison/SML/nqueen-12.sml
@@ -0,0 +1,33 @@
+fun member x [] = false
+| member x (y::ys) = if x=y then true else (member x ys);
+
+(* 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
+  *-------------
+*)
+fun threat k m [] = false
+  | threat k m (x::xs) =
+   if (k = x-m) orelse (k = m-x) then true
+    else (threat (k+1) m xs);
+
+
+fun queen1 0 b n = []
+  | queen1 m b n =
+    if (member m b) orelse (threat 1 m b) then (queen1 (m-1) b n)
+    else if (length b) = (n-1) then [m::b]@(queen1 (m-1) b n)
+         else (queen1 n (m::b) n) @ (queen1 (m-1) b n);
+
+fun queen n = queen1 n [] n;
+
+val n = 12;
+length (queen n);