# How to create a Sudoku puzzle in Python

## How to create a Sudoku puzzle in Python

You can generate a random sudoku solution board where all numbers are filled in and then remove some of them to create the puzzle. This will ensure that the puzzle always has a solution. Making sure that it has exactly one solution is a bit more challenging (hint: you must leave at least 17 numbers for a 9×9 sudoku)

The algorithm below will generate a NxN random sudoku solution board instantly for N < 1000.

``````base  = 3
side  = base*base

# pattern for a baseline valid solution
def pattern(r,c): return (base*(r%base)+r//base+c)%side

# randomize rows, columns and numbers (of valid base pattern)
from random import sample
def shuffle(s): return sample(s,len(s))
rBase = range(base)
rows  = [ g*base + r for g in shuffle(rBase) for r in shuffle(rBase) ]
cols  = [ g*base + c for g in shuffle(rBase) for c in shuffle(rBase) ]
nums  = shuffle(range(1,base*base+1))

# produce board using randomized baseline pattern
board = [ [nums[pattern(r,c)] for c in cols] for r in rows ]

for line in board: print(line)

[6, 2, 5, 8, 4, 3, 7, 9, 1]
[7, 9, 1, 2, 6, 5, 4, 8, 3]
[4, 8, 3, 9, 7, 1, 6, 2, 5]
[8, 1, 4, 5, 9, 7, 2, 3, 6]
[2, 3, 6, 1, 8, 4, 9, 5, 7]
[9, 5, 7, 3, 2, 6, 8, 1, 4]
[5, 6, 9, 4, 3, 2, 1, 7, 8]
[3, 4, 2, 7, 1, 8, 5, 6, 9]
[1, 7, 8, 6, 5, 9, 3, 4, 2]
``````

You can then remove some of the numbers from the sudoku solution to create the puzzle:

``````squares = side*side
empties = squares * 3//4
for p in sample(range(squares),empties):
board[p//side][p%side] = 0

numSize = len(str(side))
for line in board: print([+  .join(f{n or .:{numSize}} for n in line)+])

[6  .  .  .  .  3  .  .  1]
[.  9  .  .  .  .  .  .  3]
[4  .  3  .  .  .  6  .  .]
[.  .  .  5  9  .  2  .  6]
[.  .  .  .  .  .  .  .  .]
[.  .  7  .  .  .  .  .  4]
[.  .  .  .  .  .  1  7  .]
[.  .  2  .  .  8  .  .  .]
[.  .  8  .  .  .  .  4  2]
``````

For 4×4 up to 36×36 puzzles, you could make a nicer print of the board like this:

``````def expandLine(line):
return line+line[5:9].join([line[1:5]*(base-1)]*base)+line[9:13]
line0  = expandLine(╔═══╤═══╦═══╗)
line1  = expandLine(║ . │ . ║ . ║)
line2  = expandLine(╟───┼───╫───╢)
line3  = expandLine(╠═══╪═══╬═══╣)
line4  = expandLine(╚═══╧═══╩═══╝)

symbol =  1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ
nums   = [ []+[symbol[n] for n in row] for row in board ]
print(line0)
for r in range(1,side+1):
print( .join(n+s for n,s in zip(nums[r-1],line1.split(.))) )
print([line2,line3,line4][(r%side==0)+(r%base==0)])

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 6 │   │   ║   │   │ 3 ║   │   │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 9 │   ║   │   │   ║   │   │ 3 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 4 │   │ 3 ║   │   │   ║ 6 │   │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║ 5 │ 9 │   ║ 2 │   │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 7 ║   │   │   ║   │   │ 4 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │   ║   │   │   ║ 1 │ 7 │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 2 ║   │   │ 8 ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 8 ║   │   │   ║   │ 4 │ 2 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
``````

[EDIT]

Here are some additional information on the shuffling process …

Shuffling rows is broken down in groups of 3 rows. It is ok to swap groups as a whole but we cant swap rows across groups without breaking the integrity of the blocks. (the same reasoning applies to columns)

For example:

``````0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase)
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
|
3 [8, 1, 4,  5, 9, 7,  2, 3, 6]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
|
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

* for g in shuffle(rBase)
``````

We can swap groups 0,1,2 by moving all 3 of their rows at the same time:

``````3 [8, 1, 4,  5, 9, 7,  2, 3, 6]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -|     -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
|
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -| *   -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|
|
0 [6, 2, 5,  8, 4, 3,  7, 9, 1]            |     -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase)
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|

* for g in shuffle(rBase)
``````

