sudoku

[matt271]

i want to make an algorithm to solve sudoku puzzles w/out brute force.

so far i have coded 2 methods. "elimination" where every "square" has all possible values and u run through them eliminating impossible values. once only one possible value remains, thats the value of the square.
this works great on the 'easy' ones.

i then added another method where if only one possible 4 exists in a row, col, or box, set it to that value (ie 4)

this works on a lil more harder ones, but still now the "evil" ones.

i need more methods that dont require "playing it through" or "guess and test"

anybody have any ideas?

also what would the next step on this puzzle be:



ty

[corriep]

I know one algorithm that may or may not help you out.
(awesome GIMP skillz)

!!NOTE: This won't work on this specific puzzle but it does work. This is why I put in a '#' as a place holder for any other number, or else it won't work.

Anyways, when we compare the 8 in red, we find that an 8 can be placed in either of the green spot. Which ever spot the 8 goes in it doesn't matter, it cancels out that row and reveals that the blue 8 must be placed there.

This algorithm is very situational and I'm not sure how much use it will be but it is better than nothing
It may prove more useful if used recursively but I have never tried it. Good luck.

[bbi5291]

There are lots of sites online that have techniques for solving Sudoku puzzles, here's one.

In some cases you really do have to use brute force though. Smart brute force though.

I'll attach an implementation sometime soon.

Edit: http://compsci.ca/v3/viewtopic.php?p=186484

[leafs23]

search sudokus on google

[saltpro15]

wow, having flashbacks to ECOO finals, anyone else?

[bbi5291]

I don't get it, why? I don't remember a Sudoku problem...

[saltpro15]

oh, this just reminded me of Q4. It wasn't actually Sudoku, it was some Italian similar puzzle though.