/sci/ - Science & Math

>>5607378
backtracking and guessing are two different things. The latter won't get you there.

usually you can get very far by checking the rules and make notes for each field of the possible allowed entries. then fill all fields with only one possible solution. rinse repeat.

though this will only work with simple sodokus, with thetougher one you will run into occasions where you have to check more than one possible solution. here you could create several threads - or use backtracking.

>>5607378
I can walk through my sudoku solving process and see if it helps you come up with a program. Not being a programmer myself I can't say with confidence, but it should definitely be possible because it all stems from facts that logically follow form the information given.

You can think of it as a linear programming problem. You create equations and solve it.

I am working on this currently but it is not quite my area and i find it really hard to think this way.

>>5607411
True, but if you never guess, that is, you only write a number down when you _know_ it's the right answer, you should never have to backtrack.

>>5607430
Yep, but that's pretty hard.

For minimal coding effort, reduce to SAT.

>>5607378
do you even breadth first searches?

Seriously though, the very basis of AI is taking a bunch of guesses and seeing if it pans out.

Guessing is silly.

Just build a 9x9 array of integers. Set them all to 0x03FF, indicating that all digits are possible in each square (that's 10 '1' bits).

Now, apply your facts. For example, There's a '5' in cell 0,0. That means that a[0,0] = (1 << 5). All the other cells in that row, in that column, and in that 3x3 square need to have their (1 << 5) bit reset.

Do this for all those given numbers. Now, look for cells with only one bit still set. Those cells have vales diretly implied by the given digits. Apply the same rules for them.

Rinse. Repeat.

>>5607430
thats pretty hard when you encounter a situation where several possibilies to continue arise.

and when writing a program to solve arbitrary sudokus , you may also run into occasions when there are several possible solutions for it (e.g. when you generate some in the first place and want to check if it has only a single solution).

>>5607430
Sudoku solvers don't 'write down' anything. Allowing for backtracking just means bruteforcing.

There is at least one class of moves that are certain and that you can do before you start the brute force. In OP's example the 1 of the top right block can only be below the eight. The conditions that force it to be there are that there isn't a one in the block yet, the top row is excluded, the mid and right columns are excluded and beyond that there is only one space. If you can generalize those conditions you can run that before bruteforcing.

I hope this makes sense because I'm sleepy and tired.

>>5607449
There will be situations when the sudoku has an unique solution but this procedure won't find it.
It's a good start, but you will additionally need to guess at some points and backtrack.

>>5607475
Backtracking does not necessarily imply bruteforcing. See, for instance,
>>5607449
>>5607480

>>5607489
I think it does. You may write down what is certain before bruteforcing but you can never backtrack on that because it is certain. The moment you start guessing is the moment you might backtrack.

>>5607499
Note that after you guessed once, you might be able to definitely solve some squares again. This algorithm only guesses when it's not trivial to fill any square in, which is rather a heuristic than plain bruteforce.

>>5607499
when you encounter a situation where several possible continuations are possible, just start a new thread for each one. you might get tons of threads, but you never need to backtrack

>>5607526
Right. In that sense it's not a bruteforce. Maybe I'm using bruteforce wrong here.

But in any case, there are sudokus where at some point there are no more trivial moves so any sudoku solver has to be able to start guessing at some point.

>>5607378
Well you'd start with getting it to assign all possibilities to each sqauare

And then spirals OP
Spirals.

>>5607537
"guessing" to me implies randomness, i.e. if you have 5 possible moves, pick one at random and keep going. The trouble with this is that you will repeat the same guesses and the program will bog down.

>>5607378

The most common and best way to solve Sudoku is with backtracking.

However, David Eppstein recently devised a method that solves it one digit at a time, and is supposedly nearly as good. Reference is here:

http://arxiv.org/abs/1202.5074

I wrote a solver for ProjectEuler problem number 96. The key was to order the empty squares by the number of entries you could enter in them without violating the summation rules. If some empty square has only one possibilty, then you can fill it in. If there is no such empty square, go with a square with two possibilities. Try the possibilities in numerical order. If you reach a dead end, back up and try the next possibility for the previous square if there is one. If not, back up again, etc.

>>5607535
>all that time and you used gif instead of png

When you are done writing yours, go here,

http://blog.davidsingleton.org/sudoku/

curl up into a ball, and cry.