Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Make a solver for Su Doku in freebasic.
#21
i finally got it working (re-posted above) now i just need to clean it up a bit, and give it a good testing.

have you had any thought on how to check if there is more than one solution? i guess i would just leave it running after it has discovered the solution and see what happens, but i haven't tried it yet.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#22
The way I see it, there's various "depth levels" of logic needed. Quick examples:

Level 0 - It's the only number that can fit in that cell:

Code:
1 2 3
4 6 7
8 X 9

The X has to be 5. This is oversimplified but almost every puzzle has a few of those in it to begin with.

Level 1 - It's the only place in a row, column, or box where that number can go:

Code:
2 7 3 | 1 6 8 | 4 5 X

Once again, oversimplified case but the X has to be a 9.

Level 2 - Indirect elimination of cells.

Code:
1 2 3 | 4 X Y | 5 Z W
5 6 9 | 2 3 7 | 1 4 8
4 7 8 | 1 5 R | 2 3 9

This is really oversimplified but it gets the point across. The 6 in row 1 has to be in Z or W, so it can't be in X or Y. Therefore, R has to be a 6.

It's possible to get even deeper with this, too, but I just got up so I don't feel like coming up with examples.
url=http://www.lggaming.com/user/xerol/songs/recycled]Recycled CompoST[/url] - Best of 2005 Album by Xerol.
Reply
#23
I did some more work on my one (code posted a few threads up)

Now it seems to solve all puzzles, and can determine if it is a fully valid sudoku (having only one valid solution). I've nearly got it working on 4x4 sudokus (Cell Values 0-F) aswell, but havent posted that yet as its even more spaghetti at the moment.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#24
Quote:The way I see it, there's various "depth levels" of logic needed.

Indeed the case I think. It's just a mathematical problem with one extremely efficient yet not obvious solution.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#25
Do you mean Donald Knuths Dancing Links Algorithm? I've been looking into this, but am wondering if i can use it in the case where i want to work out the number of possible solutions? I don't really understand it yet, and on the wikipedia page for DLX it says its a brute force algorithm, so i don't see yet how it will be faster than the brute force system i currently employ.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#26
I don't mean any brute force algorithm. A brute force algorithm, by definition, attempts all paths given the ruleset as a way to create paths. The efficient solution will solve the problem in the smallest amount of steps possible given the current state of the puzzle....
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#27
What is the best way then? is it DLX as mooted by wikipedia?

it says ... is a recursive, nondeterministic, depth-first, brute-force algorithm

If i implement the noted improvement in my code to search for the next cell with the lowest probability, rather than just the next empty cell, surely this would be just as quick?
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#28
Well I think it uses some set of derived constraints based on the rules, while the first brute-force algorithm ignores any logic until it's apparent that a new positioning of a number violates the rules. If my vague understanding of this algorithm is correct, I would not call the "Dancing Links" algorithm a brute force algorithm (even though that's what it says..).

EDIT1:
Quote:What is the best way then? is it DLX as mooted by wikipedia?

Probably.

Quote:If i implement the noted improvement in my code to search for the next cell with the lowest probability, rather than just the next empty cell, surely this would be just as quick?

I have no idea, but make sure to keep the choices always the same on each search level.

EDIT2:
Did you edit your post just now? :???:

EDIT3:
http://spivey.oriel.ox.ac.uk/mike/comp2005/results.html (another link from Wikipedia)
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#29
thanks for the link. Its a shame they dont include the submitted programs, i would of liked to see them.

no i didnt edit my post.

after reading more about dancing links, i think that is bascially what i have coded.

the constraints are checked for, by looking to see whether a number is valid in a given cell. Also i use backtracking, which is where the name 'dancing links' apparently come from. The only part i guess that isnt't DLX is the fact i don't look for the first cell with the least number of possible numbers, but that is something i noted in the code and will be trivial for me to implement.

I would though agree with wiki that it is brute force, as you do have to check every possible combination until you find the result (albeit within the constraints of the game)

EDIT : just found this page which has knuths papers available for d/l

http://www-cs-faculty.stanford.edu/~knut...rints.html

EDIT 2 : reading more about boolean matrix stuff makes me think i'm not doing it that way...

anyhow this puzzle from the page you posted was particually useful to me

Code:
Dim TestBoard01(81) As Integer = _
  { _
    0, 1, 0,  0, 0, 0,  0, 0, 0, _
    0, 2, 0,  0, 0, 0,  0, 0, 0, _
    0, 3, 0,  0, 0, 0,  0, 0, 0, _
  _
    0, 4, 0,  0, 0, 0,  0, 0, 0, _
    0, 5, 0,  0, 0, 0,  0, 0, 0, _
    0, 0, 0,  0, 0, 0,  0, 0, 0, _
  _
    0, 0, 0,  0, 0, 6,  7, 8, 9, _
    0, 0, 0,  0, 0, 0,  0, 0, 0, _
    0, 0, 0,  0, 0, 0,  0, 0, 0  _
  }

my code did not used to look for this kind of problem, so would keep searching until all possibilitys were exhausted.
EVEN MEN OF STEEL RUST.
[Image: chav.gif]
Reply
#30
Well, I dunno. If it (Dancing Links) is brute force, what's the real efficiency/speed difference between Dancing Links and the initial brute force algorithm mentioned earlier?


I'm guessing that the puzzle you posted is an unsolvable one.... I don't see any immediate contradictions... are they there? Anyway, finding out if a puzzle is unsolvable is probably as fast as finding the solution..
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)