(همچنین با "پازل جواهر"، "پازل رئیس جمهورها"، "بازی پانزده"، "مربع اسرارآمیز" و بسیاری اسامی دیگر نیز شناخته می شود) یک ( ) است که از قابی با مربع های شماره گذاری شده که با ترتیبی تصادفی چیده شده اند در حالی که جای یکی از این مربع ها، خالی است. این پازل، در ابعاد مختلف وجود دارد، یکی از معروف ترین این پازل ها، پازل کوچکتر با نام می باشد. اگر ابعاد قاب 8x8 باشد، به پازل داده شده، یا گفته می شود و اگر 8x8 باشد، به آن یا گفته می شود و به همین ترتیب برای ابعاد دیگر نیز نام گذاری انجام می شود. هدف این پازل این است که مربع ها را با استفاده از جا به جایی کشویی(منظور انتقال هر مربع که کنار فضای خالی قرار دارد به فضای خالی می باشد)، مرتب کرد (ترتیب مدنظر، از کوچکترین به بزرگترین است).
 یک مسئله کلاسیک در مدل کردن ها که شامل می باشد. الگوریتم جستجوی کاشفی که معمولاٌ برای این مسئله استفاده می شود، شامل شمردن تعداد مربع هایی که در جای درست خود قرار ندارند و پیدا کردن حاصل جمع (مجموع قدر مطلق تفاضل طول و عرض آن دو نقطه) بین موقعیت هر مربع که در جای غلط قرار دارد با موقعیت همان مربع در چینش درست (به ترتیب) می شود.
 در نظر داشته باشید که هر دو قابل قبول هستند، به عنوان مثال آن ها هیچوقت تعداد حرکات باقی مانده را مقداری بیشتر از واقعیت تخمین نمی زنند که باعث افزایش بازده مثل می شود.
 
 جانسون و استوری با استفاده از نشان دادند که نصف چینش های ابتدایی برای غیرقابل حل هستند؛ فرقی ندارد چه تعداد حرکت انجام شود. این کار از طریق تعریف کردن یک تابع از چینش کاشی ها که تحت هر حرکت قابل قبولی است انجام میشود، و بعد با استفاده از این، فضای تمام حالت های نام گذاری شده را به دو قابل دسترسی و غیر قابل دسترسی افراز می کنیم.
 ی موردنظر، زوجیت حاصل جمع جابجایی برای تمام شانزده مربع و زوجیت بین (فضای خالی که توسط هیچ کاشی ای پر نشده است) و گوشه ی پایین سمت راست است. دلیل ناوردا بودن این مقدار، این است که هر جابجایی زوجیت هردو مقدار جابجایی و فاصله منهتن را باهم تغییر می دهد. در حالت خاصی که مربع خالی در گوشه ی پایین سمت راست قرار داشته باشد، پازل حل پذیر است اگر و فقط اگر جابجایی قطعات باقی مانده زوج باشد.
 نشان دادند این موضوع برای قاب های با ابعاد 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 است و در اثر لغزاندن عددی به راست و چپ ، تعداد نابجایی ها تغییر نمیکند اما با لغزاندن آن به بالا و پایین تعداد نابجایی ها به اندازه زوج تا تغییر میکند پس زوجیت تعداد نابجایی ها همیشه یکسان است پس جداول با تعداد نابجایی فرد را نمیتوان حل کرد.
 
 این پازل توسط نویس پالمر چپمن اختراع شد، یک رئیس پستخانه اهل ، که گفته می شود حتی در سال ۱۸۷۴ به دوستان خود نشانش داد، یک پازل پیشرو که متشکل از ۱۶ قطعه ی شماره گذاری شده بود، که باید در ردیف های چهار تایی گذاشته می شدند به طوری که جمع هر کدام ۳۴ شود. تعدادی از نسخه ی بهبود یافته ی از طریق فرزند نویس، فرنک به رسیدند، و از انجا به واسطه ی انواع ارتباطات، به رسیدند و در نهایت به ؛ که در آن جا دانش آموزان شروع به تولید این پازل کردند و تا دسامبر ۱۸۷۹، آنها را هم به طور محلی و هم در می فروختند، وقتی که یکی از این پازل ها به مثایس رایس ،که یک تجارت نجاری مجلل را هدایت می کرد، نشان داده شد، او در ماه دسامبر ۱۸۷۹ شروع به تولید این پازل کرد، و یک فروشنده "yankee notions" را متقاعد کرد که ان را به اسم "پازل جواهرات" بفروش برساند. در اواخر ژانویه ۱۸۸۰، دکتر چارلز پوی، یک دندان پزشک ساکن با پیشنهاد جایزه ای نقدی برای حل توجه ها را جلب کرد تا جایی که در فوریه ی ۱۸۸۰ این بازی باعث مقدار زیادی شور و اشتیاق شد؛ همچنین در در ماه مارس و در اپریل در اروپا، ولی این اشتیاق تا ماه ژوئیه از بین رفت، ظاهرا این پازل تا سال ۱۸۸۹ در معرفی نشده بود. در ۲۱ فوریه ۱۸۸۰ نویس چپمن برای "block solitaire puzzle" اقدام به کرد. هر چند با ثبت این اختراع مخالفت شد؛ احتمالا به خاطر اینکه به اندازه کافی از که متعلق به ارنست کینزی بود تفاوت نداشت.
 
 
 
سم لوید بین سال های ۱۸۹۱ تا ۱۹۱۱ ادعا می کرد که مخترع پازل است! به طور مثال در کتاب دایرةالمعارف پازل ها (منتشر شده در سال ۱۹۱۴) نوشته شده :" ساکنان قدیمی سرزمین پازل ها به خاطر دارند که چگونه در اوایل دهه هفتاد من تمام دنیا را بابت یک جعبه کوچک با ابعاد قابل حرکت دیوانه کردم که بعدها با نام شناخته شد.". این در حالی است که لوید هیچ ارتباطی با اختراع این پازل یا محبوبیت اولیه ی آن نداشت و صد البته، شور و شوق و همه گیر شدن این پازل به دهه هشتاد بر می گردد نه دهه هفتاد! اولین مقاله لوید درباره ی پازل در سال ۱۸۸۶ منتشر شد و او تا سال ۱۸۹۱، ادعایی نسبت به اختراع این پازل نداشت. 
مدتی بعد، وقتی لوید برای کسی که بتواند پازل را با ترتیب منحصربفرد داده شده توسط لوید را حل کند، جایزه ی هزار دلاری تعیین کرد، شور و شوق نسبت به پازل افزایش یافت. چینش منحصربفردی که مدنظر لوید بود، حالتی بود که صرفا جای ۱۴ و ۱۵ عوض شده باشند که لوید آن را نامید. حدوداً یک دهه قبل از طرح این مسئله توسط لوید، غیرقابل حل بودن این پازل توسط جانسون و استوری اثبات شده بود.
{"title": "پازل ۱۵", "link": "https://fa.wikipedia.org//w/index.php?title=%D9%BE%D8%A7%D8%B2%D9%84_%DB%B1%DB%B5&oldid=32943011", "language": "fa"}