# Introduction to Reconfiguration
## 1 Introduction  
Solving puzzles, planning robot motion, and editing between strings can all be viewed as the transformation between states or configurations, where a configuration can be the arrangement of puzzle pieces, the location of a robot with respect to obstacles in space, or the ordering of symbols to form a string. When configurations are defined as feasible solutions to a problem, such as the coloring of vertices in a graph, a step in a transformation between solutions can be viewed as an adjacency relation between configurations. The area of _reconfiguration_ considers both structural and algorithmic problems on the space of solutions, under various definitions of feasibility and adjacency. Reconfiguration arises in countless problems that involve movement and change, including problems in computational geometry such as morphing graph drawings [1] and polygons [2], and problems relating to games and puzzles, such as the 15-puzzle (Figure 1a), a topic of research since 1879 [3]. Work on related problems was unified into a common framework in 2011 [4], leading to a widening interest in the area and the types of problems and approaches considered. Reconfiguration is distinct from other approaches to the solution space of problems, such as local search [5; 6; 7; 8] (given a solution to an instance, find a better solution that is close to the input solution), reoptimization [9; 10] (given an instance, an optimal solution, and changes to the instance, find an optimal solution to the changed instance), and incremental problems [11] (given a yes-instance, a witness that it is a yes-instance, and changes to the instance, determine if the changed instance is a yes-instance). The _reconfiguration framework_ is defined in terms of a source problem, an instance of the source problem, a definition of a _feasible solution_, and a definition of _adjacency_ of feasible solutions. Whereas in principle there are no restrictions on the definitions of feasible solutions and adjacency, for the sake of tractability, adjacency is typically polynomially testible. We can then view the solution space as a _reconfiguration graph_, in which vertices represent feasible solutions to the given instance of the source problem, and two vertices are joined by an edge if their corresponding feasible solutions are adjacent. In addition to being represented as a graph, the relationship among feasible solutions can be viewed as a process, where two solutions are adjacent if one can be transformed into another by a single _reconfiguration step_. We will use the graph view and the transformation view interchangeably. For example, a path between two solutions in the reconfiguration graph can be seen as a sequence of reconfiguration steps, or _reconfiguration sequence_, transforming one into the other. Although the terminology has not yet stabilized, for the sake of readability, consistent terminology is used throughout this paper and, where possible, unnecessary notation will be avoided. We will refer to the framework using the name of the source problem, such as Satisfiability Reconfiguration, with the definitions of feasible solution and/or adjacency omitted when clear from context. So far, we have not yet specified any problems to solve in the reconfiguration framework; the specification of the problem (as discussed in more detail in Section 2) adds a fifth dimension to the dimensions of source problem, instance, definition of feasible solutions, and definition of adjacency. The multitude of dimensions leads to challenges in specifying problems as well as in organizing this survey. In order to highlight key elements of the area, each section focuses on a few dimensions at a time, often with a focus on a single source problem. In order not to overwhelm the reader, terminology is introduced gradually, and many open problems are raised when the relevant dimension is being considered.