50124. Knights' Tour with Functions

I'm a slow walker, but I never walk backwards.

Task Description

A knight in chess has up to eight possible valid moves, as shown in the following figure.

index of possible movements

Assume that we have $m$ knights on an $n$ by $n$ chess board. The knights are indexed from $1$ to $m$. The knights will move one step at a time according to their increasing index order.

A knight decides its next move by the number of valid moves from the move he is about to take. This is denoted as the $p$ value of this moves. A valid move is defined as a move that it does not move the knight out of the board, and it does not move the knight into a cell that any knight is currently in, or has been to. A knight will choose the move that has the minimum $p$-value.

We first write a function validMoveNum to count the number of valid moves when we are given the row $r$ and column $c$ of the cell a knight is in, the board size $n$, and an array visited. A cell in the visited array has a non-zero integer if the corresponding cell has been visited by any knight, and 0 otherwise. For example, if visited[2][5] = 0 it means that the cell at row 2 and column 5 has not been visited by any knight. If the given location ($r$, $c$) is out of the board or has been visited, the function should return -1, otherwise it returns the number of valid moves a knight at ($r$, $c$) can make. The prototype of validMoveNum function is as follow:

1
int validMoveNum(int r, int c, int n, int visited[100][100]);

The following is an example of how validMoveNum works. Assume that the green cell is ($r$, $c$), and the grey cells are visited cells, validMoveNum should return 2 because there are two valid moves starting from ($r$, $c$). By definition the return value of validMoveNum is the $p$-value of a move that moves the knight into ($r$, $c$).

valid moves

You can check your function with this function main_validMoveNum.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include "validMoveNum.h"
#define MAXN 100
int r[MAXN*MAXN];
int c[MAXN*MAXN];
int visited[MAXN][MAXN]={0};
int move[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
void print_p(int p[]){
    for(int j=0; j<8; j++){
        printf("%d",p[j]);
        if(j==7)
            printf("\n");
        else
            printf(" ");
    }
    return;
}
int main(){
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<m; i++){
        scanf("%d%d", &r[i], &c[i]);
        visited[r[i]][c[i]] = 1;
    }
    int p[8];
    for(int i=0; i<m; i++){ //each knight
        for(int j=0; j<8; j++)
            p[j] = validMoveNum(r[i]+move[j][0], c[i]+move[j][1], n, visited);   
        print_p(p);   
    }
    return 0;
}

After computing the $p$ values of all eight possible moves, a knight chooses the valid move with the minimum $p$-value. We write a function nextMove to do this. This function nextMove has four parameters, the knight’s row $r$, the knight’s column $c$, board size $n$, and an array visited, which is the same as in validMoveNum.
It is obvious that nextMove should call validMoveNum to simplify its work. nextMove should return -1 if there is no valid move it can find. Otherwise, it returns the index of the move (from 0 to 7) it should go, as shown in the first picture.

The prototype of function nextMove is as below:

1
int nextMove(int r, int c, int n, int visited[100][100]);

You can check your function with this function main_nextMove.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include "nextMove.h"
#define MAXN 100
int visited[MAXN][MAXN]={0};
int move[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
int main(){
    int n, m, r, c;
    scanf("%d",&n);
    scanf("%d%d",&r,&c);
    scanf("%d",&m);
    for(int i=0; i<m; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        visited[a][b] = 1;
    }
    printf("%d", nextMove(r, c, n, visited));
}

Finally, we need to complete a main function which uses function validMoveNum and nextMove to simulate several knights’ movement. First of all, the main function reads the board size $n$, number of knights $m$, and locations of all $m$ knights as inputs. After that, the main function checks where each knight should go in increasing index order. For every knight, we first call validMoveNum to get the number of possible moves. If there are no valid moves then this knight will not move. If this knight has valid moves we then call nextMove to find a move for him. If all knights cannot move, the simulation stops.

Compile

1
2
3
gcc -O2 main_validMoveNum.c validMoveNum.c
gcc -O2 main_nextMove.c nextMove.c validMoveNum.c
gcc -O2 main.c validMoveNum.c nextMove.c

Input Format

For main_validMoveNum.c and main.c, the input format is the same and has only one test case. The first line is board size $n$ and number of knights $m$. The following $m$ lines are the positions of the $m$ knights in the index order from $1$ to $m$. The format of the position is $r$ and $c$, where $r$ is the row index and $c$ is the column index.

  • $1\leq n\leq 100$
  • $1\leq m\leq n^{2}$
  • $0\leq r, c\leq n-1$

For main_nextMove.c, the input has only one test case as well. The first line is the board size $n$. The following line is the row and column of a single knight. The third line is number of visited cells $m$, and the following $m$ lines are positions $r$ and $c$ of $m$ different visited cells.

  • $1\leq n\leq 100$
  • $0\leq m\leq n^{2}$

Output Format

For main_validMoveNum.c: The output is $m$ lines of eight valid move numbers $p$, which are the returned values of function validMoveNum of all $m$ knights, when assuming no knight moves in this case. Note that value -1 is only returned when the location we are checking is out of board.

  • $-1\leq p\leq 7$

For main_nextMove.c: The output is the index of direction $i$ where the only knight should go. Note that value -1 is only returned when the knight has no valid move.

  • $-1\leq i\leq 7$

For main.c: The output is the final state of the $n$ by $n$ board. The value of each cell records the index of the knight that visited it and the step count, in the format of $\left( 10000 \times \textit{index} + \textit{stepCount}\right) $. Note that the step count of the initial state is zero. If there are cells never visited their values should be zero. Note that there is no space at the end of each line.

Subtasks

  • 20 points: Only the correctness of validMoveNum will be considered in these subtasks.
  • 30 points: Both the correctness of nextMove and validMoveNum will be considered in these subtasks.
  • 50 points: main will be checked, which means all three functions validMoveNum, nextMove, and main should be correct in order to get all the points.

Note that if you only complete a single function, for example validMoveNum, and want to submit if for a partial credits, your main.c and `nextMove.c`` should be empty function so they will compile, as shown below:

1
int main(){}
1
int nextMove(){}

Sample Input 1 (for validMoveNum)

3 2
0 0
2 2

Sample Output 1

-1 -1 1 1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 1 1

Sample Input 2 (for nextMove)

3
2 2
3
0 1
0 2
2 0

Sample Output 2

6

Sample Input 3 (for main)

3 2
0 0
2 2

Sample Output 3

10000 10003 20002
20001 0 10001
10002 20003 20000

Discussion