The Game of the Amazons (or Amazons for short) is a two-player abstract strategy game. It is played on a checkerboard that has the form of a $$10 \times 10$$ grid. The two payers are white and black. Each player has four amazons, which start on the checkerboard in the following configuration.

The starting position in The Game of the Amazons.

The starting position in The Game of the Amazons, where amazons are represented by letters.

A supply of markers that represent arrows is also required. In order to refer to the squares on the checkerboard, the rows are numbered from top to bottom and the columns from left to right, starting from zero. The amazons are indicated with letters, as shown in the figure on the right: white amazons are indicated with lowercase letters (a, b, c and d) and black amazons with uppercase letters (A, B, C and D).

White moves first and the players alternate moves thereafter. Each move consists of two parts. First, a player moves one of its own amazons one or more empty squares in a straight line (horizontal, vertical or diagonally). This is exactly as a queen moves in chess. In moving an amazon it may not cross or enter a square occupied by an amazon of either color or an arrow.

An amazon can move horizontally, vertically and diagonally in eight directions, just like a queen on the chessboard. The directions are represented by N, NE, E, SE, S, SW, W and NW.

Second, after moving an amazon, the amazon shoots an arrow from its landing square to another square, using another queen-like move. This arrow may travel in any horizontal, vertical or diagonal direction (even backwards along the same path the amazon just traveled, into or across the starting square if desired). An arrow, like an amazon, cannot cross or enter a square where another arrow has landed or an amazon of either color stands. The square where the arrow lands is marked to show that it can no longer be used.

A possible first move of white: amazon a is moved 2 squares in southeastern (SE) direction and shoots an arrow over 6 squares in northeastern (NE) direction.

Black is completely enclosed and cannot make another move. White wins the game.

The first player that can no longer make a move loses. Draws are impossible.

Assignment

The position of a square on the checkerboard is represented as a tuple $$(r, c)$$, where $$r \in \mathbb{N}$$ (int) indicates the row number and $$c \in \mathbb{N}$$ (int) the column number.

The eight directions in which amazons can move and shoot arrows are indicated by one or two uppercase letters (str), as shown in the figure in the introduction that illustrates how the queen moves in chess.

Define a class Amazons that can be used to simulate games of Amazons. No arguments must be passed when creating a new game (Amazons): the game always has the same starting position. Each game (Amazons) must have at least the following properties:

amazons: a dictionary (dict) that maps the position of each amazon on the checkerboard onto the letter (str) that indicates the specific amazon
arrows: a set with the positions of all arrows on the checkerboard

If a game (Amazons) is passed to the built-in function str, a string representation (str) of the checkerboard must be returned. Each row forms a separate line, with empty squares represented by an underscore (_), squares where an arrow has landed by an asterisk (*) and squares with an amazon by the corresponding letter.

In addition, each game (Amazons) must support at least the following methods:

A method position that takes the letter (str) of an amazon. The method must return the position of the amazon on the checkerboard.
A method possible_directions that takes the letter (str) of an amazon. The method must return a set with all directions (str) in which the amazon can move at least one square (or shoot an arrow, which is the same).
A method move_amazon that takes three arguments: i) the letter (str) of an amazon, ii) a direction (str) and iii) a number $$n \in \mathbb{N}_0$$ (int). The method must move the amazon $$n$$ squares in the given direction and return a reference to the object on which it was called. If this is not possible, the amazon should not move and the method must raise an AssertionError with the message invalid move.
A method shoot_arrow that takes three arguments: i) the letter (str) of an amazon, ii) a direction (str) and iii) a number $$n \in \mathbb{N}_0$$ (int). The method must let the amazon shoot an arrow over $$n$$ squares in the given direction and return a reference to the object on which it was called. If this is not possible, no arrow should be shot and the method must raise an AssertionError with the message invalid move.
A method winner that takes no arguments. The method must return a number (int) that indicates who wins the game: there's no winner yet (0), white wins (1) or black wins (2).

Example

        >>> board = Amazons()
>>> board.amazons
{(3, 0): 'A', (0, 3): 'B', (0, 6): 'C', (3, 9): 'D', (6, 0): 'a', (9, 3): 'b', (9, 6): 'c', (6, 9): 'd'}
>>> board.arrows
set()
>>> print(board)
___B__C___
__________
__________
A________D
__________
__________
a________d
__________
__________
___b__c___
>>> board.winner()
0
>>> board.position('a')
(6, 0)
>>> board.possible_directions('a')
{'E', 'S', 'N', 'NE', 'SE'}
>>> board.move_amazon('a', 'W', 3)
Traceback (most recent call last):
AssertionError: invalid move
>>> print(board.move_amazon('a', 'SE', 2))
___B__C___
__________
__________
A________D
__________
__________
_________d
__________
__a_______
___b__c___
>>> board.amazons
{(3, 0): 'A', (0, 3): 'B', (0, 6): 'C', (3, 9): 'D', (9, 3): 'b', (9, 6): 'c', (6, 9): 'd', (8, 2): 'a'}
>>> board.position('a')
(8, 2)
>>> board.possible_directions('a')
{'E', 'S', 'SW', 'NW', 'NE', 'W', 'N'}
>>> board.shoot_arrow('a', 'SE', 1)
Traceback (most recent call last):
AssertionError: invalid move
>>> print(board.shoot_arrow('a', 'NE', 6))
___B__C___
__________
________*_
A________D
__________
__________
_________d
__________
__a_______
___b__c___
>>> board.arrows
{(2, 8)}
>>> board.winner()
0
>>> board.position('C')
(0, 6)
>>> board.possible_directions('C')
{'E', 'SE', 'S', 'W', 'SW'}
>>> print(board.move_amazon('C', 'E', 3).shoot_arrow('C', 'SW', 2))
___B_____C
__________
_______**_
A________D
__________
__________
_________d
__________
__a_______
___b__c___
>>> board.amazons
{(3, 0): 'A', (0, 3): 'B', (3, 9): 'D', (9, 3): 'b', (9, 6): 'c', (6, 9): 'd', (8, 2): 'a', (0, 9): 'C'}
>>> board.arrows
{(2, 7), (2, 8)}
>>> board.position('C')
(0, 9)
>>> board.possible_directions('C')
{'W', 'SW', 'S'}
>>> board.winner()
0
>>> board = board.move_amazon('c', 'N', 3).shoot_arrow('c', 'N', 4)
>>> board = board.move_amazon('D', 'N', 2).shoot_arrow('D', 'S', 1)
>>> board = board.move_amazon('a', 'NW', 2).shoot_arrow('a', 'NE', 4)
>>> board = board.move_amazon('B', 'E', 5).shoot_arrow('B', 'W', 1)
>>> board = board.move_amazon('b', 'N', 3).shoot_arrow('b', 'N', 4)
>>> board = board.move_amazon('A', 'NE', 2).shoot_arrow('A', 'S', 1)
>>> board = board.move_amazon('a', 'N', 4).shoot_arrow('a', 'E', 1)
>>> print(board.move_amazon('A', 'E', 6).shoot_arrow('A', 'W', 1))
_______*BC
_______*AD
a****_****
__________
__________
__________
___b__c__d
__________
__________
__________
>>> board.amazons
{(6, 9): 'd', (0, 9): 'C', (6, 6): 'c', (1, 9): 'D', (0, 8): 'B', (6, 3): 'b', (2, 0): 'a', (1, 8): 'A'}
>>> board.arrows
{(2, 7), (2, 6), (2, 9), (2, 8), (0, 7), (2, 1), (2, 3), (2, 2), (2, 4), (1, 7)}
>>> board.possible_directions('A')
set()
>>> board.winner()
1