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

 


Forgot your password?
Close
typodupeerror
×
Programming Games

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

Posted by EditorDavid from the million-dollar-check-mate dept.
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 More

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

Comments Filter:

  • Large size? (Score:3)

    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,

        • Comment removed based on user account deletion

          • Re: (Score:2)

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

            • Comment removed based on user account deletion
          • 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)
            • Comment removed based on user account deletion
              • 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

                • Re: (Score:2)

                  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?

                  • Comment removed based on user account deletion

                  • 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

                    • Re: (Score:2)

                      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.

                • Comment removed based on user account deletion
            • Comment removed based on user account deletion

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

        • Re: (Score:3)

          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

        • Re: (Score:2)

          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.

      • The story is mis-worded. You did it again editors. (Score:5, Informative)

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

  • misleading title and rebranded P vs NP (Score:5, Insightful)

    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.

    • Re: (Score:2)

      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.

  • Solve P=NP win $$$ (Score:1)

    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.

  • The actual content of the article (Score:4, Informative)

    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.

    • Re: (Score:1)

      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?

    • Re: (Score:2)

      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)

    • Comment removed based on user account deletion

    • Re: (Score:2)

      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.
      • Comment removed based on user account deletion

        • Re: (Score:2)

          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.

        • Re: (Score:2)

          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

      • Re: (Score:2)

        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

        • Comment removed based on user account deletion

        • Re: (Score:2)

          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,

          • Re: (Score:2)

            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

            • Re: (Score:2)

              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.

    • Re: (Score:1)

      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?

  • Visualizer of different algos (Score:3, Interesting)

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

Slashdot Top Deals

I THINK THEY SHOULD CONTINUE the policy of not giving a Nobel Prize for paneling. -- Jack Handley, The New Mexican, 1988.

Close