Enhance Sudoku puzzle generator

Question

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))

• l0b0: Is this off topic ("not working as intended")?
• Stephen Rauch: @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.

Answer 1

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.

• Eden: How do I implement a priority queue in the solver? I tried to do so and everything just got messed up.
• Peter Taylor: 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.
• Eden: The best result of remove_cells is on average 53 seconds per puzzle.

Answer 2

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