Qbasicnews.com
May 29, 2020, 03:14:13 AM
 Pages: 1 [2] 3
 Author Topic: Make a solver for Su Doku in freebasic.  (Read 21711 times)
Agamemnus
x/ \z

Posts: 3491

 « Reply #15 on: January 21, 2006, 12:17:45 PM »

Gotta start somewhere.  :king:

Now try to implement a decision tree...
 Logged

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.
yetifoot
Ancient Guru

Posts: 575

 « Reply #16 on: January 22, 2006, 12:15:20 PM »

could you explain a little of the theory behind your method agamenmnus? i've been working on a more effective method than the random one i posted, but it has seemed to get too complex so i'm sure i must be doing something wrong.
 Logged

EVEN MEN OF STEEL RUST.
Xerol
Member

Posts: 30

 « Reply #17 on: January 22, 2006, 06:04:51 PM »

I've been meaning to write one eventually, but here's the general idea I had:

1) Check all cells for "possible numbers". So take every non-filled cell. Check the row, column, and box for placed numbers, and eliminate those. If there's only 1 number left, it has to go in there.
2) Check each row for each number - if only 1 box can have a number, it has to go there.
3) Repeat #2 for each column & box.

Every time a number is found, start over from the beginning(for speed - usually filling a cell allows another cell to be filled easily, and step 1 is the "quickest" one to check).

I'm pretty sure all properly constructed sudokus can be solved this way. However, lately I've been seeing some that haven't "met the rules" and require a guess at some point or another(a properly constructed one should never require a guess).
 Logged

url=http://www.lggaming.com/user/xerol/songs/recycled][size=24]Recycled CompoST[/size][/url] - Best of 2005 Album by Xerol.
Agamemnus
x/ \z

Posts: 3491

 « Reply #18 on: January 23, 2006, 11:56:36 AM »

Right, you must consider how to structure your tree such that the decisions that it makes are reversible (so you don't get stuck) in all cases, and that it fully implements the rules of the game in the decision.

A basic decision tree is as follows:

1) Considering the rules of the game, determine all the possible moves that you can make in time t. (t would be the smallest decision you can make: in this case, placing a number on a sudoku matrix) Note the number of moves you can make c. In this case your move amount is stored in, for instance, possible%(t).

2) Make your move, starting with the Nth decision (out of c decisions in the time frame). N is initially equal to 0. (Just set your array for decisions, decision%(t) to all 0's before starting the search...) Add one to decision%(t) to record this and set t = t + 1.

2b) Before you actually do anything in 2, if you are already at your maximum amount of moves (you've tried the last move already), you must set t = t - 1.

3) Update your Sudoku matrix (or game information) to reflect the new move.

4) Check if you have reached your goal. If you have, end. If you haven't, go back to (1).

The only problems with this method in solving a problem are:
1) It may take a long time to loop through all the possibilities. You can use a smarter move making decision function to narrow the possibilities. (less moves per round = faster solution)
2) For this to finish in a finite amount of time (ie: so it isn't an infinite loop), each set of choices you make must be determined in the same order as any other choice. And also the choices cannot be such that you encounter the same set in two decision trees, otherwise you will start looping. (Consider adding a function to remove a piece instead of adding it -- you will get a constant loop)

I hope this helps a bit.
 Logged

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.
yetifoot
Ancient Guru

Posts: 575

 « Reply #19 on: January 23, 2006, 11:56:49 AM »

thanks xerol but i've got that far.  pure logic is used mainly on beginner and intermediate sudokus.  Advanced sudokus however force the player to use an extra level or two of imagination, which means a different method is needed.

here's an example of an advanced puzzle.

{ _
0, 0, 5,  0, 8, 0,  0, 0, 7, _
0, 8, 7,  0, 0, 0,  0, 0, 0, _
9, 0, 2,  1, 0, 0,  0, 8, 0, _
_
0, 0, 9,  0, 0, 4,  8, 1, 0, _
0, 2, 6,  8, 9, 0,  0, 0, 0, _
8, 0, 3,  0, 0, 0,  6, 7, 9, _
_
0, 0, 4,  7, 1, 8,  2, 9, 0, _
0, 0, 8,  0, 0, 0,  7, 0, 1, _
0, 0, 1,  3, 0, 0,  4, 6, 8  _
}

There will come points in this puzzle where a number could be valid in two or more positions, and that is the part i am having trouble with.  This is valid in sudoku and is kind of the whole point because it stretchs your brain, testing possibilities.

Agamemnus:  i made a recursive tree version, but it seems to be slower than my random version, so i must be doing something wrong.
 Logged

EVEN MEN OF STEEL RUST.
yetifoot
Ancient Guru

Posts: 575

 « Reply #20 on: January 23, 2006, 12:59:07 PM »

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.
 Logged

EVEN MEN OF STEEL RUST.
Xerol
Member

Posts: 30

 « Reply #21 on: January 23, 2006, 07:59:47 PM »

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.
 Logged

url=http://www.lggaming.com/user/xerol/songs/recycled][size=24]Recycled CompoST[/size][/url] - Best of 2005 Album by Xerol.
yetifoot
Ancient Guru

Posts: 575

 « Reply #22 on: January 24, 2006, 02:37:56 AM »

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.
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #23 on: January 25, 2006, 11:15:32 PM »

Quote from: "Xerol"
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.
 Logged

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.
yetifoot
Ancient Guru

Posts: 575

 « Reply #24 on: January 26, 2006, 06:43:18 AM »

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.
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #25 on: January 29, 2006, 01:41:50 AM »

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....
 Logged

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.
yetifoot
Ancient Guru

Posts: 575

 « Reply #26 on: January 29, 2006, 08:26:54 AM »

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?
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #27 on: January 29, 2006, 08:54:33 PM »

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:
 Logged

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.
yetifoot
Ancient Guru

Posts: 575

 « Reply #28 on: January 29, 2006, 11:48:22 PM »

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.

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/~knuth/preprints.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.
 Logged

EVEN MEN OF STEEL RUST.
Agamemnus
x/ \z

Posts: 3491

 « Reply #29 on: January 30, 2006, 07:39:49 PM »

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..
 Logged

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.
 Pages: 1 [2] 3