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
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.
Implementing Enterprise Observability for Success by Manisha Agrawal and Karun Krishnannair(7259)
Supercharging Productivity with Trello by Brittany Joiner(6523)
Secrets of the JavaScript Ninja by John Resig Bear Bibeault(6409)
Mastering Tableau 2023 - Fourth Edition by Marleen Meier(6288)
Inkscape by Example by István Szép(6139)
Visualize Complex Processes with Microsoft Visio by David J Parker & Šenaj Lelić(5839)
Build Stunning Real-time VFX with Unreal Engine 5 by Hrishikesh Andurlekar(4824)
Design Made Easy with Inkscape by Christopher Rogers(4552)
Customizing Microsoft Teams by Gopi Kondameda(4098)
Linux Device Driver Development Cookbook by Rodolfo Giometti(3932)
Extending Microsoft Power Apps with Power Apps Component Framework by Danish Naglekar(3685)
Business Intelligence Career Master Plan by Eduardo Chavez & Danny Moncada(3617)
Salesforce Platform Enterprise Architecture - Fourth Edition by Andrew Fawcett(3559)
Pandas Cookbook by Theodore Petrou(3541)
The Tableau Workshop by Sumit Gupta Sylvester Pinto Shweta Sankhe-Savale JC Gillet and Kenneth Michael Cherven(3342)
TCP IP by Todd Lammle(2981)
Drawing Shortcuts: Developing Quick Drawing Skills Using Today's Technology by Leggitt Jim(2909)
Applied Predictive Modeling by Max Kuhn & Kjell Johnson(2857)
Work Smarter with Microsoft OneNote by Connie Clark(2840)
