Member Avatar for macdonald12

Hello all,

I'm trying to make a program in C, but it's actually the algorithm that's giving me hell.

The goal is to create a program that calculates and displays the total number of end-locations (all locations, including similar ones) an object can reach in a 2d board (grid), using a defined maximum of moves, using only pre-defined movements.

For example, if the object would start at (0,0), and the movements would be defined as:

movement1: (x+3) (y+1)
movement 2: (x+2) (y+3)

and the maximum of allowed moves would be 8. Then what would all the possible end-location coordinates be? (of the in total (2*2*2*2*2*2 = 64 moves?).

It's probably very easy, but i've been going crazy over it for a couple of hours now - and i keep on ending up with nested for-loops that just don't work out.

If anyone out here could give me a push into the right direction, it would be very much appreciated! :)

Edited by macdonald12 because: n/a
  • 2 Contributors
  • 5 Replies
  • 203 Views
  • 6 Days Discussion Span
  • Latest Post Latest Post by SVR

Dani AI

Generated

Good progress from and useful pointers from . Two different problems often get mixed up here and it helps to call them out first: (A) counting every move sequence of exactly K steps (each choice counted) and (B) enumerating distinct coordinates reachable in up to K steps. Problem A is trivial combinatorics (M^K where M is number of move choices). Problem B is the interesting one and is where efficiency matters.

A practical, scalable solution for B is iterative dynamic programming (level-by-level propagation). Keep a map keyed by (x,y) with a count (number of ways to arrive there in t moves). Initialize with start -> 1. For t = 1..K create next_map by, for every (x,y,count) in current_map and for every allowed move (dx,dy), adding count into next_map[(x+dx,y+dy)]. After each step merge duplicate keys (sum counts). After K steps the keys of the map are the reachable coordinates; sums give route-multiplicities. Time is O(K S M) where S is distinct positions per level and M is number of moves. Memory is O(S). This avoids exploring all M^K sequences when many share endpoints.

A compact C-style outline (aggregation by sorting is one simple way to dedupe without external hash libraries):

typedef long long cnt_t;
struct Node { int x,y; cnt_t cnt; };

/* build next[] by appending cur[i] + each move[j], then qsort(next) by (x,y)
   and merge consecutive equal (x,y) summing cnt to compress duplicates */

Two extra tips tied to this thread: use a shortest-path test to prune early — for knight moves there is a small closed-form helper to compute the minimal number of moves on an infinite board. That test is stronger than the naive delta/2 heuristic and avoids useless work:

int min_knight_moves(int dx, int dy) {
    dx = abs(dx); dy = abs(dy);
    if (dx < dy) { int t=dx; dx=dy; dy=t; }
    if (dx==1 && dy==0) return 3;
    if (dx==2 && dy==2) return 4;
    int a = (dx+1)/2;
    int b = (dx+dy+2)/3;
    int m = a > b ? a : b;
    while ((m & 1) != ((dx + dy) & 1)) m++;
    return m;
}

Use that to reject targets when allowedMoves < min_knight_moves(dx,dy). Also watch integer overflow for large K (use 64-bit counters or big integers) and choose BFS when you only need the minimum moves rather than counts.

Recommended Answers

All 5 Replies

Member Avatar for SVR

If speed is not critical use a recursive function.

GenNextMove(int depth)
{
   if(depth == nMaxMove)
   {
      nTotalPos++;
      return;
   }
   for(i = 0;i<nMoves;i++)
   {
        GenNextMove(depth+1);
   }
   
}

main(...)
{
    GenNextMove(0);
}

You can pass the current position as well to store in a final positions array when MaxMoves is reached.

Member Avatar for macdonald12

Thank you very much for your input SVR, i've used it to create the following code for me to practice and understand:

#include <stdio.h>
#include <stdlib.h>

int x, y = 0;

int endLocations = 0;
int maxJumps = 8;

void nextJump(int depth) {

	if(depth == maxJumps) {
		printf("Endposition (x,y) = (%d,%d)\n", x, y);
		endLocations++;
		return;
	}
	
	int i;
	
	for(i=1;i<3; i++) {
	
		switch(i) {
		
			case 1:
					x = x+3;
					y = y+1;
			case 2:
					x = x+2;
					y = y+3;
		}
		nextJump(depth+1);
	}
}

int main (int argc, char *argv[]) {

	nextJump(1);
	printf("Total endlocations: %d\n", endLocations);
	
	return 0;
}

Considering it's getting late and i probably need some sleep, i'm most likely doing something stupid now - as this keeps on returning 128 endlocations which don't look correct.

Any further help would be much appreciated, thanks alot for your input already :)

Edited by macdonald12 because: n/a
Member Avatar for SVR

You'll want to keep your x & y local so each move is incremented from the correct position (you'll need to pass these in as params with the starting position sent in the first call). As it is the global position is getting added to (which is the last end position you happen to be on). The local version gets restored as you return to the previous depth and things can continue from there.

As for the depth, you are starting at 1. You should start at 0. 0 position being the start and not a move).
For each path down to MaxMove you will get positions as such ...

0: x = ?, y = ? // start pos
1: x = ?, y = ? // after move 1
2: ...
...
maxJumps: x = endx, y = endy // after maxJumps

Put a printf before the maxJumps check.

With 2 options and 8 depth I think it should give you 2^8 or 256 end positions.

Member Avatar for macdonald12

