Suduku solver

hammana · 2012-03-31 00:57:21

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

gAr · 2012-03-31 01:43:02

Hi hammana,

Thanks for the code.

phrontister · 2012-04-11 05:27:31

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-14 23:38:22)

anonimnystefy · 2012-04-11 05:30:04

Hi phro

Stay online! I need to ask you something!

anonimnystefy · 2012-04-11 05:34:03

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?

phrontister · 2012-04-11 06:04:14

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.

anonimnystefy · 2012-04-11 06:07:37

Oh,ok.Nevermind then.

How good are you in BASIC?

phrontister · 2012-04-11 06:31:41

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.

bobbym · 2012-04-11 06:33:13

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.

phrontister · 2012-04-11 06:38:42

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.

bobbym · 2012-04-11 06:39:43

Most of these silly problems I pose are one liners in M!

anonimnystefy · 2012-04-11 06:44:34

hi bobbym

What is M?

bobbym · 2012-04-11 06:45:52

Mathematica.

anonimnystefy · 2012-04-11 06:49:34

Aham...okay.

Do you have Mathematica?

bobbym · 2012-04-11 07:11:40

Yes, I have it.

anonimnystefy · 2012-04-11 07:37:06

How much did it cost?

bobbym · 2012-04-11 07:38:07

149 dollars back then. It is much cheaper now, especially for students.

anonimnystefy · 2012-04-11 07:44:49

How much is it for students?

bobbym · 2012-04-11 07:48:32

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.

anonimnystefy · 2012-04-11 07:55:54

I will see if the my school has Mathematica or any other useful math package.

bobbym · 2012-04-11 07:57:55

Ask around someone will provide you with a lot of help.

phrontister · 2012-04-11 13:17:21

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-11 16:03:55)

bobbym · 2012-04-11 13:38:35

Hi phrontister;

Is your solver handwritten?

phrontister · 2012-04-11 16:21:32

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.

bobbym · 2012-04-11 19:41:58

Hi phrontister;

Okay, I was just wondering whether you would show the code if you had written it.

Math Is Fun Forum

#1 2012-03-31 00:57:21

Suduku solver

#2 2012-03-31 01:43:02

Re: Suduku solver

#3 2012-04-11 05:27:31

Re: Suduku solver

#4 2012-04-11 05:30:04

Re: Suduku solver

#5 2012-04-11 05:34:03

Re: Suduku solver

#6 2012-04-11 06:04:14

Re: Suduku solver

#7 2012-04-11 06:07:37

Re: Suduku solver

#8 2012-04-11 06:31:41

Re: Suduku solver

#9 2012-04-11 06:33:13

Re: Suduku solver

#10 2012-04-11 06:38:42

Re: Suduku solver

#11 2012-04-11 06:39:43

Re: Suduku solver

#12 2012-04-11 06:44:34

Re: Suduku solver

#13 2012-04-11 06:45:52

Re: Suduku solver

#14 2012-04-11 06:49:34

Re: Suduku solver

#15 2012-04-11 07:11:40

Re: Suduku solver

#16 2012-04-11 07:37:06

Re: Suduku solver

#17 2012-04-11 07:38:07

Re: Suduku solver

#18 2012-04-11 07:44:49

Re: Suduku solver

#19 2012-04-11 07:48:32

Re: Suduku solver

#20 2012-04-11 07:55:54

Re: Suduku solver

#21 2012-04-11 07:57:55

Re: Suduku solver

#22 2012-04-11 13:17:21

Re: Suduku solver

#23 2012-04-11 13:38:35

Re: Suduku solver

#24 2012-04-11 16:21:32

Re: Suduku solver

#25 2012-04-11 19:41:58

Re: Suduku solver

Board footer