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.


As 2022 starts, let’s take some time to share our goals for CircuitPython in 2022. Just like past years (full summary 2019, 2020, and 2021), we’d like everyone in the CircuitPython community to contribute by posting their thoughts to some public place on the Internet. Here are a few ways to post: a video on YouTub, a post on the CircuitPython forum, a blog post on your site, a series of Tweets, a Gist on GitHub. We want to hear from you. When you post, please add #CircuitPython2022 and email circuitpython2022@adafruit.com to let us know about your post so we can blog it up here.

Stop breadboarding and soldering – start making immediately! Adafruit’s Circuit Playground is jam-packed with LEDs, sensors, buttons, alligator clip pads and more. Build projects with Circuit Playground in a few minutes with the drag-and-drop MakeCode programming site, learn computer science using the CS Discoveries class on code.org, jump into CircuitPython to learn Python and hardware together, TinyGO, or even use the Arduino IDE. Circuit Playground Express is the newest and best Circuit Playground board, with support for CircuitPython, MakeCode, and Arduino. It has a powerful processor, 10 NeoPixels, mini speaker, InfraRed receive and transmit, two buttons, a switch, 14 alligator clip pads, and lots of sensors: capacitive touch, IR proximity, temperature, light, motion and sound. A whole wide world of electronics and coding is waiting for you, and it fits in the palm of your hand.

Join 32,000+ makers on Adafruit’s Discord channels and be part of the community! http://adafru.it/discord

Have an amazing project to share? The Electronics Show and Tell is every Wednesday at 7pm ET! To join, head over to YouTube and check out the show’s live chat – we’ll post the link there.

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

Follow Adafruit on Instagram for top secret new products, behinds the scenes and more https://www.instagram.com/adafruit/

CircuitPython – The easiest way to program microcontrollers – CircuitPython.org


Maker Business — Pololu’s account of the chip shortage

Wearables — Make it sticky

Electronics — Your job’s a joke, you’re broke, your semiconductor is DOA

Python for Microcontrollers — Python on Microcontrollers Newsletter: Raspberry Pi Pico turns one and more! #Python #CircuitPython @micropython @ThePSF

Adafruit IoT Monthly — 2021 in Recap!

Microsoft MakeCode — MakeCode Thank You!

EYE on NPI — Maxim’s Himalaya uSLIC Step-Down Power Module #EyeOnNPI @maximintegrated @digikey

New Products – Adafruit Industries – Makers, hackers, artists, designers and engineers! — NEW PRODUCT – ESP32­-S3­-DevKitC-1 – ESP32-S3-WROOM-2 – 32MB Flash 8MB PSRAM

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.

Sorry, the comment form is closed at this time.