[Math-Fun added back, as this was kinda fun. To me, anyway.]
Date: Wed, 08 Nov 2006 17:49:48 -0800 From: Nick Baxter <nickb@baxterweb.com>
I have two questions for you. What is the "R library"? How long does it take to solve a "trivial" Sudoku puzzle?
There are 3 things to understand here: S, SPlus, and R. * S is a language for statisticians designed in the late 80s. Think Scheme + APL + every statistical library you can think of. (And a few odd things, like the sudoku library contributed by Seeliger, Bengtsson, and Brahm.) * SPlus is a commercial implementation of S. * R is a free, open-source implementation of S. Seems to be more reliable than SPlus: I've had same-day fixes from library authors; you can't buy support like that! http://www.r-project.org/ As for your question re trivial sudokus: if by "trivial", you mean the easy ones published in some newspapers, I have no idea how those are selected. (I'm not really a puzzle guy.) On the other hand, if you mean a "typical" sudoku in the sense that it's randomly selected, then we can MEASURE that! Assuming that "difficulty" translates into computer time, which is of course dubious... I took a sample of 500 random sudokus: the usual 9x9 grids, random solutions, then 58 of 81 cells randomly blanked. (The sudoku library suggests 50/81 blanks, but the "world's most difficult sudoku" has 58, so I went with that. Obviously this parameter could be changed, or even randomly drawn from some distribution.) Solution times were measured in seconds, on an IBM T40 laptop with 2gb of memory running R under Windows2000. Here are the mean, std dev, skewness, kurtosis, range, and quartiles. mean stdDev skewness kurtosis 11.09398 51.72290 18.90855 389.56443 0% 25% 50% 75% 100% 2.67000 5.37750 6.32000 7.21500 1095.12000 Note that the mean is much larger than the median, so there are a lot of outliers. That's confirmed by the hardest one, which took 1095 sec to solve. So our "world's hardest sudoku" is about 5x harder than the median one with similar parameters, but nowhere near the hardest found in this sample! The R script which generated these data was:
library("sudoku") library("moments") source("profile.r"); profile("solveSudoku") times <- unlist(sapply(1:500, function(ignore) { solveSudoku(generateSudoku(Nblank = 58), print.it = FALSE); result <- profileResults(); resetProfiles(); result })["user", ]) c("mean" = mean(times), "stdDev" = sd(times), "skewness" = skewness(times), "kurtosis" = kurtosis(times), quantile(times, probs = c(0.00, 0.25, 0.50, 0.75, 1.00))) -- Steve Rowley <sgr@alum.mit.edu> http://alum.mit.edu/www/sgr/ Skype: sgr000