[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