Is a regular tessellation $\{p,q\}$ always possible on some closed surface $S$?

This problem was solved in

Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S. Regular tessellations of surfaces and (p,q,2)-triangle groups. Ann. of Math. (2) 116 (1982), no. 1, 113–132.

From the MathReview of the paper:

The authors consider regular tessellations of type $(p,q)$ on a surface; a generalization of the Platonic solids. The parameter $p$ is the number of edges on each face while $q$ is the valence of each vertex. The main theorem states that as long as obvious necessary conditions, based on Euler's formula, are satisfied then a regular tessellation of type $(p,q)$ exists on a surface $M$. Furthermore, the edges can be geodesics and a classification of regular tessellations of type $(p,q)$ on $M$ is given based on $\pi_1(M)$. The main technique used to prove the theorem is construction of appropriate branched coverings over surfaces with irregular patterns.

The main result of their paper is Theorem 1:

Let $M$ be a closed surface and let $p, q, V, E, F$ be positive integers such that $$ V-E+F=\chi(M)$$ and $$ pF=2E=qV$$

Then: There exists a $(p, q)$-tessellation on $M$ consisting of $F$ $p$-sided faces, $E$ edges and $V$ vertices each of valence $q$; except when $M$ is the projective plane, $(p, q) = (3,3)$, $V = F = 2$, and $E = 3$.

Note that the above conditions are also necessary for the existence of a $(p,q)$-tessellation.

An important remark: For this theorem to hold, some of the polygonal faces $\sigma$ of the tessellation are allowed to be "singular'' in the sense that some of the edges of $\sigma$ are glued to each other on the surface $M$. A simple example of a singular face is the tessellation of the 2-torus which has unique 2-dimensional rectangular face, whose edges are identified in the standard manner. In other words, the CW complex underlying the tessellation, need not be regular.