And we can swap between the 3 rows of a group (e.g. 3,4,5) …

``````0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3] |  group 0 -|     -| r in shuffle(rBase)
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
|
5 [9, 5, 7,  3, 2, 6,  8, 1, 4]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
3 [8, 1, 4,  5, 9, 7,  2, 3, 6] /           |     -|
|
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

* for g in shuffle(rBase)
``````

We CANNOT swap rows across groups (e.g. 1 <–> 3):

``````0 [6, 2, 5,  8, 4, 3,  7, 9, 1]                  -|
3 [8, 1, 4,  5, 9, 7,  2, 3, 6] |  group 0 -|     -| r in shuffle(rBase)
2 [4, 8, 3,  9, 7, 1,  6, 2, 5] /           |     -|
|
1 [7, 9, 1,  2, 6, 5,  4, 8, 3]            |     -|
4 [2, 3, 6,  1, 8, 4,  9, 5, 7] |  group 1 -| *   -| r in shuffle(rBase)
5 [9, 5, 7,  3, 2, 6,  8, 1, 4] /           |     -|
|
6 [5, 6, 9,  4, 3, 2,  1, 7, 8]            |     -|
7 [3, 4, 2,  7, 1, 8,  5, 6, 9] |  group 2 -|     -| r in shuffle(rBase)
8 [1, 7, 8,  6, 5, 9,  3, 4, 2] /                 -|

* for g in shuffle(rBase)
``````

See the duplicate 8 in the top left block, duplicate 7 below that, etc.

Single solution puzzle

In order to generate a sudoku puzzle with only one solution you will need a solver function that can tell you if there are more than one solution. The strategy I would suggest is to start with 75% (or more) of the numbers removed, then check that there is only one solution. If there is more than one solution, put back a number and check again. You can put back a number at a random position or select a position where the solutions differ (which will converge faster to a single solution puzzle)

First write a solver that will generate all solutions that it finds (ideally as a generator because we only need the first 2). Heres a simple one:

