Project Euler

Project Euler is a series of computational problems that, generally speaking, can be solved by a computer in less than a minute. At least, that was my goal when solving them.

\(^\dagger\) The magic 100 number may also have been motivated by Wes McKinney’s blog post where he gives “Extra points if you have [solved 100 or more problems on Project Euler]”.

Occasionally the simplest brute force algorithm works, but often clever modifications are required. In many cases, advanced mathematics (e.g. number theory) is required, which is why I stopped after 100 problems.\(^\dagger\) You can find my all 100 of my solutions here, but I wanted to highlight a few particularly interesting ones.

Problem 96: Sudoku

Problem 96 is one of my favorites. The goal is to solve a Sudoku puzzle algorithmically. The crude brute force method is obviously too slow, but the space of possible valid solutions can be drastically reduced by applying the constraints of the game: each digit 1 to 9 must be present in each row, column, and 3 by 3 subgrid. I settled on an algorithm that systematically fills one digit at a time with a candidate solution, i.e. one that satisfies the Sudoku constraints. It keeps on filling digits until either the grid is complete, meaning the puzzle has been solved, or no candidate solutions exist. In the latter case, the algorithm must backtrack to a previous state that could have more candidate solutions, and continue its search. I implemented this guess and backtrack via recursion.

The current puzzle was designed to be difficult (for humans, at least) by mathematician Arto Inkala, taken from this article.

Given a 3 by 3 numpy array representing a Sudoku grid, the following solve_sudoku() function prints the solution if it is solvable.

Note

You can try out the code without leaving this page! Hover over the launch button at the top of this page, then click the Live Code button. You can even modify the code so if you’re having trouble with a Sudoku puzzle, just modify puzzle to your liking. Zeros are interpreted as empty cells. If you prefer a Jupyter environment, use the Binder button instead.

You’ll need to run the following cell manually because Live Code sessions assume a cwd of the root directory. Refresh the page to revert to the original view.

import os

try:
    os.chdir("./website/python/")
except FileNotFoundError:
    pass
print(f"cwd: {os.getcwd()}")

cwd: /home/adam/projects/website/website/python

import numpy as np


def solve_sudoku(grid, print_sol=False):
    """Solve a Sudoku grid using backtracking, assuming a
    unique solution is defined. grid is updated in-place."""
    n_empty = 0  # Count empty entries as we search through the grid.

    # 4 loops to easily index each of 9 rows, columns, and 3x3 grids.
    # Start searching in top-left 3x3 grid.
    for row in range(3):
        for col in range(3):
            for subrow in range(3 * row, 3 * (row + 1)):
                for subcol in range(3 * col, 3 * (col + 1)):

                    # Fill empty entries.
                    if grid[subrow, subcol] == 0:
                        n_empty += 1

                        # For possible solutions satisfying Sudoku constraints,
                        # recursively continuing search with updated grid.
                        # Backtrack if necessary.
                        for sol in range(1, 10):
                            if is_not_possible_sol(sol, grid, row, col, subrow, subcol):
                                continue
                            else:  # sol may be a valid solution.
                                grid[subrow, subcol] = sol
                                if solve_sudoku(grid, print_sol):
                                    return True
                                else:  # No solution found; backtrack.
                                    grid[subrow, subcol] = 0
                        # No possible solutions found; terminate this branch and backtrack.
                        return False

    # If no empty entries counted (grid is complete), return True.
    is_solvable = n_empty == 0
    if is_solvable:
        if print_sol:
            print(grid)
    else:
        print("No solution found.")
    return is_solvable


def is_not_possible_sol(sol, grid, row, col, subrow, subcol):
    """Determine if sol may fill element grid[subrow, subcol] given Sudoku
    constraints."""
    return (
        sol in grid[subrow, :]
        or sol in grid[:, subcol]
        or sol in grid[3 * row : 3 * (row + 1), 3 * col : 3 * (col + 1)]
    )


# Initialize a puzzle. Zeros represent empty cells.
puzzle = """800000000
            003600000
            070090200
            050007000
            000045700
            000100030
            001000068
            008500010
            090000400"""

