I'm just now coding a Sudoku solver, in BASIC. This is the info I used (after much work because I'd never messed with Sudoku before), to code my program.
It's not nearly as small as the one posted above, but it uses a virtual "odometer" at the end for any trial and error that's needed - so I enjoy it. This is the whole info and description: This is my standard sized Sudoku puzzles algo/program summary. Box refers to any of the smaller box of 9 squares which are contained within the larger puzzle. Peer's are other squares which must be scanned. It might be other squares on the same row in one case, or other squares in the same column, or the squares within the same box. Unit refers to either a row, column, or box, depending on context. == Start == Working the "Possibles": 1. Assign all possible values to an array of possibles to allow record keeping of them, for every square. I use a 2D array for the possibles, and a 2D array also, for the puzzle board. The puzzle board is oriented by row and col, and the possibles array is oriented by square number (11 to 99), and possible value (1 to 9). Row * 10 + column = square number. 2. Remove all possibles for each square which conflict with permanent values in each of the squares' peer's, in each unit (row, column, and box) 3. Upgrade squares with only one value (a solo), into a permanent value. If any solo's are upgraded, return to #2 and repeat it and #3, again. Repeat steps 2 and 3 until no more changes are made in the possibles. Working the "Must Be's": 4. Scan each unit, one at a time, for each value. If the unit has a value located in just one square, then upgrade that possible into a permanent value. This is an example: (from today's newspaper Sudoku) Code: 1 2 3 4 5 6 7 8 9 ============================================= 1347 2 1357 145 1345 45 9 4567 145678 Square #9 on this row has an 8 as a possible, and it's the only square on the entire row that CAN be an eight. So it get's updated to 8, permanently. It is a "must be". Don't forget the column's and box unit's "must be's"! If you have made changes, return to #2, and repeat steps 2 - 4. The Rule of Pairs: There are two rules for pairs, outside and inside. Both are "must be" logic, applied to pairs. An example of outside: Code: 1 2 3 4 5 6 7 8 9 ======================================== 13 2 13 145 1345 45 9 4567 145678 In the row above, square #1 and #3 have a matching pair of possibles. By definition of the game, these two squares can ONLY be either a 1 or a 3, and nothing else. We can't know yet which value will be correct for either square, but it MUST collectively use up the 1 and 3 value for the entire row. So all values of 1 or 3 OUTSIDE the #1 or #3 square, can be eliminated! Square 4 becomes simply "45", etc. My program implements this both as a string of char's, and as just integer values in the possibles array. Both may lead to glazing over of one's eye's, and remembering the pleasantries to be found in daydreams & dozing. The INSIDE rule of pairs removes some possibles from the pairs, themselves: Code: 1 2 3 4 5 6 7 8 9 ============================================== 1347 2 1347 45 456 45 9 4567 145678 Square 1 and 3 have matching pairs of possibles "1347", and the "13" part of their possibles, in unique to those two squares, in this unit. Which means the 4 & 7 values can be removed from the possibles for square #1, and square #3. We don't know (again!), which value will be correct, but it MUST be ONLY a 1 or a 3 for them both. The examples puzzles I've gather so far, don't have a good example of the Inside Rule of Pairs, so my program does not include this logic. The Pairs rules also apply to larger groups of possibles: triples, quads, etc. For any changes, you need to loop back to step #2, and repeat all steps until no more changes are found. This is the great "propagator" in Sudoku, and it happens fast and often. You don't need to repeat the steps after every change, but you need to repeat all the steps above your own, for any steps listed above which make a change in the possibles. There's no need to keep any index or record of what changes you've made, etc. Just give it access to the possibles array and let it run. Trial and Error Substitution: Tough Sudoku puzzles can't be solved by mere logical inferences. (Although they do a huge amount of the work in eliminating possibles.) Intelligent trial and error will be needed. I don't use this (yet), but I certainly believe it's the best way to handle T & E. I call it the "Magic Touch": Code: 1 2 3 4 5 6 7 8 9 ============================================= 1347 2 1357 145 1345 45 9 4567 145678 Imagine this unit is being looked over for a t&e. Would it be "magical"? Yep! Square #6 has only two possibles: 4 and 5. Permanent values such as square #7 will give us nothing here, but square #6 has a 50% chance of being right. Save the current board position/possibles arrays, and make square 6 into a 4. Send it back to Step #2 and above, letting the values found, propagate throughout the board. It's rather amazing how it does it! Now see if the puzzle is solved. No? Then restore the possibles and problem arrays, and try the value 5 in square 6, and send it to Step #2, etc. You may need to try several combinations of these "magical" squares for before you find the correct solution, but just keep track of where you are in the t&e searching, and remember that one of them MUST be right. (or the puzzle has no solution or your program has an error). In my program I used an "odometer" approach to this phase. Imagine the squares of the puzzle all stretched out in a straight line, horizontal. Each square as a "wheel" with a guessed (or actual) value. Squares with a permanent values are "jumped over" in any incrementing of values. Showing this for one row: Code: 1 2 3 4 5 6 7 8 9 ========================================= 13 2 37 145 345 456 9 67 78 A small while loop through the possibles arrays for each square finds the next number for each square to be tried. If it fails when tested for the current row, another increment is made to the smallest, rightmost "wheel", and repeats. My "odometer" would try: 1 2 3 1 3 4 9 6 7 'initial low values 1 2 3 1 3 4 9 6 8 'increment right-most wheel (the driver) 1 2 3 1 3 4 9 7 7 'increment wheel #8, reset driver wheel 1 2 3 1 3 4 9 7 8 'increment driver wheel 1 2 3 1 3 5 9 6 7 'update sqr #6, reset #7 and driver wheel As you can see, this is all "stupid", because wheel #4 is a repeat of #1, an obvious non-solution. So I dutifully wrote a function to supply only valid possible numbers to the odometer. But the smart way, was slower than the "stupid" way. Now I let the virtual odometer make it's own errors, and quickly increment the driver "wheel" value, again. Eventually finding: 1 2 3 4 5 6 9 7 8 as the first solution If the smallest wheel increments through all it's possibles, then it moves the incrementor over to the wheel to it's left, and increments that wheel to the next possible value. Then it returns to the rightmost wheel, which has been set for it's smallest possible value. When a solution is found for all the rows requested, it may stop, or it can be set to continue throughout the entire search space (which is until the incrementor control reaches the "zero" column (I use only the 1 - 9 array subscripts in this program). In the latter case, it will find all the possible solutions to the puzzle. Imagine an odometer of a car, attached directly to an incredibly fast high-speed, motor (the cpu). This is simply the virtual representation of that odometer, at high speed. If you want it to handle multiple rows at a time, it starts with the highest row in the puzzle / possibles array, and works it's way to the lower rows, (toward the higher rows on the screen), by recursively calling itself with a lower row number. It's important to have the columns and boxes tests done ONLY if the preceeding tests have been successful. You have to maximize an odometer's code efficiency. Is it fast? Yes, but ONLY because a HUGE number of possibles have been removed by the above steps. Is it efficient? No. "Magical Touch" is hugely efficient. The "odometer" logic, is just for fun (but it is plenty fast enough, generally). It all depends on how many possibles remain, the efficiency of your code in implementing it, and your hardware. On my laptop with a 950Mhz P3, it's fast enough. If the puzzle doesn't need the "odometer", (trial & error), then it's solved in less than a second. Much less than a second if you limit the amount of info that's printed to the screen. Easy puzzles are done in "zero" time, less than 6/100's of a second, for Windows. If the "odometer" is used, it all depends how many rows you want it to solve for, and how many possibles remain. The search always begins at the lowest possible set of values. Should the answer be found at the extreme high end of the search space, it will use a lot more computation, and a little more time. It's very important that the implementation of the odometer, be streamlined in it's operation. Any wasted code in the inner-most loops, are going to have a big negative impact. Adak P.S. My program is dedicated to Mike Frayer. An exasperating person, but a true friend. Mike died from a very rapid leukemia, as a young man, having never been sick a day in his life with anything more than a flu/cold. Within 24 hours of first seeing a doctor for his "flu", he was brain-dead at Stanford Hospital from the leukemia! If you wanted to talk about computers, current events, programming, or computer games, Mike was your guy. Whatever he lacked in knowledge, he more than made up for with his infectious brand of boundless enthusiasm for these topics. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
