Friday, October 26, 2018

optimization - Maximize 'chains' in a Sudoku


Yet to be solved.


Take 2 numbers such that $N, M \in \{1,2,3,4,5,6,7,8,9\}; N \ne M$.



Start with a solved 9x9 Sudoku grid. Find any $N_1 = N$.
Find an $M_1 = M$, in the same row as $N_1$.
In the same column as $M_1$, find $N_2 = N$.
Find an $M_2 = M$, in the same row as $N_2$.


Keep repeating the process till you reach the cell you started with. You would have formed a 'chain' of linked up cells.



A 'complete chain' exits between $M$ and $N$ iff there are nine $N$s and nine $M$s in this chain (all $N$s and $M$s are chained together).



Create the maximum possible 'complete chains' in a Sudoku.


Edit:



Please try adding a proof to why a certain number is the absolute maximum.



Answer




Here is a Sudoku where 27 out of the 36 pairs have complete chains:
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3
9 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
3 4 5 6 7 8 9 1 2

8 9 1 2 3 4 5 6 7
5 6 7 8 9 1 2 3 4
2 3 4 5 6 7 8 9 1



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