JuMPing into Puzzle Solving with Linear Programming

Learn how to formulate and solve a linear program using the Julia language on a number puzzle similar to Sudoku

Photo by Austin Neill on Unsplash

Linear programming (LP) is a powerful technique to solve optimization problems, and you will often see it applied to problems from airline scheduling, vehicle routing, to revenue management. In this post, I’d like to explore a more whimsical application — how can linear programming be used to solve a puzzle?

The puzzle is similar to Sudoku, so I’m going to extend the well-known Sudoku LP formulation for this new brain teaser. I recommend that you understand that Sudoku solution first before proceeding since it will have some similar logic ( here’s a medium post about it ).

Introducing the puzzle

This puzzle was introduced to me by a friend who speculated that it could be solved with LP. The problem was presented on Jane Street Puzzles, and you can read the description here . From just reading about the constraints, it seems pretty similar to Sudoku — there are constraints on number of occurrences, but also some other constraints regarding first/last appearance, the sum of values, etc. Can it be solved with LP? The answer is Yes, and let’s see how.

The first puzzle that I will use for my example