0

September 11, 2017 AT 2:00 am

Can You Solve the Million-Dollar, Unsolvable Chess Problem?

Image

Atlas Obscura explains why this seemingly simple question is so difficult to solve.

The riddle is based on what is known as the Queens Puzzle, first devised in 1850. Eight queens must be placed on a standard chessboard so that no two pieces can take one another. According to a release from the university, “This means putting one queen each row, so that no two queens are in the same column, and no two queens in the same diagonal.” Solutions are not hard to imagine, but the problem becomes more complex when the chessboard grows—say 100 queens on a 100-by-100 chessboard.

New research from computer science professors Ian P. Gent, Christopher Jefferson, and Peter Nightingale refers to a still more challenging variant in which the board is even larger, but some queens have already been placed. In an interview with the Clay Mathematics Institute, Gent said this problem, technically known as the “n-Queens Completion Problem,” falls into a class of high-level math puzzles known as “NP-Complete.” Any algorithm that could solve it, Gent said, could therefore be used indirectly to solve others in the class—and be a contender for the Millennium Prize.

Check out the official release from St. Andrew’s here.


Check out all the Circuit Playground Episodes! Our new kid’s show and subscribe!

Have an amazing project to share? Join the SHOW-AND-TELL every Wednesday night at 7:30pm ET on Google+ Hangouts.

Join us every Wednesday night at 8pm ET for Ask an Engineer!

Learn resistor values with Mho’s Resistance or get the best electronics calculator for engineers “Circuit Playground”Adafruit’s Apps!


Maker Business — Lessons Learned Scaling Airbnb 100X

Wearables — ABS ABC

Electronics — When do I use X10?

Biohacking — The Quantified Self Approach to Lowering Blood Glucose

Get the only spam-free daily newsletter about wearables, running a "maker business", electronic tips and more! Subscribe at AdafruitDaily.com !



No Comments

No comments yet.


Leave a comment

Adafruit has a "be excellent to each other" comment policy. Help us keep the community here positive and helpful. Stick to the topic, be respectful of makers of all ages and skill levels. Be kind, and don't spam - Thank you!

Prove you are human by reading this resistor:

0Ω+/- 5%

0
0
1
2
3
4
5
6
7
8
9

0
0
1
2
3
4
5
6
7
8
9

0
0
1
2
3
4
5
6
7
8
9

5
5
10

Prove you are human by reading this resistor:


Match the sliders on the left to each color band on the resistor.

Click Here for a new resistor image.

New to electronics? Click here to learn how to read resistor values.

Or learn to read resistors by playing Mho's Resistance!