sodoku solving program

[_player1537]

I am wanting to make a program that solves sodokus, but I don't know where to start (aside from the input of a sodoku, which I will work on later). What would be a good equation to put the correct numbers in the correct spots. I was thinking maybe make it figure out where a number could not go and then put in what's left, ie start with numbers 1-9 and check each row for numbers and get rid of that number in the list. Does that make sense and if it does would it work?
_________________
there are three kinds of people in this world, those who can count and those who can't.
there are 10 types of people in this world, those who understand binary and those who don't.




-Player

[KermMartian]

The simplest Sudoku solves does no look-ahead/guessing. In other words, it searches each 3x3 square, and for each of the nine digits, checks if there's only one spot in that square where it can go. If so, it places it. It makes enough passes over the board to solve it completely. However, this can fail in some boards where you may need to do guessing and checking to properly solve the game. I think Tari may have made a solver (and others, since we had a Sudoku contest) somewhere.
_________________

[_player1537]

thank you, I will try to work on one tonight. What do you think I should use to hold the sodoku problem while it is solving, a matrix or a string or list?
_________________
there are three kinds of people in this world, those who can count and those who can't.
there are 10 types of people in this world, those who understand binary and those who don't.




-Player

[KermMartian]

Even though it's large, a matrix will be your best bet as far as simplicity of addressing. Strings would be more efficient, but I bet the code to extract and insert digits would far defeat the efficiency in size of the data storage itself.
_________________

[_player1537]

[rthprog]

[KermMartian]

rthprog understood me perfectly. This solution method is basically the same thing you do with your brain when you solve a sudoku puzzle. You look at each empty spot inside a given 3x3 square. As you know, each 3x3 square can contain only one each of digits 1-9. Therefore, each empty spot can only be whatever digits have no been used yet in that 3x3 square, which will have the same cardinality as the number of empty spots in the square. Next, you check the 1x9 row and the 9x1 column that contain the given spot, for each of the digits that remain in the 3x3 square, and if that digit is already somewhere in the row or column, it can't be in the given spot. If, after checking all possible digits for that spot, only one is not illegal, then that's the right answer, and you substitute that digit in that spot. Voila!
_________________

[rthprog]

...I'm wondering if it might possible to describe a sudoku problem as a (rather long) series of equations, and then use matrices to solve for the unknowns... the matrice would probably be too large to fit in ram, but if it indeed worked, it could be a significantly faster alternative to the method already described.

[Komak57]

Although you might think it much, it would probably be good for you to design a sudoku app in order to understand how it works. Until then, heres some info that might come in handy.

To start, easy sudoku puzzles are easy to solve, as they have some plain-and-simple locations that you dont have to guess. harder sudoku puzzles give you half of those digits, so its mostly a guessing game. Technically speaking, you dont have to solve the entire sudoku puzzle to get your results. Only the center and corner pieces are mandatory. Less so the center. Solving 3/4 of the corner pieces will essentially have solved the puzzle. Simply design a randomiser to guess at the combination of 3 corners, and then to fill in the remaining pieces and check if its correct, on failure, try again.

examples...
Easy sudoku

expert...

you should first have it register the rows and collums each unchangable number is limited from.

1)Filling in the first square numerically would give you a limitation sequence like this...
(1,1: 8) (1,2: 6) (1,3: 1,3,4,6,9)
(2,1: 1,2,3,4,6,8) (2,2: 1,3,8) (2,3: 1,2,3,4,6,8,9)
(3,1: 1,2,3,4,5,6,7,9) (3,2: 1,3,5,7,8,9) (3,3: 1,2,3,4,6,8,9)
2)next it would clear all stationary numbers from the list.. in this case 8 and 6
(1,1: 8) (1,2: 6) (1,3: 1,3,4,9)
(2,1: 1,2,3,4) (2,2: 1,3) (2,3: 1,2,3,4,9)
(3,1: 1,2,3,4,5,7,9) (3,2: 1,3,5,7,9) (3,3: 1,2,3,4,9)
3)now it generates any numbers that cant fit elsewhere
86?,???,???
4)then fills in digits in numerical order in all possible combinations
1: 861,234,579
2: 863,214,579
3: 864,231,579
for smaller explanation, ill keep the solutions to 3... btw, 2 cannot be replaced by 1 in 1,3...

Next corner
keep in mind, this will only read numbers already provided
step1)
(1,1: 1,2,3,4,5,7,9) (1,2: 1,2,3,4,7,9) (1,3: 1,2,3,4,5)
(2,1: 1,2,3,4,7) (2,2: 5) (2,3: 9)
(3,1: 1,2,3,4,5,7,9) (3,2: 1,2,3,4,6,7,8,9) (3,3: 1,2,3,4,5,6,8)
step2)
(1,1: 1,2,3,4,7) (1,2: 1,2,3,4,7) (1,3: 1,2,3,4)
(2,1: 1,2,3,4,7) (2,2: 5) (2,3: 9)
(3,1: 1,2,3,4,7) (3,2: 1,2,3,4,6,7,8) (3,3: 1,2,3,4,6,8)
step3)
???,?59,???
step4)
1: 123,459,768
2: 213,459,768
3: 321,459,768

