پازل ۱۵

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

پازل ۱۵ تایی (15 puzzle) یک مسئله کلاسیک در هوش مصنوعی است. این پازل یک مربع ۴ در ۴ است که یک خانه آن خالی و بقیه خانه‌ها اعداد ۱ تا ۱۵ را دارند. هدف مرتب کردن پازل با لغزاندن اعداد می‌باشد.

حالت غیرممکن[ویرایش]

حالت غیرقابل حل

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

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

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

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

منابع[ویرایش]

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