Eight Queens Puzzle – One Million Dollars

[Wayne Komer]

Eight Queens Puzzle – One Million Dollars

August 31, 2017

Scientists have thrown down a million dollar gauntlet to computer programmers to find a solution to a “simple” chess puzzle, which could take thousands of years to solve. Computer scientists believe that any programme capable of solving the famous ‘Queens Puzzle’ would be so powerful it could solve impossible tasks such as decrypting the toughest security on the Internet.

Anyone who solves the ‘Queens Puzzle’ will be given a $1 million (£777,500) prize by the Clay Mathematics Institute in America. The puzzle, which dates back to 1850, challenges a player to place eight queens on a standard chessboard so that no two queens could attack each other. It requires putting one queen in each row so that no two queens are in the same column and no two can be diagonal. The puzzle has been completed but once the chess board increases to a large size no computer programme can solve it.

Computer scientist Professor Ian Gent, of the University of St Andrews who threw down the gauntlet, said: “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.

“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe. ”

Prof Gent and his colleagues including senior research fellow Dr Peter Nightingale and reader Dr Christopher Jefferson first became involved in the puzzle when a friend challenged prof Gent to solve it over Facebook.

The team found that once the chess board had reached 1,000 by 1,000 squares computer programmes could no longer cope with the number of options. Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that - for all practical purposes - it can’t be done. ”

The team, who published a paper in the Journal of Artificial Intelligence Research, reckon that the financial rewards reaped from a program would be immense, particularly from technological companies. Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly, so the rewards are high. ”

Read more at:

http://www.scotsman.com/regions/edin...zzle-1-4547534

http://web.engr.oregonstate.edu/~bud...nfo/chap06.pdf

[Kerry Liles]

Re: Eight Queens Puzzle – One Million Dollars

Eight Queens Puzzle – One Million Dollars

August 31, 2017

Scientists have thrown down a million dollar gauntlet to computer programmers to find a solution to a “simple” chess puzzle, which could take thousands of years to solve. Computer scientists believe that any programme capable of solving the famous ‘Queens Puzzle’ would be so powerful it could solve impossible tasks such as decrypting the toughest security on the Internet.

Anyone who solves the ‘Queens Puzzle’ will be given a $1 million (£777,500) prize by the Clay Mathematics Institute in America. The puzzle, which dates back to 1850, challenges a player to place eight queens on a standard chessboard so that no two queens could attack each other. It requires putting one queen in each row so that no two queens are in the same column and no two can be diagonal. The puzzle has been completed but once the chess board increases to a large size no computer programme can solve it.

Computer scientist Professor Ian Gent, of the University of St Andrews who threw down the gauntlet, said: “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.

“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe. ”

Prof Gent and his colleagues including senior research fellow Dr Peter Nightingale and reader Dr Christopher Jefferson first became involved in the puzzle when a friend challenged prof Gent to solve it over Facebook.
The team found that once the chess board had reached 1,000 by 1,000 squares computer programmes could no longer cope with the number of options. Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that - for all practical purposes - it can’t be done. ”

The team, who published a paper in the Journal of Artificial Intelligence Research, reckon that the financial rewards reaped from a program would be immense, particularly from technological companies. Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly, so the rewards are high. ”

Read more at:

http://www.scotsman.com/regions/edin...zzle-1-4547534

http://web.engr.oregonstate.edu/~bud...nfo/chap06.pdf

Thanks for posting this Wayne!

I am sure the copy editors at the Scotsman have no idea that many of the pieces in the photographs are NOT Queens... lol

[Hugh Brodie]

Re: Eight Queens Puzzle – One Million Dollars

This is hard to believe. I just did a Google search for "8 queens problem java" and there are numerous programs that have been written.

(I then looked at the second link that Wayne had provided and saw many more programs/solutions).

[Kerry Liles]

Re: Eight Queens Puzzle – One Million Dollars

This is hard to believe. I just did a Google search for "8 queens problem java" and there are numerous programs that have been written.

(I then looked at the second link that Wayne had provided and saw many more programs/solutions).

The challenge is to come up with an algorithm (other than brute force examining all possible positions) for the general case... Somewhere there was a quote about solving 1000x1000 size boards would be nearly impossible with current processing power. In Wayne's post it says

... but once the chess board increases to a large size no computer programme can solve it.

With a standard 8x8 board brute force can easily be used (that is how those programs you mentioned operate).

[Neil Frarey]

Re: Eight Queens Puzzle – One Million Dollars

This is hard to believe. I just did a Google search for "8 queens problem java" and there are numerous programs that have been written.

(I then looked at the second link that Wayne had provided and saw many more programs/solutions).

