Adak

This is my standard 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)

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:

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:


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

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:

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.

DaWei

How does your Magical Odometer differ from the run-of-the-mill nested loop? Just curious.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Adak

"Magic" is part of the "magical touch", which was described, but my program doesn't use that logic.

I believe "normal" sudoku logic would work across the puzzle squares, testing the next proposed number for *a* square, then move to the next square and repeat this, for all squares. It's square-oriented.

The odometer does it differently. It puts out the lowest possible values into the complete row, and then increments the right-most squares's value as high as it will go, testing the entire row each time it increments the single square.

Then it moves the incrementor over one square to the left, and increments it one time, and moves it back to the right-most square and repeats the increment and test, cycle. It's row-oriented, not square-oriented.

It dosn't need nested loops, it has "wheels"!

Adak

DaWei

No nested loops?

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Adak

When you see the green smiley, and he's grinning large - I might just be joking a bit.

In this case, quite a bit.

When you have to traverse arrays, loops are the ticket.

The "odometer" thing goes back to a program that Mike Frayer was trying to make up - a space travel game, etc. He needed a gauge to continually show the spacecraft's distance from Earth in millions of kilometers. So I integrated an "odometer" into his game for him.

He was delighted with it. After that, whenever he needed some gizmo or other for one of his programs, he'd solicit my help.

That's why I wanted to add an odometer to this program. It's not as efficient as just plain nested loops, working from square to square. More fun, if you like odometers, though. (But neither of those is as efficient as using Knuth's "Algorithm X" (aka "Dancing Links"), either.

As long as you have the possible values for the squares cut way down, they're all fast enough. It's a puzzle, we're not programming rockets, here.

Adak