پازل ۱۵

پازل ۱۵ تایی (همچنین با "پازل جواهر"، "پازل رئیس جمهورها"، "بازی پانزده"، "مربع اسرارآمیز" و بسیاری اسامی دیگر نیز شناخته می شود) یک پازل کشویی(sliding puzzle) است که از قابی با مربع های شماره گذاری شده که با ترتیبی تصادفی چیده شده اند در حالی که جای یکی از این مربع ها، خالی است. این پازل، در ابعاد مختلف وجود دارد، یکی از معروف ترین این پازل ها، پازل کوچکتر با نام پازل-۸ می باشد. اگر ابعاد قاب ۳x۳ باشد، به پازل داده شده، پازل-۸ یا پازل-۹ گفته می شود و اگر ۴x۴ باشد، به آن پازل-۱۵ یا پازل-۱۶ گفته می شود و به همین ترتیب برای ابعاد دیگر نیز نام گذاری انجام می شود. هدف این پازل این است که مربع ها را با استفاده از جا به جایی کشویی(منظور انتقال هر مربع که کنار فضای خالی قرار دارد به فضای خالی می باشد)، مرتب کرد (ترتیب مدنظر، از کوچکترین به بزرگترین است).

حل شده پازل ۱۵ تایی

پازل-n یک مسئله کلاسیک در مدل کردن الگوریتم ها که شامل الگوریتم جستجوی کاشف می باشد. الگوریتم جستجوی کاشفی که معمولاٌ برای این مسئله استفاده می شود، شامل شمردن تعداد مربع هایی که در جای درست خود قرار ندارند و پیدا کردن حاصل جمع فاصله منهتن (مجموع قدر مطلق تفاضل طول و عرض آن دو نقطه) بین موقعیت هر مربع که در جای غلط قرار دارد با موقعیت همان مربع در چینش درست (به ترتیب) می شود.

در نظر داشته باشید که هر دو قابل قبول هستند، به عنوان مثال آن ها هیچوقت تعداد حرکات باقی مانده را مقداری بیشتر از واقعیت تخمین نمی زنند که باعث افزایش بازده الگوریتم های جستجو مثل A* می شود.

حل پذیری

جانسون و استوری با استفاده از زوجیت نشان دادند که نصف چینش های ابتدایی برای پازل-n غیرقابل حل هستند؛ فرقی ندارد چه تعداد حرکت انجام شود. این کار از طریق تعریف کردن یک تابع از چینش کاشی ها که تحت هر حرکت قابل قبولی ناوردا است انجام میشود، و بعد با استفاده از این، فضای تمام حالت های نام گذاری شده را به دو کلاس هم ارز قابل دسترسی و غیر قابل دسترسی افراز می کنیم.

ناوردای موردنظر، زوجیت حاصل جمع جابجایی برای تمام شانزده مربع و زوجیت فاصله منهتن بین مربع خالی (فضای خالی که توسط هیچ کاشی ای پر نشده است) و گوشه ی پایین سمت راست است. دلیل ناوردا بودن این مقدار، این است که هر جابجایی زوجیت هردو مقدار جابجایی و فاصله منهتن را باهم تغییر می دهد. در حالت خاصی که مربع خالی در گوشه ی پایین سمت راست قرار داشته باشد، پازل حل پذیر است اگر و فقط اگر جابجایی قطعات باقی مانده زوج باشد.

جانسون و استوری نشان دادند این موضوع برای قاب های با ابعاد n x m هم برقرار است : "تمام جایگشت های زوج قابل حل هستند" (به شرطی که n و m هر دو از 2 بیشتر باشند). این موضوع به نظر سرراست و مستقیم می رسد ولی اینطور نیست و اثباتش با استقرا روی m و n ، کمی دشوار است. آرچر در سال ۱۹۹۹ با استفاده از مسیر های همیلتونی کلاس های هم ارزی را مشخص کرد و اثبات دیگری ارائه داد.

ویلسون در سال ۱۹۷۴، شباهت پازل-۱۵ را با محدوده ی خاصی از گراف های دو همبند مطالعه کرد. او نشان داد که به جز در چندضلعی ها و گرافی بخصوص با ۷ راس، می توان تمام جایگشت ها را بدست آورد مگر اینکه گراف دوبخشی باشد، که در این حالت فقط جایگشت های زوج را می توان بدست آورد. گراف بخصوص گفته شده، یک شش ضلعی با یک قطر و یک راس دیگر رد وسطش است : 1/6 جایگشت هایش بدست می آید.