"We can provide an amusing but nevertheless illustrative metaphor for the difference between a conventional and object-oriented solution.

A conventional program is like a human being sitting above the board, and moving the chess pieces, which have no animate life of their own. In object-oriented solution, on the other hand, we will empower the pieces to solve the problem themselves.

That is, instead of a single monolithic entity controlling the outcome, we will distribute responsibility for finding the solution among many interacting agents."

http://web.engr.oregonstate.edu/~bud...nfo/chap06.pdf

*****

Reminds very much of a somewhat related statement by Vincent Van Gogh:

"We have by no means reached the point where people might understand the remarkable relations that exist between one piece of nature and another, mutually explanatory and setting each other off."

*****

Self-awareness on a base level is a Pandora's Box that I, for one, would love to open.

[Steve Douglas]

Re: Eight Queens Puzzle – One Million Dollars

"We can provide an amusing but nevertheless illustrative metaphor for the difference between a conventional and object-oriented solution.

A conventional program is like a human being sitting above the board, and moving the chess pieces, which have no animate life of their own. In object-oriented solution, on the other hand, we will empower the pieces to solve the problem themselves.

That is, instead of a single monolithic entity controlling the outcome, we will distribute responsibility for finding the solution among many interacting agents."

http://web.engr.oregonstate.edu/~bud...nfo/chap06.pdf

*****

Reminds very much of a somewhat related statement by Vincent Van Gogh:

"We have by no means reached the point where people might understand the remarkable relations that exist between one piece of nature and another, mutually explanatory and setting each other off."

*****

Self-awareness on a base level is a Pandora's Box that I, for one, would love to open.

This is a bit old (48MB???), but ...

Once upon a time, in a kingdom not far from here, a king summoned two
of his advisors for a test. He showed them both a shiny metal box
with two slots in the top, a control knob, and a lever. "What do
you think this is?"

One advisor, an Electrical Engineer, answered first. "It is a
toaster," he said. The king asked, "How would you design an embedded
computer for it?" The advisor: "Using a four-bit microcontroller, I
would write a simple program that reads the darkness knob and
quantifies its position to one of 16 shades of darkness, from snow
white to coal black. The program would use that darkness level as
the index to a 16-element table of initial timer values. Then it would
turn on the heating elements and start the timer with the initial
value selected from the table. At the end of the time delay, it
would turn off the heat and pop up the toast. Come back next week, and
I'll show you a working prototype."

The second advisor, a software developer, immediately recognized the
danger of such short-sighted thinking. He said, "Toasters don't
just turn bread into toast, they are also used to warm frozen waffles.
What you see before you is really a breakfast food cooker. As the
subjects of your kingdom become more sophisticated, they will demand
more capabilities. They will need a breakfast food cooker that can
also cook sausage, fry bacon, and make scrambled eggs. A toaster
that only makes toast will soon be obsolete. If we don't look to the
future, we will have to completely redesign the toaster in just a
few years."

"With this in mind, we can formulate a more intelligent solution to
the problem. First, create a class of breakfast foods.
Specialize this class into subclasses: grains, pork, and poultry.
The specialization process should be repeated with grains divided into
toast, muffins, pancakes, and waffles; pork divided into sausage, links,
and bacon; and poultry divided into scrambled eggs, hard- boiled eggs,
poached eggs, fried eggs, and various omelette classes."

"The ham and cheese omelette class is worth special attention because
it must inherit characteristics from the pork, dairy, and poultry
classes. Thus, we see that the problem cannot be properly solved
without multiple inheritance. At run time, the program must create
the proper object and send a message to the object that says, 'Cook
yourself.' The semantics of this message depend, of course, on the
kind of object, so they have a different meaning to a piece of toast
than to scrambled eggs."

"Reviewing the process so far, we see that the analysis phase has
revealed that the primary requirement is to cook any kind of
breakfast food. In the design phase, we have discovered some derived
requirements. Specifically, we need an object-oriented language
with multiple inheritance. Of course, users don't want the eggs to get
cold while the bacon is frying, so concurrent processing is
required, too."

"We must not forget the user interface. The lever that lowers the
food lacks versatility, and the darkness knob is confusing. Users
won't buy the product unless it has a user-friendly, graphical
interface. When the breakfast cooker is plugged in, users should
see a cowboy boot on the screen. Users click on it, and the message
'Booting UNIX v.8.3' appears on the screen. (UNIX 8.3 should be out
by the time the product gets to the market.) Users can pull down a
menu and click on the foods they want to cook."

