AI can be used to explore fundamental properties of spatial complexity that are characteristic of some particular map size and entropy class irrespective of the population they represent, i.e. to prove that the values of spatial complexity increases in 4 × 4 binary maps as their spatial entropy increases, attains a maximum and then decreases. Yet, it is uncertain how might AI cope with intractable spatial problems which may emerge from land use optimisation or from spatial (board) games. In fact, it is shown that spatial complexity may affect computability in cases of even small domains. Nevertheless, new mathematical methods may enable us to tackle computationally hard problems that might hamper the growth of Spatial AI in the future.