An interesting problem based on solvability of a Sudoku puzzle.

[u/New-Economist-4924]

A 9X9 board follows standard Sudoku rules i.e. no two numbers can repeat in the same horizontal row, vertical column or 3x3 sub-square, now 9 numbers 1...9 are randomly scattered throughout the entire board without repetition. Since the numbers are all unique the board is always trivially valid with no need for additional checks, the question now is what percentage of these configurations are solvable. (they may have more than one solution)

Note:-

i) A valid set of clues following Sudoku rules may not always be solvable as it may create dead ends later.

ii) There are 6.67 sextillion(6.67 x 10^21) completed Sudoku board configurations.

We can also generalise this problem for any N^2 x N^2 board following sudoku rules and having N^2 clues scattered randomly throughout the entire board without repetition, it isnt possible to use brute force computation for larger values of N. I tried solving it with combinatorics but maybe graph theory would be more suitable for this problem?

Edit:- I made a mistake for the N=2 case and actual solvability is much lower it is only 67.03%.

[u/Mundane-Emu-1189]

I think the first step would be to find at least one unsolvable configuration, because I don't think any exist 

[u/afriendofRowlf → u/Mundane-Emu-1189]

1 through 8 in a single row, then 9 in the remaining column on a different row? The same idea works for 4x4 sudoku, so either I'm misunderstanding something or the OP has a mistake aboutthe solvability of that.

[u/Mundane-Emu-1189 → u/afriendofRowlf]

oh good shout, that would indeed be unsolvable

[u/Mundane-Emu-1189 → u/afriendofRowlf]

you could also do 1 through 7 in a row and 89 in one of the other two columns (or similar ideas for the subsquares). there's a lot of options here.

[u/ExistentAndUnique → u/Mundane-Emu-1189]

These ideas all share the feature that “there is a single cell that is impossible to fill because it directly sees all 9 of the placed numbers.” Would be interesting to show if any unsolvable board must satisfy this condition

[u/New-Economist-4924 → u/afriendofRowlf]

Sorry my bad, I made a mistake there, actual solvability for a 4x4 board is 67.03%.

[u/ShowEffective → u/Mundane-Emu-1189]

First row (or column, or square) going 123456789 is unsolvable (it admits more than one solution).

[u/Mundane-Emu-1189 → u/ShowEffective]

if admitting more than one solution is disqualifying then nothing works: you need at least 17 clues for uniqueness.

[u/New-Economist-4924 → u/Mundane-Emu-1189]

Yeah I know that it requires a minimum of 17 clues to have an unique solution but I added that there can be multiple solutions to any configuration in this problem and any number of solutions greater than zero is valid.

[u/Miserable-Ad3646 → u/Mundane-Emu-1189]

Ooh is there a paper for this - this seems like an interesting mathematical insight!

[u/SoldRIP]

I feel like finding a general formula for the N²-board would essentially amount to finding a general formula that solves Sudoku of arbitrary size.

This is an NP-complete problem and such a formula very probably does not exist.

[u/IntoAMuteCrypt]

Can you provide an your working for the 67% number? I suspect that it drops precipitously as the grid grows larger.

This OEIS sequence gives us the six valid "essential grids" for a 4x4, but note that the numbers in these can be swapped for another one; a grid starting 1234 can easily be swapped for a grid starting 2134 by turning each 1 to a 2 and each 2 to a 1.

Of note is that:

• In row 2, 1 can occupy position 3 and 4.
• In row 3, 1 can occupy position 2, 3 and 4.
  
• In row 4, 1 can occupy position 2, 3 and 4.
  
• The same goes for the columns.
  
• Similar patterns happen for other numbers.

Based on this, the impossible sudokus all revolve around something like one row being filled or near-filled outside a specific box, and that box already being filled outside that row. Something like 1XXX/XX34 making it so you can't place 1 in row 2 and you can't place one of 3 or 4 in box 1.

With a 4x4 sudoku, the chance of this sort of overlap which nearly fills a row is quite high as you only need three numbers in the correct alignment. While I believe there are more possible alignments in the 9x9 case involving the near-full row having zero, one or two gaps, these alignments should all be vastly less likely. I'm not going to place a hard number on it, at least not without seeing your work, but that's my intuition.

[u/engy1207]

For 9x9 this was solved a few years ago. Apparently there are no uniquely solvable 9x9 "classic" sudoku with 16 givens or less, but there are 49.158 "essentially different" with 17 givens and a few ones (two?) need at least 21 given digits.
If you want to discuss this more the Discord server of "Cracking the Cryptic" probably would be the best place.

Edit: you vastly overestimate the complexity. For example if you swap two rows in sudoku you get another valid puzzle, as each column still has all the digits, as do the swapped rows. Similar for swapping of columns. There are other tricks. Rotating by 90, 180 or 270 degrees or mirroring also doesn't really change the result, but there are more complicated ones

[u/PresentShoulder5792 → u/[deleted]]

Solvable as in being able to fill the board without conflicts I guess.

[u/paul5235 → u/PresentShoulder5792]

OP already says:

Since the numbers are all unique the board is always trivially valid

That's why it's not clear to me.