PDA

View Full Version : Quickest Sudoku Check

Skott
02-20-2006, 06:11 PM
So, once you've completed a Sudoku puzzle, what's the quickest and/or most effortless way of verifying that you haven't made any mistakes? (Apart, that is, from looking it up in the paper the next day.)

I assume that the longest method would be to actually manually verify that there are no repeating numbers in each column, row, and 3x3 grid (27 set checks of 9 each, or 243 checks). But something tells me there's a quicker way... like only checking 5 3x3 grids and one specific row and column (7 set check of 9 each or 63 checks), for hypothetical example.

ultrafilter
02-20-2006, 06:40 PM
Are you doing this by hand or with a computer?

Here's a decent algorithm that can offer an upper bound for any particular method.

1. Sort each row and check for duplicates. There's a well-known algorithm that does both at the same time. Basically, you move each number into the corresponding slot (so 1 goes into the first slot, 2 the second, 3 the third, etc.). If at any point you find yourself trying to duplicate an entry, you've got duplicates. In the worst case this uses 8 swaps, and there are 9 rows, so you've got 72 swaps.

2. Perform the above operation on each column. Again, 8 swaps per column and 9 columns, so 72 swaps if there are no duplicates in a given column.

3. Lastly, do the same thing with each 3x3 box. Same deal, 8 swaps and 9 boxes, so 72 swaps if there are no dups.

If there are no duplicate, we're using 216 swaps. Each swap is a comparison and an assignment, so you're talking only 532 operations. There are no immediately obvious (to me, at least) shortcuts.

TJdude825
02-20-2006, 06:49 PM
Make up and memorize a color system, such as 1=white, 2=green, 3=blue, etc... and solve by colors instead of numbers, using markers or colored pencils. That should make it easier to check manually afterwards.

What you can do, which may or may not be faster, is count the occurences of each digit. There should be nine 1's, nine 2's, etc. This won't guarantee that you've done everything right, but if you make a mistake, it seems pretty likely that you might have, say, ten 7's and eight 4's.

Skott
02-20-2006, 07:52 PM
Are you doing this by hand or with a computer?
By hand. Say for example, my wife does today's puzzle in the newspaper and hands me the newspaper after she's completed the puzzle and says, "Here, is this right?"

The requirements of the puzzle are that the numbers 1-9 appear in each column, row, and 3x3 square without repeating, so I count the numbers from 1 to 9 in each of them, and assuming there are no repeats, then she's met the requirements and the puzzle is solved. And even though some of the numbers are givens, I still have to check them in order to assure no duplicates of that given.

However, this requires, as I mentioned above, 247 checks. There are only 81 squares though, so I'm obviously checking each square three times. What if I only check the columns, for example, can I be assured that the rows and squares are correct as well? Or if I do two of the three? Or some other combination?

dnooman
02-20-2006, 09:58 PM
If the last number you put in is definitely right, there's almost a 100% chance you did it right. It's all based on deduction. One can't usually make dozens of correct deductions and end up with a wrong answer at the end. I'd say that it's damn near impossible to make a mistake big enough to still make your last number work.

Icarus
02-20-2006, 10:06 PM
my wife ........says, "Here, is this right?"

A wife is ALWAYS right, silly.

CurtC
02-20-2006, 10:13 PM
I agree with dnooman - anytime I've made a mistake, I always learn about it well before I fill in the last cell. If she asks you if it's right, glance at it for a few seconds and say "yes."

N9IWP
02-20-2006, 10:18 PM
I guess I would count that as 27 checks.
I do a row, couning 1, 2, 3 ... 9 making sure each number appears
do that for the other 8 rows (9 checks)
Then to the same for columns (9 checks) and grids (9 checks)

Brian

dtilque
02-21-2006, 12:48 AM
I asked this question once on rec.puzzles. Someone else came up with this shortcut:

First check each of the 9 3x3 boxes. Then check the rows and columns. But you can skip the 3rd, 6th and 9th rows and columns when doing those checks.

jacquilynne
02-21-2006, 08:03 AM
Personally, I solve sudoku in a spreadsheet. I have the spreadsheet set to add up the rows and columns for me, as well as the boxes. When I'm finished, if all of those numbers are 45, it's completed correctly.

02-21-2006, 08:09 AM

CurtC
02-21-2006, 08:51 AM
There's lots of Sudoku programs that you can use to check for mistakes, but they don't help if you're just wanting to do it in the newspaper. There's something more satisfying to me about doing one on a piece of paper than on a computer screen. And it has to be in ink - I think if I did one with a pencil it wouldn't be as satisfying.

Tastes of Chocolate
02-21-2006, 11:30 AM
Personally, I solve sudoku in a spreadsheet. I have the spreadsheet set to add up the rows and columns for me, as well as the boxes. When I'm finished, if all of those numbers are 45, it's completed correctly.

I'd go with a version of this. Add up the digits in the rows/columns/boxes. Each should add to 45. If you go with dtilque's method of skipping some of the rows/columns, you only have 21 sums.

sj2
02-21-2006, 01:31 PM
Hmmm...is it possible to read every other line on the horizontal and then the vertical? I'd think the chances of having skipped an error this way would be slim.

If you like to do them online, zylom.com has an easy/hard version which allows you to use a pencil tool to jot notes...and of course, it checks it for you.

jacquilynne
02-21-2006, 02:44 PM
I'd go with a version of this. Add up the digits in the rows/columns/boxes. Each should add to 45. If you go with dtilque's method of skipping some of the rows/columns, you only have 21 sums.
In the interest of reducing calculations, definitely that would work. But I actually use those totals as a handy reference while I'm solving. When I'm down to just one remaining square in the row, I find it easier to look at the total, see '42' and think 'oh, it's a 3' than to scan the row and figure out which number is missing. So I'll keep the extra calculations just to speed up the solving.

Chronos
02-21-2006, 03:17 PM
What I usually do (if I feel the need to check, which I usually don't) is check the rows and columns three at a time, number-by-number. To clarify:

I start by checking 1s. I look at the first three rows (equivalently, the first three blocks), and see where the 1s are. There should be a 1 in each block, and the three of them should all be in different rows. Then I check the next 3 rows (3 blocks) the same way, then the bottom set. After that, I do the same check for the 2s, 3s, and so on. Then I do the same checks for the columns, 3 at a time. I can quickly pick out the three of each number in the set I'm looking at, and this method requires a total of 18 such checks.

Really, though, I only bother with all of this in the rare event that I use a reductio ad absurdem method, and that I fill in the entire grid from an assumption before I notice any contradiction. Although many people attempt to solve sudoku by guessing right from the beginning, such a method is almost completely hopeless.