Lesson 1

In this chapter, we study the well-known 15 puzzle, in which one aims to arrange 15 square tiles in order within a square frame. Remarkably, solvability is governed by mathematics: a configuration can be solved if and only if the associated permutation is even.

To understand this criterion, we introduce the basic theory of even and odd permutations — a fundamental concept in algebra and discrete mathematics. We then develop simple methods for working with permutations and use them as building blocks for a program that solves any valid configuration almost instantly.