# Common problems/puzzles that can creatively be solved with linear programming?

I am interested in common problems/puzzles that have a clear set of rules/constraints and objective that lends itself to modeled and solved with a linear program. Especially for people new to LPs, I think that translating a tangible problem into a mathematical formulation is one of the best ways to explain the applicability of LPS.

Some easy examples I can think of would be sudoku and the 8-queens puzzle. What are other examples that come to mind?

• Something like a static/deterministic version of Tetris Commented Apr 9, 2022 at 8:30
• Continuous LP only, or also MILP? Commented Apr 9, 2022 at 15:30
• @MarkL.Stone sorry, definitely MILPs as well. Commented Apr 9, 2022 at 17:32
• One concern about using puzzles like sudoku to explain the applicability of LP and MILP models is that they do not have meaningful objective functions. You are solving for any (or, more commonly, the unique) feasible solution, not for a "best" solution among many.
– prubin
Commented Apr 9, 2022 at 20:04
• There are a few questions already about puzzles that can be solved using OR. I just created a puzzles-games tag for them. Commented Apr 11, 2022 at 0:49

I do this all the time over at https://puzzling.stackexchange.com/. Currently, a search for "linear programming" yields 44 results. Most of these actually use integer linear programming, and several involve chessboard problems. But here's one that uses LP and has a nice animation: https://puzzling.stackexchange.com/questions/111297/five-friends-and-two-motorcyclists/111301#111301

See also these posts, where I have used LP duality to provide short certificates of optimality for various puzzles.

• This is great, exactly what I was interested in. Thanks for the reply! Commented Apr 9, 2022 at 17:38

Some other puzzles that you can solve with (MI)LPs:

• Suppose an electronic lock has 3 digits, and that the lock opens once the right code is entered, no matter what was tried just before. What is the fastest way to open the lock (the shortest sequence of numbers that will open the lock)?