The GNU Linear Programming Kit (GLPK)
The GNU Linear Programming Kit is a free set of tools for solving linear programming problems. It is written in C but there are several interfaces that allow it to be used from Python. These include PyGLPK, ctypes-glpk and PyMathProg but, sadly, none of these have been updated to work with Python 3 or the current version of GLPK (4.49). However, ctypes-glpk uses Python’s ctypes for its GLPK interface and I found that it was possible to build on this to provide a version that works with Python 3 and glpk 4.49 on Windows. I have made my version available here.
Using GLPK via Python, we can now solve the puzzle as follows:
Here are some of the configurations that the program finds: