10

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.

ghosts_in_the_code
  • 7,024
  • 1
  • 30
  • 100
  • 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: http://math.stackexchange.com/questions/1204566/enumeration-of-solved-sudoku-puzzles 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. – JLee Mar 25 '15 at 14:35
  • Also, have you seen this paper? http://www.math.ie/McGuire_V1.pdf – JLee Mar 25 '15 at 14:38
  • @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. – ghosts_in_the_code Mar 27 '15 at 15:44
  • 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. – JLee Mar 27 '15 at 15:48
  • @IanMacDonald I saw your edit. I just wanted to know what $\in$ is supposed to mean. – ghosts_in_the_code Apr 02 '15 at 09:54
  • $X \in S$ is read as "$X$ is an element of the set $S$" – Ian MacDonald Apr 02 '15 at 10:56

1 Answers1

7

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

Raziman T V
  • 2,448
  • 16
  • 29
  • Good effort! I'll accept your answer if a better one doesn't come up. – ghosts_in_the_code Mar 22 '15 at 19:21
  • 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. – JLee Mar 23 '15 at 17:01
  • is this value of maximum chains final ? – Abr001am Mar 27 '15 at 16:08
  • @Agawa001 No, it isn't. That's why I've put a bounty. – ghosts_in_the_code Mar 29 '15 at 14:33
  • 1
    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 – Abr001am Mar 29 '15 at 15:03
  • the good news is that brute force is not THAT unrealistic, since there are ONLY 5.4 billion essentially diffferent sudokus (as opposed to the 6,670,903,752,021,072,936,960 possible sudokus, which would take nearly forever to brute force) – JLee Apr 01 '15 at 13:31
  • @JLee Maybe you could do it (if you know how to) and receive the bounty. – ghosts_in_the_code Apr 01 '15 at 14:12
  • 1
    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. – JLee Apr 01 '15 at 14:19
  • @ghosts_in_the_code im trying harder to complete n-1 couples with the first digit in a smaller grid but cudnt do it , if there is no more than 27 per 36 chains , it s not woth the shot – Abr001am Apr 01 '15 at 14:19
  • @JLee u can reduce it until hundred times faster if u know how and where ur code can be drawn out – Abr001am Apr 01 '15 at 14:22
  • besides, i strongly suspect 27 is the max. i put a few hours into finding one with more, and got nowhere close – JLee Apr 01 '15 at 14:25
  • hmmm thats pretty enticing information – Abr001am Apr 01 '15 at 14:30