3
$\begingroup$

Fundamentally, I'm looking for help on two things:

  1. Verification that my math is correct for the assumption that all Xs are Y.

  2. Proof that are the inverse is true, that all Y's are X, or, if it's not true, example of X that is outside the Y set.

More specifically, the assumption is :

  1. All solved Sudoku puzzles, where "solved" is defined as a 9x9 grid having the set 1-9 in each column, row, and 3x3 quadrant, can be verified as solved by taking the sum of each row, column, and quadrant, as the sum will always be 1215. This is based on taking the sum of each digit in the set (1+9 + 8+2 + 7+3 + 4+6 + 5 = 45) and multiplying by the total number of sets (9 rows + 9 columns + 9 quadrants = 27), so 45 * 27 = 1215.

  2. If the assumption above is correct, is this sum unique to solved puzzles, or are there permutations of a completed (but not solved) board that would give 1215 using the same method?

After a general search and skimming 2 wikipedia articles on Sudoku mechanics (Mathematics of Sudoku and Sudoku Algorithms), I'm still not seeing this simple approach to verifying a board as solved. All math and logic seem dedicated to solving puzzles (as in finding the correct digit for each cell) or to generating solvable puzzles. This has me thinking I am overlooking something with my math and logic, but I can't think of a board where the sum of the sets wouldn't be 1215 or a board where the sum would be 1215 and it would be an invalid board.

I am ready to be shown the err of my ways, but it would be cool to confirm that a board can be solved without confirmation that each cell value is valid.

$\endgroup$
7
  • $\begingroup$ Is any board with all entries filled in a "completed (but not solved) board"? If so, consider the board filled with all fives. $\endgroup$ – user856 Jun 13 '12 at 8:05
  • $\begingroup$ I almost edited the method to indicate that each set could not have duplicates, but realized that this was the definition of the game. Doh. Good example. $\endgroup$ – Anthony Jun 13 '12 at 8:17
  • 1
    $\begingroup$ Well, yes, assumption 1 is true. But it would be just as good, and three times quicker, to check that the total of all 81 squares on the board is $45\times9 = 405$. This is because the sum of the 9 rows is the same as the sum of the 9 columns, and the sum of the 9 blocks; it is the total of all 81 squares. $\endgroup$ – user856 Jun 13 '12 at 8:48
  • 2
    $\begingroup$ No, any possible board, whether correct or not, whether adding up to 405 or not, will have sum of all rows = sum of all cols = sum of all blocks = sum of all squares. Think about it: when you add up the totals of all the rows, which squares are getting added up? $\endgroup$ – user856 Jun 13 '12 at 8:57
  • 2
    $\begingroup$ All solved Sudoku boards do have such a sum of 1215. But, not all boards which have a sum of 1215 are solved Sudoku boards. In other words, if we have a solved Sudoku board, then it has such a sum of 1215. But, it is NOT necessarily true that if we have a board with sum of 1215, then that board is a solved Sudoku board. $\endgroup$ – Doug Spoonwood Jun 13 '12 at 11:39
18
$\begingroup$

Apropos your comment,

I'm guessing... that there is not an arithmetic way to check for set uniqueness?

there actually is a way, using only arithmetic, to check whether a sequence of nine numbers each between $1$ and $9$ contains all unique elements: for each number $n$ in the sequence, replace it with $2^{n-1}$, then add them all up and check that the sum is $511$. For example, the row $[5 | 3 | 4 | 6 | 7 | 8 | 9 | 1 | 2]$ is valid because $$2^{5-1} + 2^{3-1} + 2^{4-1} + 2^{6-1} + 2^{7-1} + 2^{8-1} + 2^{9-1} + 2^{1-1} + 2^{2-1} \\ = 16 + 4 + 8 + 32 + 64 + 128 + 256 + 1 + 2 \\ = 511,$$ but $[5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5]$ is not because $$2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} + 2^{5-1} \\ = 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 + 16 \\ = 144 \ne 511.$$

It should be clear that any permutation of the same set of numbers should give the same sum, so any valid solution should have the sum $511$. What is not immediately obvious is that no other sequence of nine numbers can give this sum. This is true because the Hamming weight of $511$ is $9$. The sum of $N$ numbers that are powers of $2$ can have Hamming weight at most $N$, and if there are duplicates among them, the weight of the sum is strictly less than $N$. So the only way to get a Hamming weight of $9$ by adding nine powers of $2$ is if they are all distinct.

$\endgroup$
11
  • 3
    $\begingroup$ +1 to a sneaky way of checking a bitwise XOR of nine patterns of nine bits. $\endgroup$ – Jyrki Lahtonen Jun 13 '12 at 10:54
  • $\begingroup$ @Jyrki: It's not quite a bitwise XOR because it has a carry, but yes, it's a very similar thing. $\endgroup$ – user856 Jun 13 '12 at 11:09
  • $\begingroup$ Quite. It's XOR only when right :-) $\endgroup$ – Jyrki Lahtonen Jun 13 '12 at 11:10
  • $\begingroup$ @Anthony +1 : simply adding all numbers wont make you sure that the row, column or quadrant have the right numbers: adding all numbers to 45 could be achieved repeating numbers, too. To verify the correcteness of the game, you have to verify rows, columns and quadrants, and make sure the digits don't repeat in each one. $\endgroup$ – woliveirajr Jun 13 '12 at 14:36
  • $\begingroup$ @RahulNarain - Why is this unique to [1-9] set? For a Sudoku board of 16x16, the same method returns a sum of 65,535, which, if I'm understanding the principle correctly, has a Hamming weight of 16 (expressed in Hex as FFFF). So shouldn't the 2^n-1 always return the all-bits-flipped binary sum, as long as the conditions are that the set starts with one and other values are consecutive and unique? Or am I out of my league? (The value of it always holding true would be that a more generic algorithm could verify a board of any magnitude). $\endgroup$ – Anthony Jun 14 '12 at 4:31
