In the past, about a year ago, when I was first learning Python, I wrote a "Sudoku problem solving program" as an exercise. After that, I had a brief Clean Code, but I didn’t know anything about this program. Too much optimization. ([Python] Use Program to solve Sudoku problem)
I have always been very ashamed. Firstly, the code of that program is not easy to read, and secondly, when encountering advanced problems, the speed of solving problems is not fast. For example, I challenged the world's most difficult Sudoku problem called "11 Star" (https://newtalk.tw/news/view/2012-06-30/26670):
40 seconds! It took too long! In view of this, taking advantage of my more free time recently, I re-written a faster version.
So, let me record it below!
First of all, my original program uses recursion, but just like my classmate said: recursion is something that a master uses! For a mortal like me, it's almost enough to write a For loop.
import time # Settings start_time = time.time() class Sudoku(): def __init__(self, board): self.board = board self.size = len(self.board[0]) self.choices = [-1 if self.board[i][j] else 1 for i in range(self.size) for j in range(self.size)] self.x = 0 self.y = 0 def plot(self): cn = 0 for row in self.board: print(row) for _ in row: if _ != 0: cn += 1 print('===========================', cn) def row(self, n): return n in self.board[self.y] def col(self, n): return n in [self.board[_][self.x] for _ in range(9)] def square(self, n): return n in [self.board[b][a] for a in range(self.x//3*3, self.x//3*3+3) for b in range(self.y//3*3, self.y//3*3+3)] def collision(self, n): if self.row(n) or self.col(n) or self.square(n): return True else: return False def backward(self): self.board[self.y][self.x] = 0 self.choices[self.c] = 1 if self.x == 0: self.x = 8 self.y -= 1 else: self.x -= 1 while self.choices[self.y * self.size + self.x] == -1: if self.x == 0: self.x = 8 self.y -= 1 else: self.x -= 1 def forward(self): if self.x == 8: self.x = 0 self.y += 1 else: self.x += 1 def isEnd(self): for row in self.board: if 0 in row: return False return True def run(self): while not self.isEnd(): self.c = self.y*self.size+self.x if self.choices[self.c] != -1: if self.collision(self.choices[self.c]): # Error if self.choices[self.c] != 9: self.choices[self.c] += 1 continue # Back else: self.backward() # Success else: self.board[self.y][self.x] = self.choices[self.c] # plot() self.forward() else: self.forward() self.plot() print('time:', time.time()-start_time) if __name__ == '__main__': board = [[8, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [0, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [0, 9, 0, 0, 0, 0, 4, 0, 0]] s = Sudoku(board) s.run()
Output:
The same problem was shortened from 40 seconds to 1 second. I hope that my programming skills will increase by about 40 times.
The following is the Github URL of my Sudoku program: https://github.com/ccs96307/Sudoku, everyone is welcome to visit it freely.