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.

  • 2
    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.2012-06-13

2 Answers 2

18

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.

  • 0
    @Jason: I don'$t$ know if it's called anything in mathematics. In computer science it's kind of like a [bit set](http://en.wikipedia.org/wiki/Bit_array).2013-01-15
9

$\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$.

  • 0
    @Anthony There exists no simple way to check for uniqueness like that, because the order of the entries doesn't affect their sum. In other words, because addition of natural numbers is both commutative and associative. {1, ..., n}={n, ..., 1} *and* +(1, ..., n)=+(n, ..., 1), where "+" indicates n-ary addition extended from the binary addition operation on the natural numbers. So, we can always produce a board which violates the row, column, and box rules of Sudoku.2012-06-13