David Empson wrote:
Scott Hemphill <hemphill@hemphills.net> wrote:If you think that one's tough, try this one. It's much harder, at least for my algorithm. I don't know where I got it, but I saved it under the filename "hints17-2". I have four files of the form "hints17-x", all very tough, but this one is the worst: ..1.2.7.. .5.....9. ...4..... .8...5... .9....... ....6...2 ..2...... ..6.....5 .....9.83Not even symmetrical. (Shudder.) Interestingly my PDA was able to verify this one much faster. I don't have time to look at it now, but I'll get to it in a few days.
Scott and I have both noticed that the time for a backtrack solution depends very strongly on the order in which the boxes are scanned for a trial placement. This puzzle is on the SUDOKU disk as VEVIL (Very evil ;-). I also added the 180-degree rotation of this puzzle as RVEVIL, where the solver will effectively scan the grid in the reverse order. The solver takes 3.5 times longer to solve the rotated puzzle! Scott did an experiment in which the solver scanned all the "evil"puzzles in reverse (actually, upper left to lower right) and in a majority of cases, the solution times changed by a factor of two
or more. The solver currently scans "backward", from lower right to upper left, for efficiency and coding convenience. BTW, I'm glad that the 1MHz Apple II is hanging in there with your PDA in solution speed. ;-) -michael Fast Sudoku solver for Apple II's! Home page: http://members.aol.com/MJMahon/ "The wastebasket is our most important design tool--and it's seriously underused."