I was thinking about making a little program that would automatically solve the Sudoku puzzles that are cropping up in newspapers these days. http://en.wikipedia.org/wiki/Sudoku
However, it is turning out to be a lot more complicated than I first thought.
The wikipedia article points towards Constraint programming http://en.wikipedia.org/wiki/Constraint_programming but as far as I can see it just appears to be Boolean processing
I have attached my project so far, but I don't think I am going the right way about it.
Anybody got any ideas for this.
Even psuedo code is useful at this point.
Last edited by agmorgan; Jun 6th, 2005 at 10:04 AM.
Reason: Change title to include VB
I haven't really got anything useful for you at the moment I'm afraid (although some of the links at the Wikipedia page have good forums with some code examples).
I just wanted to ask have you got a Sudoko creator? (preferably code) or maybe a link to a decent freeware one?
I haven't really got anything useful for you at the moment I'm afraid (although some of the links at the Wikipedia page have good forums with some code examples).
I just wanted to ask have you got a Sudoko creator? (preferably code) or maybe a link to a decent freeware one?
I haven't really got anything useful for you at the moment I'm afraid (although some of the links at the Wikipedia page have good forums with some code examples).
I just wanted to ask have you got a Sudoko creator? (preferably code) or maybe a link to a decent freeware one?
Hi First of all create a legal Sudoko grid:
1 Create arrayGrid(8,8) to hold the selected numbers
2 Create arrayTemp(8) and put the numbers 1 - 9 in it.
3 Use a random generator to produce a number in the range
r.Next(0,arrayTemp.getUpperBound(0)) (assume 4 is the number)
4 Put the contents of arrayTemp(4) into arrayGrid(0,0)
5 arrayTemp(4) = arrayTemp(5): arrayTemp(5) = arrayTemp(6) etc
6 redim Preserve arraytemp(arraytemp.getUpperbound(0) - 1)
Repeat 3 to 6 until you have the full first row of the grid.
7 Create arraySequence(8) to hold the sequence of numbers in the first row.
8 For x = 0 to 8: arraySequence(x) = arrayGrid(0,x)
9 You can now choose to start the next line with either arraySequence(3) or arraySequence(6)
10 Fill the second and third rows with the exact sequence of numbers as contained in arraySequence()
11 Start the fourth row with arraySequence(1) and then Fill the fourth, fifth and sixth with the exact sequence of numbers as contained in arraySequence()
12 Start the seventh row with arraySequence(2) and continue as per the previous step 11.
You will now have a legitimate grid.
You can mix it up by swaping any rows (or any columns) with any other row (or column) provided they both go through the same miniblock of 9 squares.
You can also mix it up by changing all occurrences of one number with all occurrences of another number.
Now you have your legal grid, you have to decide how difficult to make the puzzle. First of all, to make the solution unique, you HAVE to reveal at least one number in each of 8 rows and 8 columns (in theory you could get away with fewer, depending on the construction of the miniblocks)
That, however, would probably be a very difficult puzzle to solve. If you want to make it easier, make sure that the number of possible selections for at least one of the blank slots is limited to two numbers.
Hope that helps, but I find solving the puzzles very boring. It's far more interesting coding the creation of the puzzle!! I did try using entirely random number generation, but I could never get better than 79 valid numbers - although I could complete some of those grids by looking at them I could not convert that process into coding. The maximum number of consecutive attempts I made was 1,453,000 and that produced 8 grids with 79 valid numbers.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
NotLHk (otherwise known as SomethingElse) has come up with a very good method of designing a grid. It is very nearly random (probably as random as you can get for all practical purposes) and produces a legitimate grid 75% of the time.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Writing a solver is not all that difficult once you know how to do it. I wrote one including a rudimentary GUI in about 4 hours. The actual code in c++ to solve the problem is about 80 lines.
The basic algorthim uses recursion to find the answer. At any point in your search, you will have a partially completed puzzle which you will pass to the next level. You will also want to keep information about candidates for unfilled cells (ie. a candidate for an unfilled cell, is a number that doesn't immediately violate the rules of sodoku ie. the row/column and grid restraints).
As each level of recursion:
choose an empty cell that has the least number of candidates (this will speed up the search). The cell however must have a least one candidate.
If there are no empty cells, the puzzle has been solved. Return some kind of TRUE result.
If there is no cell with candidates, the puzzle is insolvable. Return some kind of FALSE result.
Choose a candidate at random and apply that move. (ie. put the the number in the cell and update your candidates list for cells that are effected by this move)
Use recursion, (ie. call this function back) to solve the resulting puzzle. One of two things will happens with the resulting sub-puzzle.
a) it is solved. In this case the orginal puzzle has been solved
b) it is insolvable. In this case, the cell/candidate pair you chose is wrong. Choose from remaining candidates for the cell and repeat the recursion until you solve the puzzle or you run out of candiates in which case the puzzle is unsolvable.
I wasn't working on a solver, but only a generator.
I managed to get it to make a true Soduko pattern 85 % of the time {About 830 to 865 out of every 1000 attempts}, withoiut recursion on bad "guesses".
My code is propably going to pull a "jack" {think "titanic"}, just drop away in my code archive, fade away to the murky depths of unused oblivion, unless y'all would like to see it?
My code is propably going to pull a "jack" {think "titanic"}, just drop away in my code archive, fade away to the murky depths of unused oblivion, unless y'all would like to see it?
I'd like to have a look
(the generators I've seen so far aren't exactly perfect, knowing how well you deal with these kinds of issues I think yours would be better!)
How long do these solver apps take to solve the average puzzle?
I am writing a solver that uses a more human approach to the problem, thus no timewasting recursion is involved. I have solved loads of sudoku's with a pen and paper (all of them since this thread started actually ) and my brain doesn't use recursion so why should an app?
The way I see it is that there is only ONE solution to any given sudoku, and that the minimum necessary data is given at the beginning. Therefore it must be possible to advance positively towards the goal at every iteration.
Its quite possible to solve a hardcopy sudoku without scribbling out numbers as you go along and correcting your mistakes. This is what I am basing my program on and its coming along quite nicely.
I'm using 2 or 3 'attack' techniques to locate number traps and missing numbers. These attacks can be done in sequential waves, each one complementing the others and hopefully adding a number to the grid after each wave or batch of waves at least.
(At least I'm learning C# at high speed )
This would have made a BRILLIANT topic for a programming contest.
Last edited by wossname; Jul 6th, 2005 at 08:54 AM.
I am writing a solver that uses a more human approach to the problem, thus no timewasting recursion is involved. I have solved loads of sudoku's with a pen and paper (all of them since this thread started actually ) and my brain doesn't use recursion so why should an app?
.
Actually your brain IS using recursion. If you could read the software for your brain you would be amazed how often recursion arises. (By recursion I assume you mean using the same code over and over to examine slightly different data until the desired result is achieved.)
BTW have you tried the Samurai type Su Doku? (Four normal grids each conjoining with a fifth central grid which overlaps each of the other four by one minigrid of 9 numbers)
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
The way I see it is that there is only ONE solution to any given sudoku, and that the minimum necessary data is given at the beginning. Therefore it must be possible to advance positively towards the goal at every iteration.
Actualy, there is usaly about 3 solutions to each puzzle, but it depends howmuch has been filled in.
Actualy, there is usaly about 3 solutions to each puzzle, but it depends howmuch has been filled in.
There are ALWAYS many possible solutions to a grid - unless the following rules are observed when displaying the clue numbers. (Assuming a standard 81 number grid)
1. At least one slot must be declared for 8 out of the 9 rows
2. At least one slot must be declared for 8 out of the 9 columns
3. At least one instance of 8 of the 9 numbers must be declared
If you do this then there is only one possible solution.
If you don't do the above it is always possible to swap one row or column for another which passes through the same minigrids and also to swap any one number for another - even swap ALL the numbers provided each occasion of each number is swapped for the same number.
If you just stick to the above minimum you will have an extremely difficult grid to solve. EDIT. See kafenils' solution. He has made it look easy
Last edited by taxes; Jul 24th, 2005 at 06:12 PM.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Actually your brain IS using recursion. If you could read the software for your brain you would be amazed how often recursion arises. (By recursion I assume you mean using the same code over and over to examine slightly different data until the desired result is achieved.)
Sure but I don't deliberately memorise hundreds of slightly different grids in my mind. My program will not do it either.
Last edited by wossname; Jul 7th, 2005 at 07:56 AM.
Yes. As I said, that would be extremely difficult to solve. You would have to do it by iteration, not reason, but it IS solvable (provided you HAVE selected those numbers from a genuine grid ) And there would be only one solution.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Hi, Actually, from the look of your figures, I suspect that it is NOT from a genuine grid. The following is extracted from a genuine grid and a person with good spatial intellect might spot it quite quickly but you could not solve it logically. So a female or an autistic person might solve it but a University professor in pure mathmetics may never do so. Please excuse my not having an grid image
How are you progressing with your Solver programme? I find it is very difficult to pick up the threads of it when I leave it for a while. I am adopting the same approach as you, trying to translate my spatial approach into code.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
yeh make it a coding contest... its a real huge challenge..sounds easy but its dat hard..lots of maths logic... i suggest two ways.. Brute Forcing or Trying some formula's
I'm game. It's not going to beat me. But I'm not sure if my code will be pretty
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
I gave it a try too in VB6. It is very simple but it does the job. For the moment it is using a kind of brute force strategy, but I am planning to make the routine CreateExecutionPlan a little "smarter" when deciding which pane in the puzzle to start with. Right know it starts in the upper left corner and moves vertically and the horizontally through the panes.
The default values in the sudoku board is an example so you can see how it works.
EDIT: I can't even write Sudoku correct
EDIT: Changed code so that panes with only one possible value is processed in the CreateExecutionPlan routine.
Last edited by kaffenils; Jul 15th, 2005 at 12:56 AM.
Well done. It seems OK. I tried it with different numbers, easy level, and it completed the grid correctly but finished up with a messagebox showing "Error 9 subscript out of range" and then exited the programme.
I'll try it with harder puzzles later.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Well done. It seems OK. I tried it with different numbers, easy level, and it completed the grid correctly but finished up with a messagebox showing "Error 9 subscript out of range" and then exited the programme.
I'll try it with harder puzzles later.
I haven't had much chance to test it, and error handling is (ehmm) non existing. Do you have the numbers that gave subscript out of range?
Edit: I found the problem. It occured when the board was completely solved in the CreateExecutionPlan routine which caused the program to attemt a redim of an array to -1 elements . I uploaded the new files to my previous post.
Last edited by kaffenils; Jul 15th, 2005 at 01:00 AM.
I'd like to have a look
(the generators I've seen so far aren't exactly perfect, knowing how well you deal with these kinds of issues I think yours would be better!)
Well, I ripped apart my 85 %'re, and got rid of some optimizing structures, 'cause I couldn't understand what I was doing, after a few weeks!
Anyways, after rebuilding with less efficient structures, more code, but essentually {I think} doing the same thing, I was able to experiment.
I am now up to an average of 97 % efficiency, in terms of building Soduku patterns, with no look ahead.
Attached you will find my progie, with little or no documentation.
I've stolen a few hours from work, barnstorming the code VIA straight mental coding, with little, if any, pencil pushing.
After 1000 full 3 SQUARE column generations, it builds 974 successful SODUKU patterns. {On a column basis, after 3000 columns, it fails 27, so you could even say it is 99 % effiient}
At least on my last run.
SO... It averages 97 % on a full 9x9 pattern.
If you read the other thread, it hinges on building row assignments first. Thus, every cell, before assigning columns, can be potentially 3 numbers each.
Determining the columns of each number from that point, builds the entire SODUKU pattern.
I've been out, so I'm not much up to documenting anything at this moment.
So, I'll just attach it, and let you ponder WHAT THE HECK DOES THAT DO!!!
-Lou
{Again, Its all Random, after eliminating numbers from cells, after they've been assigned to be in specific cells. If they create an impossabile arrangement, I don't backtrack. Its a failure, and I count it as such. the key area is:
VB Code:
If FIRST_TWO <> "" Then
MyOutStr = FIRST_TWO
Else
If FIRST_THREE <> "" Then
MyOutStr = FIRST_THREE
Else
If FIRST_ONE <> "" Then
MyOutStr = FIRST_ONE
MsgBox("WHAA!!!!")
Else
Exit While
End If
End If
End If
If you interchange FIRST_THREE with FIRST_TWO, it goes from 97 % to 85 %.
So,... Perhaps there's a way to get 100 % efficiency? I've got something in mind, about typifying pairs across rows, but I won't get into that right now.
WHAT IS THAT!!!
WHERE"D OUR SMILEYS GO!!!
OMG!!!
-Lou
{BTW, You might want to remove the ref to PDFLib. I removed my code that used it, but I forgot about actually removing that.}{Oh, and its in VBNet}
Last edited by NotLKH; Jul 22nd, 2005 at 02:58 PM.
I've tested your solution to destruction and it is amazing
It solves puzzles which are completely beyond logical solution. It is twice as quick as my solution, which only works on a logical basis anyway.
It's only failing is that it won't recognise when a solution is impossible and tells you it is completed when there are several blank slots. - try getting it to solve a problem with an illegal number ( e.g. two 8's in the same miniblock or row).
I've looked at your code and can't fathom it - but I never got into VB6 much.
Well done
If anyone doubts my assessment then try filling it in with the numbers 1 to 8 diagonally accross the grid (That is the absolute minimum number of slots you can reveal and still have a unique solution)
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
From the look of it, kaffenils' code is a good start. As far as I can tell, it determines a basic template for each cell by eliminating numbers which are already in the same row / column / SQUARE and then going from there using brute force.
However, there is the prospect for improvement because the point of these puzzles is that at any given time between start and completion, there exists a cell in the puzzle with an absolutely determinable number. The difficulty is that once you're beyond the simple crossreferencing of rows and columns, the rules get harder to apply programatically.
Effectively, from this perspective, there are two different ways to look at the puzzle, which need to be run in parallel.
1) Which number can go in this cell?
2) Given that I have to have the number [2] in this [row / column / SQUARE] where can it go?
All sudoku moves work on this basis - sometimes it is not necessarily obvious what they are though, and may be difficult to program. For example, one common move on the more difficult puzzles is to recognise that a particular number must go in a particular row within a SQUARE by elimination, but without knowing in which cell. The fact of knowing that it is in that row, however, means that a set of possibilities in another SQUARE is eliminated, allowing a different move to be made.
I suspect that setting up code to catch this sort of move for all numbers and all rows / columns / SQUARES is going to be tricky, but without it a fully logical "pseudohuman" solver won't work and you'll have to do the guesswork (brute force) method.
I understand completely what you are saying and that is what I have done im my solution. i.e.
1. Check the numbers one at a time and see if they already exist in a row, column or miniblock. I then mark those numbers as not being able to go in that row, column or miniblock.
2. Check to see if that number has been excluded from 8 of the slots in each row, column or miniblock. If it has, that number must go in the remaining slot.
3. Repeat the above until either 81 slots have been filled or no suitable slots can be found.
The above is exactly what I do when I solve the puzzles manually, but although kafenils' solution does incorporate this, he goes further, but I can't see how. Also his is twice as fast as mine That may, of course, be something to do with his using VB6, but that does not explain how his solution solves seemingly unsolveable puzzles.
kafenils, would you mind explaining your approach, please?
Last edited by taxes; Jul 24th, 2005 at 08:56 PM.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Just a quick note, there is a competition starting soon (in the VBForums Coding Contests forum) for a Sudoku solver, so you may not want to make your methods too public
NotLKH, thanks for that - I haven't had a chance to look yet (no .Net at home ), but I'm sure I'll have fun with it
Hi Wossname, The grid you posted is solved by kafenils' solution in less than half a second!!!!! You can even leave out one of the numbers you entered!!! If you leave out more than one then the result is not a unique grid.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Just a quick note, there is a competition starting soon (in the VBForums Coding Contests forum) for a Sudoku solver, so you may not want to make your methods too public
You're too late. I reckon kafenils has already won it. And he has posted his full code - if you are familiar with VB6
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
we'll have to see about that, I'm sure that people will come up a variety of methods - some of which may be noticably better than those which have been posted already.
(I have already seen one privately which is much faster, but may not be capable of solving the grids above).
[RESOLVED] [VB] Sudoku Solver
Reply With Quote
Originally Posted by si_the_geek
I might start again.
), but I'm sure I'll have fun with it 