Knight Movement (Chess)

[Ikaron]

This isn't a "How do i..?" thread, it's just for discussion as I'm interested how other people might go about solving this problem.

So a Knight, for those who don't play chess, can only move 2 squares in one direction and 1 square in the other, like an L. A friend asked me if I could come up with a way to display the next move of a knight without doing something like:
Highlight(x+2, y+1);
Highlight(x+2, y-1);
Highlight(x-2, y+1);
until you account for all 8 potential moves.

This is what I came up with after thinking it over:

void Knight::ShowMoves(int x, int y)
{
	// represent X coordinate as 0,
	// represent Y coordinate as 1
	const int xCoord = 0;
	const int yCoord = 1;

	int iA(0), iB(0); // special index iterators
	int next[2], cur[2]; // next represents next position,
			     // cur represents current position

	cur[xCoord] = x;
	cur[yCoord] = y;

	// iA represents X on the first iteration, and Y on the second.
	// iB represents what iA does not.
	for (iA = xCoord; iA <= yCoord; iA++)
	{
		next[xCoord] = cur[xCoord];
		next[yCoord] = cur[yCoord];

		iB = (iA == xCoord) ? yCoord : xCoord; // Set iB to what iA isn't

		// +2 on the first iteration, -2 on the second.
		for (int a = 0; a < 2; a++)
		{
			next[iA] = (next[iA] > cur[iA]) ? cur[iA] - 2 : cur[iA] + 2;

			// +1 on the first iteration, -1 on the second.
			for (int b = 0; b < 2; b++)
			{
				next[iB] = (next[iB] > cur[iB]) ? cur[iB] - 1 : cur[iB] + 1;

				pChessBoard->Highlight(next[xCoord], next[yCoord]);
			}
		}
	}
}

I'm curious what solutions other people might be able to come up with if they so care to. :) Also feel free to discuss / critique my code, this was just a fun little thing I did at the random request of a friend.

[helios]

It seems awfully complex for a rather simple problem.

inline safe_highlight(int x,int y){
    if (is_inside(x,y))
        highlight(x,y);
}

void highlight_knight(int x,int y){
    static const int offsets[][2]={
        {1,-2},
        {2,-1},
        {2,1},
        {1,2},
        //Note that the elements below this point are the opposite signs of the
        //previous ones, so the array could be cut in half by adding a little
        //more logic to the loop.
        //It doesn't matter much, though.
        {-1,2},
        {-2,1},
        {-2,-1},
        {-1,-2}
    };
    for (int i=0;i<8;i++)
        safe_highlight(x+offsets[i][0],y+offsets[i][1]);
}

[Ikaron]

That's definitely a much more elegant solution. My goal was to come up with a solution that didn't pre-define all possible moves and instead used the fact that it could be broken down into a simple pattern to do so instead, but yeah, it's over complicated.

Thanks for your response. :)

[R0mai]

Little math trickery, from a just graduated (ex)high-school student.

#include <iostream>

template<class T>
T integer_pow(const T& a, unsigned b) {
    T res = 1;
    while(b--) {
        res *= a;
    }
    return res;
}

int main() {    
    for(int x = 1; x <= 8; ++x) {
        std::cout << 
            (390600 - 
            954634 * x +
            889245 * integer_pow(x,2) -
            419300 * integer_pow(x,3) +
            109935 * integer_pow(x,4) - 
            16226 * integer_pow(x,5) + 
            1260 * integer_pow(x,6) -
            40 * integer_pow(x,7))/840 
        << ", " <<  
            (241920 - 
            608610 * x +
            570591 * integer_pow(x,2) -
            270389 * integer_pow(x,3) +
            71190 * integer_pow(x,4) -
            10535 * integer_pow(x,5) +
            819 * integer_pow(x,6) - 
            26 * integer_pow(x,7))/2520
         << std::endl;
    }   
}

[helios]

That's a Lagrange polynomial, isn't it? Isn't it? You pervert.

[Ikaron]

My mathematical skills are rather lacking, but it looks kind of like a taylor series though I could be horribly wrong. Either way, that's rather impressive R0mai, definitely makes me want to brush up on my math.

[R0mai]

@helios To be honest I didn't know it was called Lagrange polynomial, but yes it looks like it is onetwo.

@Ikaron For each polynomial I solved 8 equations in the form y == h + g x + f x^2 + e x^3 + d x^4 + c x^5 + b x^6 + a x^7 for variables a,b,c...h substituting (x, y) for each equation with (1,-2),(2,-2),(3,-1) etc.

And as I see, WolframAlpha could have done this for me within seconds : http://www.wolframalpha.com/input/?i=InterpolatingPolynomial%5B{-2%2C+-2%2C+-1%2C+-1%2C+1%2C+1%2C+2%2C+2}%2C+x%5D

[helios]

Yes, that's exactly how interpolating polynomials are constructed. Of course, it kind of defeats the purpose of the whole interpolation thing if you're only going to evaluate it at the points you used to construct it.

[kev82]

for(int i=0;i!=25;++i) {
	if(i%5==2 || i/5 == 2 || (abs(-2+i%5)+abs(-2+i/5)) != 3) continue;
	std::cout << -2+i%5 << " " << -2+i/5 << std::endl;
}