I am trying to find a mathmatical formula to determine the minimal moves the knight needs to make in order to reach a house X from an initial position Z. I have already discovered the formula for the minimal moves that works in case the row or the column of the knigth and the target position is the same, AS IT SEEMS. Now I am intrigued with the fact the measure the distance between the knight and the target position gets far (distance equals distance between columns plus distance between rows), the more a number tends to repeat, having that number the minimal moves the knight needs to make in order to reach a house X, as you can see here (every red dot in a same row needs the same minimal number of moves for the knight to reach in it):
Can someone with a high numerical IQ give me a light on this topic?
@Megadoggah It seems you did not understand the problem. The problem is: Given an starting position X for a horse in an empty board and a house Z that is different from X, calculate through a mathmatical formula the minimal of legal moves in which the horse needs in order to reach that house.
Oh I see. Pretty difficult.
That’s going to be a very difficult formula. More like a programed algorithm.
@AcabaComigo - Perhaps you may find some info or links in this Wiki article about the "Knights Tour" I see it has some math formula's regarding Knight movement on a grid. :] - en.wikipedia.org/wiki/Knight%27s_tour
So are we supposed to take an IQ test first or something?
The simplest is to make an 64x64 array with the 64 squares a1...h8 horizontally as well as vertically and then the distance in knight moves on their intersection.
I cannot offer you a perfect solution, but one that is reasonably close:
Your problem can be cast into the form of a metric travelling salesman problem. Take all fields you want to reach as nodes, take a reasonable portion of the pairs as edges (e.g. all but you can do better). Then convince yourself that the problem is metric, i.e. the usual inequality d(a,b) <= d(a,c) + d(c,b) holds. Then you can approximate the optimal solution by a factor of 2 with the minimal spanning tree and by a factor of 1.5 with Christofides' algorithm.
If you put some thought into picking the edges, this problem should become reasonably easy. However, I have not taken an IQ test, so I'm not qualified to offer you help there...
I actually wrote a program for this, sort of, in python with pygame, and although I did it with an 8x8 board, you could easily scale it up to a 32x32 board, and then figure out the pattern and work backwards. I will make a video on my program, but in the mean time here is my code:
And are attached images. It is color coded as follows: Pink is initial, red is 1 move away, orangy-red is 2 moves away, orange is 3 moves away, yellow is 4 moves away, green is 5 moves away, and blue is 6 moves away. :
Edge case: placing your knight on the outer two rows / columns means it will reach anywhere in 5 moves, except the 8 squares d2,e2,d7,e7,b4,b5, and g4,5 where it can reach anywhere within 4 moves;
Center case: placing your knight here allows it to reach anywhere within 4 moves;
Corner case: placing your knight here allows it to reach anywhere within 5 moves, but the opposite corner is going to take 6 moves to get to;
The program I wrote gave me some other insight, which I plan to summarize into a video. But the key thing to take away (although if you play a lot of chess you somewhat already know) is that in a 7x7 grid, the knight can get to any square in 2 or three moves, except going diagonally by two squares, which takes four moves. Recognizing if a square is 2 moves away is rather easy for a knight, but three squares is not always obvious, but if the square is within 3 units from the Knight, is not two moves away, or diagonal to the knight by 2 units, then it is always three moves away.
I will make a forum post and youtube video of this later, after I improve some aspects. I would like to introduce placing pieces on the board to restrict the Knight. It shouldn't be too hard to change the code by changing the "while" statement so that it doesn't stop at 64 squares, removing the restriction that squares need to be between 1 and 8, and fiddle with the module PyGame so that it displays more than just 8 squares, and make the color list longer.... I will do something about this and come back with some photos maybe.
I made something like this for an infinite board but the pattern gets boring rather quickly, and I got my computer stolen so I don't know where it is. But it is repetitive, somewhat octagonal, and I'm sure there's a formula for it, but it's not clear to me how you would write the formula.