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 AI
The columns from left to right are numbered 19 (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,,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 \...