``````def shortSudokuSolve(board):
size    = len(board)
block   = int(size**0.5)
board   = [n for row in board for n in row ]
span    = { (n,p): { (g,n)  for g in (n>0)*[p//size, size+p%size, 2*size+p%size//block+p//size//block*block] }
for p in range(size*size) for n in range(size+1) }
empties = [i for i,n in enumerate(board) if n==0 ]
used    = set().union(*(span[n,p] for p,n in enumerate(board) if n))
empty   = 0
while empty>=0 and empty<len(empties):
pos        = empties[empty]
used      -= span[board[pos],pos]
board[pos] = next((n for n in range(board[pos]+1,size+1) if not span[n,pos]&used),0)
used      |= span[board[pos],pos]
empty     += 1 if board[pos] else -1
if empty == len(empties):
solution = [board[r:r+size] for r in range(0,size*size,size)]
yield solution
empty -= 1
``````

Starting with a `solution` variable with all numbers present and `board` variable containing the puzzle with 3/4 of numbers cleared, you can add numbers back to the board until there is only one way to solve it:

``````solution=[[9, 5, 3, 1, 6, 7, 4, 2, 8],
[4, 2, 8, 3, 5, 9, 7, 6, 1],
[7, 6, 1, 8, 2, 4, 9, 5, 3],
[5, 8, 4, 9, 3, 6, 2, 1, 7],
[6, 3, 9, 7, 1, 2, 5, 8, 4],
[2, 1, 7, 4, 8, 5, 6, 3, 9],
[3, 4, 5, 6, 9, 1, 8, 7, 2],
[8, 7, 2, 5, 4, 3, 1, 9, 6],
[1, 9, 6, 2, 7, 8, 3, 4, 5]]
board=[ [0, 0, 0, 0, 0, 0, 0, 0, 8],
[0, 2, 0, 0, 5, 0, 7, 6, 0],
[0, 6, 0, 0, 0, 0, 0, 0, 3],
[5, 0, 0, 0, 0, 0, 2, 0, 7],
[0, 3, 0, 0, 1, 0, 0, 0, 0],
[2, 0, 0, 4, 0, 0, 0, 3, 0],
[0, 0, 0, 6, 0, 0, 0, 0, 0],
[8, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 2, 7, 0, 0, 4, 0]]

import random
from itertools import islice
while True:
solved  = [*islice(shortSudokuSolve(board),2)]
if len(solved)==1:break
diffPos = [(r,c) for r in range(9) for c in range(9)
if solved[r][c] != solved[r][c] ]
r,c = random.choice(diffPos)
board[r][c] = solution[r][c]
``````

output:

``````╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║   │   │   ║   │   │ 7 ║   │   │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 2 │   ║   │ 5 │   ║ 7 │ 6 │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 6 │   ║ 8 │   │ 4 ║   │   │ 3 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║ 5 │   │   ║   │   │   ║ 2 │   │ 7 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 3 │   ║   │ 1 │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 2 │   │   ║ 4 │   │   ║   │ 3 │   ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │ 4 │   ║ 6 │   │   ║   │   │   ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 8 │   │   ║   │   │   ║ 1 │   │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║ 1 │   │   ║ 2 │ 7 │   ║   │ 4 │   ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝
``````

Note that this will work in a reasonable time for 9×9 sudoku boards but you will need a much better/faster solver function for larger boards

This should work.

``````def sudoku(size):
import time
start_time=time.time()

import sys
import random as rn
mydict = {}
n = 0
print --started calculating--
while len(mydict) < 9:
n += 1
x = range(1, size+1)
testlist = rn.sample(x, len(x))

isgood = True
for dictid,savedlist in mydict.items():
if isgood == False:
break
for v in savedlist:
if testlist[savedlist.index(v)] == v:
isgood = False
break

if isgood == True:
isgoodafterduplicatecheck = True
mod = len(mydict) % 3
dsavedlists = {}
dtestlists = {}
dcombindedlists = {}
for a in range(1,mod + 1):
savedlist = mydict[len(mydict) - a]
for v1 in savedlist:
modsavedlists = (savedlist.index(v1) / 3) % 3
dsavedlists[len(dsavedlists)] = [modsavedlists,v1]
for t1 in testlist:
modtestlists = (testlist.index(t1) / 3) % 3
dtestlists[len(dtestlists)] = [modtestlists,t1]
for k,v2 in dsavedlists.items():
dcombindedlists[len(dcombindedlists)] = v2
dcombindedlists[len(dcombindedlists)] = dtestlists[k]
vsave = 0
lst1 = []
for k, vx in dcombindedlists.items():
vnew = vx
if not vnew == vsave:
lst1 = []
lst1.append(vx)
else:
if vx in lst1:
isgoodafterduplicatecheck = False
break
else:
lst1.append(vx)
vsave = vnew

if isgoodafterduplicatecheck == True:

mydict[len(mydict)] = testlist
print success found, len(mydict), row

print --finished calculating--
total_time = time.time()-start_time
return mydict, n, total_time

return_dict, total_tries, amt_of_time = sudoku(9)
print
print --printing output--
for n,v in return_dict.items():
print n,v
print process took,total_tries,tries in, round(amt_of_time,2), secs
print -------------------
``````

#### How to create a Sudoku puzzle in Python

If your goal is to create 9 x 9 Sudoku, then why not a simpler program?
Works on any of n^2 x n^2 (boards) in poly-time. To create a puzzle, you may have to remove elements manually. Guaranteeing one solution requires some backtracking. Poly-time is what you want for larger n^2 x n^2 Sudoku Latin-Squares.

``````#Provide a list of non-repeating n-elements to output a valid sudoku grid.
#this code runs on python3
print(enter with [1,2,3...] brackets)
tup = input()[1:-1].split(,)
#Input required to map out valid n x m or n^2 x n^2 Sudoku Grid
x = input(Enter mapping valid Sudoku eg. 3 for 9 x 9:)
e = input(Enter 9 for 9 x 9 ...12 for 12 x 12:)
f = input(Enter 3 if its a 9 x 9 ... n^2 x n^2:)
x = int(x)
e = int(e)
f = int(f)
#Manipulation of Elements to prepare valid grid
squares = []
for i in range(len(tup)):
squares.append(tup[i:] + tup[:i])

#Everything below here is just printing
for s in range(x):
for d in range(0,e,f):
for si in range(s,e,f):
for li in range(d,d+f):
print(squares[si][li], end = )
print()

#Remember that if you want
#to create a single board of n^2 x n^2
#you need to edit the below
#for a valid grid
#for example
#a 9 x 9
#would be a 3 x 3
#and so on.
``````

No repeating elements!
Also, please remember that you need to know multiplication to output a properly mapped n^2 x n^2. For example, a 25 x 25
should be a 5 x 5 for the inputs as follows

For x, x = 5

For e, e = 25

for f, f = 5

Also, I had a buddy who helped me convert my algorithm into this python code for my amateur Sudoku project. Thanks to that Reddit user.

By the way, its actually O(m^2) time.
Proof

Thank you Reddit buddy for the help.