Computer Science

Description

Imagine a game played on an N by N grid in which there is a very fast runner who can make two moves in a turn where each move is southward or southwest or southeast.

For example, if the runner R starts at the top as shown

```...R..
......
......
......
......
......
```

Then he can end up in any of the places having a lower case "r":

```......
..rrr.
.rrrrr
......
......
......
```

That is, he must move one space or two spaces, but each move is one southward and at most one east or west. The tackles, and there are k of them (defender will choose) can each move one space in any direction: north, south, east, west, northwest, southwest, northeast, or southeast.

Starting here,

```......
.T....
......
......
..T...
......
```

the northern most one can end up in the top 8 places and the southern most one can end up in the lower 8 places.

```ttt...
t.t...
ttt...
.ttt..
.t.t..
.ttt..
```

The tackles win if they prevent the runner from moving. For example,

```
......
......
......
....R.
...TTT
......

```

The runner wins if it reaches the southern most rank.

Here is the game setup. You will be given a 10 by 10 grid. There is one runner and k defenders. The defender gets to pick k, but then his/her opponent gets k too when he/she is the defender. The runner begins anywhere he wants on the northern-most row. The k tackles then place themselves anywhere that is at least 3 spaces away from the runner. The runner has the first turn. After that, play alternates.