Last Updated on 2021-04-10 by Clay
Do you know a game it named "Sudoku"? It's a puzzle which is formed from numbers, I thick it's fans are everywhere. (Just like my mom.)
First, I quote the introduction of Wikipedia:
Sudokuย (ๆฐ็ฌย sลซdoku, digit-single)ย (/suหหdoสkuห/,ย /-หdษk-/,ย /sษ-/, originally calledย Number Place)[1]ย is aย logic-based,[2][3]ย combinatorial[4]ย number-placementย puzzle. The objective is to fill a 9ร9 grid with digits so that each column, each row, and each of the nine 3ร3 subgrids that compose the grid (also called "boxes", "blocks", or "regions") contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.
Wiki
Put the figures:
Today I want to note a small practice program when I learning Python.
Although there aren't any great skill and code, and there are a lot of things that can be optimized, but the solving program is started with my Python.
And then, let me introduce it to you!
Solution
Sudoku has only a few simple rules:
- The numbers in a row are not repeated
- The numbers in a column are not repeated
- Numbers within the 9-square grid (3x3) are not repeated
- All rows, columns, and squares are composed of 1 to 9
How is it? Very simple?
My program is divided into two parts:
At first, when we initialize our topic, first I will judge the "only one solution", that is, traverse the entire board and find only one solution on the board. Place it, then fill in that single solution.
When we still find such a "unique solution", my program will run endlessly until I can't find any answer.
Of course this way of programming is not enough to complete the Sudoku problem! (Some simple problem maybe.) Sudoku problems often have a "temporary" situation that does not reveal the "what is the correct solution" in the plural answer.
And then, we must use some violent solution of the program! Using the concept of "recursive", I will continue to fill in the possible answers. If I find that the board has not been filled and there is no answer, but the board has not been completed yet, we will go back to the previous layer and exclude us. Fill in this solution and continue to look for positive solutions.
I think everyone can hear that the second part of "recursive" is much more complicated than the first part of "filling in a unique solution".
This is why we need the first part to simplify the board.
Code
# -*- coding: utf-8 -*- import time class Sudoku: def __init__(self, board=None): self.board = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [3, 4, 0, 0, 5, 0, 0, 0, 1], [6, 0, 5, 0, 2, 0, 4, 3, 0], [5, 0, 0, 0, 0, 9, 8, 1, 0], [0, 9, 0, 6, 0, 0, 0, 0, 5], [4, 0, 0, 0, 0, 1, 2, 7, 0], [2, 0, 8, 0, 9, 0, 1, 6, 0], [1, 6, 0, 0, 4, 0, 0, 0, 7], [0, 0, 4, 0, 0, 0, 0, 0, 0]] if board: self.board = board self.position_state = [[[n for n in range(1, 10)] for a in range(9)] for b in range(9)] self.set_list = [] self.iter_times = 0 self.board_num = self.set_num() def board_plot(self): for _ in range(9): print(self.board[_]) print('-------------------------------------', self.set_num()) def only_one_check(self, x, y): row = self.board[x] column = [self.board[_][y] for _ in range(9)] new_x = x//3*3 new_y = y//3*3 square = [self.board[a][b] for a in range(new_x, new_x+3) for b in range(new_y, new_y+3)] total_collision_num_list = list(set(row + column + square)) total_num_list = [1, 2, 3, 4, 5, 6, 7, 8, 9] for _ in total_collision_num_list: if _ in total_num_list: total_num_list.remove(_) if len(total_num_list) == 1: return total_num_list[0] else: return False def row_check(self, x, y, n): if n in self.board[x]: return True def column_check(self, x, y, n): column_list = [self.board[_][y] for _ in range(9)] if n in column_list: return True def square_check(self, x, y, n): new_x = x//3*3 new_y = y//3*3 square_list = [self.board[a][b] for a in range(new_x, new_x+3) for b in range(new_y, new_y+3)] if n in square_list: return True # count the number we set into the board def set_num(self): num = 0 for a in range(9): for b in range(9): if self.board[a][b] != 0: num += 1 return num def board_num_add_check(self, n): board_num_now = self.set_num() if board_num_now > n: return True, board_num_now else: return False, board_num_now def simplify_sudoku(self, n): self.board_plot() for a in range(9): for b in range(9): if self.board[a][b] == 0: result = self.only_one_check(a, b) if not result: continue else: self.board[a][b] = result test, num = self.board_num_add_check(n) if test: self.board_plot() x, y = self.simplify_sudoku(num) return x, y else: return 0, 0 def check_end(self): for a in range(9): if 0 in self.board[a]: return False return True def run(self): global i, j while True: if self.board[i][j] == 0: if self.position_state[i][j]: n = self.position_state[i][j].pop() if self.row_check(i, j, n) or self.column_check(i, j, n) or self.square_check(i, j, n): continue else: self.board[i][j] = n self.board_plot() self.set_list.append([i, j]) result = self.check_end() if not result: if j == 8: i += 1 j = 0 else: j += 1 else: print('The End') break else: self.position_state[i][j] = [_ for _ in range(1, 10)] i, j = self.set_list.pop() print(i, j) self.board[i][j] = 0 else: if j == 8: i += 1 j = 0 else: j += 1 if __name__ == '__main__': startTime = time.time() sudoku = Sudoku() i, j = sudoku.simplify_sudoku(sudoku.board_num) result = sudoku.check_end() if result: print('The End') else: sudoku.run() print('cost:', time.time()-startTime, 's')
Output:
[7, 8, 9, 3, 1, 4, 6, 5, 2]
[3, 4, 2, 8, 5, 6, 7, 9, 1]
[6, 1, 5, 9, 2, 7, 4, 3, 8]
[5, 2, 7, 4, 3, 9, 8, 1, 6]
[8, 9, 1, 6, 7, 2, 3, 4, 5]
[4, 3, 6, 5, 8, 1, 2, 7, 9]
[2, 5, 8, 7, 9, 3, 1, 6, 4]
[1, 6, 3, 2, 4, 5, 9, 8, 7]
[9, 7, 4, 1, 6, 8, 5, 2, 3]
------------------------------------- 81
The End
cost: 0.013887643814086914 sIt's very long, so please smile to it.
I will explain my program briefly. Because there are too many lines, I will only explain the basic functions of the important class of Sudoku.
__init()__:
This part is to initialize the board, you can fill in the questions you want to solve.
board_plot():
Plot the board.
only_one_check():
This is the first stage of the talk, "Looking for a unique solution," which is quite simple.
row_check():
Determine if the value we filled in is in the row
column_check():
Determine if the value we filled in is in the column.
square_check():
Determine if the value we filled in is in the square.
check_end():
Determine if the board is filled.
run():
Carry out the recursion and gradually find the Sudoku solution. (that is, the second part)
By the way, I also put all the code on github, welcome everyone to leave a message, or give star to support =)
https://github.com/ccs96307/Sudoku
Future Work
What you can still think of now is to make a GUI! When I was writing this program, I actually tried to use Pygame to make a somewhat ugly interface, but because of the bugs that occurred when I was running multiple times, and then there were other things to be busy at the time, I was temporarily on hold.
If there are more chapter about Sudoku, maybe I will re-write a good-looking interface again.
If you want to learn the basics of Python, let me refer to what I wrote: Python Tutorial
Thank you for your reading!