<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%%%%%%%% Champs titre %%%%%%%
% Pour le titre

\subsection*{Reconfiguration par 2-adjacence dans la grille carrée}
%

% Pour la liste des auteurs
\index{Galliot, F.}\index{Gravier, S.}\index{Sivignon, I.}
%
% Citer un par un les auteurs et leur affiliation
\underline{Florian Galliot}, LaBRI, Bordeaux, {\tt florian.galliot@u-bordeaux.fr}\\ %souligner l'orateur
\indent Sylvain Gravier, Institut Fourier, Grenoble, {\tt graviers@univ-grenoble-alpes.fr}\\
\indent Isabelle Sivignon, GIPSA-lab, Grenoble, {\tt isabelle.sivignon@grenoble-inp.fr}\\


% Pour le sommaire
\addcontentsline{toc}{section}{F. Galliot, S. Gravier et I. Sivignon : Reconfiguration par 2-adjacence dans la grille carrée}
%

%%%%%% Fin Champs titre %%%%%%%%%%%%%%
% Ensuite, le résumé -- 1 PAGE MAXIMUM



Nous étudions un problème de reconfiguration dans la grille carrée. Une \textit{configuration} est un ensemble de pièces indistinguables disposées sur des cases de la grille carrée, avec au plus une pièce par case. La règle de déplacement est la \textit{2-adjacence} : une pièce ne peut être déplacée que vers une case vide dont au moins deux cases voisines (haut, bas, gauche, droite) sont déjà occupées par des pièces. Etant donné deux configurations $A$ et $B$, quand est-il possible de passer de $A$ à $B$ via une séquence de déplacements licites ?

\begin{figure}[ht]
	\begin{center}
		\includegraphics[scale=.4]{Figure_JGA_Galliot.pdf}
		\caption{Le puzzle de gauche est résoluble en 12 mouvements. Le puzzle de droite n'est pas résoluble. \label{figure_JGA_Galliot}}
	\end{center}
\end{figure}

Ce problème, dont certaines instances apparaissaient dans la littérature récréative dès les années 1950, a été formulé en toute généralité par Demaine et. al. en 2002 \cite{ref_JGA_Galliot}. Cet article introduit une notion cruciale de \textit{pièces bonus}, et affirme notamment que tous les puzzles ayant deux pièces bonus sont résolubles. Il s'avère que les auteurs ont sous-estimé certains cas : nous exhibons une famille de contre-exemples qui montre qu'aucun nombre constant de pièce bonus n'est suffisant en général. Nous montrons cependant, à l'aide d'un algorithme de résolution intuitif, que les puzzles ayant deux pièces bonus sont résolubles au-delà d'un certain nombre total de pièces, qui est serré à une constante additive près pour les puzzles de format carré. Enfin, nous inaugurons l'étude des puzzles ayant une seule pièce bonus : quand le nombre total de pièces est minimum, le problème se réduit à un jeu "type taquin".




\begin{thebibliography}{99}

\bibitem{ref_JGA_Galliot} Erik D. Demaine, Martin L. Demaine, Helena A. Verill. Coin-moving puzzles. In \textit{More Games of No Chance}. Cambridge University Press. ISBN 978-0521808323, pp. 405–431.

\end{thebibliography}</pre></body></html>