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

Improve this question
$\endgroup$
6
  • $\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, 2015 at 14:35
  • $\begingroup$ Also, have you seen this paper? math.ie/McGuire_V1.pdf $\endgroup$
    – JLee
    Mar 25, 2015 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, 2015 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, 2015 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, 2015 at 9:54

1 Answer 1

Reset to default
7
+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

Improve this answer
$\endgroup$
12
  • $\begingroup$ Good effort! I'll accept your answer if a better one doesn't come up. $\endgroup$
    – ghosts_in_the_code
    Mar 22, 2015 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, 2015 at 17:01
  • $\begingroup$ is this value of maximum chains final ? $\endgroup$
    – Abr001am
    Mar 27, 2015 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, 2015 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, 2015 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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