Solving an NP-Hard Problem for Fun and Profit
summary
A tournament seating solver for CATAN frames the problem as NP-hard seating constraints: tables of 3–4 where A) no player repeats the same seat position and B) no repeat opponents. Early genetic-algorithm attempts fail, so the solution uses a deterministic Python engine that scores every seat, queues low-scoring players, lets them try seats (dethroning others), and iterates until convergence. Typical runs hit a global minimum in ~20–40 iterations, complete in seconds using matplotlib, statistics and cProfile for analysis — released as TourneyMan Python implementation and deployed at Origin and GenCon 2018.
AI-written summary · about
chapters (6)
related talks
29mLet our optima combine!
01h 30mHow To Write a Rubik’s Cube Solver
22mThere is always another way: Sharpen your NumPy skills with the 8 Queens puzzle
46mTight Genes: Intro to Genetic Algorithms
30mDoing stupid things with ASTs
12mConstrainedrandom - a Python package that does what it says on the tin
29mOptimizing fantasy basketball decisions with Python
31mPython Doesn’t Have to Be Slow: Speeding Up a Large-Scale Optimization Algorithm