6
\$\begingroup\$

I wrote a Python script that generates a Sudoku puzzle. Everything works just fine but it takes too much time to generate puzzle from a completed board (remove_cells).

How can I enhance the efficiency and make it faster?

import random

def generate():
    """ Returns a completed Sudoku board """

    board = [[cell() for _ in range(9)] for _ in range(9)]
    stack = [board[0][0]] + [None for _ in range(80)]
    index = 1

    while index < 81:
        if not stack[index]:
            stack[index] = board[index // 9][index % 9]
        else:
            stack[index].index += 1
            if stack[index].index == 9:
                stack[index].index = 0
                stack[index] = None
                index -= 1
                continue

        if test_cell([stack[9 * i : 9 * i + 9] for i in range(9)], 
                    (index // 9, index % 9)):
            index += 1

    return board

def solver(puzzle):
    """ Returns:
    Completed Sudoku puzzle -- if the puzzle is unique and solvable
    None -- if the puzzle is not unique or not solvable """

    solved = None
    board = copy(puzzle)
    queue = []

    # Queue -- list of empty cells (None):
    # (x, y) - the coordinates of the empty cell
    # [] - the list of candidates for the empty cell
    for x in range(9):
        for y in range(9):
            if not board[x][y]:
                queue.append([(x, y), []])

    index = 0
    while index < len(queue):
        if index == -1:
            break
        x, y = queue[index][0]
        # If board[x][y] is None:
        # finds the candidates for the generated cell
        if not board[x][y]:
            board[x][y] = cell(False)
            for board[x][y].index in range(9):
                if test_cell(board, queue[index][0]):
                    queue[index][1].append(board[x][y].index)
        # If there is not candidates for board[x][y],
        # removes that cell and goes to the previous cell
        if not queue[index][1]:
            board[x][y] = None
            index -= 1
        else:
            # Assigns the first candidate to the cell,
            # removes it from the list of candidates
            board[x][y].index = queue[index][1][0]
            queue[index][1] = queue[index][1][1:]
            # If this is the end of queue
            if index == len(queue) - 1:
                if solved:
                    # If the puzzle is already solved, thus it is not unique
                    return None
                solved = copy(board)
                # Searches for another solution
                board[x][y] = None
                index -= 1
            else:
                index += 1

    return solved

def remove_cells(board):
    """ Creates a puzzle from a completed Sudoku board """
    puzzle = copy(board)
    cells = [num for num in range(81)]
    random.shuffle(cells)

    # Deletes a random cell and check if still unique and solvable.
    # If not: puts the cell back to the board and continues
    for index in cells:
        x, y = index // 9, index % 9
        cell_backup = puzzle[x][y]
        puzzle[x][y] = None
        if not solver(puzzle):
            puzzle[x][y] = cell_backup

    return puzzle

def test_cell(board, position):
    """ Checks if the cell's value in the given coordinates is valid """
    x, y = position
    for i in range(9):
        # Tests column
        if i != x and board[i][y] and board[i][y].value == board[x][y].value:
            return False
        # Tests row
        elif i != y and board[x][i] and board[x][i].value == board[x][y].value:
            return False

    # Tests box
    for i in range((x // 3) * 3, (x // 3) * 3 + 3):
        for j in range((y // 3) * 3, (y // 3) * 3 + 3):
            if i == x and j == y:
                continue
            if board[i][j] and board[i][j].value == board[x][y].value:
                return False

    return True

def copy(board):
    """ Returns a deep copy of a board """
    temp = [[None for _ in range(9)] for _ in range(9)]
    for x in range(9):
        for y in range(9):
            if board[x][y]:
                temp[x][y] = cell(False)
                temp[x][y].index = board[x][y].value - 1
    return temp

def print_board(board):
    """ Prints the given board """
    print('-' * 25)
    for i in range(9):
        line = []
        for x in range(9):
            if board[i][x]:
                line.append(board[i][x].value)
            else:
                line.append(0)
        print('| {} {} {} | {} {} {} | {} {} {} |'.format(line[0], line[1], line[2], line[3], line[4], line[5], line[6], line[7], line[8]))
        if (i + 1) % 3 == 0:
            print('-' * 25)

class cell:
    def __init__(self, rand = True):
        self.numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        self.index = 0

        if rand:
            random.shuffle(self.numbers)

    @property
    def value(self):
        return self.numbers[self.index]

Usage example:

from Sudoku import *

board = generate()
print_board(board)
puzzle = remove_cells(board)
print_board(puzzle)
print_board(solver(puzzle))
\$\endgroup\$
  • \$\begingroup\$ Is this off topic ("not working as intended")? \$\endgroup\$ – l0b0 Jun 15 '18 at 3:10
  • \$\begingroup\$ @l0b0, If this is off topic, then any question that hopes for performance suggestions is off topic. I would suggest that your question is probably best asked on Meta. I think your question is: does as intended mean as hoped for, or some such. \$\endgroup\$ – Stephen Rauch Jun 15 '18 at 3:16
2
\$\begingroup\$

How can I enhance the efficiency and make it faster?

There are two big algorithmic improvements you can make.

Firstly, optimise the solver. The solver does nearly all of the work in the generator, but it looks pretty close to the simplest possible implementation. That's fine as a starting point: make it work, then make it fast.

If you want to stick to brute force, you can at least use heuristics to speed it up. For example, rather than just sticking all of the cells into a queue, use a priority queue and tackle the ones with fewest remaining options first. A slightly more sophisticated version of this expresses the constraints in more symmetrical form and tackles rows/columns/boxes with few options as well as cells with few options. See the Wikipedia description of sudoku as exact set cover.

Alternatively, don't use brute force. Instead, use the strategies that humans use to solve sudoku. The great advantage of doing this is that you know that the sudoku you generate won't leave the human solver frustrated by requiring "trial and error". It also means that you can easily implement a crude difficulty ranking: what's the most advanced technique required to solve it? If it requires XY-wing, it's harder than one which can be solved purely by the basic techniques. You can push this idea further by looking at how many cells are directly solvable at a time, but that's getting off-topic.

Secondly, optimise the usage of the solver. In remove_cells, when you're testing whether index can be removed, you don't need to solve the entire puzzle. You just need to show that there's only one possibility for index. If you're doing brute force, that means prioritising that cell. If you're using standard techniques, it means that you can put an early return into solver.

\$\endgroup\$
  • \$\begingroup\$ How do I implement a priority queue in the solver? I tried to do so and everything just got messed up. \$\endgroup\$ – Eden Jun 15 '18 at 13:20
  • \$\begingroup\$ I don't use Python very often, so I'm not best placed to answer in detail. But even if you forget the priority queue and just recalculate each time which cell has fewest options I expect you'll get orders of magnitude of speedup. \$\endgroup\$ – Peter Taylor Jun 15 '18 at 16:37
  • \$\begingroup\$ The best result of remove_cells is on average 53 seconds per puzzle. \$\endgroup\$ – Eden Jun 15 '18 at 18:17
1
\$\begingroup\$

If I remember correctly there are some rules you can use to shift the rows. Create solved board and shuffle it, then hide as many solved cells as you need.

Here is a link to how you can do most of that

http://www.algosome.com/articles/create-a-solved-sudoku.html

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.