after you get all 4 corners done (though you could do this for all 9 squares) you can do 2 things. 1, try to fit combination block 1,1:1 (top left combo 1) with 1,2:1 (top middle combo 1) and cycle through till one fits, then continue to 3 until it locks up (unable to find a combination, and continue with 1,1:2 until all squares fit, or have it manually continue to do a more complicated version of step 1-4...
for an exampe, combo 1,1:1 doesnt fit with 1,2:1 due to digit 1 being in first slot and would cycle through until 1 wasnt in the first column, and since there are no combinations listed (yeah, i made it smaller on purpose) would try 1,1:2 with 1,2:1... 3 doesnt fit and would eventually lock up because there are no listed combinations... causing it to attempt 1,1:3 with 1,2:1 and 7 (and 9) dont fit... because of the limit of 3 combinations, this example would fail... but continue on, it would eventually come out with the solution.

good luck coding it
_________________
Foxes Rule our World...

Koware Technologies current projects:
[v0.0.2]-DS C++(MapleStory DS)

v[playability].[working functions].[progress 0-9]

[rthprog]

[Komak57]

you might wanna re-check my process... the only way doing a process of elimination would work is if you were playing easy mode... which gives you 2~5 answers to each block... with my provided modification to Kerms method essentially DOES use elimination when and where possible. But again, in expert, you only get about 2 answers per block, and solving it yourself, theres a LOT of guesswork... the only faster way to solving it would be to have every possible configuration listed in an array/matrix and find the one that matches... which would still take forever depending on how far down the list it is...

with the above method, it would only take a few seconds to get all the combinations of 1 block, multiply that by 9, and then account for the cycling of combinations... it would take maybe 5~10 minutes at most. depends on the processor and what language its written in to how fast it really goes... i can immagine with an adequate 2ghz processor and something like C++ or other 'clean' language it would take an average of 2 minutes per expert puzzle
_________________
Foxes Rule our World...

Koware Technologies current projects:
[v0.0.2]-DS C++(MapleStory DS)

v[playability].[working functions].[progress 0-9]

[KermMartian]

Yup, my method does indeed fail on medium or hard puzzles, due to the need to do lookahead guesswork. Very impressive post there, Komak.
_________________

[_player1537]

Thank you Komak, I just have two questions: what does" " mean and how do you define your locations, like if you said (1,2) what point on the sodoku are you talking about? Other than that, I agree, your post was really good

btw, I am programming this on my calculator (ti-84+ silver edition) in Ti-Basic, I will maybe port it to something faster if I make a working version.
_________________
there are three kinds of people in this world, those who can count and those who can't.
there are 10 types of people in this world, those who understand binary and those who don't.




-Player

[rthprog]

[steelersfan1693]

hehehehe

[KermMartian]

[_player1537]

thank you Kerm, I have written the modules that check what numbers have not been used by the 3x3 square and the rows and columns too. Then it checks which numbers match between them all. Finally it checks if any of the numbers match, and if there is only one answer, it places it. should be done soon
_________________
there are three kinds of people in this world, those who can count and those who can't.
there are 10 types of people in this world, those who understand binary and those who don't.




-Player

[Komak57]

Keep in mind that there are multiple possibilities for each block (9 squares per block, 9 blocks per puzzle)... the answer cant be found until you have ruled out more variants in multiple matrices. It may take quite a few matrices to find out the right combination... In my above matrix, you would end up with 9 matrices holding a maximum of 9^9! = 362880 (9^9 = 387420489, permutation (non repeating numbers) = 362880). multiply by 9 means 3265920 total variables will be saved between all 9 matrices.. a TI calculator would be incapable of this formula. this is a maximum though, which ignores the fact that 2 numbers are givin immediately, and more for easier difficulties. I hope your using a 'clean' code, or this will take some time to decipher it.

you can find a lot more math on the subject with some good ol documentation from wikipedia here : http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

I could be a bit more helpful if i knew the base language you were using (basic, C, assembly etc) My programming talent is the ability to translate any code into another code i know.
_________________
Foxes Rule our World...

Koware Technologies current projects:
[v0.0.2]-DS C++(MapleStory DS)

v[playability].[working functions].[progress 0-9]

[_player1537]

ti-basic, I will look at that website in a minute.
_________________
there are three kinds of people in this world, those who can count and those who can't.
there are 10 types of people in this world, those who understand binary and those who don't.




-Player