"Having made the wise decision of specifying the software first in
the design phase, all that remains is to pick an adequate hardware
platform for the implementation phase. An Intel Pentium with 48MB
of memory, a 1.2GB hard disk, and a SVGA monitor should be sufficient.
If you select a multitasking, object oriented language that supports
multiple inheritance and has a built-in GUI, writing the program
will be a snap."

The king wisely had the software developer beheaded, and they all
lived happily ever after.

Steve

[Paul Bonham]

Re: Eight Queens Puzzle – One Million Dollars

Eight Queens Puzzle – One Million Dollars

August 31, 2017

Scientists have thrown down a million dollar gauntlet to computer programmers to find a solution to a “simple” chess puzzle, which could take thousands of years to solve. Computer scientists believe that any programme capable of solving the famous ‘Queens Puzzle’ would be so powerful it could solve impossible tasks such as decrypting the toughest security on the Internet.

Anyone who solves the ‘Queens Puzzle’ will be given a $1 million (£777,500) prize by the Clay Mathematics Institute in America. The puzzle, which dates back to 1850, challenges a player to place eight queens on a standard chessboard so that no two queens could attack each other. It requires putting one queen in each row so that no two queens are in the same column and no two can be diagonal. The puzzle has been completed but once the chess board increases to a large size no computer programme can solve it.

Computer scientist Professor Ian Gent, of the University of St Andrews who threw down the gauntlet, said: “If you could write a computer program that could solve the problem really fast, you could adapt it to solve many of the most important problems that affect us all daily.

“This includes trivial challenges like working out the largest group of your Facebook friends who don’t know each other, or very important ones like cracking the codes that keep all our online transactions safe. ”

Prof Gent and his colleagues including senior research fellow Dr Peter Nightingale and reader Dr Christopher Jefferson first became involved in the puzzle when a friend challenged prof Gent to solve it over Facebook.

The team found that once the chess board had reached 1,000 by 1,000 squares computer programmes could no longer cope with the number of options. Dr Nightingale said: “However, this is all theoretical. In practice, nobody has ever come close to writing a program that can solve the problem quickly. So what our research has shown is that - for all practical purposes - it can’t be done. ”

The team, who published a paper in the Journal of Artificial Intelligence Research, reckon that the financial rewards reaped from a program would be immense, particularly from technological companies. Dr Jefferson added: “There is a $1,000,000 prize for anyone who can prove whether or not the Queens Puzzle can be solved quickly, so the rewards are high. ”

Read more at:

http://www.scotsman.com/regions/edin...zzle-1-4547534

http://web.engr.oregonstate.edu/~bud...nfo/chap06.pdf

WAYNE KOMER, IS THIS FOR REAL???

Within half an hour of reading this post, I solved the problem with a general-case algorithm that works on both even-sized boards (8x8, 10x10, etc) and odd-sized boards (9x9, 11x11, etc.).... up to ANY SIZE and not needing any brute-force search. I didn't write a program for it, I did it on various size boards using my own logic. And it works every time.

Tomorrow I will write the C++ program for it, that should take me about an hour to write it and test it.

I found the site for Clay Mathematics Institute and there it mentions 7 "Millenium Problems" each of which has a $1 million reward. But none of them are as simple as this 8 Queens problem, the closest one is a "P vs NP" problem. The description of that doesn't even mention anything about 8 Queens.

Also, to win one of the million dollar prizes, a solution has to be published for 2 years and then considered by people at CMI for worthiness. So my question is, are these 2 Scottish professors offering $1 million of their own money? Doesn't seem likely. It seems they found this millenium problem and just decided to tell the world that anyone can win it by solving the 8 Queens problem for the general case, which is misinformation as far as I can tell.

I will post tomorrow night if the program succeeds. Sorry, no clues on how I solved it. But Wayne.... if I verify the success of my algorithm... and if you can verify that there's really $1 million for simply solving that particular problem and not the more insidiuous "P vs NP" problem... well, I'll make sure you get a piece of the action.

[Wayne Komer]

Re: Eight Queens Puzzle – One Million Dollars

Eight Queens Puzzle – One Million Dollars

August 31, 2017

I enjoy posting quirky chess news even if I cannot always verify its accuracy.

At the moment I am still trying to figure out if an Olympiad can be held under Victoria Falls. The scenario is delicious with a thousand players in a large cavern with water pounding down outside!

As for the 8 queens problem, I refer you to:

http://jair.org/papers/paper5512.html

http://www.ijera.com/papers/Vol3_iss...3313461349.pdf

http://ccis2k.org/iajit/PDF/vol.11,no.6/5421.pdf

https://www.hindawi.com/journals/jopti/2017/5650364/

and good luck. I hope you have the solution.

[Paul Bonham]

