X-Git-Url: https://git.xandkar.net/?a=blobdiff_plain;f=compiler%2Ftestcases%2Fqueens.tig;fp=compiler%2Ftestcases%2Fqueens.tig;h=1254b121aacb66b225f43f7c32adc01be1241807;hb=38ffcb1fc99ecb7a48097cbcf97b9a3062c8bfa0;hp=0000000000000000000000000000000000000000;hpb=4f2aaee3ef5f70f7769931032fd50af0403c51ae;p=tiger.ml.git

diff --git a/compiler/testcases/queens.tig b/compiler/testcases/queens.tig
new file mode 100644
index 0000000..1254b12
--- /dev/null
+++ b/compiler/testcases/queens.tig
@@ -0,0 +1,42 @@
+/* A program to solve the 8-queens problem */
+
+let
+  var N := 8
+
+  type intArray = array of int
+
+  var row := intArray [ N ] of 0
+  var col := intArray [ N ] of 0
+  var diag1 := intArray [N+N-1] of 0
+  var diag2 := intArray [N+N-1] of 0
+
+  function printboard() = (
+    for i := 0 to N-1 do (
+      for j := 0 to N-1 do print(if col[i]=j then " O" else " .");
+      print("\n")
+    );
+    print("\n")
+  )
+
+  function try(c:int) = (
+    /*  for i:= 0 to c do print("."); print("\n"); flush();*/
+    if c=N
+    then printboard()
+    else
+      for r := 0 to N-1
+      do
+        if row[r]=0 & diag1[r+c]=0 & diag2[r+7-c]=0
+        then (
+          row[r]       := 1;
+          diag1[r+c]   := 1;
+          diag2[r+7-c] := 1;
+          col[c]       := r;
+          try(c+1);
+          row[r]       := 0;
+          diag1[r+c]   := 0;
+          diag2[r+7-c] := 0
+        )
+  )
+in
+  try(0)
+end