// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (13 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 96 Solution

Project Euler 96 Solution

Project Euler 96: Solve SuDoku puzzles


Project Euler 96 Problem Description

Project Euler 96: 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.

0 0 3
9 0 0
0 0 1
0 2 0
3 0 5
8 0 6
6 0 0
0 0 1
4 0 0
0 0 8
7 0 0
0 0 6
1 0 2
0 0 0
7 0 8
9 0 0
0 0 8
2 0 0
0 0 2
8 0 0
0 0 5
6 0 9
2 0 3
0 1 0
5 0 0
0 0 9
3 0 0
4 8 3
9 6 7
2 5 1
9 2 1
3 4 5
8 7 6
6 5 7
8 2 1
4 9 3
5 4 8
7 2 9
1 3 6
1 3 2
5 6 4
7 9 8
9 7 6
1 3 8
2 4 5
3 7 2
8 1 4
6 9 5
6 8 9
2 5 3
4 1 7
5 1 4
7 6 9
3 8 2

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.

Analysis

Read an external file and parse into required format, solve Sudoku puzzles and add the first 3 digits: All in under 30 lines of Python.

Input file:
Each puzzle was converted from it’s native form into a string of 81 integers where zeros are blank squares. Any line with the word ‘Grid’ was ignored. The supplied data has been pre-validated, so sanity checks are not performed. Here’s an example for the puzzle listed in the problem description:
Grid 01
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300

And here is what the solver expects:
003020600900305001001806400008102900700000008006708200002609500800203009005010300

For more information on this concise solution consult:
Shortest Python Sudoku solver

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank

Project Euler 96 Solution

Runs < 6 seconds in Pypy.
from urllib import urlopen
s = 0

def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and (i % 9)/3 == (j % 9)/3)
def r(a):
    global s
    i = a.find('0')
    if i == -1:
        s+=int(a[0:3])

    excluded_numbers = set()
    for j in range(81):
        if same_row(i,j) or same_col(i,j) or same_block(i,j):
            excluded_numbers.add(a[j])

    for m in '123456789':
        if m not in excluded_numbers:
            r(a[:i] + m + a[i+1:])

file = urlopen('https://projecteuler.net/project/resources/p096_sudoku.txt','r').readlines()
fx = ''.join([line[:9] for line in file if not 'Grid' in line])
fx = [fx[i:(i+81)] for i in range(0,len(fx),81)]

[r(p) for p in fx]

print "Project Euler 96 Solution =", s
download arrowUse this link to get the Project Euler 96 Solution Pypy source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|24702|

Afterthoughts

  • Grid #13 took the longest.
  • Using PyPy instead of Python27 saved 85 seconds (18 times faster)
  • 50 lines of 81 integer starting grids: pe96.prob
  • 50 lines of 81 integer solutions: pe96.sol
  • Project Euler 96 Solver here.
Project Euler 96 Solution last updated

Discussion

No comments yet.

Post a comment