Previous Entry Share Next Entry
Games..
2012
unknownj
It's kind of neat, I now have a Sudoku solver..

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)

  • 1
To think I had a go at my Dad and Anthony for just *playing* the game... :oP

Yeah, but I don't play the game. I ruin the game. Isn't that okay? ;o)

I find that even "fiendish" puzzles don't hinge on guessing... you just need to work ahead with logic like if cell(x2,y7) contains either 1 or 7 && cell(x2,y3) contains 1 or 5 && both cell(x6, y3) and cell(x8, y3) contain either 5 or 3 then you can be sure that the first cell contains 7.

You 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:

    3       4    
  7     5     2  
9     6   2     3
    7 4   3 1    
  9           3  
    8 5   6 2    
7     8   5     9
  8     3     1  
    6       5    

Yes, that's something I haven't coded for yet..

The next challenge will indeed be to show that if a number must exist within a specific region, then it cannot exist in a conflicting one.

The simple case of this is when looking at where a number may be.. 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 too difficult.. 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)

I'd direct you to http://www.setbb.com/phpbb/?mforum=sudoku for more discussion on the programming of automated solvers.

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

it's not that it's cheating but that it's totally pointless.

Any more pointless than doing it the normal way?

Sudoku is pointless however you play it

in your anonymous opinion maybe

  • 1
?

Log in

No account? Create an account