USACO DEC08 Problem 'chkr' Analysis

by Fatih Gelgi

The trivial solution for this problem is brute-force (exhaustive) search that tries all the alternatives. One of the easiest way to do that is to use recursion. In the problem, we can try all possible jumps for each king. The recursive procedure for each king can be given as follows:

1. Add the current location to the list of moves.
2. If there is no remaining opponent's checkers then write the solution and terminate the program.
3. Otherwise, from the current location, check each direction if it is avaliable to jump over an opponent's checker. If available,
   1. mark that checker, and make a recursive call to the jumped location,
   2. after exiting the recursive call, remove the mark,

Note that, in the recursive procedure, we don't mark the moves of the king on the board since the king can jump to a location that is already passed. For example, consider board below:

  1 2 3 4 5 6 7 8           R C
1 - + - + - + - +    start: 6 5
2 + - + - + - + -    move:  4 3
3 - + - K - + - +    move:  6 1
4 + - + - + - + -    move:  8 3
5 - o - o - o - +    move:  6 5
6 + - + - K - + -    move:  4 7
7 - o - o - + - +
8 + - + - + - K - 

The king at (6,5) make a loop and returns back to its original location then jumps of the the checker at (6,5). If the moves of the king are marked then it cannot return back to (6,5).

The solution requires O(N^2) memory since it keeps the board - O(N^2), moves - O(N^2) and the recursive function - at most O(N^2) deep.

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

char board[200+4][200+4];			/* guards on edge */
int movelistr[200], movelistc[200], nmoves;
int n, ncheckers;
FILE *fout;

int dx[4] = {-1,  1, -1,  1};
int dy[4] = {-1, -1,  1,  1};

domove (r,c) {
    int j;
    board[r][c] = '+';
    movelistr[nmoves] = r;
    movelistc[nmoves] = c;
    nmoves++;
    if (nmoves == ncheckers+1) {
	for (r = 0; r < ncheckers+1; r++) 
	    fprintf (fout, "%d %d\n", movelistr[r]-1, movelistc[r]-1);
	exit (0);
    }
    for (j = 0; j < 4; j++) {
        int x = dx[j];
        int y = dy[j];
        if (board[r+x][c+y] == 'o' && board[r+2*x][c+2*y] == '+') {
	    board[r+x][c+y] = '+';		/* remove this checker */
	    board[r+2*x][c+2*y] = 'K';		/* move the king */
	    domove (r+2*x, c+2*y);		/* do all moves for him in new place */
	    board[r+2*x][c+2*y] = '+';		/* 'move' king back */
	    board[r+x][c+y] = 'o';		/* to here */
        }
    }
    nmoves--;
    board[r][c] = 'K';
}

main () {
    FILE *fin = fopen ("chkr.in", "r");
    fout = fopen ("chkr.out", "w");
    int i, j;

    fscanf (fin, "%d", &n);
    for (i = 2; i < n+2; i++) {
	fscanf(fin, "%s", &board[i][2]);
        for (j = 2; j < n+2; j++)
	    if (board[i][j] == 'o')
		ncheckers++;
    }
    for (i = 2; i < n+2; i++)
	for (j = 2; j < n+2; j++)
	    if (board[i][j] == 'K') domove(i,j);
    fprintf (fout, "impossible\n");
    exit (0);
}