Skip to content

[Python] Use the for-loop program to solve Sudoku problems (optimized version)

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.

Tags:

Leave a ReplyCancel reply

Exit mobile version