You are not logged in.
#1 2012-03-31 23:57:21
- hammana
- Member
Offline
Suduku solver
Hi
Progrmming a Sudoku solver has been a challenge for me. The difficulty was to imagine the appropriate algorithm. I finally wrote the following in LB (Liberty Basic). I found no bug in it so far.
It is based on the following algorithm.
Cells are numbered from left to right, up to down. their number r goes from 1 to 81.
l1, c1 are the line and column of the cell. l2, c2 are the line and column of the upper left cell of the 3x3 square containing the cell r.
the core of the algorithm is the table tbv(81,10). each line correspond to a cell. Columns 1 to 9 indicate the digit allowed for that cell. I+f cell r is allowed the value v, tbv(r,v)=0, otherwise it contains the number of the cell that forbids that value. as explained below)
All possible values are tested for all cells, in ascending order. After assigning a value v to a cell r we should block that value in all empty cells of the same line, column and square, (see sub block). then check that no cell after r is blocked (all values forbidden). Otherwise we should erase everything done (see sub unblock) and test the next value. If we have reached the last possible value for cell r we go back to cell r-1 and repeat the same procedure.
tbv(r,10) is given any number other than zero if r is a cell which has a preassigned value, these lines are always skipped in the process.
If you like to write such program in LB and have any question, do'nt hesitate to call
#2 2012-04-01 00:43:02
- gAr
- Star Member
Offline
Re: Suduku solver
Hi hammana,
Thanks for the code.
"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?
"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."
#3 2012-04-12 03:27:31
- phrontister
- Real Member
Offline
Re: Suduku solver
Hi hammana,
Nice program! 
I ran it in LB, and found no bugs. I tried it on some tough puzzles and it solved them all...usually in under 15 seconds.
I don't know all that much LB, so I'd need to spend a fair bit of time on your code to understand it...maybe one day.
I made some changes to the program that I found to be handy. The main ones are:
1. To avoid typing each puzzle into the program code I included a prompt asking for the user to enter their puzzle, which would take the form of a continuous string of 81 characters: eg,
..........35..82.69.6.2..7...3.81.5...........2.54.1...4..6.7.17.89..42..........
Blanks can be either zeros or full stops (periods). The above puzzle was created by a sudoku generator I have that uses full stops for blanks.
I altered your code a bit to deal with this change (it might be a bit clumsy but it works ok, I think).
2. I specified the output window size to be large enough to avoid scrolling.
3. Timer included...solution time on my PC for the above puzzle is about 10 seconds.
4. Included box borders.
Here's my code:
Last edited by phrontister (2012-04-15 21:38:22)
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#4 2012-04-12 03:30:04
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
Hi phro
Stay online! I need to ask you something! 
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#5 2012-04-12 03:34:03
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
Hi phro
Could you help me make a Sudoku solver in Pascal.
If not then I would like to learn to do it at least in Maxima.
What do you say?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#6 2012-04-12 04:04:14
- phrontister
- Real Member
Offline
Re: Suduku solver
Hi anonimnystefy,
I'm sorry, but the only programming language I 'know' is BASIC...and it's really only enough to have a bit of fun with for helping me to solve some maths puzzles...plus a few other bits and pieces.
When get time to have a better look at hammana's code - which I'm looking forward to doing - I'll know more, but still only in BASIC.
I don't know Maxima at all.
Some time down the track I'd like to learn some Python, but I can't see me ever progressing past the dabbling stage with any programming language.
That's all I need to stay happy enough. It's only a hobby - one that I enjoy - but life's far too busy for me to be able to devote the necessary time to learn much more.
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#7 2012-04-12 04:07:37
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
Oh,ok.Nevermind then.
How good are you in BASIC?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#8 2012-04-12 04:31:41
- phrontister
- Real Member
Offline
Re: Suduku solver
I'm really just a self-confessed occasional dabbler who'll never make the grade beyond the 'know-enough-to-get-by' level. I'm purely self-taught and have never tried to learn how to write efficient code.
I don't program enough to remember how to do what from one task to another, and when there's a new challenge I always have to give myself a refresher course and look up previous stuff I've done to get clued up again. Occasionally I learn something new, but the journey is slow.
When I get the opportunity to have a go at using BASIC to solve a puzzle I quite enjoy it, but my lack of knowledge holds me back...as I'm sure BASIC's limitations do too, which is why I'd like to try another language some time.
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#9 2012-04-12 04:33:13
- bobbym
- Administrator
Online
Re: Suduku solver
When I get the opportunity to have a go at using BASIC to solve a puzzle I quite enjoy it, but my lack of knowledge holds me back...as I'm sure BASIC's limitations do too, which is why I'd like to try another language some time.
I will teach you M whenever you say the word.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#10 2012-04-12 04:38:42
- phrontister
- Real Member
Offline
Re: Suduku solver
Thanks, Bobby, I know your offer has always been there and I'm sure that one day I'll want to move on from where I am with this. You'll be the first one I'll ask.
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#11 2012-04-12 04:39:43
- bobbym
- Administrator
Online
Re: Suduku solver
Most of these silly problems I pose are one liners in M!
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#12 2012-04-12 04:44:34
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
hi bobbym
What is M?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#13 2012-04-12 04:45:52
- bobbym
- Administrator
Online
Re: Suduku solver
Mathematica.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#14 2012-04-12 04:49:34
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
Aham...okay.
Do you have Mathematica?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#15 2012-04-12 05:11:40
- bobbym
- Administrator
Online
Re: Suduku solver
Yes, I have it.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#16 2012-04-12 05:37:06
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
How much did it cost?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#17 2012-04-12 05:38:07
- bobbym
- Administrator
Online
Re: Suduku solver
149 dollars back then. It is much cheaper now, especially for students.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#18 2012-04-12 05:44:49
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
How much is it for students?
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#19 2012-04-12 05:48:32
- bobbym
- Administrator
Online
Re: Suduku solver
Last time I saw it at 49 bucks american. But the prices change and may be different elsewhere. Your professor should know more about it than I do. Most college kids get it for nothing at school and then sort of take it home with them.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#20 2012-04-12 05:55:54
- anonimnystefy
- Real Member
Offline
Re: Suduku solver
I will see if the my school has Mathematica or any other useful math package.
The limit operator is just an excuse for doing something you know you can't.
“It's the subject that nobody knows anything about that we can all talk about!” ― Richard Feynman
“A secret's worth depends on the people from whom it must be kept.” ― Carlos Ruiz Zafón
#21 2012-04-12 05:57:55
- bobbym
- Administrator
Online
Re: Suduku solver
Ask around someone will provide you with a lot of help.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#22 2012-04-12 11:17:21
- phrontister
- Real Member
Offline
Re: Suduku solver
Hi hammana,
I ran my sudoku generator overnight to give it a good amount of time to come up with a more difficult puzzle than the ones I've been testing your solver with, and this was the one it rated as the hardest it found:
6.....9.......7.18.7.5....6..798..3...........9..732..3....2.8.94.7.......6.....3
It took the solver nearly 7 minutes. That is quite a different result from the other tests, none of which went over 20 seconds.
I tested it in your original version and my altered one, with similar results.
I have several freeware solvers, and all of them found the solution pretty much instantaneously. Same with two online solvers I tried it on.
Interesting... 
Last edited by phrontister (2012-04-12 14:03:55)
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#23 2012-04-12 11:38:35
- bobbym
- Administrator
Online
Re: Suduku solver
Hi phrontister;
Is your solver handwritten?
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.
#24 2012-04-12 14:21:32
- phrontister
- Real Member
Offline
Re: Suduku solver
Hi Bobby,
Do you mean the generator? The solver is hammana's. Anyway, I haven't written either.
The generator is one written by Henk Westhuis. It's called IntoSudoku, and I own a registered version of the software. It's a solver too, plus being a good teaching aid and worksheet.
When sudokus were all the rage I learnt some of the complex patterns so I could solve the diabolicals, but they bored me after a while and I've now lost interest in them. Scanning, scanning, scanning and more scanning of candidates... 
I haven't done a sudoku for ages.
"The good news about computers is that they do what you tell them to do. The bad news is that they do what you tell them to do." - Ted Nelson
#25 2012-04-12 17:41:58
- bobbym
- Administrator
Online
Re: Suduku solver
Hi phrontister;
Okay, I was just wondering whether you would show the code if you had written it.
In mathematics, you don't understand things. You just get used to them.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.