Wednesday, March 01, 2006
Let's scream
I'd read about Screamer so by the time I'd heard of Sudoku I thought that this was something that just "screamed" for Screamer. Plus, when you tell your friends that you're working on a Lisp/AJAX RSS reader as a kind of laboratory for exploring ideas about natural language processing, you get a blank look. Tell them you're writing a Sudoku solver and they understand that.
Screamer has two parts. The first part is backtracking/search. You can write your program somewhat normally, but where your searching ends you put a "fail" call. Where your code doesn't "fail" is where your answers get collected. Brian Kuhn posted an "interview question" where you have a sequence of numbers, positive and negative, and you return the subsequence that would give the highest total. He had 100 lines of Java; with Screamer's help I had
Every time the subtotal is higher than the previous total there's a "success", and the sublist is collected by the "all-values" call. When it's done, the highest of them all is at the end of that list.
The other part is the "constraints" part, where you list the constraints on your variables, wind up Screamer, and let it go. The main problem I found with Screamer is that it doesn't handle arrays well, it does lists better, and individual variables best of all. This turned Sudoku into an exercise in typing. I had to list out 81 variables - mostly are "something between 1 and 9", some are the starting numbers - and 27 constraints, 9 row, 9 column and 9 box.
You can see the code here. If you have a Gmail account, you should get your Google page to host files if you don't want your own domain.
I've also wanted to learn LTK, so I wrote a separate LTK front-end for Sudoku. It uses LTK as well as the LTK "mega-widgets" in ltk-mw.lisp. Inside it uses a Sudoku solver that takes a 2D array as input, 0's for blanks, and returns a 2D array. Code is here. If you want to try this out as is you'll need to get Screamer loaded.
Something funny in the license for Screamer. Part of the conditions of its use is you have to send an e-mail telling them what version of Common Lisp you're using it with, so they can list it. I'll be adding OpenMCL 1.0 under Mac OSX and SBCL 0.9.0 under Linux. If you try this out then let them know.
Screamer has two parts. The first part is backtracking/search. You can write your program somewhat normally, but where your searching ends you put a "fail" call. Where your code doesn't "fail" is where your answers get collected. Brian Kuhn posted an "interview question" where you have a sequence of numbers, positive and negative, and you return the subsequence that would give the highest total. He had 100 lines of Java; with Screamer's help I had
(screamer:define-screamer-package :maxsub
(:export :findmaxsub))
(in-package :maxsub)
(defun findmaxsub (numbers)
(let ((total -99999))
(car
(nreverse
(all-values
(let ((begin (an-integer-between 0 (1- (length numbers))))
(end (an-integer-between 1 (length numbers))))
(when (>= begin end) (fail))
(let ((subtotal (apply #'+ (subseq numbers begin end))))
(if (> total subtotal)
(fail)
(setf total subtotal)))
(subseq numbers begin end)))))))
Every time the subtotal is higher than the previous total there's a "success", and the sublist is collected by the "all-values" call. When it's done, the highest of them all is at the end of that list.
The other part is the "constraints" part, where you list the constraints on your variables, wind up Screamer, and let it go. The main problem I found with Screamer is that it doesn't handle arrays well, it does lists better, and individual variables best of all. This turned Sudoku into an exercise in typing. I had to list out 81 variables - mostly are "something between 1 and 9", some are the starting numbers - and 27 constraints, 9 row, 9 column and 9 box.
You can see the code here. If you have a Gmail account, you should get your Google page to host files if you don't want your own domain.
I've also wanted to learn LTK, so I wrote a separate LTK front-end for Sudoku. It uses LTK as well as the LTK "mega-widgets" in ltk-mw.lisp. Inside it uses a Sudoku solver that takes a 2D array as input, 0's for blanks, and returns a 2D array. Code is here. If you want to try this out as is you'll need to get Screamer loaded.
Something funny in the license for Screamer. Part of the conditions of its use is you have to send an e-mail telling them what version of Common Lisp you're using it with, so they can list it. I'll be adding OpenMCL 1.0 under Mac OSX and SBCL 0.9.0 under Linux. If you try this out then let them know.
