[Nickle] nickle: Branch 'master' - 3 commits

Bart Massey bart at keithp.com
Sat Nov 10 00:42:04 PST 2012


 examples/sudoku.5c |  135 +++++++++++++++++++++++++++++++++++------------------
 1 file changed, 91 insertions(+), 44 deletions(-)

New commits:
commit e309b5a8d9df4f8ec2027cf09d4070997a0d2a47
Author: Bart Massey <bart at cs.pdx.edu>
Date:   Sat Nov 10 00:40:50 2012 -0800

    added check mode to sudoku solver

diff --git a/examples/sudoku.5c b/examples/sudoku.5c
index 2bea177..489c242 100755
--- a/examples/sudoku.5c
+++ b/examples/sudoku.5c
@@ -152,8 +152,31 @@ void make_quadrant_puzzle(file prob, file soln) {
     print_grid(soln, g);
 }
 
-void count_prob(file prob) {
-    printf("not yet\n");
+grid read_prob(file prob) {
+    int[...] g = {};
+    int i = 0;
+    side = 0;
+    while (side == 0 || i < side**2) {
+        int ch = getc(prob);
+        if (ch == '\n') {
+            if (side == 0) {
+                side = i;
+                unit = sqrt(side);
+            }
+            continue;
+        }
+        if (ch == '.') {
+            g[i++] = 0;
+            continue;
+        }
+        if (ch >= 'a' && ch <= 'z') {
+            g[i++] = 10 + ch - 'a';
+            continue;
+        }
+        g[i++] = ch - '0';
+    }
+    print_grid(stdout, g);
+    return g;
 }
 
 if (dim(argv) > 0) {
@@ -183,16 +206,19 @@ if (dim(argv) > 0) {
 	}
     };
     parseargs(&argd, &argv);
-    side = unit ** 2;
-    init_edges();
     dev_srandom(16);
 
     if (count_solns) {
-       twixt(file prob = open(basename + "-prob.txt", "r"); close(prob))
-           count_prob(prob);
+       twixt(file prob = open(basename + "-prob.txt", "r"); close(prob)) {
+           grid g = read_prob(prob);
+           init_edges();
+           printf("%d\n", solve(&g, false, false));
+       }
        exit(0);
     }
 
+    side = unit ** 2;
+    init_edges();
     twixt((file prob = open(basename + "-prob.txt", "w")),
           (file soln = open(basename + "-soln.txt", "w"));
           close(prob),
commit 061cb1ec69aabe674a343f5612e49dd7c7779fc1
Author: Bart Massey <bart at cs.pdx.edu>
Date:   Sat Nov 10 00:03:50 2012 -0800

    cleaned up a bunch of sudoku solver stuff

diff --git a/examples/sudoku.5c b/examples/sudoku.5c
index bfe5546..2bea177 100755
--- a/examples/sudoku.5c
+++ b/examples/sudoku.5c
@@ -12,13 +12,6 @@ autoimport ParseArgs;
 
 int unit, side;
 
-void setunit(int n) {
-    unit = n;
-    side = unit ** 2;
-}
-
-setunit(3);
-
 typedef int[*] grid;
 
 void print_grid(file f, grid g) {
@@ -51,10 +44,15 @@ bool edge(int p1, int p2) {
     return false;
 }
 
-bool[side**2, side**2] edges = {[i, j] = edge(i, j)};
 
-# check whether the value in g at p
-# conflicts with any other values of g
+bool[*, *] edges;
+
+void init_edges() {
+     edges = (bool[side**2, side**2]){[i, j] = edge(i, j)};
+}
+
+# check whether the value in g at p is consistent with every
+# other value in g
 bool check(&grid g, int p) {
     for (int p2 = 0; p2 < dim(g); p2++)
 	if (g[p2] == g[p] && edges[p, p2])
@@ -64,13 +62,14 @@ bool check(&grid g, int p) {
 
 # simple-minded DFS solver doesnt scale.  assumes it is
 # passed a grid whose filled cells conform to constraints.
-# returns a solution count of 0, 1, or 2 with 2 meaning "2
-# or more".  the recall parameter says whether to undo
-# (true) or preserve (false) the solution; if the latter,
-# then only 0 or 1 will be returned.  the randomize
+# returns a solution count which is a lower bound on the
+# true number of solutions, accurate if 0 or 1.  the
+# preserve parameter says whether to preserve (true) or
+# clear (false) cells of the solution: if preserve is true,
+# the first solution found is returned.  the randomize
 # parameter says to try the values in random order; this is
 # useful for puzzle construction.
-int solve(&grid g, bool recall, bool randomize) {
+int solve(&grid g, bool preserve, bool randomize) {
     int p = 0; 
     for (p < dim(g); p++)
         if (g[p] == 0)
@@ -91,15 +90,14 @@ int solve(&grid g, bool recall, bool randomize) {
 	    g[p] = i + 1;
 	if (!check(&g, p))
 	    continue;
-	answer += solve(&g, recall, randomize);
-        # early return
-	if (answer >= 2)
-	    break;
-	if (!recall && answer >= 1)
-	    break;
+	int result = solve(&g, preserve, randomize);
+        if (preserve && result > 0)
+            return result;
+        answer += result;
+        if (answer > 1)
+            break;
     }
-    if (i >= side || recall)
-	g[p] = 0;
+    g[p] = 0;
     return answer;
 }
 
@@ -114,7 +112,7 @@ void del_soln(&grid g) {
 	&int d = &g[delns[i]];
 	int save = d;
 	d = 0;
-	int s = solve(&g, true, false);
+	int s = solve(&g, false, false);
 	if (s >= 2)
 	    d = save;
 	assert (s != 0, "clearing cell removed solutions!");
@@ -125,7 +123,8 @@ void del_soln(&grid g) {
 # of the solver can do this.
 grid create_soln() {
     grid g = (int[side**2]){0, ...};
-    assert(solve(&g, false, true) != 0, "cannot create puzzle");
+    int nsolns = solve(&g, true, true);
+    assert(nsolns > 0, "cannot create puzzle");
     return g;
 }
 
@@ -133,7 +132,9 @@ void make_std_puzzle(file prob, file soln) {
     grid g = create_soln();
     del_soln(&g);
     print_grid(prob, g);
-    solve(&g, false, false);
+    int nsolns = solve(&g, false, false);
+    assert(nsolns == 1, "found %d solns", nsolns);
+    solve(&g, true, false);
     print_grid(soln, g);
 }
 
@@ -145,10 +146,16 @@ void make_quadrant_puzzle(file prob, file soln) {
 	for (int y = 0; y < unit; y++)
 	    g[x + unit * xoff + (y + unit * yoff) * side] = 0;
     print_grid(prob, g);
-    assert(solve(&g, false, false) == 1, "more than one solution");
+    int nsolns = solve(&g, false, false);
+    assert(nsolns == 1, "found %d solutions", nsolns);
+    solve(&g, true, false);
     print_grid(soln, g);
 }
 
+void count_prob(file prob) {
+    printf("not yet\n");
+}
+
 if (dim(argv) > 0) {
     argdesc argd = {
 	args = {
@@ -157,6 +164,11 @@ if (dim(argv) > 0) {
 	      abbr = 'q',
 	      desc = "Construct puzzle with missing quadrant"
 	    },
+	    { var = (arg_var.arg_flag) &(bool count_solns = false),
+	      name = "count",
+	      abbr = 'c',
+	      desc = "Count number of solutions to puzzle"
+	    },
 	    { var = (arg_var.arg_int) &unit,
 	      name = "unit",
 	      abbr = 'u',
@@ -172,16 +184,25 @@ if (dim(argv) > 0) {
     };
     parseargs(&argd, &argv);
     side = unit ** 2;
-
+    init_edges();
     dev_srandom(16);
-    file prob = open(basename + "-prob.txt", "w");
-    file soln = open(basename + "-soln.txt", "w");
-    if (quadrant)
-	make_quadrant_puzzle(prob, soln);
-    else
-	make_std_puzzle(prob, soln);
-    close(prob);
-    close(soln);
+
+    if (count_solns) {
+       twixt(file prob = open(basename + "-prob.txt", "r"); close(prob))
+           count_prob(prob);
+       exit(0);
+    }
+
+    twixt((file prob = open(basename + "-prob.txt", "w")),
+          (file soln = open(basename + "-soln.txt", "w"));
+          close(prob),
+          close(soln)) {
+        if (quadrant)
+            make_quadrant_puzzle(prob, soln);
+        else
+	    make_std_puzzle(prob, soln);
+    }
+    exit(0);
 }
 
 
commit 929e8ec4598d46a4f4bb040148d9f818a6d2fd2a
Author: Bart Massey <bart at cs.pdx.edu>
Date:   Fri Nov 9 22:48:54 2012 -0800

    added edge cache to sudoku example

diff --git a/examples/sudoku.5c b/examples/sudoku.5c
index 3eca589..bfe5546 100755
--- a/examples/sudoku.5c
+++ b/examples/sudoku.5c
@@ -51,25 +51,25 @@ bool edge(int p1, int p2) {
     return false;
 }
 
+bool[side**2, side**2] edges = {[i, j] = edge(i, j)};
+
 # check whether the value in g at p
 # conflicts with any other values of g
 bool check(&grid g, int p) {
     for (int p2 = 0; p2 < dim(g); p2++)
-	if (g[p2] == g[p] && edge(p, p2))
+	if (g[p2] == g[p] && edges[p, p2])
 	    return false;
     return true;
 }
 
-# simple-minded DFS solver doesnt
-# scale.  assumes it is passed a grid
-# whose filled cells conform to constraints.
-# returns a solution count of 0, 1, or 2
-# with 2 meaning "2 or more".  the recall
-# parameter says whether to undo or preserve
-# the solution; if the latter, then only 0
-# or 1 will be returned.  the randomize parameter
-# says to try the values in random order; this
-# is useful for puzzle construction.
+# simple-minded DFS solver doesnt scale.  assumes it is
+# passed a grid whose filled cells conform to constraints.
+# returns a solution count of 0, 1, or 2 with 2 meaning "2
+# or more".  the recall parameter says whether to undo
+# (true) or preserve (false) the solution; if the latter,
+# then only 0 or 1 will be returned.  the randomize
+# parameter says to try the values in random order; this is
+# useful for puzzle construction.
 int solve(&grid g, bool recall, bool randomize) {
     int p = 0; 
     for (p < dim(g); p++)
@@ -115,7 +115,7 @@ void del_soln(&grid g) {
 	int save = d;
 	d = 0;
 	int s = solve(&g, true, false);
-	if (s == 2)
+	if (s >= 2)
 	    d = save;
 	assert (s != 0, "clearing cell removed solutions!");
     }


More information about the Nickle mailing list