Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
Programming Games

Solve a 'Simple' Chess Puzzle, Win $1 Million (st-andrews.ac.uk) 125

An anonymous reader brings an important announcement: Researchers at the University of St Andrews have thrown down the gauntlet to computer programmers to find a solution to a "simple" chess puzzle which could, in fact, take thousands of years to solve, and net a $1 million prize. Computer Scientist Professor Ian Gent and his colleagues, at the University of St Andrews, believe any program capable of solving the famous "Queens Puzzle" efficiently would be so powerful, it would be capable of solving tasks currently considered impossible, such as decrypting the toughest security on the internet. In a paper [PDF] published in the Journal of Artificial Intelligence Research today, the team conclude the rewards to be reaped by such a program would be immense, not least in financial terms with firms rushing to use it to offer technological solutions, and also a $1 million prize offered by the Clay Mathematics Institute in America.

Devised in 1850, the Queens Puzzle originally challenged a player to place eight queens on a standard chessboard so that no two queens could attack each other. This means putting one queen in each row, so that no two queens are in the same column, and no two queens in the same diagonal. Although the problem has been solved by human beings, once the chess board increases to a large size no computer program can solve it.

This discussion has been archived. No new comments can be posted.

Solve a 'Simple' Chess Puzzle, Win $1 Million

