Abstract
Spatial complexity can be playful, surprising and artful: some of its pleasant facets are highlighted in this chapter, as they emerge from the examination of spatial partitions and by means of games playable on boards of squares: chess, go, tic-tac-toe, checkers (among many other spatial games) revealing how charming the spatial complexity of square arrangements can be. Indeed, square maps are scientifically interesting as well as a source of inspiration throughout the ages, from Latin squares and famous modern painters to the mysterious Arnold Cat Maps and video games. Square maps can be both symbols of minimalism in art as well as genitors of highly complex mazes and labyrinths. With innumerable algorithmic challenges pertaining to them, they are a source of entertainment and endowed with a geometric shape perfectly suited for displaying and exploring the puzzling, mystic and aesthetic aspects of spatial complexity.
Intelligence in labyrinths
(Michel De Certeau 1984, p. 90)
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abbott, E. A. (1991). Flatland: A romance of many dimensions. Princeton, N.J.: Princeton University Press.
Altieri, C. (2001). Representation, representativeness and non-representational Art. In C. Shukla (Ed.), Art and representation: Contributions to contemporary aesthetics (pp. 243–261). Westport, CT: Praeger.
Anglin, W. S. (1990). The square pyramid puzzle. The American Mathematical Monthly, 97(2), 120–124.
Arnold, V., & Avez, A. (1968). Ergodic problems in classical mechanics. New York: Benjamin.
Aron, J. (2011, June 4). The world’s hardest problem: There’s a solution that will change everything. New Scientist, 2815, 37–41.
Arquilla, J., & Ronfeldt, D. (2001). The advent of netwars (revisited). In J. Arquilla, & D. Ronfeldt (Eds.), Networks and Netwars. Santa Monica, CA: Rand.
Berelkamp, E. R., Conway, J. H., & Guy, R. K. (2004). Winning ways for your Mathematical Plays (Vol. 4). Wellsley, MA: A.K. Peters.
Chen, G., Mao, Y., & Chui, C. (2004). A symmetric image encryption scheme based on 3d Chaotic Cat Maps. Chaos, Solitons and Fractals, 21, 749–761.
Chirikov, B. V. (1979). A universal instability of many-dimensional oscillator systems. Physics Reports, 52, 263.
De Certeau, M. (1984). The practice of everyday life. Berkeley, CA: University of California Press.
Demaine, E. D., Hohenberger, S., Liben-Nowell, D. (2002, October 21). Tetris is hard, even to approximate. arXiv:cs/0210020v1.
DeMaio, J. (2007). Which chessboards have a closed knight’s tour within the cube? The Electronic Journal of Combinatorics, 14, R32.
Ewald, K. C. (2001). The neglect of aesthetics in landscape planning in Switzerland. Landscape and Urban Planning, 54(1), 255–266.
Fraenkel, A., & Lichtenstein, D. (1981). Computing a perfect strategy for n × n chess requires time exponential in n. Journal of Combinatorial Theory A, 31, 199–214.
Gibbins, N. M. (1944, May). Chess in 3 and 4 dimensions, Mathematical Gazette, 46–50.
Holzer, M., & Jakobi, S. (2012). On the complexity of rolling block and Alice mazes. Lecture Notes in Computer Science, 7288, 210–222.
Iwata, S., & Kasai, T. (1994). The Othello game on an n × n board is PSPACE-complete. Theoretical Computer Science, 123(2), 329–340.
Jelliss, G. P., & Marlow, T. W. (1987). 3d tours. Chessics, 2(29/30), 162.
Kornfeld, I. P., Fomin, S. V., & Sinai, Ya. G. (1982). Ergodic theory. New York: Springer.
Kumar, A. (2008). Magic knight’s tours for chess in three dimensions. Mathematical Gazette, 92, 111–115.
Lichtenberg, A., & Lieberman, M. (1992). Regular and chaotic dynamics. New York: Springer.
Ma, D. G. (1985). An elementary proof of the solution to the diophantine equation 6y2 = x(x + 1)(2x + 1). Sichuan Daxue Xuebao, 4, 107–116.
Papadimitriou, F. (2002). Modelling Indicators and indices of landscape complexity: An approach using GIS. Ecological Indicators, 2, 17–25.
Papadimitriou, F. (2009). Modelling spatial landscape complexity using the Levenshtein algorithm. Ecological Informatics, 4(1), 51–58.
Papadimitriou, F. (2012). The algorithmic complexity of landscapes. Landscape Research, 37(5), 599–611.
Papadimitriou, F. (2013). Mathematical modelling of land use and landscape complexity with ultrametric topology. Journal of Land Use Science, 8(2), 234–254.
Pickover, C. (2009). The Maths book. London: Sterling.
Reisch, S. (1980). Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13, 5966.
Robson, J. M. (1983). The complexity of go. In Information Processing; Proceedings of IFIP Congress (pp. 413–417).
Robson, J. M. (1984). N by N checkers is Exptime complete. SIAM Journal on Computing, 13(2), 252–267.
Stewart, I. (2008). Professor Stewart’s cabinet of mathematical curiosities. London: Profile Books.
Stewart, I. (2010). Cows in the Maze and other Mathematical explorations. Oxford: Oxford University Press.
Tegmark, M. (2014). Our Mathematical universe. New York: Vintage.
Viglietta, G. (2013). Gaming is a hard job, but someone has to do it. arXiv:1201.4995v5.
Watkins, J. J. (2004). Across the board: The Mathematics of chessboard problems. Princeton, NJ: Princeton University Press.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Papadimitriou, F. (2020). Squares, Cats and Mazes: The Art and Magic of Spatial Complexity. In: Spatial Complexity. Springer, Cham. https://doi.org/10.1007/978-3-030-59671-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-59671-2_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-59670-5
Online ISBN: 978-3-030-59671-2
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)