Math Is Fun Forum / Post a reply

You are not logged in.

Index
» Coder's Corner
» Suduku solver

Post a reply

Go back

Write your message and submit

Name

E-mail

Enter Answer:

Message

[quote=phrontister]Hi hammana,

Nice program! :up

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:

[hide=Altered version][code]    mainwin 29 35

prompt "Type (or Ctrl+v) string into box" + chr$(13) + "Use non-numeric characters for blanks";grid$

StartTime = Time$("ms")

dim v1(81) 'valeur des cellules
    dim tbv(81,10)

Rem  ----------Get cell values & print unsolved puzzle

print "Starting grid:"
    for i = 1 to 81
        v1(i) = val(mid$(grid$,i,1))
    next i
    gosub [grid]
    print "Please wait: solving...":print

Rem  ----------Initializing table tbv

on error goto [whoops]

for r=1 to 81

l1=int((r+8)/9): c1=r-9*(l1-1)
        l2=int((l1-1)/3)*3+1: c2=int((c1-1)/3)*3 + 1
        if v1(r)>0 then
            tbv(r,10)=10
            For c=1 To 9
                if tbv(c+9*(l1-1),v1(r))=0 then tbv(c+9*(l1-1),v1(r))=r
            Next c
            For l=1 To 9
                if tbv(c1+9*(l-1),v1(r))=0 then tbv(c1+9*(l-1),v1(r))=r
            Next l
            For l=l2 To l2+2
                For c=c2 To c2+2
                    if tbv(c+9*(l-1),v1(r))=0 then tbv(c+9*(l-1),v1(r))=r
                next c
            Next l
        end if
    next r
    Rem  ----------------  -------- RMAX
    r=81
    while tbv(r,10)=10
        r=r-1
    wend
    rmax=r

Rem ------------  Starting
    r=1

[start]
    if r<rmax then
        do while tbv(r,10)=10
        r=r+1
        loop
        v=1
        do until tbv(r,v)=0
        v=v+1
        loop

[blocking]
        call block r,v
        REM -----------------------blocking test
        for i=r+1 to rmax
            do while tbv(i,10)=10
            i=i+1
            loop
            fl=0
            for j=1 to 9
                if tbv(i,j)=0 then fl=1
            next j
            if fl=0 then exit for
        next i
        if fl=1 then  r=r+1 :goto [start]

[unblocking]
        call unblock r,v
        fb=0
        for i=v+1 to 9
            if tbv(r,i)=0 then v=i:fb=1:exit for
        next i
        if fb=1 then goto [blocking]'-----------------
        if r=rmin then print "end of program",c:stop
        r=r-1
        while tbv(r,10)=10
            r=r-1
        wend
        v=1
        do until tbv(r,v)=r
        v=v+1
        loop
        goto [unblocking]
    else
        for v=1 to 9
            if tbv(rmax,v)=0 then tbv(rmax,v)=rmax
        next v
        gosub [solution]
    end if

[finish]
    EndTime = Time$("ms")
    Print "Done in ";(EndTime - StartTime) / 1000;" seconds"
    stop

REM  ------------------Visualize tbv()
sub tbv1
    for i=1 to 81
        print i;" ";
        for j=1 to 10
            a$=str$(tbv(i,j))+"       "
            print left$(a$,6);
        next j
        print
    next i
    stop
end sub
Rem    --------------BLOCKING
sub block r, v
    l1=int((r+8)/9): c1=r-9*(l1-1)
    l2=int((l1-1)/3)*3+1: c2=int((c1-1)/3)*3 + 1
    For c=1 To 9
        if tbv(c+9*(l1-1),v)=0 then tbv(c+9*(l1-1),v)=r
    Next c

For l=1 To 9
        if tbv(c1+9*(l-1),v)=0 then tbv(c1+9*(l-1),v)=r
    Next l

For l=l2 To l2+2
        For c=c2 To c2+2
            if  tbv(c+9*(l-1),v)=0 then tbv(c+9*(l-1),v)=r
        next c
    Next l
end sub
Rem  -------------------UNBLOCKING
sub unblock r, v
    l1=int((r+8)/9): c1=r-9*(l1-1)
    l2=int((l1-1)/3)*3+1: c2=int((c1-1)/3)*3 + 1

For c=1 To 9
        if tbv(c+9*(l1-1),v)=r then tbv(c+9*(l1-1),v)=0
    Next c

For l=1 To 9
        if tbv(c1+9*(l-1),v)=r then tbv(c1+9*(l-1),v)=0
    Next l

For l=l2 To l2+2
        For c=c2 To c2+2
            if  tbv(c+9*(l-1),v)=r then tbv(c+9*(l-1),v)=0
        next c
    Next l
end sub
REM  -------------- Printing GRID

[solution]
    print "Solution:"
    grid$=""
    for i=1 to 81
        for j=1 to 9
            if tbv(i,j)=i then grid$=grid$+str$(j)
        next j
    next i