# Convert string puzzle to 9x9 numpy array of integers.
puzzle = puzzle.split("\n")
for i in range(len(puzzle)):
    line = puzzle[i].strip()
    puzzle[i] = [int(char) for char in line]
grid = np.array(puzzle)
print("initial grid:")
print(grid)

# Solve the puzzle!
print("solving...")
solve_sudoku(grid, print_sol=True)

initial grid:
[[8 0 0 0 0 0 0 0 0]
 [0 0 3 6 0 0 0 0 0]
 [0 7 0 0 9 0 2 0 0]
 [0 5 0 0 0 7 0 0 0]
 [0 0 0 0 4 5 7 0 0]
 [0 0 0 1 0 0 0 3 0]
 [0 0 1 0 0 0 0 6 8]
 [0 0 8 5 0 0 0 1 0]
 [0 9 0 0 0 0 4 0 0]]
solving...

[[8 1 2 7 5 3 6 4 9]
 [9 4 3 6 8 2 1 7 5]
 [6 7 5 4 9 1 2 8 3]
 [1 5 4 2 3 7 8 9 6]
 [3 6 9 8 4 5 7 2 1]
 [2 8 7 1 6 9 5 3 4]
 [5 2 1 9 7 4 3 6 8]
 [4 3 8 5 2 6 9 1 7]
 [7 9 6 3 1 8 4 5 2]]

True

Other Games

Problem 54 and Problem 84 are also fun problems that require you to implement Poker and Monopoly movement. They are not particularly difficult algorithmically, but they require a bit of care in keeping track of all possibilities. The Poker problem tasks you to construct an algorithm that, given two valid Poker hands, determines the outcome of that game. The Monopoly problem tasks you to simulate playing Monopoly by yourself, implementing all the movement rules like dice roll movement and “Go to Jail” squares. You are then tasked with finding the long term probabilities of landing on any given square. The most common square is the Jail square, with probability near 6%. The code for these problems is a bit long, but you can find my solutions (along with all the other 100 problems) here.

Maximum Paths

Problem 18 and Problem 67 contain a triangle of numbers like

   3
  7 4
 2 4 6
8 5 9 3

Starting from the top, you take either a step left or right to the row below, repeating until you reach the bottom. You are tasked for finding the path that results in the maximum sum of numbers traversed. In the above case, that path is 3 + 7 + 4 + 9 = 23. The brute force solution of iterating through all \(2^{\text{number of rows} - 1}\) paths works for Problem 18, but is incredibly inefficient. The follow-up problem, Problem 67, has 100 rows and therefore cannot solved with brute force.

An efficient algorithm modifies a purely “greedy” approach that would step in the direction of the largest number. Starting from the top, we can’t use a “greedy” approach because the full path is unknown. However, on the very last choice, a greedy approach is fine because the path terminates there. Take, for example,

   3
  7 4
 2 4 6
8 5 9 3

Conditioned on reaching the line 2 4 6, if we are at 2 we should always choose max(8, 5) = 8 and similarly choose 9 if we are at 4 or 6. Thus the largest sum conditioned on reaching 2 4 6 results in a reduced triangle

     3
   7   4
10  13  15

We can iteratively apply this logic resulting in

     3       -->  23.
  20   19

In Python:

import time


def reduce_triangle(nums):
    last_row = nums[-1]
    next_last_row = nums[-2]
    for i in range(len(next_last_row)):
        next_last_row[i] += max(last_row[i], last_row[i + 1])
    nums = nums[:-2]
    nums.append(next_last_row)
    return nums


start = time.time()

# Process data.
with open("p67_tri_nums.txt") as f:
    nums = f.read().split("\n")

rows = len(nums)
for i in range(rows):
    nums[i] = [int(x) for x in nums[i].split(" ")]

# Compute maximum path sum.
while len(nums) > 1:
    nums = reduce_triangle(nums)
print(nums)

print(time.time() - start)

[[7273]]
0.0031964778900146484