Comments Filter:
  • by hcs_$reboot ( 1536101 ) on Saturday September 02, 2017 @02:00PM (#55129417)
    "once the chess board increases to a large size no computer program can solve it"

    How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.
    • "once the chess board increases to a large size no computer program can solve it"

      How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.

      More to the point, anything larger that 8x8 isn't a chess board - problem solved, where's my money?

      • anything larger that 8x8 isn't a chess board - problem solved, where's my money?

        Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.

        So you'll need to split that money with me, pal. :)

        Of course, it's just slightly possible that TFS is not an accurate summary of the actual article / problem,

        • Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board,

          The summary and even the linked page are a bit confusing on this front, but the paper is clearer. Apparently, this isn't an 8-queen problem, but an n-queen problem in an n*n board. The exact conditions aren't too clear either (e.g., "solve the problem really fast"), but it seems that creating an acceptably quick solution for n = 1000 should be enough.

          • by Anonymous Coward

            Since this is all really backed by the discussion about NP != P, what you need to do is create a polynomial time solution for it and then that will be "fast enough". If your algorithm executes in exponential time it won't be fast enough.

            If you don't understand what I just said, welcome to Slashdot, we (used to) talk tech stuff here. Read this: en.wikipedia.org/wiki/Time_complexity [wikipedia.org].

            • If you don't understand what I just said, welcome to Slashdot, we (used to) talk tech stuff here

              I am a senior programmer with 2 university degrees (one of them in engineering) who has been full-time working on software development for over the last 8 years. I know what your time complexity is and its exact applicability to my work: none. I also have been contributing here relatively often during the last years; most of the times by mostly focusing on "tech" issues. What do you think that is more "tech": actually solving a problem by coming up with the optimal algorithm; or getting lost (read below) on

          • About a half a minute on my laptop after programming for about 20 minutes. I am sure that's not what the prize is about.

            (C++14 using gcc on Linux)

            #include <iostream>
            #include <algorithm>
            #include <cstdlib>
            #include <cmath>

            int s[1000];

            double energy() {
            int result = 0;
            for (int i = 1; i < 1000; ++i) {
            for (int j = 0; j < i; ++j) {
            if (std::abs(s[i]-s[j]) == i - j)
            • About a half a minute on my laptop after programming for about 20 minutes. I am sure that's not what the prize is about.

              There seems to be lots of misunderstanding(-prone people) in this thread (and I have to still read a few replies below; I don't want even to imagine what is waiting for me down there! Pff). Please, re-read my comment and tell me where I have written any indication regarding the proceeding or expectations in this specific problem? I have plainly summarised what the linked page (+ a sensible interpretations of its contents because it is very unclear) says. That professor is expressly saying that for n=1000, t

              • Good grief. It's amazing all you could deduce from reading one line of text I wrote and from not reading the code associated with it. You didn't understand what the code is about, but somehow that indicates some problem with me, not with you. I see.

                The program I wrote works. It's a straightforward implementation of simulated annealing (look it up) for this problem, where the word "energy" is the standard term for the thing you are trying to minimize. I didn't bother making it for general n (although you can
                • by Whibla ( 210729 )

                  I confess I didn't understand the code, but that doesn't prevent me asking:

                  How long did it take to run for n=1,000?

                  How long will it take to run for n=1,000,000?

                  • If you want to spend time on something actually relevant, you should take a look at the PHP code in the lower part of this thread. It might need some tweaking, but it already represents a first good enough approach. The time requirements there are negligible.
                  • I confess I didn't understand the code

                    It's fairly straight forward. The "s" array holds numbers from 0 to N, and represents the positions of queens on the board, for example if s[3]==5 then there's a queen at position (3,5). This method of representing the board automatically ensures no two queens share a row or column, so you just have to worry about diagonals.

                    The "energy" function compares every queen with every other queen to see if they are on the same diagonal, and returns the number that are.

                    The code starts with numbers all in order in th

                    • by Whibla ( 210729 )

                      Thanks. That was very informative.

                      I don't think 1,000,000 is feasible with this algorithm.

                      You might be right. It might not be productive either.

                • Now, take your pill and breathe.

                  OK. I am always ready to recognise my errors and even to give as many chances as necessary to people really meaning well. I guess that the fact that my first impression about your intentions was really bad is pretty clear; even that I have had quite few bad experiences with misunderstanding-prone individuals. But if I made a mistake, I would be more than happy to correct it. And even in case of realising that your intention was good, regardless of the accuracy of your approach, I would also apologise for my

            • Down this thread, you can find a PHP code delivering what is expected. It might not be perfect (not really sure), but it is certainly very close to solve the problem here. And the size of the code (+ effort for an actually knowledgeable person, actually understanding the problem and actually delivering a reasonably acceptable solution) is similar to your crap. See? Doing something useful or relevant requires pretty much the same effort than making a fool of yourself, lying and contributing towards creating
          • The exact conditions aren't too clear either (e.g., "solve the problem really fast"),

            They are clear: "What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”

            • "What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”

              Can you please tell me where you can find that sentence in the summary or in the linked page?

        • by clovis ( 4684 )

          anything larger that 8x8 isn't a chess board - problem solved, where's my money?

          Not only that, but if an 8-queen solution works on an 8x8 board, it'll work just as well on a 1000x1000 or a 10k x 10k board, etc. board. Move it over, put it in the same relative location in the 8x8 group at the corner of the larger board, done. So solve for 8x8 and move.

          So you'll need to split that money with me, pal. :)

          Of course, it's just slightly possible that TFS is not an accurate summary of the actual article / problem, but...

          Nah. Besides, everyone knows that reading TFA is un-American. Even reading the summary raises red flags with Homeland Security, and may result in a National Security Letter (which you can read, but can't discuss.)

          You are correct, the article and the summary are misleading/wrong.
          Here's those guys explaining the problem and prize again.
          https://www.claymath.org/event... [claymath.org]

        • I'm not sure whether or not I understood your "solution", but if I did, I don't think it works quite as easily as you suggest.

          What I think you proposed, was dividing the larger board into a grid of sub-grids, and then just filling them in recursively (so, for example, to get a 64x64 solution, start with an 8x8 solution, replace each empty square with an empty 8x8 grid inside of it, and each queen with an 8x8 solution). If that's your method, it doesn't work because the diagonals on the higher order board sp

        • by mikael ( 484 )

          The same could be said about factorizing large integer numbers in encryption or bitcoin mining with 256-bit hashes based on SHA-256. But it's the ratio to the vast combination size relative to the actual available solutions. Universities have a similar challenge in finding a campus wide timetable that guarantees that no student has a set of courses that clash in terms of tutorials/lectures/lab times, but that all students can attend tutorials/lectures/labs that are common to many subjects.

      • by Jack9 ( 11421 ) on Saturday September 02, 2017 @02:47PM (#55129583)

        > 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.”

        It's not the solution that gets you the prize, but the proof that the solution can be done quickly (without exploring nearly every permutation).

      • More to the point, anything larger that 8x8 isn't a chess board

        Well... [wikipedia.org]

    • How large is that? Many algorithms for simpler problems would fail if the size is multiplied by a big number.

      To slashdot's apparent surprise, once again the article happens to provide the answer. Amazing run of good fortune there.

      -- "What would be necessary would be either a proof that there is an algorithm that can solve the n-Queens Completion puzzle in polynomial time, or a proof that no such algorithm exists.”

  • by z3alot ( 1999894 ) on Saturday September 02, 2017 @02:01PM (#55129427)
    First of all, the problem cant in any real sense be considered a chess puzzle, except in the superficial sense of placing queens on a board. Chess reasoning has nothing to do with a solution of the problem.

    Second of all, the $1m prize is exactly the clay millennium prize for the resolution of P vs NP. If n-qeens has a solution in P, being NP-complete, this implies P=NP.

    tldr Sensationalist title is sensationalist
    • Moreover, you can write a headline like this every single day and never exhaust the number P vs NP equivalent problems.

      How Sudoku could win you a million dollars [unimelb.edu.au]

      Finding others is an exercise for the reader.

    • It also isn't even the only chess related problem which is NP-complete. For example, the retrograde chess problem is NP-complete. That problem is whether given an arbitrary chess board with some set of pieces, can you reach a given other configuration? It is very easy to make NP-complete or NP-hard problems involving chess, and this has to do with the fact that generic chess (who would win with a given configuration and a given set of pieces) is either PSPACE complete or EXP complete depending on how exactl
    • I don't understand the fuss, I found not only one but TWO ways to figure out P=NP using Python. Doesn't even require numpy or a GPU and it works even with super big numbers.

      #Solution 1:

      for N in range(sys.maxsize):
      P = 0
      if P == N * P:
      print("it works.")

      #Solution 2:

      for P in range(sys.maxsize):
      N = 1
      if P == N * P:

    • It's not necessarily the issue of P=NP, though such a solution absolutely would resolve this issue.

      The "problem" here is that there is no cost function. This is an Ariadne's Thread dilemma in that you can only verify your solution once you have placed as many queens as your placement will allow. You cannot place a single queen on an n x n board and then conclude that you are one step closer to a solution. There is no way to subdivide this problem, hence no way to solve it in a "sufficiently" fast manner (i.

    • by igny ( 716218 )
      It is not equivalent to the clay millennium prize. One can solve the queen chess problem by building an efficient quantum computer. You can't get the clay millennium prize if you built such quantum computer.
  • by Anonymous Coward

    Also something about chess.

  • I solved it (Score:2, Funny)

    by Anonymous Coward

    I have discovered a truly remarkable program which this box is too small to contain. I'll complete it after I get back from a duel I have later today.

  • by Anonymous Coward on Saturday September 02, 2017 @02:14PM (#55129481)

    Three researchers proved that the queen problem is NP-complete. The prize is the millennium prize for P=NP. The journal publication is at http://jair.org/papers/paper5512.html.

    • by Anonymous Coward

      I haven't read the paper, but I have a suspicion that this paper's conclusion that partially-filled N-queens is NP complete will be shown to be false.

      Why? Because my gut tells me that you can probably permute the board and convert partially-filled n-queens problem to a "normalized" form that can be solved as efficiently as the empty board n-queens problem: "can this input be rearranged into a prefix substring of the normalized solution for NxN?"

      • Because my gut tells me that you can probably permute the board and convert partially-filled n-queens problem to a "normalized" form that can be solved as efficiently as the empty board n-queens problem: "can this input be rearranged into a prefix substring of the normalized solution for NxN?"

        Interesting idea, but JOTTOMH I'm concerned about the normalization step. Permutation grows super-polynomially, of course, so naive normalization won't get you out of NP-Complete.

        Or from the other direction: assuming one-way functions exist, then starting with a normal-form partial-N-queens solution, shuffling into any of the non-normal permutations is poly-time, but reversing that shuffle looks at first glance like it might be orthogonal to some other one-way functions.

        But that's based on, like, 30 seconds

  • Serious question... I've written something like that before, and although it wasn't speedy... I don't recall it being particularly long either.

    Also, does it have to come up with all solutions quickly, or just one?

    • by mark-t ( 151149 )
      Nm... answered my question. They want a P solution.... the algorithm I wrote I never tried for anything 1000x1000 before, so I don't know how it would do.
    • "Quick" is defined in terms of how the running time for the solver scales with the size of the board. If you plot the time it takes to place N queens on an NxN board, you get an exponential curve for all currently known solvers. Either of two possibilities will result in winning $1 million:

      1. Proving that this is the best one can do and that there are no better algorithms.
      2. Finding a queens-placing algorithm whose running time is bounded by a polynomial function on N.

    • http://jair.org/papers/paper5512.html [jair.org] has the actual paper. What they have proven is that determining whether one can on an n-n chess board, given a starting set of queens in certain locations solve the n-queens problem on that board is NP-complete, and that counting the number of solutions is P#-complete (which is a little more technical and I don't want to get into). Here's the basic idea (if you want more, I recommend reading an intro complexity book like "The Nature of Computation" by Moore and Mertens)
      • Good of you to point out that the actual problem is something much harder than described in the OP. If the problem is just to find one solution to the n-queens problem, there are constructive algorithms for placing queens on the board that produce one solution (well, four with symmetry) in O(n) operations. Not just polynomial, but linear.
  • Start cursor in the upper left cell.
    Mark/Queen location

    --- Subroutine start
    Shift cursor right, down 2 (like a Knight!)
    Mark
    if out of bounds or final Y row
    break
    --- Subrouting end

    Shift cursor up, right 2
    Mark

    --- Subroutine start
    Shift cursor right, up 2
    Mark
    if out of bounds or initial Y row
    break
    --- Subrouting end

    Done. There is a simple solution, but the prize is about being able to prove there is a simple solution, without coming up with it (P = NP)

    • Done. There is a simple solution, but the prize is about being able to prove there is a simple solution, without coming up with it (P = NP)

      Setting some sensible constraints to a problem makes sense; even expecting a specific solution out of different possibilities. But just thinking about a very specific approach while (poorly) enunciating a problem doesn't make other solutions invalid; the person enunciating the problem is the one being wrong.

      From the confusing summary and linked page, your approach (didn't test it, but looks fine; I mean something on these lines) is the solution. It is not the solution they expect because they made a mistak

    • by Sique ( 173459 )
      You can claim your prize as soon as your algorithm put onto a standard computer came up with a solution to the "n queens on an n x n board" with n=1000.
      • You can claim your prize as soon as your algorithm put onto a standard computer came up with a solution to the "n queens on an n x n board" with n=1000.

        No. I can bet you 1 million (I don't having this amount with me, but I might be getting it soon. LOL) right now that the parent poster will not get anything. This was some kind of promotion of their paper by bringing into picture that other prize for proving N/NP problem (their site links to the prize's site). But they seemed to have made their message too commercial and too unclear until the point of seeming to be proposing a different thing.

        On the other hand, that algorithm (or another one on these lines

        • by Sique ( 173459 )
          I don't think you got the joke.

          I know what his algorithm does. And for n=1000, it will take more time than a billion universes put together. Thus he will get nothing -- at least not in this Universe.

          • I don't think you got the joke.

            I am afraid that the only not getting it is you. Read my previous comment again, mainly the second paragraph. I recommend you to do it slower this time.

            I know what his algorithm does. And for n=1000, it will take more time than a billion universes put together.

            The second sentence seems to indicate that the first sentence is wrong and you didn't understand my previous comment (read it again, please). Here comes more help just in case: you want to find out the right locations for the queens right? Now visit the Wikipedia article which I am linking in my previous comment and look at the picture on the RHS, this is ho

        • by clovis ( 4684 )

          I gotta say this is interesting, but maybe not workable.
          Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?
          We can't know ahead of time what the new location of the solved puzzle will be in the larger puzzle.
          We'll have to try all the possible new locations. I doubt it can be guaranteed that if a solution for n exists, then there will be guaranteed a solution for n+1 in which that n solution can be embedded, and that is a requirem

          • I gotta say this is interesting, but maybe not workable.

            Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.

            Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?

            This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the parent poster is proposing (i.e., starting in a given position and moving like the knight would do) seems as a descript

            • Ah! Come on! This has been my worse wrong-posting here since ever. Please, read only up to the first "You might even consider different approaches for different sizes.", otherwise you might get yourself into an endless loop. LOL
          • (I am reposting by removing the unnecessary repetitions, a direct consequence of my Sunday-morning reliability :))

            I gotta say this is interesting, but maybe not workable.

            Even before testing it and by being completely aware that such a proceeding is certainly not recommendable, I am quite sure that it is perfectly (and relatively simply) doable.

            Is there a simple algorithm for locating the solved 8x8 into a 10x10 and then placing the remaining 2 queens into the open squares?

            This isn't exactly what I meant. My approach was to use the solved sample to understand how to proceed, to find out the trend (by including how it varies with bigger/smaller board sizes) and to implement it. What the paren

      • by Jack9 ( 11421 )

        It takes under a second to run this (given a fair bit of memory, since scripting languages are greedy):

        $start = microtime();

        $n = 1000;
        $emptyVal = 0;
        $queenVal = 1;
        $n_by_n_array = array_fill(0, $n, array_fill(0, $n, $emptyVal));
        $xptr = 0;
        $yptr = 0;

        $queensPlaced = 0;

        while(true)
        {
        $n_by_n_array[$yptr][$xptr] = $queenVal;
        $queensPlaced++;

        $xptr += 1;
        $yptr += 2;
        if ($yptr

        • I am not sure that you can blindly apply what works for 8x8 to any size without doing anything else, but the eventual modifications are likely to be quite irrelevant. As written above, you should be able to come with a reasonably reliable approach just by analysing the simpler scenarios (7x7 and 9x9) and see how lower/higher sizes affect the original pattern. Also properly validating this approach, even just for a few simpler scenarios isn't completely straightforward (at least, not as straightforward as wr
        • by Whibla ( 210729 )

          I share CustomSolvers2's reserve in your apparent assumption that a technique that works specifically(?) on an 8*8 board would work for larger boards. A simple, and obvious test would be to try it with a 9*9 grid, and eyeball the result - though you'd have to implement some way to view the proposed solution for that board size. I don't even know, does the particular algorithm you're using work for all the smaller board sizes as well? FWIW, I'm a bit ashamed to admit I do not currently understand your code,

          • by Jack9 ( 11421 )

            My solution does not satisfy as a solution for n queens in an n x n board for many different values. Notably, there is no solution for n=4, n=3, n=2.

            The problem is deceptively easy for n/2+1 placements. Once past that, it takes an increasingly (maybe infinitely) complex perturbation to get a stable algorithm as size increases. See 8x8 below, where 8/2+1 placements are algorithmically simple.

            1 0 0 0 0 0 0 0
            0 0 0 0 1 0 0 0 -- 1, ceil(n/2) always a valid placement starting from 0 index
            0 1 0 0 0 0 0 0
            0 0 0 0 0

            • by Whibla ( 210729 )

              Thanks.

              If you were able to come up with a relatively simple general solution, it's not very hard for a computer to calculate 1mil x 1mil grid (https://www.quora.com/How-many-operations-per-second-can-a-computer-do-How-is-it-related-to-GHz). If you can parallelize this problem (which will do so nicely), the processing time of that experiment won't be noticeable. Proving that it's properly parallelized is another NP problem.

              And I tend to agree.

  • Ok, So give me a cluster of 30K machines, each machine having access to a few k of computer cores (think 4 GPUs) that gives me access to about 100M compute cores to solve this problem. I imagine this is a rather ridiculously easy problem to throw cores at - so with 100M cores in a compute cluster I imagine this problem simplifies into a few months worth of cluster time...
    • You imagine wrong. Which is the entire point.
    • by lucm ( 889690 )

      with 100M cores in a compute cluster I imagine this problem simplifies into a few months worth of cluster time...

      It depends. Do the nodes in the cluster run systemd?

  • And slashdot gets stupider yet.

    So, prove P=NP, win $1 million. Makes sense, why is this nonsense even here?
  • by gbell ( 84505 ) on Saturday September 02, 2017 @05:41PM (#55130205)

    Really cool in-browser visualizer of 5 different algorithms for solving this problem...

    http://haseebq.com/n-queens-visualizer/ [haseebq.com]

  • Both the summary and the article are crap.

    The important part is the following line from the abstract:

    We show that n-Queens Completion is both NP-Complete and #P-Complete.

    All the rest (other than the math in the actual paper) is fluff.

  • the answer is 42.
  • it feels like it should be possible to set up a physical analog of the problem and let it find its own stable point. Isn't this what quantum computing is meant to solve ? Or is that cheating by trying every possible solution just very quickly ? There, I've just demonstrated my ignorance (again).

You don't have to know how the computer works, just how to work the computer.

Working...