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.
# posted by Richard Cook @ 5:45 AM 
Comments:
<< Home
Not great. On my 1 Ghz iBook it takes about .7 seconds to do one puzzle, much slower than Jalat's Let's Dance. This was mainly an exercise in learning Screamer and LTK, and the only contest mine will win would be "ease of understanding". Someone could probably look at the Screamer version and understand the rules of Sudoku without knowing Sudoku beforehand.
screamer+ is an extension to screamer that attemps to make it work better with aggregates. You might want to use it. I have a mostly CL-clean version somewhere, although I think the quasi totality of the work was in fixing EVAL-WHENs and dependencies.
# posted by 
: 4:50 PM
: 4:50 PM
I tried Screamer+, but the arefv they had implemented mainly varied the indices of the array access, not the data in the arrays.
Here's a solution in Java which is much less than 100 lines of code and runs in O(n) as apposed to your solution which is O(n^2).
int[] maxSeq(int[] a) {
int max = 0, sum = 0,low = 0, high = 0, maxlow = 0, maxhigh = 0;
for ( int i = 0 ; i < a.length ; i++, high++ ) {
sum += a[i];
if ( sum < 0 ) {
sum = 0;
low = i+1;
} else if ( sum > max ) {
max = sum;
maxlow = low;
maxhigh = high;
}
}
int[] seq = new int[maxhigh-maxlow];
System.arraycopy(a, maxlow, seq, 0, maxhigh-maxlow);
return seq;
}
int[] maxSeq(int[] a) {
int max = 0, sum = 0,low = 0, high = 0, maxlow = 0, maxhigh = 0;
for ( int i = 0 ; i < a.length ; i++, high++ ) {
sum += a[i];
if ( sum < 0 ) {
sum = 0;
low = i+1;
} else if ( sum > max ) {
max = sum;
maxlow = low;
maxhigh = high;
}
}
int[] seq = new int[maxhigh-maxlow];
System.arraycopy(a, maxlow, seq, 0, maxhigh-maxlow);
return seq;
}
# posted by : 6:16 AM
: 6:16 AM
I'd be interested to hear more about your Screamer experiences in future blog posts. I have tried to use it on a few occasions, and I've found it was difficult to debug the nondeterministic search, and that harvesting information out of a nondeterministic part of one of my programs and into a "normal" part was difficult. I've always ended up giving up and using a more conventional search approach, or using CLP in Prolog, where nondeterminism is basic to the language and hence better integrated.
# posted by : 9:27 AM
: 9:27 AM
Kevin,
The last parameter to System.arraycopy is length, which needs to be 'maxhigh - maxlow + 1'. Also, your app doesn't work for all negative numbers; from Brian's comments in his solution,
{-5, -12, -3, -7} => {-3}
The last parameter to System.arraycopy is length, which needs to be 'maxhigh - maxlow + 1'. Also, your app doesn't work for all negative numbers; from Brian's comments in his solution,
{-5, -12, -3, -7} => {-3}
Richard,
Thanks for catching the off-by-one bug. The line above the arraycopy() needs a "+1" also.
I didn't read the original problem carefully so I figured that if all of the numbers were negative then the largest largest sum would be zero and it would belong to any zero-length sequence.
Post a Comment
Thanks for catching the off-by-one bug. The line above the arraycopy() needs a "+1" also.
I didn't read the original problem carefully so I figured that if all of the numbers were negative then the largest largest sum would be zero and it would belong to any zero-length sequence.
# posted by : 6:51 PM
: 6:51 PM << Home
