9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I know you said you are looking into Sudokus and trying to prove that there exists no 16-hint solvable sudoku. You might find this useful: math.stackexchange.com/questions/1204566/… Since there are only ~5.4 billion essentially different sudokus, you can loop through every possible one and do some light analysis (like the one above with complete chains) and have a more definitive answer. $\endgroup$ – JLee Mar 25 '15 at 14:35
  • $\begingroup$ Also, have you seen this paper? math.ie/McGuire_V1.pdf $\endgroup$ – JLee Mar 25 '15 at 14:38
  • $\begingroup$ @JLee Thank you, but since I've asked on Puzzling SE, I would like a more logical explanation rather than just writing a program to solve all possibilities. I don't not know much about algorithms and all. $\endgroup$ – ghosts_in_the_code Mar 27 '15 at 15:44
  • $\begingroup$ my intention was that this solution would allow you to know for certain how the sudoku numbers relate to one another in chain length, and how many chains are possible, assuming that it might somehow help you in your broader goal of showing there exists no 16-hinter. $\endgroup$ – JLee Mar 27 '15 at 15:48
  • $\begingroup$ @IanMacDonald I saw your edit. I just wanted to know what $\in$ is supposed to mean. $\endgroup$ – ghosts_in_the_code Apr 2 '15 at 9:54
6
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Good effort! I'll accept your answer if a better one doesn't come up. $\endgroup$ – ghosts_in_the_code Mar 22 '15 at 19:21
  • $\begingroup$ the one i created was the same thing, except rows 2 and 3 were swapped, and it also yields 27 out of 36 pairs. so, that leads me to believe that rows 1-3, and 4-6, and 7-9 can be in any order and still yield the same answer. $\endgroup$ – JLee Mar 23 '15 at 17:01
  • $\begingroup$ is this value of maximum chains final ? $\endgroup$ – Abr001am Mar 27 '15 at 16:08
  • 1
    $\begingroup$ well if it is programatically based value , i think it is final , a mathematical proof is not likely as a bruteforce technique is probable to validate that..besides ... i couldnt reach n-1 (=8) couples by the first value (assuming 1) it seems to me impossible to have 36 pairs $\endgroup$ – Abr001am Mar 29 '15 at 15:03
  • 1
    $\begingroup$ I know how to, but getting the 5.4 billion essentially different sudokus is challenging because I'd have to put a lot of time into either: A. Finding someone with the flash drive (see my link on the question) and learning how to unload it OR B.generating them myself (which takes about 2 weeks, and maxes out my CPU, which I need for other things). No amount of points would convince me to do this. $\endgroup$ – JLee Apr 1 '15 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.