The New Sudoku Players' Forum

[dukuso]

when you discard the blocks in a sudoku, then we have the well
known and much analyzed NP-complete "quasigroup completion problem (QCP)".

I turned out, that there is a phase-transition point(PTP)
when about 43% of the grid is filled with clues.
QCPs with randomly filled clues are hardest to solve near the PTP.
Below the PTP almost all QCPs are solvable while above almost
all are unsolvable, when n is large enough.

see e.g.:
http://www.sciencenews.org/articles/20000506/mathtrek.asp
http://www.cs.cornell.edu/gomes/gs-csgc.pdf

How is it with sudokus ? I assume we have similar behaviour here.
Where is the PTP for sudokus ?

[frazer]

I wondered about this a little. It seems to me that if you put a random digit on a square in the grid, then you are reducing the number of valid sudoku solutions by a factor of 9. The total number of solution grids is 6.67e21, which lies between 9^22 and 9^23. Consequently, if you place randomly 23 numbers on a blank grid, you should expect just under 1 solution. Placing further clues randomly makes it less and less likely that there are solutions. Conversely, placing fewer than 23 numbers makes it likely that there are several solutions. Indeed, relating to another thread, placing 17 numbers randomly, you could expect 400000 solutions, and placing 16 numbers, you could expect about 3500000 solutions. So, purely on these "information-theoretic" grounds, I'd suspect that 23 clues (about 28.4%) is the PTP.

[dukuso]

what's the asymptotics ?
In QCP for n=9 we have the PTP at about 35-40% (the Gomes-table
starts with n=11, so I'm guessing this)
while for larger n it seems to converge to about 43%.

For n=9 sudoku we have about 28%, so the asymptotics could be 30-35%
(?)
What's with the constrained sudoku suggested here in another thread ?
(the one with the additional constraint that no two cells at the same
offset of some blocks may contain the same digit)
What with diagonal sudokus, diagonal latin squares, pandiagonal
latin squares , ...
Looks interesting. Maybe someone will examine this !?!