My sister seems to think that in writing a program to do Sudoku for me, I'm

cheating. I, on the other hand, don't think I'm playing entirely the same

game, and certainly not on the same playing field, and therefore it's okay..

Surely the reward is in devising and implementing the correct strategy to

win a game, rather than going through the motions, following the mental

algorithm you've come up with.. Once you have your method, surely successive

games only serve to validate the method - a benefit only conferred when

you've won, which takes time.

So why not devise a method, and then automate it? The thinking is still

there, because you have to come up with the method in the first place. Then

you have to test it, and work out how to convert it into something a

computer can understand, and then try it out.

It took me until last Sunday, when I was on the train with my grandfather to

actually grasp the game. Until that point, I had tried to use a process of

elimination in order to find the correct number for a given square. He

suggested that I try finding the correct square for a given number, at which

point I started to get the whole point.. I'd been looking at it from a

"never more than one of each number per line & box" perspective, when really

it's "exactly one of each number per line & box", meaning that for a given

line, if there's only one possible square that a particular number could be

in, it logically must be there.

This has enabled me to construct a decent piece of software that can solve

just about any sudoku puzzle, with minimal human interaction, provided it

doesn't involve too much guesswork.

It's got two stages.. the first is a "numbers for cells" method. For a given

cell, it calculates all possible numbers that are still available to that

cell. So effectively, it shows the numbers 1-9

*except*for those that

are already present in the same row, column or box. If there exists only one

viable number, it fills it in. For easy puzzles, all you have to do is run

this once, and it tends to find the complete solution.

The second stage is a "cells for numbers" method. For a given number, it

highlights all cells where that number is viable. It then searches through

each row, and if it finds a row with just one cell highlighted, then it puts

the number into that row. It does the same for the columns and the boxes.

For medium puzzles, a combination of the two will tend to find the complete

solution given enough iterations.

Then there's the difficult puzzles, that tend to hinge on a single guess or

assumption. I've yet to determine whether I can use any sort of probability

model to choose which cell to guess at.. in any case, I have a sort of

save/rewind button, that allows you to go back to the last point at which

you were confident that everything was correct.

Add to that built in error-checking (ensuring that no number appears twice

anywhere, and that no cells are left without any options), and it makes the

whole thing somewhat easy to do. I picked a random difficult one, and ran my

program. It got as far as it could, and then I had to make a single guess as

to what a number might be. I did, and it then went on to complete the rest

of it for me. And none of it works by brute force - just logical deduction

:o)

Now granted, this makes each individual game rather boring, but the fun is

in building the software to do it for me, and in optimising it, and adding

new features to make it work better.. Oh, and in the fact that I can solve

them faster than you ;o)

morethanblindunknownjadcottYou could probably code this with some sort of stack-based arrangement, but I can't even begin to think how it would be done.

As an example, this puzzle fucked me up for about 5 hours and it's still got a whopping 28 clues:

unknownjThe next challenge will indeed be to show that if a number

mustexist within a specific region, then it cannot exist in a conflicting one.The simple case of this is when looking at where a number

maybe.. If within a given box you can narrow its location down to either one row or column within that box, then logically it cannot exist in that row or column outside of that box.That one is fairly easy to code, because the relevant function takes a single number, and tries to find where it can go. So in the course of that function, it will just need to examine each of the nine boxes, and determine whether any of them 'knock out' any of the other possibilities..

Your example is much, much harder.. and actually, it's something I hadn't considered yet. I was already aware that within a given box, if you have two cells with the same two possibilities, then you can eliminate those numbers from elsewhere within that box, but I hadn't considered doing it with rows and columns yet..

In theory, it shouldn't be

toodifficult.. Except that it wouldn't work for me. If I was storing the whole.. I dunno.. game space somewhere, then it would be fine. As in, if somewhere I had stored every possible value of a particular cell. But I don't - I generate it all on the fly, which makes it hard, because then I can't just eliminate possibilities without searching for them each time..If I was doing it in real code, it would be an object that holds objects that holds objects, and it'd be nice and easy. But Excel would be a bitch for that ;o)

nozzaAnd as Adcott pointed out, a well-formed puzle shouldn't require any guess-work at all..

shy(Anonymous)shy(Anonymous)shy