Learn Web Development with Python by Fabrizio Romano

Author:Fabrizio Romano
Language: eng
Format: epub
Tags: COM051360 - COMPUTERS / Programming Languages / Python, COM060130 - COMPUTERS / Web / Design, COM060180 - COMPUTERS / Web / Web Services and APIs
Publisher: Packt Publishing
Published: 2018-12-21T05:06:12+00:00

grid = dict((square, digits) for square in squares)

for square, digit in zip(squares, puzzle):

if digit in digits and not place(grid, square, digit):

return False # Incongruent puzzle

return grid

def solve(puzzle):

grid = parse_puzzle(puzzle)

return search(grid)

This simple parse_puzzle function is used to parse an input puzzle. We do a little bit of sanity checking at the beginning, asserting that the input puzzle has to shrink into a set that is a subset of the set of all numbers plus a dot. Then we make sure we have 81 input characters, and finally we define grid, which initially is simply a dictionary with 81 keys, each of which is a square, all with the same value, which is a string of all possible digits. This is because a square in a completely empty grid has the potential to become any number from 1 to 9.

The for loop is definitely the most interesting part. We parse each of the 81 characters in the input puzzle, coupling them with the corresponding square in the grid, and we try to "place" them. I put that in double quotes because, as we'll see in a moment, the place function does much more than simply setting a given number in a given square. If we find that we cannot place a digit from the input puzzle, it means the input is invalid, and we return False. Otherwise, we're good to go and we return the grid.

parse_puzzle is used in the solve function, which simply parses the input puzzle, and unleashes search on it. What follows is therefore the heart of the algorithm:

def search(grid):

if not grid:

return False

if all(len(grid[square]) == 1 for square in squares):

return grid # Solved

values, square = min(

(len(grid[square]), square) for square in squares

if len(grid[square]) > 1

)

for digit in grid[square]:

result = search(place(grid.copy(), square, digit))

if result:

return result

This simple function first checks whether the grid is actually non-empty. Then it tries to see whether the grid is solved. A solved grid will have one value per square. If that is not the case, it loops through each square and finds the square with the minimum amount of candidates. If a square has a string value of only one digit, it means a number has been placed in that square. But if the value is more than one digit, then those are possible candidates, so we need to find the square with the minimum amount of candidates, and try them. Trying a square with "23" candidates is much better than trying one with "23589". In the first case, we have a 50% chance of getting the right value, while in the second one, we only have 20%. Choosing the square with the minimum amount of candidates therefore maximizes the chances for us to place good numbers in the grid.

Once the candidates have been found, we try them in order and if any of them results in being successful, we have solved the grid and we return. You might have noticed the use of the place function in the search too. So let's explore its code:

def

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.