Wednesday, June 12, 2019

There is a reason sudoku uses squares


There exists a 9x9 grid with the cells in one single row numbered 1-9 in order. The cells in the other 8 rows are initially empty.


enter image description here
Note: The cells initially containing numbers can be in any one row; not necessarily the first.


Draw borders to divide the square into 9 non-intersecting continuous regions containing 9 cells each such that you make a sudoku-like puzzle with a unique solution. You may not add any additional numbers or hints. A sudoku-like puzzle, for this question, has the following rules:




  • each cell in the 9x9 grid contains exactly 1 integer between 1 and 9 inclusive





  • each row and column and bordered region contains each integer between 1 and 9 inclusive exactly once





Answer



There is a unique solution to the following



enter image description here




The solution is



enter image description here



Proof of uniqueness



Let us use the following notation:
The rows from top to bottom are given the labels $A-I$
The columns from left to right are numbered $1-9$ (as with the top row).

Firstly, $B9$ must be $1$ since it is the last in its continuous region. Then, this forces $C8$ to be $1$ since none of the rest of row $B$ can contain $1$ nor can column $9$. Similarly, we find that going down diagonally to the left all the entries are $1$ down to $I2$.

Now, look at $C9$. The entry here, $x$, must be the same as $D8$, since its continuous region has to contain $x$ but row $C$ and column $9$ already contain $x$. By a similar line of reasoning, we find, recursively, that the entries $E7$, $F6$, $G5$, $H4$ and $I3$ are all $x$ but of course cannot be $3,4,\ldots,9$ so $x=2$ and $B1$ must also be $2$.

We can continue this line of reasoning, next starting at the entry in $D9$, calling this $y$ and proceeding diagonally left and down to find $y=3$.

In this way, we can fill the entire grid, recursively always beginning at the topmost entry in column $9$.




No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...