[grid]
    for row = 0 to 8
        if row mod 3=0 then print "+-------+-------+-------+"
        first = 1+row*9
        last = first+8
        for cell = first to last
            if (cell-1) mod 3=0 then print "| ";
            print mid$(grid$,cell,1);" ";
        next cell
        print "|"
    next row
    print "+-------+-------+-------+":print
    return

[whoops]
    print "No solution":print
    goto [finish][/code]
[/hide][/quote]

BBCode: on
[img] tag: on
Smilies: on

Options

Never show smilies as icons for this post

Go back

Topic review (newest first)

phrontister: 2012-04-27 02:20:29

hammana wrote:
In fact it took me 9 hours to solve it, but the same grid rotated 90 degrees is solved in 18 minutes.

In which direction was your rotation?

My computer took 12.75 hours to solve the unrotated version.

I tried to see if the compiled version runs faster, but the .exe file i obtain does not work.

I ran this puzzle in the LibertyBASIC Booster compiler, with the following times:

Unrotated: 115 minutes;
90° clockwise rotation: 89 minutes;
180° rotation: 82 seconds;
90° anticlockwise rotation: 226 seconds

I also tried the puzzle (unrotated) using fqvarfort's solver that I mentioned in post #27, and got these times:

LibertyBASIC: 145 minutes;
LibertyBASIC Booster compiler: 68 minutes

I had a bit of spare time and played around with the idea of incorporating a grid rotation option into my amended version of your program. Here's the result, which seems to work ok, both in LB and the LBB compiler:

Here's the string I used for the puzzle input:

..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9

phrontister: 2012-04-15 01:37:22

Hi hammana,

I changed the code in my post #3 to add box borders to your program's output for both the starting grid and the solution.

I also included an error trap to print "No solution" if none found (eg, for puzzles incorrectly entered).

phrontister: 2012-04-14 03:16:36

Hi hammana,

Thanks for that Wiki link. I didn't try to follow what they said there because I'm not really into sudokus anymore, but out of curiosity I ran the four 'hardest sudokus' in your program, and it solved them all.

Solution times:
Discrepancy: 282 seconds
golden nugget: 283 seconds
Red_Dwarf: 124 seconds
coloin: 2 seconds

Here is a link to a solver discussion on a JustBasic forum (JustBasic is the freeware version of LibertyBasic).

I ran fqvarfort's solver, and got these times, which are about an eighth of yours:

Discrepancy: 38 seconds
golden nugget: 36 seconds
Red_Dwarf: 16 seconds
coloin: 0.3 seconds

I didn't compare the coding of the two programs, but you might find it interesting.

I also ran purecardmagic's GUI that incorporates fqvarfort's solver. It requires typing the initial puzzle cells into a typical sudoku-style grid, and it works well, but I prefer single-string entry for actions such as copy/pasting puzzles from other software and repeat puzzle entry.

fqvarfort's solver requires hard coding each puzzle into the program, doesn't display the original puzzle and outputs the solution as a string...and so I changed the code like I did yours.

An innovative freeware program I have is SudokuSusser, which is a very strong solver and good tutor. It supports image entry, whereby you can simply copy/paste a puzzle graphic from a website or your computer and run it in SS. Unfortunately it seems to be no longer supported, and it may be difficult to find a download for it.

I tried to see if the compiled version runs faster, but the .exe file i obtain does not work.

What compiler did you use? The only one I found that is specifically for LB is GLBCC - program and docs at lbpp.sourceforge.net/ - but I can't get it to work on my computer (Windows XP).

hammana: 2012-04-13 21:16:49

Hi phrontister

http://en.wikipedia.org/wiki/Sudoku_algorithms

The above site discusses the various algorithms to solve Sudoku. I learned that I am using the "Brute Force Algorithm" which is the least elegant one. The site gives the worst case grid to show the disadvantage of this algorithm. In fact it ooks me 9 hours to solve it, but the same grid rotated 90 degrees is solved in 18 minutes. I tried tho see if the compiled version runs faster, but the .exe file i obtain does not work.

bobbym: 2012-04-12 17:41:58

Hi phrontister;

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

phrontister: 2012-04-12 14: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-12 11:38:35

Hi phrontister;

Is your solver handwritten?

phrontister: 2012-04-12 11: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...

bobbym: 2012-04-12 05:57:55

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

anonimnystefy: 2012-04-12 05:55:54

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

bobbym: 2012-04-12 05: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-12 05:44:49

How much is it for students?

bobbym: 2012-04-12 05:38:07

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

anonimnystefy: 2012-04-12 05:37:06

How much did it cost?

bobbym: 2012-04-12 05:11:40

Yes, I have it.

Ads

Menu

Post a reply

Topic review (newest first)

hammana wrote:

Board footer

Login

Ads

Menu

Post a reply

Topic review (newest first)

hammana wrote:

Board footer