Deletes entries at random in a sudoku.
Y = sudoku_delrandom ( X , nr , vari )
a filled 9x9 matrix, without zeros
the average number of entries removed by 3x3 block. Higher nr generates a more difficult sudoku.
an integer d is picked in the interval [nr-var,nr+vari], and the number of deleted entries is d=min(7,d).
Delete entries in each subblock with a variance of vari.
Notice that there is only a weak link between the number of givens and the difficulty of a sudoku puzzle. For example, many 17-givens sudokus are easy to solve, while AIEscargot, which is extremely difficult has 23 givens.
The algorithm makes a loop over the 3x3 blocks. For each block of the sudoku, compute the integer d randomly in the interval [nr-var,nr+vari]. In order to ensure that at most 7 entries are deleted in a block, takes d=min(7,d). Take d random integers in the sequence 1,2,...,9. Delete the cells of the block which corresponds to these integers.
This algorithm can be used when X is a sudoku solution and we want to produce a puzzle. We are interested in the number of givens (i.e. the number of nonzero entries) in the generated puzzle. We run this algorithm 1000 times on the same solution and compute the min, max, average and standard deviation of the number of givens, as in the example.
Nr = 5, vari=2 Givens: min=23, max=46, average=36, std=4 Unknowns: min=34, max=58, average=45, std=4
Nr = 6, vari=2 Givens: min=19, max=38, average=28, std=3 Unknowns: min=43, max=61, average=53, std=3
Nr = 7, vari=2 Givens: min=18, max=32, average=23, std=2 Unknowns: min=51, max=63, average=58, std=2
Nr = 5, vari=1 Givens: min=30, max=42, average=36, std=2 Unknowns: min=38, max=52, average=45, std=2
Nr = 6, vari=1 Givens: min=21, max=34, average=27, std=2 Unknowns: min=48, max=61, average=54, std=2
Nr = 7, vari=1 Givens: min=18, max=24, average=20, std=1 Unknowns: min=56, max=63, average=61, std=1
These are the numbers presented in "Programming Sudoku": Easy : unknowns from 40 to 45 (i.e. from 36 to 41 givens), Medium : unknowns from 46 to 49 (i.e. from 32 to 35 givens), Difficult : unknowns from 50 to 53 (i.e. from 28 to 31 givens), Extremely difficult: unknowns from 54 to 58 (i.e. from 27 to 23 givens).
To get these results, use the following settings: Easy : nr = 4.72, vari = 0.5, Medium : nr = 5.27, vari = 0.5, Difficult : nr = 5.72, vari = 0.5, Extremely difficult: nr = 6.22, vari = 0.5.
TODO: add an option to make the sudoku symetrical.
X = [ 6 7 3 1 5 8 2 4 9 4 1 8 2 6 9 5 3 7 9 2 5 4 3 7 8 6 1 5 8 2 3 4 1 7 9 6 3 4 7 6 9 2 1 8 5 1 9 6 7 8 5 3 2 4 7 5 4 8 2 6 9 1 3 2 3 1 9 7 4 6 5 8 8 6 9 5 1 3 4 7 2 ]; Y = sudoku_delrandom ( X , 5 , 2 ) Y = sudoku_delrandom ( X , 6 , 2 ) Y = sudoku_delrandom ( X , 7 , 2 ) nr = 5 vari = 2 for i = 1 : 1000 givens(i) = sum(sudoku_delrandom ( solution , nr , vari )>0); unknowns(i) = sum(sudoku_delrandom ( solution , nr , vari )==0); end mprintf("Nr = %d, vari=%d\n", nr, vari ) mprintf("Givens: min=%d, max=%d, average=%d, std=%d\n",min(givens), .. max(givens), round(mean(givens)), round(st_deviation(givens)) ) mprintf("Unknowns: min=%d, max=%d, average=%d, std=%d\n",min(unknowns), .. max(unknowns), round(mean(unknowns)), round(st_deviation(unknowns)) ) | ![]() | ![]() |