برای ورژن های بزرگتر پازل-n، پیدا کردن جواب کار راحتی است ولی پیدا کردن کوتاه ترین جواب، یک مساله ی ان‌پی سخت است. همچنین الگوریتم تقریبی پیدا کردن کمترین تعداد جابجایی ها با افزودن یک مقدار ثابت، ان‌پی سخت است ولی تقریب مورد نظر، از مرتبه ی چندجمله ای است. برای پازل-۱۵، تعداد اپتیمال حرکات مورد نیاز، بین 0 تا 80 تاست (17 حالت با 80 حرکت وجود دارد) ؛ یا به عبارت دیگر 43 حرکت چند مربعی! پازل-۸ هم می توان گفت این پازل با حداکثر 31 حرکت تکی یا 24 حرکت چند مربعی قابل حل است!

تعداد موقعیت های ممکن برای پازل-۲۴، 25!/2 ≈ 7.76×10²⁴ است که مقدار زیادی است و محاسبه اش با الگوریتم خدا طولانی است. در سال 2011، کران پایین 152 حرکت تکی یا 42 حرکت چندتایی بدست آمد، همچنین کران بالا 208 حرکت تکی یا 109 حرکت چندتایی منتشر شد. در سال 2016، کران بالا از 208 به 205 حرکت تکی بهبود پیدا کرد.

اثبات دیگر

نگاه دیگر به این مساله این گونه است که : می توانیم مقدار ناوردا را، جمع زوجیت تعداد وارونگی ها در نظر بگیریم. در مورد این مرتبه (پازل-۱۵)، ۱۵ تکه ی شماره گذاری شده داریم و زوجیت تفاضل شماره سطر قسمت خالی با آخرین سطر را داریم. این یک ناوردا است چون هر جابجایی ستونی، یعنی وقتی یک قطعه را داخل همان ستون جابجا می کنیم، زوجیت هر دوی وارونگی ها و فاصله سطری تا سطر آخر را تغییر می دهد؛ و هر جابجایی سطری، یعنی وقتی یک قطعه را داخل همان سطر جابجا می کنیم، زوجیت هیچ کدام از این متغیر ها را تغییر نمی دهد. حال اگر به پازل حل شده توجه کنیم، متوجه می شویم که مجموع مورد نظر، مقداری زوج است. پس با استفاده از استقرای ریاضی ، اثبات اینکه اگر در هر مرحله از حل کردن پازل، مجموع موردنظر مقداری فرد باشد، آن پازل غیر قابل حل است، کاری ساده است. به خصوص اگر قسمت خالی در گوشه پایین سمت چپ باشد (یا به‌طور کلی تر، هر جایی در سطر آخر!) ، پازل قابل حل است اگر و فقط اگر تعداد وارونگی قطعات شماره گذاری شده مقداری زوج باشد.

حالت غیرممکن

نیمی از حالت‌های این پازل قابل حل نیست.

در حالت کلی تر برای جداول n*n میتوان قابل حل یا غیرقابل حل بودنشان را اثبات کرد.

نابجایی: به ازای هر i به طوریکه i>j ولی i زودتر از j در جدول آمده باشد.

برای n های فرد میتوان از روش ناوردایی و زوجیت استفاده کرد ؛ اگر تعداد نابجایی ها در جدول به هم ریخته فرد باشد جدول غیرقابل حل است زیرا زوجیت نابجایی ها در جدول مرتب شده زوج و برابر 0 است و در اثر لغزاندن عددی به راست و چپ ، تعداد نابجایی ها تغییر نمیکند اما با لغزاندن آن به بالا و پایین تعداد نابجایی ها به اندازه زوج تا تغییر میکند پس زوجیت تعداد نابجایی ها همیشه یکسان است پس جداول با تعداد نابجایی فرد را نمیتوان حل کرد.

تاریخچه

پازل غیر قابل حلی که توسط سم لوید ارائه شد. در این پازل فقط جای قطعه شماره 14 و 15 عوض شده است.این پازل غیر قابل حل است چون برای حل آن، نیاز به عوض شدن مقداری ناوردا است که با تعریف ناوردا بودن در تناقض است.

