-----------------------------------

matt271

Wed May 20, 2009 11:48 pm


sudoku

-----------------------------------

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:

http://i42.tinypic.com/2w70nxf.jpg

ty


-----------------------------------

corriep

Mon May 25, 2009 8:34 pm


Re: sudoku

-----------------------------------

I know one algorithm that may or may not help you out. 
http://img22.imageshack.us/img22/7214/sudokuy.jpg(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

Mon May 25, 2009 10:04 pm


Re: sudoku

-----------------------------------

There are lots of sites online that have techniques for solving Sudoku puzzles, [url=http://www.sadmansoftware.com/sudoku/solvingtechniques.htm]here's one.

In some cases you really do have to use brute force though. [url=http://www.google.ca/url?sa=t&source=web&ct=res&cd=2&url=http%3A%2F%2Fwww-cs-faculty.stanford.edu%2F~knuth%2Fpapers%2Fdancing-color.ps.gz&ei=RlobSvurIIK8M_ffrJsP&usg=AFQjCNEc-tWUOdj5in3D3bt0ct-10zw2GQ&sig2=zvqrAISVGfR-AAMiSMiLbg]Smart brute force though.

I'll attach an implementation sometime soon.

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


-----------------------------------

leafs23

Sat May 30, 2009 4:30 pm


RE:sudoku

-----------------------------------

search sudokus on google


-----------------------------------

saltpro15

Sat May 30, 2009 5:39 pm


RE:sudoku

-----------------------------------

wow, having flashbacks to ECOO finals, anyone else?


-----------------------------------

bbi5291

Sat May 30, 2009 6:24 pm


Re: sudoku

-----------------------------------

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


-----------------------------------

saltpro15

Sat May 30, 2009 6:45 pm


RE:sudoku

-----------------------------------

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