חידת מוסך המכוניות

הקשיים של בעל מוסך מוסבים למעין בילוי שיש בו קסם מיוחד. כל מה שצריך זה להכין תוכנית או דיאגרמה פשוטה על דף נייר או קרטון ולמספר שמונה אסימונים, מ-`1` עד `8`. אז משפחה שלמה יכולה להיכנס לתחרות משעשעת כדי למצוא את הפתרון הטוב ביותר לקושי.

האיור מייצג את תוכנית מוסך המכוניות, עם מקום לשתים עשרה מכוניות. אבל השטח מצומצם בצורה לא נוחה, ולכן הבעלים נתקל לעתים קרובות במבוכה רבה. נניח, למשל, ששמונה המכוניות הממוספרות מ-`1` עד `8` נמצאות במקומות המוצגים, איך ניתן להזיז אותן בצורה המהירה ביותר כך ש-`1, 2, 3` ו-`4` יחליפו מקומות עם `5, 6, 7` ו-`8` — כלומר, כשהמספרים עדיין רצים משמאל לימין, כפי שהם כרגע, אבל השורה העליונה הוחלפה בשורה התחתונה? מהו המספר הקטן ביותר של מהלכים אפשריים?

מכונית אחת זזה בכל פעם, וכל מרחק נחשב למהלך אחד. כדי למנוע אי הבנות, מקומות העצירה מסומנים בריבועים, ויכולה להיות רק מכונית אחת בריבוע בכל פעם.