این پازل توسط نویس پالمر چپمن اختراع شد، یک رئیس پستخانه اهل کانستوتا، نیویورک، که گفته می شود حتی در سال ۱۸۷۴ به دوستان خود نشانش داد، یک پازل پیشرو که متشکل از ۱۶ قطعه ی شماره گذاری شده بود، که باید در ردیف های چهار تایی گذاشته می شدند به طوری که جمع هر کدام ۳۴ شود. تعدادی از نسخه ی بهبود یافته ی پازل-۱۵ از طریق فرزند نویس، فرنک به سایراکیوز، نیویورک رسیدند، و از انجا به واسطه ی انواع ارتباطات، به واچ هیل، رود آیلند رسیدند و در نهایت به هارتفورد، کنتیکت؛ که در آن جا دانش آموزان مدرسه ی ناشنوایان امریکا شروع به تولید این پازل کردند و تا دسامبر ۱۸۷۹، آنها را هم به طور محلی و هم در بوستون ،ماساچوست می فروختند، وقتی که یکی از این پازل ها به مثایس رایس ،که یک تجارت نجاری مجلل را هدایت می کرد، نشان داده شد، او در ماه دسامبر ۱۸۷۹ شروع به تولید این پازل کرد، و یک فروشنده "yankee notions" را متقاعد کرد که ان را به اسم "پازل جواهرات" بفروش برساند. در اواخر ژانویه ۱۸۸۰، دکتر چارلز پوی، یک دندان پزشک ساکن ووچستر ،ماساچوست با پیشنهاد جایزه ای نقدی برای حل پازل-۱۵ توجه ها را جلب کرد تا جایی که در فوریه ی ۱۸۸۰ این بازی باعث مقدار زیادی شور و اشتیاق شد؛ همچنین در کانادا در ماه مارس و در اپریل در اروپا، ولی این اشتیاق تا ماه ژوئیه از بین رفت، ظاهرا این پازل تا سال ۱۸۸۹ در ژاپن معرفی نشده بود. در ۲۱ فوریه ۱۸۸۰ نویس چپمن برای "block solitaire puzzle" اقدام به ثبت اختراع کرد. هر چند با ثبت این اختراع مخالفت شد؛ احتمالا به خاطر اینکه به اندازه کافی از "پازل بلوکی" که متعلق به ارنست کینزی بود تفاوت نداشت.

سم لوید

سم لوید بین سال های ۱۸۹۱ تا ۱۹۱۱ ادعا می کرد که مخترع پازل است! به طور مثال در کتاب دایرةالمعارف پازل ها (منتشر شده در سال ۱۹۱۴) نوشته شده :" ساکنان قدیمی سرزمین پازل ها به خاطر دارند که چگونه در اوایل دهه هفتاد من تمام دنیا را بابت یک جعبه کوچک با ابعاد قابل حرکت دیوانه کردم که بعدها با نام پازل-۱۴-۱۵ شناخته شد.". این در حالی است که لوید هیچ ارتباطی با اختراع این پازل یا محبوبیت اولیه ی آن نداشت و صد البته، شور و شوق و همه گیر شدن این پازل به دهه هشتاد بر می گردد نه دهه هفتاد! اولین مقاله لوید درباره ی پازل در سال ۱۸۸۶ منتشر شد و او تا سال ۱۸۹۱، ادعایی نسبت به اختراع این پازل نداشت.

نقیضه‌ای به نام «پازل باعظمت رئیس‌جمهور» که سناتور روسکو کانکلینگ از حزب جمهوری‌خواه را در حین بازی پازل ۱۵ نشان می‌دهد. همهٔ خانه‌های پازل با سر یک نامزد احتمالی عضو حزب جمهوری‌خواه برای احراز مقام رئیس‌جمهور ایالات متحده آمریکا پر شده‌است که در میان آن‌ها افرادی چون ژنرال گرانت، ژنرال شرمن، ساموئل تیلدن به چشم می‌خورند. سناتور کانکلینگ از یک سو می‌خواهد سر خود را قرار دهد و از سوی دیگر آماده‌است تا سر جیمز جی. بلین را به مکان خالی جعبه ببرد.

مدتی بعد، وقتی لوید برای کسی که بتواند پازل را با ترتیب منحصربفرد داده شده توسط لوید را حل کند، جایزه ی هزار دلاری تعیین کرد، شور و شوق نسبت به پازل افزایش یافت. چینش منحصربفردی که مدنظر لوید بود، حالتی بود که صرفا جای ۱۴ و ۱۵ عوض شده باشند که لوید آن را پازل-۱۴-۱۵ نامید. حدوداً یک دهه قبل از طرح این مسئله توسط لوید، غیرقابل حل بودن این پازل توسط جانسون و استوری اثبات شده بود.

منابع

• کتاب هوش مصنوعی: رهیافتی نوین – نوشته استوارت راسل و پیتر نورویگ – ویرایش سوم - ۲۰۰۹

• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, 3rd Edition, Prentice Hall, 2009