Re: Eight Queens Puzzle – One Million Dollars

Eight Queens Puzzle – One Million Dollars

August 31, 2017

I enjoy posting quirky chess news even if I cannot always verify its accuracy.

At the moment I am still trying to figure out if an Olympiad can be held under Victoria Falls. The scenario is delicious with a thousand players in a large cavern with water pounding down outside!

As for the 8 queens problem, I refer you to:

http://jair.org/papers/paper5512.html

http://www.ijera.com/papers/Vol3_iss...3313461349.pdf

http://ccis2k.org/iajit/PDF/vol.11,no.6/5421.pdf

https://www.hindawi.com/journals/jopti/2017/5650364/

and good luck. I hope you have the solution.

It does seem this falls under "quirky" chess news, as I don't think there is any million dollar prize simply for solving this particular problem (which in the original link you provided, the problem isn't even worded clearly, it is all very vague).

Anyway, what I specifically did was to use a logical algorithm to find 1 guaranteed solution for the N Queens problem for any given board size. The time needed to calculate this one solution is dependent only on N, meaning in Big O Notation it is O(N). Thus the time required will grow linearly with N, not exponentially.

If there really was a million dollar prize for this problem, the exact problem would be explained in great detail. For example, is it necessary to find ALL solutions for a given board size, or only one guaranteed solution as I have done?

These professors seem not to be legit at all, at least in terms of declaring this million dollar prize. Cheap publicity stunt is all this seems to be.

[Neil Frarey]

Re: Eight Queens Puzzle – One Million Dollars

Easy stuff to write. Here's just three that have long since been done on GitHub:

https://github.com/iamjason/eight-queens

https://github.com/AlexJeng/n-queens

https://github.com/asad-awadia/8-Que...er/Queens.java

I too think their 1 mill offer is unclear. Object-orientation seem to suggest AI ... for each Queen?

[Mathieu Cloutier]

Re: Eight Queens Puzzle – One Million Dollars

It does seem this falls under "quirky" chess news, as I don't think there is any million dollar prize simply for solving this particular problem (which in the original link you provided, the problem isn't even worded clearly, it is all very vague).

Anyway, what I specifically did was to use a logical algorithm to find 1 guaranteed solution for the N Queens problem for any given board size. The time needed to calculate this one solution is dependent only on N, meaning in Big O Notation it is O(N). Thus the time required will grow linearly with N, not exponentially.

If there really was a million dollar prize for this problem, the exact problem would be explained in great detail. For example, is it necessary to find ALL solutions for a given board size, or only one guaranteed solution as I have done?

These professors seem not to be legit at all, at least in terms of declaring this million dollar prize. Cheap publicity stunt is all this seems to be.

Well, maybe you should claim the prize then?

[Neil Frarey]

Re: Eight Queens Puzzle – One Million Dollars

Well, maybe you should claim the prize then?

LOL

Ya Paul, go claim your prize!

[Paul Bonham]

Re: Eight Queens Puzzle – One Million Dollars

Easy stuff to write. Here's just three that have long since been done on GitHub:

https://github.com/iamjason/eight-queens

https://github.com/AlexJeng/n-queens

https://github.com/asad-awadia/8-Que...er/Queens.java

I too think their 1 mill offer is unclear. Object-orientation seem to suggest AI ... for each Queen?

All of these seem flawed, as they seem to have the exponential time complexity ( i.e. O(N^X where X > 1) ).

My solution doesn't require Object Orientation. Nor AI for each Queen. My solution is procedural, and very simple. It finds one guaranteed solution for any board size, odd or even NxN. And it does it in O(N) time complexity. Space complexity (memory used) is also O(N).

But I don't think there is any million dollar prize for it.

Using AI for each Queen is a recipe for exponential time complexity, because as N increases, the Nth Queen must communicate with N-1 other Queens ("Are you attacking me if I go here?"), which results in N^2 - N communications. Actually more than that when you add them all up, but you get the idea.

[Wayne Komer]

Re: Eight Queens Puzzle – One Million Dollars

Eight Queens Puzzle – One Million Dollars

September 2, 2017

The paper “Complexity of n-Queens Completion” by Gent, Jefferson and Nightingale is available as a pdf online.

http://jair.org/media/5512/live-5512-10126-jair.pdf

Viewers may enjoy seeing a diagrammatic solution to the 19-Queens problem.

33 pages of maths are a bit too much for me but others may revel in them.

[Kerry Liles]

Re: Eight Queens Puzzle – One Million Dollars

There is more information (perhaps some new information?) in this article on Chessbase:

http://en.chessbase.com/post/solve-a...illion-dollars