9
$\begingroup$

$\newcommand{\myentry}[1]{\tt{#1}}\newcommand{\myrow}[9]{\myentry{#1} & \myentry{#2} & \myentry{#3} & \myentry{#4} & \myentry{#5} & \myentry{#6} & \myentry{#7} & \myentry{#8} & \myentry{#9} \\ \hline}$A board that is filled with 9 of each of the digits $\myentry{1}$ through $\myentry{9}$, having a sum of all rows, columns, and regions equal to 1215, need not be a correct Sudoku board. For example, $$\large\begin{array}{|c|c|c||c|c|c||c|c|c|} \hline \myrow{1}{1}{1}{2}{2}{2}{3}{3}{3} \myrow{1}{1}{1}{2}{2}{2}{3}{3}{3} \myrow{1}{1}{1}{2}{2}{2}{3}{3}{3} \myrow{4}{4}{4}{5}{5}{5}{6}{6}{6} \myrow{4}{4}{4}{5}{5}{5}{6}{6}{6} \myrow{4}{4}{4}{5}{5}{5}{6}{6}{6} \myrow{7}{7}{7}{8}{8}{8}{9}{9}{9} \myrow{7}{7}{7}{8}{8}{8}{9}{9}{9} \myrow{7}{7}{7}{8}{8}{8}{9}{9}{9} \end{array}$$ In response to your comment below: no, that still does not suffice; consider the board $$\large\begin{array}{|c|c|c||c|c|c||c|c|c|} \hline \myrow{1}{2}{3}{1}{2}{3}{1}{2}{3} \myrow{4}{5}{6}{4}{5}{6}{4}{5}{6} \myrow{7}{8}{9}{7}{8}{9}{7}{8}{9} \myrow{1}{2}{3}{1}{2}{3}{1}{2}{3} \myrow{4}{5}{6}{4}{5}{6}{4}{5}{6} \myrow{7}{8}{9}{7}{8}{9}{7}{8}{9} \myrow{1}{2}{3}{1}{2}{3}{1}{2}{3} \myrow{4}{5}{6}{4}{5}{6}{4}{5}{6} \myrow{7}{8}{9}{7}{8}{9}{7}{8}{9} \end{array}$$ Your statement that any correctly solved board will have a sum of rows, columns, and regions of 1215 is correct (the reasoning in your question is valid), but that property is also true of any arrangement of 9 $\myentry{1}$'s, 9 $\myentry{2}$'s, ..., and 9 $\myentry{9}$'s, regardless of whether they form a correct Sudoku board. To see this, just note that the sum of the entries is $$(9\times 1)+(9\times 2)+\cdots+(9\times 9)=9\times(1+2+\cdots+9)=9\times 45=405$$ and each entry is in exactly one row, one column, and one region, so each entry is counted three times when forming the sum of the rows, columns, and regions, so that the sum is $3\times 405=1215$.

$\endgroup$
8
  • $\begingroup$ Okay, based on your example and Rahul's, does the following hold true: In a solved board, the sum of all sets is 1215 and each quadrant must contain all members of the 1-9 set? Or do all 27 sets need to be verified as valid? $\endgroup$ – Anthony Jun 13 '12 at 8:15
  • $\begingroup$ An interesting flaw in both examples (though certainly not support for my assumption) is that I'm pretty certain that no puzzle with a unique solution would start with numbers that could result in either example. Is their an obvious example of a starting config that wouldn't add up to 1215? Or is it possible that a fair board must only have a final sum of 1215 when solved? $\endgroup$ – Anthony Jun 13 '12 at 8:28
  • $\begingroup$ quick note: I don't expect an actual example, unless it already exists or is incredibly easy to generate. Given your update, I'll trust you if you can just say with confidence that a deterministically unique starting board can be finish with a sum of 1215 and still be wrong. $\endgroup$ – Anthony Jun 13 '12 at 8:32
  • $\begingroup$ @Anthony: See my recent additions to my answer. $\endgroup$ – Zev Chonoles Jun 13 '12 at 8:35
  • $\begingroup$ You had me up until the "each entry" part, do you mean if the board has the "correct" entries, just not in order that the board as a set adds up to 405? I'm going to sleep on this, as I'm feeling schooled enough from the parts I do understand. For now, I'll take satisfaction in knowing that a validation sequence can be short-circuited if the sum of the sets is not 1215 (and perhaps, if I'm reading your edit correctly, this could be further simplified by checking if the board has sum of 405 before getting sum of sets). $\endgroup$ – Anthony Jun 13 '12 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.