How Pupils Solved the n-Queens Problem on a D-Wave System
TimeWednesday, June 19th11:20am - 11:45am
DescriptionEight chess queens must be placed on a chessboard so that no two queens threaten each other. The general form of this well-known problem (n queens on an n × n board) was solves on a D-Wave quantum annealer by three schoolboys (age 14, 15 and 16) from the high school of the "Regensburger Domspatzen". Their project won the first price at a regional youth science competition (Jugend forscht 2019).
As the supervisor of the three boys I will explain what it took to teach the boys how to use a D-Wave quantum annealer, how much knowledge of quantum physics was necessary and what the pupils had to know about formulating a mathematical puzzle as a quadratic unconstrained binary optimization (QUBO) problem.
With this knowledge my students could develop an energy function for the n-queens problem on their own. Their function returns a value for every constellation from zero up to n × n queens on a n × n chessboard. The global minima of this function represent the solutions of the n-queens problem. Once the problem was well-matched to the hard-wired design of the quantum annealer chip of a D-Wave 2000Q system, the n-queen problem was solved really, really fast...
Details of the solving algorithm and how to determine the energy function for this problem will be explained by my students live on stage.