So this nonsense is popular now. I really don't get it - one grid filled with numbers is about the same as another, to me. With crossword puzzles, at least, the clues can be crafted with varying degrees of cleverness - not to mention 26 > 9.
However, it irks me that there might be peabrains running around getting good at these goofy puzzles and then having a valid claim of mental superiority when I can barely solve the "medium" puzzles in the Wed./Thurs. WaPo. So I've been practicin' some. It's all kind of tedious, but the most tedious part is checking the answer when I'm done.
So here's the nut: In the absence of an answer key, what is the fastest way to check that a su-dork-u grid contains one and only one of each digit in each row, column, and 3x3 box? Put another way: Call each row, column or box an "element"; what is the minimum number of elements that need to be checked for having each digit exactly once in order to be sure that all 27 elements have that property?
3 comments:
If each row and column lacks repeats, then the regions should also be repeat-free, I think.
Of course, checking 18 elements is only slightly less work than checking 27 elements. There's probably some way to make a shortcut using diagonals or something. Of course, by checking the rows and columns you're still looking up the value for 81 cells. At least you don't look up the values in the cells twice.
I haven't verified any of this because I haven't taken the time to write a sudorku generator.
Checking each row and column is not enough, since you also have to ensure that each 3x3 box is valid as well.
As a counterexample, imagine a sodoku solution with 1's filling the diagonal from top left to botton right. It would satisfy the diagonal/horizontal rule "each row/column must have exactly one '1'". It would violate the 3x3 rule though since the top left, middle, and bottom right 3x3 squares would each have three 1's, and all of the other squares would have zero 1's.
Suppose a correctly solved puzzle has the digit 1 in the top left corner and the digit 2 immediately right of that 1. Switching the place of these two digits will make the first and second columns on the left invalid. You can successfully validate 25 elements of this puzzle, so a minimum of 26 elements must be validated in some puzzles.
Post a Comment