Solving an NP-Hard Problem for Fun and Profit
By Raymond Chandler III

Last year I was given a task by the publishers of the CATAN board game. They wanted a tournament management tool that could help them organize, run, seat, and rank players in their world championships and several local qualifying events around the world. Most of the application was straightforward but they also had a very specific seating problem, and after doing some investigation I learned that their specific requirements made the task an NP-hard problem. The problem is this:

Given some number of players. Generate a number of tables where each table has 4 or 3 seats. Then from round to round seat players in such a way so that A) no player plays in the same seating position they previously sat in, and B) no player plays against someone they played against previously. Players should be seated as fairly as possible from round to round, and where there is a perfect solution the algorithm should arrive at it, and when there isn't it should arrive at the "fairest" solution possible. It should be able to handle any arbitrarily large number of players, and should run in seconds.

In this talk, I'm going to talk a bit more about this specific problem and how I solved it using Python. I will walk you through my different attempts and thought processes while attempting to develop a good solution. You will walk away with a process and framework to solve your own difficult problems and develop a scientific mindset that can help lead you to new discoveries.

Finally, I will present how the algorithm works, and make suggestions to how it can be applied to solve other similar types of problems. I proudly present to you: The Gamer's Algorithm.

P.S. The algorithm will be used for the first time in the wild at the CATAN World Championships at Origin Games Fair and the U.S. National Championships at Gencon in 2018.