当前位置：网站首页>Sudoku | Backtrack-7

Sudoku | Backtrack-7

2022-08-09 23:11:00 【acktomas】

数独 | 回溯-7

原文地址

Given a partially filled 9×9 二维数组“grid[9][9]”,The goal is to convert numbers（从 1 到 9）Assign to empty cells,for each row、Columns and sizes are 3×3 The subgrid contains exactly from 1 到 9 An instance of a number.

img

例子：

输入：
grid = { {3, 0, 6, 5, 0, 8, 4, 0, 0},
         {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
         {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
         {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
         {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
         {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
         {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
         {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
         {0, 0, 5, 2, 0, 6, 3, 0, 0} }
输出：
          3 1 6 5 7 8 4 9 2
          5 2 9 1 3 4 7 6 8
          4 8 7 6 2 9 5 3 1
          2 6 3 4 1 5 9 8 7
          9 7 4 8 6 3 1 2 5
          8 5 1 7 9 2 6 4 3
          1 3 8 9 4 7 2 5 6
          6 9 2 3 5 1 8 7 4
          7 4 5 2 8 6 3 1 9
说明：每行、每列和3*3的盒子
The output matrix contains unique numbers.

输入：    
gird = { { 3, 1, 6, 5, 7, 8, 4, 9, 2 },
         { 5, 2, 9, 1, 3, 4, 7, 6, 8 },
         { 4, 8, 7, 6, 2, 9, 5, 3, 1 },
         { 2, 6, 3, 0, 1, 5, 9, 8, 7 },
         { 9, 7, 4, 8, 6, 0, 1, 2, 5 },
         { 8, 5, 1, 7, 9, 2, 6, 4, 3 },
         { 1, 3, 8, 0, 4, 7, 2, 0, 6 },
         { 6, 9, 2, 3, 5, 1, 8, 7, 4 },
         { 7, 4, 5, 0, 8, 6, 3, 1, 0 } };
输出：
           3 1 6 5 7 8 4 9 2 
           5 2 9 1 3 4 7 6 8 
           4 8 7 6 2 9 5 3 1 
           2 6 3 4 1 5 9 8 7 
           9 7 4 8 6 3 1 2 5 
           8 5 1 7 9 2 6 4 3 
           1 3 8 9 4 7 2 5 6 
           6 9 2 3 5 1 8 7 4 
           7 4 5 2 8 6 3 1 9 
说明：每行、每列和3*3的盒子
The output matrix contains unique numbers.

推荐做法

Solve Sudoku

**方法1：**简单.

**方法：**The original method is to generate from 1 到 9 of all possible numeric configurations to fill empty cells.Try each configuration one by one,until the correct configuration is found,i.e. fill the slave for each unassigned location 1 到 9 的数字.After filling all unassigned positions,Check that the matrix is ​​correct.If printed correctly,The other situation will appear again.

算法：

  1. Create a function that checks if a given matrix is ​​a valid Sudoku.保留行、Columns and small boxes Hashmap.if any numbers are in hashMap The frequency in is greater than 1,则返回 false,否则返回 true;
  2. 创建一个递归函数,The function takes a grid and the current row and column indices as arguments.
  3. Check some basics.If the index is at the end of the matrix,即 i=N-1 且 j=N,then check that the mesh is correct,If correct print the grid and return true,否则返回 false.Another base case is when the column value is N 时,即 j = N,Then move to the next line,即 i++ 和 j = 0.
  4. If the current index is not assigned,Then remove the element from 1 填充到 9,and use the index of the next element（即 i、j+1）对所有 9 situation is repeated.If recursive call returns true,then break the loop and return true.
  5. If the current index is assigned,then the recursive function is called with the index of the next element,即 i, j+1

执行：

# N is the size of the 2D matrix N*N
N = 9

# A utility function to print grid
def printing(arr):
	for i in range(N):
		for j in range(N):
			print(arr[i][j], end = " ")
		print()

# Checks whether it will be
# legal to assign num to the
# given row, col
def isSafe(grid, row, col, num):

	# Check if we find the same num
	# in the similar row , we
	# return false
	for x in range(9):
		if grid[row][x] == num:
			return False

	# Check if we find the same num in
	# the similar column , we
	# return false
	for x in range(9):
		if grid[x][col] == num:
			return False

	# Check if we find the same num in
	# the particular 3*3 matrix,
	# we return false
	startRow = row - row % 3
	startCol = col - col % 3
	for i in range(3):
		for j in range(3):
			if grid[i + startRow][j + startCol] == num:
				return False
	return True

# Takes a partially filled-in grid and attempts
# to assign values to all unassigned locations in
# such a way to meet the requirements for
# Sudoku solution (non-duplication across rows,
# columns, and boxes) */
def solveSudoku(grid, row, col):

	# Check if we have reached the 8th
	# row and 9th column (0
	# indexed matrix) , we are
	# returning true to avoid
	# further backtracking
	if (row == N - 1 and col == N):
		return True
	
	# Check if column value becomes 9 ,
	# we move to next row and
	# column start from 0
	if col == N:
		row += 1
		col = 0

	# Check if the current position of
	# the grid already contains
	# value >0, we iterate for next column
	if grid[row][col] > 0:
		return solveSudoku(grid, row, col + 1)
	for num in range(1, N + 1, 1):
	
		# Check if it is safe to place
		# the num (1-9) in the
		# given row ,col ->we
		# move to next column
		if isSafe(grid, row, col, num):
		
			# Assigning the num in
			# the current (row,col)
			# position of the grid
			# and assuming our assigned
			# num in the position
			# is correct
			grid[row][col] = num

			# Checking for next possibility with next
			# column
			if solveSudoku(grid, row, col + 1):
				return True

		# Removing the assigned num ,
		# since our assumption
		# was wrong , and we go for
		# next assumption with
		# diff num value
		grid[row][col] = 0
	return False

# Driver Code

# 0 means unassigned cells
grid = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
		[5, 2, 0, 0, 0, 0, 0, 0, 0],
		[0, 8, 7, 0, 0, 0, 0, 3, 1],
		[0, 0, 3, 0, 1, 0, 0, 8, 0],
		[9, 0, 0, 8, 6, 3, 0, 0, 5],
		[0, 5, 0, 0, 9, 0, 6, 0, 0],
		[1, 3, 0, 0, 0, 0, 2, 5, 0],
		[0, 0, 0, 0, 0, 0, 0, 7, 4],
		[0, 0, 5, 2, 0, 6, 3, 0, 0]]

if (solveSudoku(grid, 0, 0)):
	printing(grid)
else:
	print("no solution exists ")

	# This code is contributed by sudhanshgupta2019a

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9

复杂性分析：

  • 时间复杂度：O(9^(n*n)).
    for each unassigned index,有 9 个可能的选项,因此时间复杂度为 O(9^(n*n)).
  • 空间复杂度：O(n*n).
    To store the output array,需要一个矩阵.

**方法2：**回溯.

方法：
像所有其他回溯问题一样,Sudoku can be solved by assigning numbers to empty cells one by one.before assigning numbers,Please check that the assignment is correct.Check the current line、current column and current 3X3 Whether the same number does not exist in the subgrid.After checking correctly,分配数字,and recursively check if this assignment is a solution.If the assignment does not yield a solution,Please try the next number for the currently empty cell.if not a number（1 到 9）获得一个解,则返回 false and prints that no solution exists.

算法：

  1. 创建一个函数,Check if the grid is incorrect after assigning the current index.为行、Columns and boxes are reserved Hashmap.if any numbers are in hashMap The frequency in is greater than 1,则返回 false,否则返回 true;hashMap It can be avoided by using loops.
  2. Create a recursive function on the grid.
  3. Check for any unassigned locations.Allocate a slave if it exists 1 到 9 的数字,Check if assigning a number to the current index makes the grid incorrect,If correct then recursively call slave 0 到 9 function for all correct cases.If any recursive call returns true,then end the loop and returntrue.Returns if there is no recursive call true,则返回 false.
  4. If there are no unassigned locations,则返回 true.

执行：

# A Backtracking program
# in Python to solve Sudoku problem

# A Utility Function to print the Grid
def print_grid(arr):
	for i in range(9):
		for j in range(9):
			print arr[i][j],
		print ('n')

		
# Function to Find the entry in the Grid that is still not used. Searches the grid to find an  entry that is still unassigned. 
# If found, the reference parameters row, col will be set the location that is unassigned, and true is  returned. 
# If no unassigned entries remains, false is returned.
# 'l' is a list variable that has  been passed from the solve_sudoku function to keep track of incrementation of Rows and Columns
# The ability to find unused entries in the grid,Search the grid for entries that are still unassigned.
# 如果找到,The parameter will be quotedrow、colSet to an unassigned location,并返回true.
# If there are no unassigned entries,则返回 false.
# 'l' 是一个从solve_sudokuList variables passed by the function,Used to track row and column increments
def find_empty_location(arr, l):
	for row in range(9):
		for col in range(9):
			if(arr[row][col]== 0):
				l[0]= row
				l[1]= col
				return True
	return False

# Returns a boolean which indicates whether any assigned entry in the specified row matches the given number.
# 返回一个布尔值,Indicates whether any allocation entry in the specified row matches the given number.
def used_in_row(arr, row, num):
	for i in range(9):
		if(arr[row][i] == num):
			return True
	return False

# Returns a boolean which indicates whether any assigned entry in the specified column matches the given number.
# 返回一个布尔值,Indicates whether any allocation entry in the specified column matches the given number.
def used_in_col(arr, col, num):
	for i in range(9):
		if(arr[i][col] == num):
			return True
	return False

# Returns a boolean which indicates whether any assigned entry within the specified 3x3 box matches the given number
# 返回一个布尔值,Indicate designation 3x3 Whether any assigned entry in the box matches the given number
def used_in_box(arr, row, col, num):
	for i in range(3):
		for j in range(3):
			if(arr[i + row][j + col] == num):
				return True
	return False

# Checks whether it will be legal to assign num to the given row, col 
# Returns a boolean which indicates whether it will be legal to assign num to the given row, col location.
# Check to specifyrow和colIs it legal to assign numbers,
# 返回一个布尔值,Indicates that a number is assigned to the designationrow和col 位置是否合法.
def check_location_is_safe(arr, row, col, num):
	
	# Check if 'num' is not already
	# placed in current row,
	# current column and current 3x3 box
	return not used_in_row(arr, row, num) and
		not used_in_col(arr, col, num) and
		not used_in_box(arr, row - row % 3,
						col - col % 3, num)

# Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a  way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes)
# Take a partially filled grid and try to assign values ​​to all unassigned positions in a way that meets the requirements of the Sudoku solution（跨行、Columns and boxes are not repeated）
def solve_sudoku(arr):
	
	# 'l' is a list variable that keeps the
	# record of row and col in
	# find_empty_location Function
	l =[0, 0]
	
	# If there is no unassigned
	# location, we are done
	if(not find_empty_location(arr, l)):
		return True
	
	# Assigning list values to row and col
	# that we got from the above Function
	row = l[0]
	col = l[1]
	
	# consider digits 1 to 9
	for num in range(1, 10):
		
		# if looks promising
		if(check_location_is_safe(arr,
						row, col, num)):
			
			# make tentative assignment
			arr[row][col]= num

			# return, if success,
			# ya !
			if(solve_sudoku(arr)):
				return True

			# failure, unmake & try again
			arr[row][col] = 0
			
	# this triggers backtracking	
	return False

# Driver main function to test above functions
if __name__=="__main__":
	
	# creating a 2D array for the grid
	grid =[[0 for x in range(9)]for y in range(9)]
	
	# assigning values to the grid
	grid =[[3, 0, 6, 5, 0, 8, 4, 0, 0],
		[5, 2, 0, 0, 0, 0, 0, 0, 0],
		[0, 8, 7, 0, 0, 0, 0, 3, 1],
		[0, 0, 3, 0, 1, 0, 0, 8, 0],
		[9, 0, 0, 8, 6, 3, 0, 0, 5],
		[0, 5, 0, 0, 9, 0, 6, 0, 0],
		[1, 3, 0, 0, 0, 0, 2, 5, 0],
		[0, 0, 0, 0, 0, 0, 0, 7, 4],
		[0, 0, 5, 2, 0, 6, 3, 0, 0]]
	
	# if success print the grid
	if(solve_sudoku(grid)):
		print_grid(grid)
	else:
		print "No solution exists"

# The above code has been contributed by Harshit Sidhwa.

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9

复杂性分析：

  • 时间复杂度： O(9^(nn)).
    for each unassigned index,有 9 个可能的选项,因此时间复杂度为 O(9^(n    n)).时间复杂度保持不变,But there will be some early pruning,So the time taken will be much less than the naive algorithm,But the upper bound time complexity remains the same.
  • 空间复杂度： O(n*n).
    To store the output array,需要一个矩阵.

方法 3：使用位掩码.

**方法：**This method is a slight optimization of the two methods above.为每一行/列/box to create a bitmask,And for each element in the grid place the position in the corresponding bitmask“值”处的位设置为 1,用于 O(1) 检查.

算法：

  1. 创建 3 个大小为 N 的数组（One for row、列和框）.
  2. The index of the box from 0 到 8.（In order to find the box index of the element,我们使用以下公式：行 / 3 * 3 + 列 / 3）.
  3. First map the initial values ​​of the grid.
  4. every time we are on the grid中添加/删除元素时,Mask the corresponding bits的位设置为 1/0.

执行：

# N is the size of the 2D matrix N*N
N = 9

# A utility function to print grid
def printing(arr):
	for i in range(N):
		for j in range(N):
			print(arr[i][j], end = " ")
		print()

# Checks whether it will be
# legal to assign num to the
# given row, col
def isSafe(grid, row, col, num):

	# Check if we find the same num
	# in the similar row , we
	# return false
	for x in range(9):
		if grid[row][x] == num:
			return False

	# Check if we find the same num in
	# the similar column , we
	# return false
	for x in range(9):
		if grid[x][col] == num:
			return False

	# Check if we find the same num in
	# the particular 3*3 matrix,
	# we return false
	startRow = row - row % 3
	startCol = col - col % 3
	for i in range(3):
		for j in range(3):
			if grid[i + startRow][j + startCol] == num:
				return False
	return True

# Takes a partially filled-in grid and attempts
# to assign values to all unassigned locations in
# such a way to meet the requirements for
# Sudoku solution (non-duplication across rows,
# columns, and boxes) */
def solveSudoku(grid, row, col):

	# Check if we have reached the 8th
	# row and 9th column (0
	# indexed matrix) , we are
	# returning true to avoid
	# further backtracking
	if (row == N - 1 and col == N):
		return True
	
	# Check if column value becomes 9 ,
	# we move to next row and
	# column start from 0
	if col == N:
		row += 1
		col = 0

	# Check if the current position of
	# the grid already contains
	# value >0, we iterate for next column
	if grid[row][col] > 0:
		return solveSudoku(grid, row, col + 1)
	for num in range(1, N + 1, 1):
	
		# Check if it is safe to place
		# the num (1-9) in the
		# given row ,col ->we
		# move to next column
		if isSafe(grid, row, col, num):
		
			# Assigning the num in
			# the current (row,col)
			# position of the grid
			# and assuming our assigned
			# num in the position
			# is correct
			grid[row][col] = num

			# Checking for next possibility with next
			# column
			if solveSudoku(grid, row, col + 1):
				return True

		# Removing the assigned num ,
		# since our assumption
		# was wrong , and we go for
		# next assumption with
		# diff num value
		grid[row][col] = 0
	return False

# Driver Code

# 0 means unassigned cells
grid = [[3, 0, 6, 5, 0, 8, 4, 0, 0],
		[5, 2, 0, 0, 0, 0, 0, 0, 0],
		[0, 8, 7, 0, 0, 0, 0, 3, 1],
		[0, 0, 3, 0, 1, 0, 0, 8, 0],
		[9, 0, 0, 8, 6, 3, 0, 0, 5],
		[0, 5, 0, 0, 9, 0, 6, 0, 0],
		[1, 3, 0, 0, 0, 0, 2, 5, 0],
		[0, 0, 0, 0, 0, 0, 0, 7, 4],
		[0, 0, 5, 2, 0, 6, 3, 0, 0]]

if (solveSudoku(grid, 0, 0)):
	printing(grid)
else:
	print("no solution exists ")

# This code is contributed by sanjoy_62.

输出

3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9

复杂性分析：

  • 时间复杂度：O(9^(n*n)).for each unassigned index,有 9 个可能的选项,因此时间复杂度为 O(9^(n*n)).时间复杂度保持不变,But it's much faster to check if a number can be used correctly,O(1).
  • 空间复杂度：O(n*n).To store the output array,需要一个矩阵,And the bitmask is required 3 The extra size is n 的数组.
原网站

版权声明
本文为[acktomas]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/221/202208091945443822.html

边栏推荐

猜你喜欢

随机推荐