Here's a recursive process to find the number of moves from point $X$ to point $Y$ in a grid $G$ with obstacles $O$.
Search algorithms work by generation the set of squares that can be reached in $n$ moves.
Let $B_0 = \{X\}$ - the border of expansion, $I_0 = \emptyset$ - interior, $E_0 = (G / O) / B_0$ -exterior.
Let $f$ - a function such that for any $g \in G$, $f(g)$ is the set of squares that can be reached from $g$ in one move. This function is the definition of the chess piece you use.
Now, iterate:
$B_n = \bigcup \limits_{x \in B_{n-1}} f(x) \cap E_{n-1}$
$I_n = I_{n-1} \cup B_{n-1}$
$E_n = E_{n-1} / B_n$
Continue until $Y \in B_n$ or $B_n = \emptyset$. In the first case $\text{distance}(X, Y) = n$, in the second, there is no path from $X$ to $Y$.
I hope that explains the general idea. There is plenty of code examples for pathfinding problems. Note that instead of sets of squares, lists of Nodes are used, where a Node is an object containing the position of a square, a reference to the Node that generated it, for the purposes of backtracking and also a priority number if heuristics are used. Heuristic is the simple idea that if $Y$ lies to the left from $X$, the path from $X$ to $Y$ most likely goes to the left (which is not true in case of obstacles). There isn't much point to use heuristics here since $f$ is usually not trivial and the grid is small.
For the Icosahedron: Each face is a triangle and each vertex is included in $5$ triangles and $5$ edges. So let's assume we can color it using only $3$ colors. Take a vertex $v$ with its $5$ neighbors $w_1,...,w_5$ with triangles $vw_iw_{i+1}$ for $i=1,2,3,4$ and $vw_5w_1$. All vertices in those triangles need a different coloring. If we start at $v$ with color $1$, $w_1$ gets color $2$ and $w_2$ gets color $3$, we can go around the circle to get $w_3 \to 2,w_4\to 3,w_5\to2$. But the last color is in conflict with the triangle $vw_5w_1$ as both $w_5$ and $w_1$ get color $2$.
Therefore we need at least $4$ colors for coloring. $4$ colors are enough as well, you can just take an example coloring.
For the dodecahedron the easiest way to argue that is by writing down an example coloring with $3$ colors. That's in general the procedure for showing that the chromatic number is $k$: Write down a coloring with $k$ colors and show that no coloring with $<k$ colors is possible.
Best Answer
Within a $2\times 2$ square, the king can move from any directly to eevery other field, hence we need at least four colours. If we assign colour $(x\bmod 2, y\bmod 2)$ to field $(x,y)$, ew see that $4$ colours also suffice.
For the rook, all fields in one column are mutually adajacent and hence must have different colours, thus requiring at least $8$ colours. But eight colours also suffice if you assign $x+y\bmod 8$ to $(x,y)$.
Similarly, the bishop has adjacent fields along a diagonal, thus also requiring eight colours. But eight colours also suffice by assigning colour $x$ to $(x,y)$.
For the knight, the original checssboard colouring witnesses that the chromatic numbre is 42$.