Su Doku

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

     
A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ “guess and test” methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.
The 6K text file, sudoku.txt (right click and ‘Save Link/Target As…’), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).
By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

The problem presented is about solving 50 Sudoku puzzles and finding the sum of the 3-digit numbers in the top left corner of each solution grid.

While it’s possible to solve these puzzles manually, it would be very time-consuming. This task is better suited for a computer program. Here’s a code in Python that uses a backtracking algorithm to solve the Sudoku:

“`python
def solve(grid, row, col, num):
for x in range(9):
if grid[row][x] == num:
return False

for x in range(9):
if grid[x][col] == num:
return False

start_row = row – row % 3
start_col = col – col % 3
for i in range(3):
for j in range(3):
if grid[i + start_row][j + start_col] == num:
return False
return True

def solve_sudoku(grid, row=0, col=0):
if row == 8 and col == 9:
return True

if col == 9:
row += 1
col = 0

if grid[row][col] > 0:
return solve_sudoku(grid, row, col + 1)
for num in range(1, 10):
if solve(grid, row, col, num):
grid[row][col] = num
if solve_sudoku(grid, row, col + 1):
return True
grid[row][col] = 0
return False
“`

To solve all 50 puzzles and find the sum of the 3-digit numbers in the top left corner, we need to read in the puzzles, solve them, and then extract the 3-digit numbers:

“`python
sum = 0
for puzzle in puzzles:
if solve_sudoku(puzzle):
sum += int(str(puzzle[0][0]) + str(puzzle[0][1]) + str(puzzle[0][2]))
print(sum)
“`
In the second block of code you would replace “puzzles” with the variable that is storing your loaded puzzles. This script will print out the sum of all fifty 3-digit numbers found in the top left corner of each solved Sudoku grid.

It’s important to remember the legality limitations when it comes to web scraping, the python script provided assumes you’re already granted with permission to use the data on that respective webpage.

More Answers: