How do you generate a Sudoku board with a unique solution? What I thought was to initialize a random board and then remove some numbers. But my question is how do I maintain the uniqueness of a solution?
15 Answers
The solution is divide in to 2 parts:
A. Generating the number pattern 600 billion
B. Generating the masking pattern ~ 7e23 combinations
A ) For Number pattern the fastest way which can generate unique combinations with NO time spent on backtracing or testing
Step 1. Choose an already exiting matrix, I chose the below one as it can be made easily by human without any help from a computing device or solver:
First row is numbers in ascending order
Second row is also in ascending order but start from 4 & roll around
Third row is also in ascending order but start from 7 & roll around
Row 4,5,6: Replace the three cell column with the top right column - 2 5 8 and roll within the 3x3 cell for last column
Row 7,8,9: Replace the three cell column with the top right column - 3 6 9 and roll within the 3x3 cell for last column
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
Step 2. Shuffle the the digits and replace in all other cells
Step 3. Randomly rearrange columns 1,2 and 3 within themselves
Step 4. Randomly rearrange columns 4,5 and 6 within themselves
Step 5. Randomly rearrange columns 7,8 and 9 within themselves
Step 6. Randomly rearrange rows 1,2 and 3 within themselves
Step 7. Randomly rearrange rows 4,5 and 6 within themselves
Step 8. Randomly rearrange rows 7,8 and 9 within themselves
Step 9. Randomly rearrange in 3 column groups of size 9x3
Step 10. Randomly rearrange in 3 row groups of size 3x9
voila...
5 8 3 1 6 4 9 7 2
7 2 9 3 5 8 1 4 6
1 4 6 2 7 9 3 8 5
8 5 2 6 9 1 4 3 7
3 1 7 4 2 5 8 6 9
6 9 4 8 3 7 2 5 1
4 6 5 9 1 3 7 2 8
2 3 1 7 8 6 5 9 4
9 7 8 5 4 2 6 1 3
B ) For Masking Pattern we need to have a solver algorithm. As we already have a quite unique number grid (which is also solved!) this gives us faster performance for using solver
Step 1: Start with selecting 15 random locations out of the 81.
Step 2: Check with solver whether it has unique solution
Step 3: If solution not unique select additional location. iterate Steps 2 and 3 until unique solution found
This should give you the very unique and fast Sudoku board.
This way you can generate any possible sudoku board as well as any other nxn sudoku board
as for how efficient this algorithm is , it took 3.6 secs to generate a million boards in java & 3.5 sec in golang
- Find any filled board of sudoku. (use trivial ones will not affect final result)
int[][] board = new int[][] {
{1,2,3, 4,5,6, 7,8,9},
{4,5,6, 7,8,9, 1,2,3},
{7,8,9, 1,2,3, 4,5,6},
{2,3,1, 5,6,4, 8,9,7},
{5,6,4, 8,9,7, 2,3,1},
{8,9,7, 2,3,1, 5,6,4},
{3,1,2, 6,4,5, 9,7,8},
{6,4,5, 9,7,8, 3,1,2},
{9,7,8, 3,1,2, 6,4,5}
};
- for each number from 1 to 9 (say num), (i.e 1, 2, 3, 5, 6, 7, 8, 9) take a random number from range [1 to 9], traverse the board, swap num with your random number.
void shuffleNumbers() {
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(9);
swapNumbers(i, ranNum);
}
}
private void swapNumbers(int n1, int n2) {
for (int y = 0; y<9; y++) {
for (int x = 0; x<9; x++) {
if (board[x][y] == n1) {
board[x][y] = n2;
} else if (board[x][y] == n2) {
board[x][y] = n1;
}
}
}
}
- Now shuffle rows. Take the first group of 3 rows , shuffle them , and do it for all rows. (in 9 X 9 sudoku), do it for second group and as well as third.
void shuffleRows() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapRows(i, blockNumber * 3 + ranNum);
}
}
void swapRows(int r1, int r2) {
int[] row = board[r1];
board[r1] = board[r2];
board[r2] = row;
}
- Swap columns, again take block of 3 columns , shuffle them, and do it for all 3 blocks
void shuffleCols() {
int blockNumber;
for (int i = 0; i < 9; i++) {
int ranNum = random.nextInt(3);
blockNumber = i / 3;
swapCols(i, blockNumber * 3 + ranNum);
}
}
void swapCols(int c1, int c2) {
int colVal;
for (int i = 0; i < 9; i++){
colVal = board[i][c1];
board[i][c1] = board[i][c2];
board[i][c2] = colVal;
}
}
- swap the row blocks itself (ie 3X9 blocks)
void shuffle3X3Rows() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Rows(i, ranNum);
}
}
void swap3X3Rows(int r1, int r2) {
for (int i = 0; i < 3; i++) {
swapRows(r1 * 3 + i, r2 * 3 + i);
}
}
- do the same for columns, swap blockwise
void shuffle3X3Cols() {
for (int i = 0; i < 3; i++) {
int ranNum = random.nextInt(3);
swap3X3Cols(i, ranNum);
}
}
private void swap3X3Cols(int c1, int c2) {
for (int i = 0; i < 3; i++) {
swapCols(c1 * 3 + i, c2 * 3 + i);
}
}
Now you are done, your board should be a valid sudoku board
To generate a board with hidden values, this can be done using backtracking sudoku algorithm with it try to remove one element from the board until you have a board that is solvable, remove until it will become unsolvable even if you remove only one more element.
if you want to categorised final generated board by difficulty, just count how many numbers are left in board while removing element one by one. The less the number harder it will be to solve
least possible hints in sudoku can be 17, but all possible sudoku board not necessarily reducible to 17 hint sudoku
SWIFT 5 version
The simply way, here my code:
First, create the function into [[Int]] array
func getNumberSudoku() -> [[Int]] {
// Original number
let originalNum = [1,2,3,4,5,6,7,8,9]
// Create line 1 to 9 and shuffle from original
let line1 = originalNum.shuffled()
let line2 = line1.shift(withDistance: 3)
let line3 = line2.shift(withDistance: 3)
let line4 = line3.shift(withDistance: 1)
let line5 = line4.shift(withDistance: 3)
let line6 = line5.shift(withDistance: 3)
let line7 = line6.shift(withDistance: 1)
let line8 = line7.shift(withDistance: 3)
let line9 = line8.shift(withDistance: 3)
// Final array
let renewRow = [line1,line2,line3,line4,line5,line6,line7,line8,line9]
// Pre-shuffle for column
let colSh1 = [0,1,2].shuffled()
let colSh2 = [3,4,5].shuffled()
let colSh3 = [6,7,8].shuffled()
let rowSh1 = [0,1,2].shuffled()
let rowSh2 = [3,4,5].shuffled()
let rowSh3 = [6,7,8].shuffled()
// Create the let and var
let colResult = colSh1 + colSh2 + colSh3
let rowResult = rowSh1 + rowSh2 + rowSh3
var preCol: [Int] = []
var finalCol: [[Int]] = []
var prerow: [Int] = []
var finalRow: [[Int]] = []
// Shuffle the columns
for x in 0...8 {
preCol.removeAll()
for i in 0...8 {
preCol.append(renewRow[x][colResult[i]])
}
finalCol.append(preCol)
}
// Shuffle the rows
for x in 0...8 {
prerow.removeAll()
for i in 0...8 {
prerow.append(finalCol[x][rowResult[i]])
}
finalRow.append(prerow)
}
// Final, create the array into the [[Int]].
return finalRow
}
Then usage:
var finalArray = [[Int]]
finalArray = getNumberSudoku()
One way to generate sudoku faster.
- find an exist sudoku.
- exchange the value with a random group.
- exchange the cell or the column or the row-grid or the column-grid.
You exchange the value will make the value different, if not exchange the rows or the column, the sudoku isn't changed in the essential.
You can flag the sudoku with 9 grids, the rows and column exchanged must do in the same grid. Like you can exchange row1-3, row4-6, row7-9, don't exchange row1-4 or row1-7. You can also exchange the row-grid(exchange row1~3 with the row4~6 or row7~9).
Solve the sudoku: record the empty with all the possible value, then check the value from 1 to 9. If one value is unique, remove it from the loop.
You can start with any valid (filled) puzzle and modify it to produce a completely different one (again, filled). Instead of permutating groups of numbers, you can swap single cells - there will be no similarity whatsoever between the seed puzzle and the resulting puzzle. I have written a simple program long ago in VB, you can find it here: https://www.charalampakis.com/blog/programming-vb-net/a-simple-algorithm-for-creating-sudoku-puzzles-using-visual-basic. It can be translated to any language easily.
Then, randomly and gradually remove cells and check if the puzzle is solvable and has a unique solution. You can also rate the puzzle in terms of difficulty depending on the rules needed for the solution. Continue until removing any known cell leads to an unsolvable puzzle.
HTH
You may need code like this:
#pz is a 9x9 numpy array
def PossibleValueAtPosition(pz:[], row:int, col:int):
r=row//3*3
c=col//3*3
return {1,2,3,4,5,6,7,8,9}.difference(set(pz[r:r+3,c:c+3].flat)).difference(set(pz[row,:])).difference(set(pz[:,col]))
def SolvePuzzle(pz:[], n:int, Nof_solution:int):# init Nof_solution = 0
if Nof_solution>1:
return Nof_solution # no need to further check
if n>=81:
Nof_solution+=1
return Nof_solution
(row,col) = divmod(n,9)
if pz[row][col]>0: # location filled, try next location
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
else:
l = PossibleValueAtPosition(pz, row,col)
for v in l: # if l = empty set, bypass all
pz[row][col] = v # try to fill a possible value v
Nof_solution = SolvePuzzle(pz, n+1, Nof_solution)
pz[row][col] = 0
return Nof_solution # resume the value, blacktrack
Quick and Dirty, but works:
import numpy as np
import math
N = 3
# rewrite of https://www.tutorialspoint.com/valid-sudoku-in-python
def isValidSudoku(M):
'''
Check a sudoku matrix:
A 9x9 sudoku matrix is valid iff every:
row contains 1 - 9 and
col contains 1 - 9 and
3x3 contains 1 - 9
0 is used for blank entry
'''
for i in range(9):
row = {}
col = {}
block = {}
row_cube = N * (i//N)
col_cube = N * (i%N)
for j in range(N*N):
if M[i][j] != 0 and M[i][j] in row:
return False
row[M[i][j]] = 1
if M[j][i] != 0 and M[j][i] in col:
return False
col[M[j][i]] = 1
rc = row_cube + j//N
cc = col_cube + j%N
if M[rc][cc] in block and M[rc][cc] != 0:
return False
block[M[rc][cc]]=1
return True
def generate_sudoku_puzzles(run_size, seed):
order = int(math.sqrt(run_size))
count = 0
valid = 0
empty = []
np.random.seed(seed) # for reproducible results
for k in range(order):
for l in range(order):
A = np.fromfunction(lambda i, j: ((k*i + l+j) % (N*N)) + 1, (N*N, N*N), dtype=int)
B = np.random.randint(2, size=(N*N, N*N))
empty.append(np.count_nonzero(B))
C = A*B
count += 1
if isValidSudoku(C):
valid += 1
last = C
# print('C(',k,l,') is valid sudoku:')
# print(C) # Uncomment for puzzle
print('Tried', count, 'valid', valid, 'yield', round(valid/count, 3)*100, '%', 'Average Clues', round(sum(empty)/len(empty)))
return(last)
posTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 0), \
(3, 0, 0, 5, 0, 7, 0, 0, 2), \
(0, 0, 5, 0, 0, 0, 3, 0, 0), \
(0, 4, 0, 3, 0, 6, 0, 5, 0), \
(6, 0, 0, 0, 0, 0, 0, 0, 8), \
(0, 1, 0, 2, 0, 8, 0, 3, 0), \
(0, 0, 7, 0, 0, 0, 4, 0, 0), \
(1, 0, 0, 8, 0, 2, 0, 0, 9), \
(0, 6, 0, 0, 9, 0, 0, 1, 0), \
])
negTest = np.array([(0, 7, 0, 0, 4, 0, 0, 6, 2), \
(3, 0, 0, 5, 0, 7, 0, 0, 2), \
(0, 0, 5, 0, 0, 0, 3, 0, 0), \
(0, 4, 0, 3, 0, 6, 0, 5, 0), \
(6, 0, 0, 0, 0, 0, 0, 0, 8), \
(0, 1, 0, 2, 0, 8, 0, 3, 0), \
(0, 0, 7, 0, 0, 0, 4, 0, 0), \
(1, 0, 0, 8, 0, 2, 0, 0, 9), \
(0, 6, 0, 0, 9, 0, 0, 1, 0), \
])
print('Positive Quality Control Test:', isValidSudoku(posTest))
print('Negative Quality Control Test:', isValidSudoku(negTest))
print(generate_sudoku_puzzles(10000, 0))
Output:
Positive Quality Control Test: True
Negative Quality Control Test: False
Tried 10000 valid 31 yield 0.3 % Average Clues 40
[[0 0 2 3 0 0 0 7 8]
[7 8 9 1 2 0 0 0 0]
[5 0 0 0 9 0 0 3 0]
[0 0 0 6 7 8 0 0 2]
[0 2 0 0 0 0 7 8 9]
[8 0 0 2 3 0 0 0 0]
[0 0 0 0 0 2 3 0 5]
[0 5 6 0 8 9 1 2 0]
[0 3 0 5 0 0 0 9 0]]
Uncomment the two lines for puzzle source.
Here is a SQL Server stored procedure to generate Sudoku puzzles. I still need to remove values from the completed grid.
CREATE PROC dbo.sp_sudoku
AS
DROP TABLE IF EXISTS #cg
;
WITH cg
AS ( SELECT 1 AS g, 1 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS g, 2 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS g, 3 AS c, RAND() AS rnd
UNION ALL SELECT 2 AS g, 1 AS c, RAND() AS rnd
UNION ALL SELECT 2 AS g, 2 AS c, RAND() AS rnd
UNION ALL SELECT 2 AS g, 3 AS c, RAND() AS rnd
UNION ALL SELECT 3 AS g, 1 AS c, RAND() AS rnd
UNION ALL SELECT 3 AS g, 2 AS c, RAND() AS rnd
UNION ALL SELECT 3 AS g, 3 AS c, RAND() AS rnd)
, cg_seq
AS (SELECT g
, c
, row_number() over (partition by g
order by rnd) AS n
FROM cg)
SELECT g
, c + ((g - 1) * 3) AS c
, n + ((g - 1) * 3) AS n
INTO #cg
FROM cg_seq
--SELECT *
-- FROM #cg
-- ORDER BY g, c
DROP TABLE IF EXISTS #rg
;
WITH rg
AS ( SELECT 1 AS g, 1 AS r, RAND() AS rnd
UNION ALL SELECT 1 AS g, 2 AS r, RAND() AS rnd
UNION ALL SELECT 1 AS g, 3 AS r, RAND() AS rnd
UNION ALL SELECT 2 AS g, 1 AS r, RAND() AS rnd
UNION ALL SELECT 2 AS g, 2 AS r, RAND() AS rnd
UNION ALL SELECT 2 AS g, 3 AS r, RAND() AS rnd
UNION ALL SELECT 3 AS g, 1 AS r, RAND() AS rnd
UNION ALL SELECT 3 AS g, 2 AS r, RAND() AS rnd
UNION ALL SELECT 3 AS g, 3 AS r, RAND() AS rnd)
, rg_seq
AS (SELECT g
, r
, row_number() over (partition by g
order by rnd) AS n
FROM rg)
SELECT g
, r + ((g - 1) * 3) AS r
, n + ((g - 1) * 3) AS n
INTO #rg
FROM rg_seq
--SELECT *
-- FROM #rg
-- ORDER BY g, r
DROP TABLE IF EXISTS #r1
;
WITH r1
AS ( SELECT 1 AS r, 1 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 2 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 3 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 4 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 5 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 6 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 7 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 8 AS c, RAND() AS rnd
UNION ALL SELECT 1 AS r, 9 AS c, RAND() AS rnd)
, r1_seq
AS (SELECT r
, c
, row_number() over (order by rnd) AS n
FROM r1)
SELECT *
INTO #r1
FROM r1_seq
DROP TABLE IF EXISTS #r_tot
;
WITH r2
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM #r1)
, r3
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM r2)
, r4
AS (SELECT r + 3 AS r
, CASE WHEN c = 1 THEN c + 8
ELSE c - 1
END AS c
, n
FROM #r1)
, r5
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM r4)
, r6
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM r5)
, r7
AS (SELECT r + 6 AS r
, CASE WHEN c = 1 THEN c + 7
WHEN c = 2 THEN c + 7
ELSE c - 2
END AS c
, n
FROM #r1)
, r8
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM r7)
, r9
AS (SELECT r + 1 AS r
, CASE WHEN c > 6 THEN c - 6
ELSE c + 3
END AS c
, n
FROM r8)
, r_tot
AS (
SELECT * FROM #r1
UNION ALL SELECT * FROM r2
UNION ALL SELECT * FROM r3
UNION ALL SELECT * FROM r4
UNION ALL SELECT * FROM r5
UNION ALL SELECT * FROM r6
UNION ALL SELECT * FROM r7
UNION ALL SELECT * FROM r8
UNION ALL SELECT * FROM r9
)
SELECT *
INTO #r_tot
FROM r_tot
DROP TABLE IF EXISTS #r_tot2
;
SELECT g.n AS r
, r.c
, r.n
INTO #r_tot2
FROM #r_tot r
, #rg g
WHERE r.r = g.r
DROP TABLE IF EXISTS #c_tot2
;
SELECT r.r
, g.n AS c
, r.n
INTO #c_tot2
FROM #r_tot2 r
, #cg g
WHERE r.c = g.c
;
WITH c1 AS (SELECT r, n FROM #c_tot2 WHERE c = 1)
, c2 AS (SELECT r, n FROM #c_tot2 WHERE c = 2)
, c3 AS (SELECT r, n FROM #c_tot2 WHERE c = 3)
, c4 AS (SELECT r, n FROM #c_tot2 WHERE c = 4)
, c5 AS (SELECT r, n FROM #c_tot2 WHERE c = 5)
, c6 AS (SELECT r, n FROM #c_tot2 WHERE c = 6)
, c7 AS (SELECT r, n FROM #c_tot2 WHERE c = 7)
, c8 AS (SELECT r, n FROM #c_tot2 WHERE c = 8)
, c9 AS (SELECT r, n FROM #c_tot2 WHERE c = 9)
SELECT c1.r
, CAST(c1.n AS CHAR(2))
+ CAST(c2.n AS CHAR(2))
+ CAST(c3.n AS CHAR(2))
+ CAST(c4.n AS CHAR(2))
+ CAST(c5.n AS CHAR(2))
+ CAST(c6.n AS CHAR(2))
+ CAST(c7.n AS CHAR(2))
+ CAST(c8.n AS CHAR(2))
+ CAST(c9.n AS CHAR(2)) AS puzzle
FROM c1, c2, c3, c4, c5, c6, c7, c8, c9 WHERE c1.r = c2.r AND c3.r = c2.r AND c4.r = c3.r AND c5.r = c4.r AND c6.r = c5.r AND c7.r = c6.r AND c8.r = c7.r AND c9.r = c8.r
ORDER BY r
Related