preface

Use Python to solve sudoku. The reason is: it is too hard to solve sudoku by yourself.

Code effect display

The tools required

Python version: 3.5.4

The main idea

The idea is simple:

Enumerate the number that can be filled in each blank first, then search deeply to solve sudoku.

The rules of Sudoku are:

Each puzzle consists of a 9×9 grid with a number of hints at different locations. The object of the game is to fill the empty squares with numbers so that each row, column, and 3×3 house does not have a duplicate number.

Code implementation

# point class
class point() :
	def __init__(self, x, y) :
		self.x = x
		self.y = y
		self.available = []
		self.value = 0


The number of lines on which this space is located
def rowNum(p ,sudoku) :
	# set is used to remove weights because there is more than one 0!
	row = set(sudoku[p.y*9: (p.y+1) *9])
	row.remove(0)
	return row


# What number is in the column where the space is
def colNum(p, sudoku) :
	col = []
	length = len(sudoku)
	for j in range(p.x, length, 9):
		col.append(sudoku[j])
	col = set(col)
	col.remove(0)
	return col


# This space is located in the number of small nine
def blockNum(p, sudoku) :
	block_x = p.x//3
	block_y = p.y//3
	block = []
	start_point = block_y*3*9 + block_x*3
	for j in range(start_point, start_point+3):
		block.append(sudoku[j])
	for j in range(start_point+9, start_point+9+3):
		block.append(sudoku[j])
	for j in range(start_point+9+9, start_point+9+9+3):
		block.append(sudoku[j])
	block = set(block)
	block.remove(0)
	return block


Initialize;
List the possible points for each blank first
The numbers 1, 2, and 3 are in the ninth house
# then the space can only be filled with a number of 4, 5, 6, 7, 8, 9
def initialize(sudoku) :
	sudokuList = []
	length = len(sudoku)
	for index in range(length):
		# Find the unit that needs to be filled in, i.e. space
		if sudoku[index] == 0:
			p = point(index%9, index//9)
			for i in range(1.10) :# if there is no I in any of the rows, columns, or small nine houses
				if (i not in rowNum(p, sudoku)) and (i not in colNum(p, sudoku)) and (i not in blockNum(p, sudoku)):
					p.available.append(i)
			sudokuList.append(p)
	return sudokuList


# Check if the number satisfies the sudoku rule after filling in the space
def check(p, sudoku) :
	if p.value == 0:
		return False
	if (p.value not in rowNum(p, sudoku)) and (p.value not in colNum(p, sudoku)) and (p.value not in blockNum(p, sudoku)):
		return True
	else:
		return False


# Show sudoku results
def showResult(sudoku) :
	for r in range(9) :for c in range(9) :print('%d ' % (sudoku[r*9+c]), end=' ')
		print(' ')


# Deep search to solve Sudoku
def solve(p, sudoku) :
	available_Num = p.available
	for ava in available_Num:
		p.value = ava
		if check(p, sudoku):
			sudoku[p.y*9+p.x] = p.value
			if len(sudokuList) < 1:
				showResult(sudoku)
				exit()
			p_next = sudokuList.pop()
			solve(p_next, sudoku)
			sudoku[p_next.y*9+p_next.x] = 0
			sudoku[p.y*9+p.x] = 0
			p_next.value = 0
			sudokuList.append(p_next)
		else:
			pass


if __name__ == '__main__':
	# 0 represents the cells to be filled in, namely Spaces
	sudoku = [
				0.0.0.0.0.0.0.0.0.0.9.3.6.2.8.1.4.0.0.6.0.0.0.0.0.5.0.0.3.0.0.1.0.0.9.0.0.5.0.8.0.2.0.7.0.0.4.0.0.7.0.0.6.0.0.8.0.0.0.0.0.3.0.0.1.7.5.9.3.4.2.0.0.0.0.0.0.0.0.0.0, 
			]
	sudokuList = initialize(sudoku)
	print('Sudoku title: \n')
	showResult(sudoku)
	print(The solution of '\n sudoku is: \n')
	p_first = sudokuList.pop()
	solve(p_first, sudoku)
Copy the code