Hello, everyone. Today, I will explain a program that outputs Sudoku answers using a method called depth-first search. It is difficult to explain the example, so please let us know in the comments if there are any deficiencies in the article.
n is a natural number, and N = n ^ 2. At this time, create a board consisting of a total of N ^ 2 squares with N rows and N columns, and divide it into n ^ 2 sections consisting of n rows and n columns with thick lines. 
At this time, write one number from 1 to N in each cell. However, all of the following three conditions shall be met.
There is a board (problem) in which numbers are written halfway, as in [Input example 1] and [Input example 2] below. Write the natural numbers 1,2,3, ..., N in the blanks on these boards, and create a program that outputs the board (answer) that satisfies the above conditions (A) to (C).
The method of creating a Sudoku answer creation program can be roughly divided into the following two stages.
The reason for checking only the squares (y, x) in 1 above is that recursion does not proceed. (In my experience, numbers are entered in only one square)
First, create a program to check whether the numbers 1 to N are used one by one in the vertical x column.
In the squares (x, 0), (x, 1), ..., (x, N-1), count the number of 1 to N in the array. At this time, True is returned if each number is used one by one, 1 is 1 and 2 is 1 ... N is 1, and False is returned if it is not used.
```python
#Find out if the answer is in the column
def checkQuestionRow(self,Row):
#An array that stores how many numbers from 1 to N are included
num = [0 for m in range((self.N + 1))]
#Vertical 0th column-vertical(N-1)Scan up to the column
for x in range(0,self.N):
#Find out how many 1 to N are included
for m in range(1,self.N+1):
#(x,Row)When the value of the square is m
if m == self.question[x][Row]:
#The number is the number of m+1
num[m] = num[m] + 1
#Column(x)Returns False if more than one number is used within
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
```
This can be judged in the same way as in the case of vertical (column). ```python def checkQuestionCol(self,Col): #An array that stores how many numbers from 1 to N are included num = [0 for m in range((self.N + 1))] #Horizontal 0th line-horizontal(N-1)Scan to the line for y in range(0,self.N): for m in range(1,self.N+1): if m == self.question[Col][y]: num[m] = num[m] + 1 #Returns False if more than one number is used in the line for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Blocks are judged as vertical colblocks, horizontal rowblocks, and so on. For example, in the case of 4 * 4 (n = 2, N = 4) Sudoku, the thick lines come to the 0th and 2nd. The thick line is 1 <= k <= n both vertically and horizontally, and it comes to the (k * n-1) th place. , K * nth is the start point, k * (n + 1) is the end point.
Replace this k with colBlock and rowBlock, and check whether the numbers 1 to N are included one by one from the start point to the end point of the vertical and horizontal blocks. ```python # 2*2，3*Check if one number from 1 to N appears for each block of 3 def checkQuestionBlock(self,rowBlock,colBlock): #Block starting point(colBlock* n ,rowBlock* n)Define startCol = colBlock * self.n startRow = rowBlock * self.n #Block end point(colBlock* {n+1} ,rowBlock* {n+1})Define endCol = (colBlock + 1) * (self.n) endRow = (rowBlock + 1) * (self.n) #An array that stores how many numbers from 1 to N are included num = [0 for m in range((self.N + 1))] #Scan block by block for y in range(startCol,endCol): for x in range(startRow,endRow): for m in range(1,self.N+1): if m == self.question[y][x]: num[m] = num[m] + 1 #Returns False if more than one number is used in the block for m in range(1,self.N+1): if num[m] > 1: return False return True ```
Finally, all the conditions (A) to (C) are summarized. If any of (A) to (C) is not satisfied, False is returned. ```python #Current(x,y)Find out if the solution is correct def checkQuestion(self,x,y):
#First, check if all Rows contain numbers from 1 to N
if self.checkQuestionRow(x) == False:
return False
#Next, check if all Cols contain numbers from 1 to N.
if self.checkQuestionCol(y) == False:
return False
#Finally, check if each block contains a number from 1 to N
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
<h2> 2: Put a number in the square (Depth-First Search) </ h2>
<p> To place numbers in Sudoku squares, follow the procedure below. </ p>
<ol> <li> Write the end condition of recursion. Recursion is aborted mainly when the column reaches N. </ li> <li> If a number is already placed in the square (y, x), the square (y, x + 1). When it is already at the end of the side, it recurses to the square (0, y + 1). </ li> <li> If the square (y, x) does not already have a number, first try putting a number from 1 to N in the square (y, x). As a result of putting it, True is returned when the conditions (A) to (C) are satisfied. In addition, recurse to the square (y, x + 1) or (0, y + 1) as in 2. </ li> <li> 3. If all the numbers from 1 to N do not meet the conditions in the square (y, x), before putting the value of the square (y, x) in {0} return. </ li> </ ol>
<p> In this way, digging one after another, and if the conditions are not met, go back one step and reconsider the search method as <b> Depth-First Search </ b>. To tell. </ p>
```python
#Search for Sudoku solutions rather than depth-first search
def solve(self,question,x=0,y=0):
#End recursion when you reach the next column after the last column
if x == 0 and y == self.N:
return True
#When a number is already placed in the square
if self.question[y][x] != 0:
#When you reach the last row, look at the beginning of the next column
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Examine the next line if it is not the last line
else:
if self.solve(self.question,x+1,y):
return True
#When no number is placed in the square
else:
for m in range(1,self.N+1):
#First, the number i is squared(x,y)Temporarily put in
self.question[y][x] = m
#If the judgment is passed, the square(x,y)Determine the value of with m
if self.checkQuestion(x,y) == True:
self.question[y][x] = m
#For debugging
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(m) + ")")
#When you reach the last row, look at the beginning of the next column
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
#Examine the next line if it is not the last line
else:
if self.solve(self.question,x+1,y):
return True
#If the judgment does not pass, restore the squares
self.question[y][x] = 0
return False
* In creating the program for this part, @ wsldenli's " Solving Sudoku with Python -Qiita I imitated.
Sudoku.py
import os
import sys
class Sudoku():
#Initialize data
def __init__(self):
#Small frame size
self.n = 2
#Define the outline and the end of the numerical value
self.N = self.n * self.n
#Initialize all array in question with 0
self.question = [[0 for i in range((self.N))] for j in range((self.N))]
#Find out if the answer is correct for rampant
def checkQuestionRow(self,Row):
#An array that stores how many numbers from 1 to N are included
num = [0 for m in range((self.N + 1))]
#Horizontal 0th line-horizontal(N-1)Scan to the line
for x in range(0,self.N):
#Find out how many 1 to N are included
for m in range(1,self.N+1):
#(x,Row)When the value of the square is m
if m == self.question[x][Row]:
#The number is the number of m+1
num[m] = num[m] + 1
#Returns False if more than one number is used in the column Row
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Vertical:Check if the numbers 1 to N appear one by one in column Col
#Basic, same behavior as checkQuestionRow
def checkQuestionCol(self,Col):
#An array that stores how many numbers from 1 to N are included
num = [0 for m in range((self.N + 1))]
#Vertical 0th column-horizontal(N-1)Scan up to the column
for y in range(0,self.N):
for m in range(1,self.N+1):
if m == self.question[Col][y]:
num[m] = num[m] + 1
#Returns False if more than one number is used in the column
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
# 2*2，3*Check if one number from 1 to N appears for each block of 3
def checkQuestionBlock(self,rowBlock,colBlock):
#Block starting point(colBlock* n ,rowBlock* n)Define
startCol = colBlock * self.n
startRow = rowBlock * self.n
#Block end point(colBlock* {n+1} ,rowBlock* {n+1})Define
endCol = (colBlock + 1) * (self.n)
endRow = (rowBlock + 1) * (self.n)
#An array that stores how many numbers from 1 to N are included
num = [0 for m in range((self.N + 1))]
#Scan block by block
for y in range(startCol,endCol):
for x in range(startRow,endRow):
for m in range(1,self.N+1):
if m == self.question[y][x]:
num[m] = num[m] + 1
#Returns False if more than one number is used in the block
for m in range(1,self.N+1):
if num[m] > 1:
return False
return True
#Current(x,y)Find out if the solution is correct
def checkQuestion(self,x,y):
#First check if all rows Row contain numbers up to N
if self.checkQuestionRow(x) == False:
return False
#Next, check if all columns Col contain numbers from 1 to N.
if self.checkQuestionCol(y) == False:
return False
#Finally, check if each block contains a number from 1 to N
colBlock = x // self.n
rowBlock = y // self.n
if self.checkQuestionBlock(colBlock,rowBlock) == False:
return False
return True
#Search for Sudoku solutions rather than depth-first search
def solve(self,question,x=0,y=0):
#End recursion when you reach the next column after the last column
if x == 0 and y == self.N:
return True
#When a number is already placed in the square
if self.question[y][x] != 0:
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
else:
if self.solve(self.question,x+1,y):
return True
#When no number is placed in the square
else:
for m in range(1,self.N+1):
self.question[y][x] = m
#For debugging
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
if self.checkQuestion(x,y) == True:
self.question[y][x] = m
if x == self.N-1:
if self.solve(self.question,0,y+1):
return True
else:
if self.solve(self.question,x+1,y):
return True
self.question[y][x] = 0
#For debugging
# print("(x,y,i) = (" + str(x) + "," + str(y) + "," + str(self.question[y][x]) + ")")
return False
#Main function
if __name__ == '__main__':
#Problem data
Sudoku = Sudoku()
Sudoku.question =[[1,0,3,4],[3,0,0,2],[0,3,0,0],[2,0,0,3]]
# Sudoku.question =[[4,0,0,0],[0,0,0,0],[1,0,4,0],[0,0,0,2]]
print("Question")
print(Sudoku.question)
Sudoku.solve(Sudoku.question,0,0)
print("Answer")
print(Sudoku.question)
Recommended Posts