mersenneforum.org The chess puzzle that led to a Fields Medal
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-02, 08:41 #1 hoppi   Aug 2022 510 Posts The chess puzzle that led to a Fields Medal https://en.chessbase.com/post/the-ch...a-fields-medal This problem can be transformed to an easier puzzle which should take minutes to solve.
2022-08-03, 08:58   #2
hoppi

Aug 2022

58 Posts

Quote:
 Originally Posted by hoppi This problem can be transformed to an easier puzzle which should take minutes to solve.

I can PM the easier puzzle to those who are curious about it but do not want to spend much time on it.

2022-08-03, 20:10   #3
swellman

Jun 2012

3,643 Posts

From the article:

Quote:
 As Dr. June Huh, now 39, explains it, his first insight into combinatorial mathematics came from a video game called The 11th hour. This horror adventure movie game from 1995 featured the following puzzle to be solved:
I played The 11th Hour back in the day. Remember encountering some difficult puzzles similar to this one in the course of playing the game, though I do not recall this particular four knight problem. Dr. Huh must have been quite young if it took him a week to solve it. Of course his gaining insight into chromatic polynomials shows his true genius.

 2022-08-04, 01:45 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 5×2,003 Posts It took me considerable time to solve it, too... If you see it as a chess board (with white and black squares) and realize that from the 10 squares, only 4 are white, and 6 are black (or viceversa, the idea is that they are not 5 and 5, and the knight moves from one color to the other) then solving it becomes much easier. Last fiddled with by LaurV on 2022-08-04 at 08:20
2022-08-04, 02:24   #5
uau

Jan 2017

149 Posts

Quote:
 Originally Posted by LaurV I took me considerable time to solve it, too... If you see it as a chess board (with white and black squares) and realize that from the 10 squares, only 4 are white, and 6 are black (or viceversa, the idea is that they are not 5 and 5, and the knight moves from one color to the other) then solving it becomes much easier.
Why would that matter much? Isn't the key thing to notice that there's only a single square from which you can reach more than two others?

2022-08-04, 03:37   #6
hoppi

Aug 2022

5 Posts

Quote:
 Originally Posted by uau Why would that matter much? Isn't the key thing to notice that there's only a single square from which you can reach more than two others?

You are on the right track.

 2022-08-04, 08:56 #7 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 234378 Posts Well... when I said it took time I didn't mean ages, but it was not something where you can see the solution in a blink, unless you do the graph of possible moves. Put a number to each square and draw a graph where the horses can wander. Which after a bit of rearranging the nodes and ignoring the numbers, it looks like this, and now you indeed can see in a blink where you have to squeeze those horses to exchange them. In fact, this puzzle could have been made more complicate by adding some squares and horses, or much simpler, for example getting rid of the two squares you never need to use (but then it would have been too simple, not many "ramifications" or "false tracks"). This reminds me the problem with the locomotion (which I first time met in primary school, and was the only guy in the class which could solve it, hehe, we had an inspection and one inspector gave this problem, so I "saved the honor" of the class, to the delight of the teacher) - there is a railroad like in the picture below, with one locomotive and two large train cars filled with goods, there is a tunnel through which the wagons can't fit, but the locomotive can. The locomotive is strong enough to push both wagons in the same time, or to pull them, or to pull one and push one (L in between) in the same time. Your goal is just to exchange the position of the wagons, having the locomotion free at the end (i.e. in the same place/loop, not locked at some end of the line behind a wagon). This puzzle also can be made more complicate, by adding loops and wagons, to which the number of movements will increase exponentially. The Rubik/Babylon tower with colored balls, the sphere, as well as the rings-on-a-wire (which is freaking difficult, but based on the same idea, you move things aside to make place for other things, then move the first things back, in reverse, or interleave them) - I met much later in life Last fiddled with by LaurV on 2022-08-04 at 09:33
2022-08-04, 09:29   #8
hoppi

Aug 2022

5 Posts

Quote:
 Originally Posted by LaurV Well... when I said it took time I didn't mean ages, but it was not something where you can see the solution in a blink, unless you do the graph of possible moves. Put a number to each square and draw a graph where the horses can wander. Which after a bit of rearranging the nodes and ignoring the numbers, it looks like this, and not you indeed can see in a blink where you have to squeeze those horses to exchange them. In fact, this puzzle could be make more complicate by adding some squares and horses, or much simpler, for example getting rid of the two squares you never need to use (but then it would have been too simple, no many ramifications). Attachment 27164

Congrats!

Now that it has been spotted, I can share my link where you can experiment with it. The second page displays both puzzles and you can click cells in the first one or in the second one, they are updated simultaneously. When you play optimally (to solve with the least number of moves), you can easily see that 2 squares to the right in the easier puzzle is not needed.

https://hoppi.neocities.org/Hop/puzz...essPuzzle.html

2022-08-04, 15:45   #9
uau

Jan 2017

149 Posts

Quote:
 Originally Posted by LaurV Well... when I said it took time I didn't mean ages, but it was not something where you can see the solution in a blink, unless you do the graph of possible moves. Put a number to each square and draw a graph where the horses can wander.
That's my point about noticing there's only a single square from which you can reach more than two others. It follows that there's only one square where you have more than one choice other than moving the knight back where it came from, and thus that observation is enough to realize that the graph must look something like what you drew (the only thing you then need to determine is the length of each of the 3 paths starting from that one square).

 Similar Threads Thread Thread Starter Forum Replies Last Post charybdis Math 2 2022-07-18 10:44 rudy235 Math 16 2018-08-08 18:58 devarajkandadai Number Theory Discussion Group 7 2017-12-06 01:46 Raman Chess 6 2016-12-06 06:50 mfgoode Lounge 4 2006-12-10 22:55

All times are UTC. The time now is 16:54.

Wed Aug 17 16:54:24 UTC 2022 up 41 days, 11:41, 1 user, load averages: 1.20, 1.38, 1.39