Friday, October 26, 2018

optimization - Maximize 'chains' in a Sudoku


Yet to be solved.


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



Start with a solved 9x9 Sudoku grid. Find any N1=N.
Find an M1=M, in the same row as N1.
In the same column as M1, find N2=N.
Find an M2=M, in the same row as N2.


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 Ns and nine Ms in this chain (all Ns and Ms 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 \...