程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

Program code for solving Sudoku in Python

編輯:Python

By chance linux One attached to the system Sudoku game , Open and play a few . But he is a novice Sudoku , I haven't played before , There is no way to get out of a few steps .

So I plan to solve Sudoku violently with the help of the powerful computing power of the computer , It's still fun .

The following is a record of my thoughts and experiences in writing Sudoku programs .

One . The basic solution to Sudoku

Programming in general , It's a methodology . Whatever the procedure , The problem solving process must be decomposed into several simple methods that can be realized by the computer . It is said that , The greatest truths are the simplest . I can only understand 0 and 1 For your computer , It is more necessary to subdivide the steps , Step by step to solve the problem .

First of all, let's think about the basic concept of Sudoku .

Sudoku has eighty-one grids in total , At the same time, it is divided into 9 Nine squares . The rules are simple —— You need the number in each cell , It is guaranteed that there are no same numbers in the horizontal and vertical rows and the nine palaces .

So our general idea is , Try to fill in the number from the first blank , from 1 Start filling in , If 1 If you don't meet the requirement that there is no repetition in the horizontal and vertical nine palaces , Then fill in 2 , And so on , Until you fill in a number that temporarily satisfies the rule , Break this box , Move to the next space and repeat the process .

If you reach a certain space, you will find that there are countless options , It means that the previous box is filled in incorrectly , Then go back to the previous grid , Continue from the break in the previous box to 9 Try , Until I go back to the wrong box .

In this case , We can sort out the important steps :

• Find the next space
• Fill in the numbers in the box in turn 1 To 9
• Recursively determine whether the filled number conforms to the rule

Two . Program

The first test of Sudoku was conducted by the Finnish mathematician inkara 3 The most difficult Sudoku in the world has been designed in months . as follows

Use spaces with 0 Express , At the same time, Sudoku is represented as a nested list , In this way, the number of rows and columns in each cell is exactly the index of each corresponding number in the list .

The procedure is as follows :

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

#coding=utf-8

import datetime

class solution(object):

  def __init__(self,board):

    self.b = board

    self.t = 0

 

  def check(self,x,y,value):# Check whether there are the same items in each row, column and palace

    for row_item in self.b[x]:

      if row_item == value:

        return False

    for row_all in self.b:

      if row_all[y] == value:

        return False

    row,col=x/3*3,y/3*3

    row3col3=self.b[row][col:col+3]+self.b[row+1][col:col+3]+self.b[row+2][col:col+3]

    for row3col3_item in row3col3:

      if row3col3_item == value:

        return False

    return True

 

  def get_next(self,x,y):# Get the next blank

    for next_soulu in range(y+1,9):

      if self.b[x][next_soulu] == 0:

        return x,next_soulu

    for row_n in range(x+1,9):

      for col_n in range(0,9):

        if self.b[row_n][col_n] == 0:

          return row_n,col_n

    return -1,-1 # If there is no next blank , return -1

 

  def try_it(self,x,y):# Main circulation

    if self.b[x][y] == 0:

      for in range(1,10):# from 1 To 9 Try

        self.t+=1

        if self.check(x,y,i):# accord with The ranks and palaces are unconditional Of

          self.b[x][y]=# Fill in the qualified 0 grid

          next_x,next_y=self.get_next(x,y)# Get next 0 grid

          if next_x == -1# If there is no next 0 grid

            return True # return True

          else:    # If there is a next 0 grid , Recursively determine the next 0 Until the Sudoku is filled

            end=self.try_it(next_x,next_y)

            if not end:  # In the recursion process, there are unqualified , namely send try_it The function returns None The item

              self.b[x][y] = 0  # Go back to the next level and continue

            else:

              return True

 

  def start(self):

    begin = datetime.datetime.now()

    if self.b[0][0== 0:

      self.try_it(0,0)

    else:

      x,y=self.get_next(0,0)

      self.try_it(x,y)

    for in self.b:

      print i

    end = datetime.datetime.now()

    print '\ncost time:', end - begin

    print 'times:',self.t

    return

 

 

s=solution([[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,8,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.start()

It is worth noting that the recursive judgment used can skillfully go back to the previous level when the wrong branch is taken . The concrete realization is through for Loop from 1 To 9 Keep filling in numbers and record breakpoints . The return value of the next layer is used to determine whether to go back .

The program output is as follows :

?

1

2

3

4

5

6

7

8

9

10

11

12

[8, 1, 2, 7, 5, 3, 6, 4, 9]

[9, 4, 3, 6, 8, 2, 1, 7, 5]

[6, 7, 5, 4, 9, 1, 2, 8, 3]

[1, 5, 4, 2, 3, 7, 8, 9, 6]

[3, 6, 9, 8, 4, 5, 7, 2, 1]

[2, 8, 7, 1, 6, 9, 5, 3, 4]

[5, 2, 1, 9, 7, 4, 3, 6, 8]

[4, 3, 8, 5, 2, 6, 9, 1, 7]

[7, 9, 6, 3, 1, 8, 4, 5, 2]

 

cost time: 0:00:00.060687

times: 45360

It can be seen that although the program has a large number of operations , But the speed is still very fast .


  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved