Chess Problem

Discussion in 'Physics & Math' started by The God, Mar 11, 2017.

  1. The God Valued Senior Member

    Messages:
    3,436
    It is possible for a Knight to cover all the 64 squares, starting from its original position, without repeating any square. This obviously requires 63 moves.

    Now take 2 white Knights at their original positions on a blank board. They are on a journey to cover all the 64 squares without repeating any square. They move in sequence in such a manner that they are never in attacking position. What is the maximum number of moves till then they avoid the attacking position?

    Can it be solved analytically?
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. rpenner Fully Wired Staff Member

    Messages:
    4,833
    Surely you mean 2 knights, one white and one black, for two knights of the same color could never be in attacking position.
    Why would there be maximum number of moves? There are over 13 trillion closed knight tours where a knight can visit every square, in a cycle with period 64. If two knights used the same, separated by some number of moves, it seems reasonable that they could move the same direction about such a path, indefinitely, without ever being able to attack the other.
    What do you mean "solved analytically" ? Analysis is not the most natural field of mathematics to apply to this subject.
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. The God Valued Senior Member

    Messages:
    3,436
    Attacking position = Separated by one move.

    Two knights starts from b1 and g1 and make moves one after another to cover all the 64 squares without repeating a square. The number of such routes are very high, but can they complete this without ever coming in attacking position.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Nacho Registered Senior Member

    Messages:
    123
    There are multiple solutions for the first problem you posed, if you instead start out at a corner square. I think there are probably many-many-many solutions. I couldn't find a way to analyze the problem, so I wrote a brute-force computer program to find solutions, and was very-very lucky to find these solutions. Though, I haven't been able to find a solution, yet (2 days work), starting out in the left-hand Knight's starting position, which is the way you posed/wrote the problem.

    I don't think the problem lends itself to an analytical approach as analysis is dependent on the placement of the moves of each and every "try", or solution that you could try. The reason for this is different squares on the board allow different number of moves of the Knight. The inner 16 squares allow 8 moves; the 20 squares surrounding that allow 6 moves; the 28 squares on the outside allow only 4 moves.

    I don't think that you could even quantify by analysis the number of moves there would be in the program I wrote, if it did (and could) run to completion. That is, again, because the number of moves in each "try" is dependent on where each move in that "try" falls on the board, and also how many moves need be taken before that "try" is found not to work. I'm saying that to quantify that number, you would have to run the problem you posed out by long-hand, the way my program does. And when that ends, and only when that ends, would you find the number. And, there are upwards of 5^63 different moves in the full solution (that is the evaluation of 1 of several ways I tried to quantify the number. There are other approximations, more accurate but more involved -- but they don't differ by more than a few powers of 10).

    I'm sure I was lucky to find the solutions I did find quickly, starting out in a corner square. I also think why I have not been lucky with the left-hand Knight's starting position test is because of the order in which I generate the 8 different Knight moves. I start out generating from the 11 o'clock position and go counter-clock-wise. That worked good on the corner test, but I'm saying that isn't working well for the left-hand Knight's starting position test. Maybe if I had started at 1 o'clock and went clock-wise I would have had more luck. I'm saying that it might be the starting moves that are mattering to the tests -- the position there are at now wouldn't change to the next Knight move position for around 10^30 years!

    I haven't (yet??) looked at the 2nd problem you posed -- the one with both Knights moving in unison.
     
    Last edited: Mar 14, 2017
  8. The God Valued Senior Member

    Messages:
    3,436
    Great Nacho for the program you have written.

    I will repeat the problem, the idea is that both knights move in turn to cover all the 64 squares.

    First Move : Knight at b1 starts and makes a move to either of 3 possibilities...that is d2, c3 and a3. Suppose he moves d2.

    Now the knight at g1 moves to either of f3, e2 and h3. But f3 is not permitted as both the nights will come in attacking position.......


    we will have to find out the maximum number of moves without the nights coming to attacking position.
     
    Last edited: Mar 15, 2017
  9. Nacho Registered Senior Member

    Messages:
    123
    Maybe I didn't state that clear enough. You can't really run a computer program to exhaustively find all of the solutions or to prove there are no solutions. I estimated it would take my "Intel i3-2370M CPU @ 2.40GHz × 4", which is low-to-medium end I guess, over 10^20 years to complete the program, give or take a few orders of magnitude. Your only hope is that you pick initial settings that will give you a quick solution, or juke around execution settings/values that you think might help you find a quick solution. Or, that maybe there are so many solutions that you will hit one no matter your initial settings and execution settings/values (this is the way I was able to find a solution in the first try starting at a corner).

    That "2 Knight" problem requires essentially the same resources as the 1st problem. There are still 63 moves made -- they are just made by 2 separate pieces, plus there is 1 more test each move that the move doesn't land within a Knight's move of the other.

    I guess it doesn't hurt to try, but if solutions are not found it won't ever prove anything.
     
  10. The God Valued Senior Member

    Messages:
    3,436
    Is there any single unique legal spread, where white (or black) has maximum number of legal moves.
     

Share This Page