Thanks again for your help! With it i was able to make a program that simulates the movement of an object in an infinite 2d-board. The movements of this object correspond to the movements of a knight in a chess-game.

This is the code for the program:

#include <stdio.h>
#include <stdlib.h>

int endLocations = 0;
int routes = 0;

int xNew, yNew;


void nextJump(int depth, int x, int y, int xEnd, int yEnd, int totalMovesAllowed) {

	int xValue = x;
	int yValue = y;

	if(depth == totalMovesAllowed) {
		if(xValue == xEnd && yValue == yEnd)
			routes++;
		endLocations++;
		return;
	}
	
	int i;
	
	for(i=1;i<9; i++) {
	
		/** Represents all eight movements a Knight can make **/
		switch(i) {
		
			case 1:
					xNew = xValue+2;
					yNew = yValue+1;
					break;
			case 2:
					xNew = xValue+2;
					yNew = yValue-1;
					break;
			case 3:
					xNew = xValue-2;
					yNew = yValue+1;
					break;
			case 4:
					xNew = xValue-2;
					yNew = yValue-1;
					break;
			case 5:
					xNew = xValue+1;
					yNew = yValue+2;
					break;
			case 6:
					xNew = xValue+1;
					yNew = yValue-2;
					break;
			case 7:
					xNew = xValue-1;
					yNew = yValue+2;
					break;
			case 8:
					xNew = xValue-1;
					yNew = yValue-2;
					break;
		}
		nextJump(depth+1, xNew, yNew, xEnd, yEnd, totalMovesAllowed);
	}
}

int main (int argc, char *argv[]) {

	int xBegin, yBegin, xEnd, yEnd, totalMovesAllowed;

	printf("Check total amount of Knightjump routes\n");
	printf("Coordinates begin position: x y: ");
	scanf("%d %d", &xBegin, &yBegin);
	printf("Coordinates end position: x y : ");
	scanf("%d %d", &xEnd, &yEnd);
	printf("Number of allowed jumps: ");
	scanf("%d", &totalMovesAllowed);

	/** Check 1 for increased efficiency 
	this is a simple check, checking for the minimum distance that needs to be covered to even reach the end-spot
	**/

	int deltaX, deltaY, movesNeededX, movesNeededY, totalMovesNeeded;
	deltaX = xEnd-xBegin;
	deltaY = yEnd-yBegin;

	if(deltaX<0)
		deltaX = deltaX*-1;
	if(deltaY<0)
		deltaY = deltaY*-1;

	movesNeededX=deltaX/2;
	movesNeededY=deltaY/2;

	if(movesNeededX<1)
		movesNeededX=1;
	if(movesNeededY<1)
		movesNeededY=1;

	if(movesNeededX >= movesNeededY)
		totalMovesNeeded = movesNeededX+1;
	else
		totalMovesNeeded = movesNeededY+1;

	if(totalMovesAllowed >= totalMovesNeeded)
	{

		/** Check 2 for increased efficiency
		This check checks for the fact that a knight-move, on a black/white-square colored board
			will always move from black -> white or vice-versa.**/

		int beginSquare, endSquare;

		if((xBegin+yBegin)%2 != 0)
			beginSquare = 0;
		else
			beginSquare = 1;
		if((xEnd+yEnd)%2 != 0)
			endSquare = 0;
		else
			endSquare = 1;

		int difference = totalMovesAllowed%2;

		if(beginSquare == endSquare && difference == 0) {
			/** Checks passed - Call actual function **/
			nextJump(0,xBegin,yBegin, xEnd, yEnd, totalMovesAllowed);
		} else if(beginSquare == endSquare && difference != 0) {
			/* not possible -> do nothing */
		} else if(beginSquare != endSquare && difference == 0) {
			/*not possible -> do nothing */
		} else if(beginSquare != endSquare && difference != 0) {
			/** Checks passed - Call actual function **/
			nextJump(0,xBegin,yBegin, xEnd, yEnd, totalMovesAllowed);
		}
	}
	printf("\nTotal amount of routes: %d\n", routes);
	
	return 0;
}

Resulting in the following output with the given input:
[IMG][/IMG]

However, i'm supposed to be making this program more efficient - so it can calculate upfront if a given end-position can be reached from the begin-position in the given amount of moves, so that it doesn't need to calculate all routes just to come to that conclusion.

For this i added 2 checks, i think the 2nd check is fairly simple and implemented correct, however, i'm not so sure on the first check.

If anyone can give some input regarding this it would be much appreciated. And thanks again, SVR! :)

Member Avatar for SVR

i'm supposed to be making this program more efficient - so it can calculate upfront if a given end-position can be reached from the begin-position in the given amount of moves, so that it doesn't need to calculate all routes just to come to that conclusion.

That is a typical search problem. The given solution is a 'depth first' search where you search down the chain of moves before considering other moves. Potentially more efficient is a 'breadth first' search where you look at all moves at a given depth before proceeding down the chain.
Each has it's merit for a given task.

Most chess programs use a combination algorithm. Do a web search for 'A* search' and 'iterative deepening'.

Some of the logic can get pretty hairy so enjoy :)

As far as the current code, you should check the xEnd & yEnd before the depth. Otherwise you're only going to get routes that are maxMoves long. It may take less than that.

I dont see anything glaringly wrong with your check#1. It makes sense that the knight can move a max of 2 in any move so anything farther than movesallowed*2 can't be reached.
I bet if you think on it hard enough you can expand that logic to determine exactly how many moves it will take without having to search at all.

Edited by SVR because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.