[Nickle] nickle: Branch 'master'
Bart Massey
bart at keithp.com
Tue Nov 6 14:36:09 PST 2012
examples/sudoku.5c | 208 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 208 insertions(+)
New commits:
commit 3bb1adaa4f0cbf99343f41c7a326b36554590c07
Author: Bart Massey <bart at cs.pdx.edu>
Date: Tue Nov 6 14:36:20 2012 -0800
actually added Sudoku example
diff --git a/examples/sudoku.5c b/examples/sudoku.5c
new file mode 100755
index 0000000..3eca589
--- /dev/null
+++ b/examples/sudoku.5c
@@ -0,0 +1,208 @@
+#!/usr/bin/env nickle
+# Sudoku generator/solver
+# Copyright © 2005 Bart Massey
+
+# This code is distributed under the MIT license. Please
+# see the file COPYING in this distribution for license
+# details.
+
+autoimport PRNG;
+import File;
+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) {
+ for (int i = 0; i < dim(g); i++) {
+ if (g[i] == 0)
+ fprintf(f, ".");
+ else
+ fprintf(f, "%d", g[i]);
+ if (i % side == side - 1)
+ fprintf(f, "\n");
+ }
+}
+
+
+# return true iff cells p1 and p2
+# may not have the same value
+bool edge(int p1, int p2) {
+ if (p1 == p2)
+ return false;
+ if (p1 // side == p2 // side)
+ return true;
+ if (p1 % side == p2 % side)
+ return true;
+ # XXX if it is in the same horizontal "stripe"
+ # and the same vertical "stripe", it is in the
+ # same "cell"
+ if (p1 // (side * unit) == p2 // (side * unit) &&
+ (p1 % side) // unit == (p2 % side) // unit)
+ return true;
+ return false;
+}
+
+# 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))
+ 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.
+int solve(&grid g, bool recall, bool randomize) {
+ int p = 0;
+ for (p < dim(g); p++)
+ if (g[p] == 0)
+ break;
+ if (p >= dim(g))
+ return 1;
+ int[*] vals;
+ if (randomize) {
+ vals = (int[side]){ [i] = i + 1 };
+ shuffle(&vals);
+ }
+ int answer = 0;
+ int i = 0;
+ for (i < side; i++) {
+ if (randomize)
+ g[p] = vals[i];
+ else
+ 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;
+ }
+ if (i >= side || recall)
+ g[p] = 0;
+ return answer;
+}
+
+# deletion-based puzzle creation algorithm
+# suggested by ksudoku.
+# g is assumed to be a partial solution
+void del_soln(&grid g) {
+ int[dim(g)] delns = { [i] = i };
+ shuffle(&delns);
+ for (int i = 0; i < dim(delns); i++) {
+ print_grid(stdout, g); printf("\n");
+ &int d = &g[delns[i]];
+ int save = d;
+ d = 0;
+ int s = solve(&g, true, false);
+ if (s == 2)
+ d = save;
+ assert (s != 0, "clearing cell removed solutions!");
+ }
+}
+
+# start by creating a random solution. a slight variant
+# of the solver can do this.
+grid create_soln() {
+ grid g = (int[side**2]){0, ...};
+ assert(solve(&g, false, true) != 0, "cannot create puzzle");
+ return g;
+}
+
+void make_std_puzzle(file prob, file soln) {
+ grid g = create_soln();
+ del_soln(&g);
+ print_grid(prob, g);
+ solve(&g, false, false);
+ print_grid(soln, g);
+}
+
+void make_quadrant_puzzle(file prob, file soln) {
+ grid g = create_soln();
+ int xoff = randint(unit);
+ int yoff = randint(unit);
+ for (int x = 0; x < unit; x++)
+ 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");
+ print_grid(soln, g);
+}
+
+if (dim(argv) > 0) {
+ argdesc argd = {
+ args = {
+ { var = (arg_var.arg_flag) &(bool quadrant = false),
+ name = "quadrant",
+ abbr = 'q',
+ desc = "Construct puzzle with missing quadrant"
+ },
+ { var = (arg_var.arg_int) &unit,
+ name = "unit",
+ abbr = 'u',
+ expr_name = "size",
+ desc = "Unit cell size"
+ }
+ },
+ posn_args = {
+ { var = (arg_var.arg_string) &(string basename),
+ name = "basename"
+ }
+ }
+ };
+ parseargs(&argd, &argv);
+ side = unit ** 2;
+
+ 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);
+}
+
+
+# Permission is hereby granted, free of charge, to any person
+# obtaining a copy of this software and associated
+# documentation files (the "Software"), to deal in the
+# Software without restriction, including without limitation
+# the rights to use, copy, modify, merge, publish, distribute,
+# sublicense, and/or sell copies of the Software, and to
+# permit persons to whom the Software is furnished to do so,
+# subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall
+# be included in all copies or substantial portions of the
+# Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
+# KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
+# WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
+# PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS
+# OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
More information about the Nickle
mailing list