This was an incomplete, untitled, unpublished draft of a post in my Blogger blog Geek Like Me, Too. About the same time, I was writing about Sudoku and Scheme on a different blog of mine called Praise, Curse, and Recurse. I’m not sure exactly why this post wound up in this blog instead of the other one. Possibly because the other blog was aggregated for a while on the Planet Scheme blog, and in this post I wind up making a case against using Scheme. In any case I have given it a title and included it here as part of my efforts to get all my writing online, including my rough drafts.
So, I’m trying to write a Sudoku solver in Scheme, in a functional style. I know that I could write a solver that would do a recursive search of the solutions and find one; I’ve done that kind of thing before. Instead I want to test out some strategies that let the program think like a human solver. I chose Scheme because it is simpler to learn than Common Lisp (giggle); eventually I want to learn idiomatic Common Lisp macros. See my “Road to Lisp” survey.
I know what I want to do, and I could do it easily in a language like Ruby, but Scheme is fighting me every step of the way.
The implementation I’m trying to use is DrScheme, part of the PLT Scheme project. This should be non-controversial; it is nicely portable, and supports a lot of dialects and libraries. Except.
I want a multi-dimensional array. This ought to be non-controversial as well, but R5RS does not support such a thing. So, I’m a Jedi: I should build my own lightsaber. I started writing a set of functions that would allow me to treat a Scheme vector as a 2-D array. For kicks I made iterators implemented with recursion, using higher-order functions. Now I want to be able to get at subarrays sharing existing cons cells. And with that partly underway, I realized that this was all great fun, but I was never going to make any progress on my Sudoku-solving algorithms if I had to spend so much of my precious free time reinventing the wheel. This is a spare-time project. I have a family. It isn’t a class project; I don’t need to prove that I can write a function to recursively traverse a sub-array; I’ve done it. I want to learn something about the actual problem at hand. So, I should be able to use an existing library for arrays, right?
What I need is a simple way to construct a 2-D array; an iterator that will feed me the coordinates, not the values; an iterator that will feed me the values; a good way to display the array; a good way to iterate on just a subset (a row or column, part of a row or column, or a Sudoki “grid” (a 3x3 box within the array). I understand basic Scheme reasonably well so if I can get most of what I want from a library, I can meet the library the rest of the way.
DrScheme allegedly supports SLIB. SLIB looks like it has most of what I need, so I can leverage that, right?
Well, I couldn’t get anywhere with it for a while, due to overhead issues. The mumble that was supposed to import SLIB did not work.
Then DrScheme 3.00 came out, and suddenly the same release of SLIB worked with the same mumble. So I’m golden, right? SLIB has nice array primitives. I can do this. First, the mumble:
(require (lib "load.ss" "slibinit")) ; loads "init.ss"
;; The pieces of SLIB I use:
(require 'array)
(require 'array-for-each)
(require 'subarray)
(require 'common-list-functions)
(define sample-puzzle-array
(list->array 2 '#()
'((() () () () 6 5 () 9 1)
(() () () () () () 5 () ())
(4 5 9 1 () () () 7 ())
(() () () () 9 () () 3 ())
(() () 1 8 () 6 7 () ())
(() 7 () () 4 () () () ())
(() 9 () () () 4 6 2 5)
(() () 4 () () () () () ())
(8 2 () 7 5 () () () ()))))to define my initial board, then I can start doing things like this:
; Makes a list 1..N => (1 2 .. N), for generating candidate lists
(define gen-delimited-list
(lambda (max)
(letrec ((gen-list
(lambda (count)
(if (> count max) (list)
(cons count (gen-list (+ count 1)))))))
(gen-list 1))))
;; Given a puzzle array containing the givens and nils, return a new
;; puzzle array containing possible lists. Each possible list contains
;; 1 to 9 possible values. Givens are converted into 1-element lists.
;; Empty (nil) boxes are converted into a list of all possibilities.
;; The possibles are not reduced yet; no rules have yet been applied.
; SLIB version:
(define make-possible-array
(lambda (puzzle-array)
(let ((possible-array (create-array #() puzzle-dimension puzzle-dimension)))
(array-map!
possible-array
(lambda (elt)
(cond ((number? elt) (list elt))
(else (gen-delimited-list puzzle-dimension))))
puzzle-array)
possible-array)))I can easily get a specific row or column or grid because of the nice subarray function:
(define get-row
(lambda (the-array row-idx)
(subarray0 the-array row-idx `(0 ,(- puzzle-dimension 1)))))
(define get-col
(lambda (the-array col-idx)
(subarray0 the-array `(0 ,(- puzzle-dimension 1)) col-idx)))
(define get-grid
(lambda (the-array grid-x-idx grid-y-idx)
(let ((start-y (* grid-y-idx puzzle-grid-dimension))
(start-x (* grid-x-idx puzzle-grid-dimension)))
(subarray0 the-array
(list start-y (+ start-y (- puzzle-grid-dimension 1)))
(list start-x (+ start-x (- puzzle-grid-dimension 1)))))))Hmmm, but I need to assemble the grid sub-array into a single list. There must be a cleaner way, but when something quick and dirty is needed, you can just use a raw list:
; TODO: This will give me the grid like this: ((nil nil nil) (nil nil nil) (4 5 9))
; I want the results as a single list like (nil nil nil nil nil nil 4 5 9)
; A temporary method for the 3x3 case only:
(define restructure-grid-to-3x3-list
(lambda (grid-array)
(let ((original-grid (array->list grid-array)))
(list (car (car original-grid))
(cadr (car original-grid))
(caddr (car original-grid))
(car (cadr original-grid))
(cadr (cadr original-grid))
(caddr (cadr original-grid))
(car (caddr original-grid))
(cadr (caddr original-grid))
(caddr (caddr original-grid))))))I wouldn’t say that really shows off the stunning elegance of Scheme, and it isn’t generalizable to arrays of different dimension, but it works, and I can leave that primitive to polish up later. So now I can consolidate the row, column, and grid list into a Sudoku board “neighborhood” using the list set operations:
; TODO: This will give me the grid like this: ((nil nil nil) (nil nil nil) (4 5 9))
; I want the results as a single list like (nil nil nil nil nil nil 4 5 9)
; A temporary method for the 3x3 case only:
(define restructure-grid-to-3x3-list
(lambda (grid-array)
(let ((original-grid (array->list grid-array)))
(list (car (car original-grid))
(cadr (car original-grid))
(caddr (car original-grid))
(car (cadr original-grid))
(cadr (cadr original-grid))
(caddr (cadr original-grid))
(car (caddr original-grid))
(cadr (caddr original-grid))
(caddr (caddr original-grid))))))Finally, I can start using the set primitives, which is how I want to think about the Sudoku solving strategies. Now that I’ve gotten a little bottom-up building done, I can start to think in terms of the problem space. Now, I just need to be able to iterate the array, and work on my sets, and I can really get somewhere, right?
I want to do this (expressed in C, more or less):
for (y = 0; y < max; y++)
for (x = 0; x < max; x++)
proc(x, y);in other words, send the array indices to a function in row-major order. It looks like there is a function, array-index-map!, which does this. But, as the exclamation point implies, it mutates the array! In fact, it destroys the contents. Not acceptable! I’m trying to write in a functional style. I don’t want to have to clone things all over the place. OK, so I’ll iterate the array indices myself. I am not comfortable doing iteration in Scheme, and I’m trying to force myself to become more comfortable with recursion, so I’ll do it like this:
(define process-array-1
(lambda (arr proc)
(letrec ((iter-x
(lambda (x-idx y-idx)
(proc arr x-idx y-idx)
(if (<>
(iter-x (+ x-idx 1) y-idx))))
(iter-y
(lambda (x-idx y-idx)
(if (<>
(begin
(iter-x x-idx y-idx)
(iter-y x-idx (+ y-idx 1)))))))
(iter-y 0 0))))That just can’t be right, can it? It seems to work. There has to be a much better way, right? Not a way that will teach me a clever trick, or a new paradigm, but a way that will let me avoid wasting my free time, those rare hours when the baby is asleep and the dishes are done, on exercises like this.
So, I’ll try the SRFIs. A friend recommended them. That seems like it is OK; DrScheme comes with support for the SRFIs. The mumble looks like this:
(require (lib "1.ss" "srfi")) ; lists
(require (lib "25.ss" "srfi")) ; multi-dimensional array primitivesLooks lovely. So, let’s see what I need to change. Well, first of all, there is no list->array. Uh-oh. Well, let’s try a different board representation:
(define puzzle-shape (shape 0 puzzle-dimension 0 puzzle-dimension))
(define sample-puzzle-array
(make-array puzzle-shape null))That seems simple enough. With a somewhat uglier representation I can provide a list of the givens, with their coordinates:
(define sample-puzzle-given-list
'(((4 0) 6) ((5 0) 5) ((7 0) 9) ((8 0) 1)
((6 1) 5)
((0 2) 4) ((1 2) 5) ((2 2) 9) ((3 2) 1) ((7 2) 7)
((4 3) 9) ((4 5) 3)
((2 4) 1) ((3 4) 8) ((5 4) 6) ((6 4) 7)
((1 5) 7) ((4 5) 4)
((1 6) 9) ((5 6) 4) ((6 6) 6) ((7 6) 2) ((8 6) 5)
((2 7) 4)
((0 8) 8) ((1 8) 2) ((3 8) 7) ((4 8) 5)))This is starting to get ugly; I really should use records, or something a little more expressive of what it means. Leave it for now; let’s put the givens into the board. Hmm… some struggling to remember the difference between caadr and cdaar… OK, this works:
(define sample-puzzle-given-list
'(((4 0) 6) ((5 0) 5) ((7 0) 9) ((8 0) 1)
((6 1) 5)
((0 2) 4) ((1 2) 5) ((2 2) 9) ((3 2) 1) ((7 2) 7)
((4 3) 9) ((4 5) 3)
((2 4) 1) ((3 4) 8) ((5 4) 6) ((6 4) 7)
((1 5) 7) ((4 5) 4)
((1 6) 9) ((5 6) 4) ((6 6) 6) ((7 6) 2) ((8 6) 5)
((2 7) 4)
((0 8) 8) ((1 8) 2) ((3 8) 7) ((4 8) 5)))At least, it appears to work; I can’t easily print it out. Also, this is not nicely functional; we’re mutating the array. But I guess that is OK. I’m going to be doing things the right way, right?
Well, let’s see what is next. I need to do my subarray access. I need to iterate the array. Hmmm. SRFI 25 is starting to look a little sparse. It provides only a few primitives. No iterators. I’d better use SRFI 47. Wait a minute, SRFI 47 has been superseded by SRFI 63. Number 63 looks pretty cool — it will give me list->array, shared arrays, and comparison operations, which could be useful later. Except — wait for it — it isn’t in PLT Scheme.
I’m getting a headache. I just rewrote a bunch of my code to try to use SRFIs instead of SLIB, after rewriting a bunch of my code to try to use SLIB in favor of my own array primitives. My free time is just about up. What have I learned, exactly?
Wait a minute… hang on…
$puzzle_grid_dimension = 3
$puzzle_dimension = $puzzle_grid_dimension * $puzzle_grid_dimension
$sample_puzzle_a =
[ [ nil, nil, nil, nil, 6, 5, nil, 9, 1 ],
[ nil, nil, nil, nil, nil, nil, 5, nil, nil ],
[ 4, 5, 9, 1, nil, nil, nil, 7, nil ],
[ nil, nil, nil, nil, 9, nil, nil, 3, nil ],
[ nil, nil, 1, 8, nil, 6, 7, nil, nil ],
[ nil, 7, nil, nil, 4, nil, nil, nil, nil ],
[ nil, 9, nil, nil, nil, 4, 6, 2, 5 ],
[ nil, nil, 4, nil, nil, nil, nil, nil, nil ],
[ 8, 2, nil, 7, 5, nil, nil, nil, nil ] ]
def puzzle_a_to_possible_a puzzle_a
possible_a = puzzle_a.clone
possible_a.each {|row|
row.collect! {|elt|
if elt == nil then
Array.new($puzzle_dimension) {|idx| idx + 1}
else
Array.new 1, elt
end
}
}
possible_a
end
$sample_possible_a = puzzle_a_to_possible_a $sample_puzzle_a
def print_vrow vrow
vrow.each {|elt|
print "[" + elt.to_s.center(9) + "] "
}
print "\n"
end
def get_row puzzle_a, y_idx
puzzle_a[y_idx]
end
def get_col puzzle_a, x_idx
Array.new($puzzle_dimension) {|idx| puzzle_a[idx][x_idx]}
end
def get_grid puzzle_a, grid_x_idx, grid_y_idx
grid = Array.new($puzzle_dimension)
$puzzle_grid_dimension.times {|y_idx|
$puzzle_grid_dimension.times {|x_idx|
puzzle_x_base = grid_x_idx * $puzzle_grid_dimension
puzzle_y_base = grid_y_idx * $puzzle_grid_dimension
grid[y_idx * $puzzle_grid_dimension + x_idx] =
puzzle_a[puzzle_y_base + y_idx][puzzle_x_base + x_idx]
}
}
grid
end
def get_grid_indices_from_coordinates x_idx, y_idx
[x_idx.div($puzzle_grid_dimension),
y_idx.div($puzzle_grid_dimension)]
end
def make_combined_vrow puzzle_a, x_idx, y_idx
[get_row(puzzle_a, y_idx),
get_col(puzzle_a, x_idx),
get_grid(puzzle_a, x_idx, y_idx)]
end
$neighborhood_found = $test_combo_vrow.flatten.uniq
print $neighborhood_foundThat’s Ruby. It isn’t even particularly idiomatic Ruby. It took me only a couple of hours to get it working, and I haven’t used Ruby all that much, and not at all in the last three months.
Why am I learning Scheme again, exactly?