الگوریتم‌های حل سودوکو

تعریف مسئله

یک بازی محبوب موبایل سودوکو

سودوکو پازلی به شکل یک جدول ۹×۹ است که تعدادی از خانه‌های آن با اعداد ۱ تا ۹ پر شده‌اند. هدف، پر کردن خانه‌های خالی جدول است به طوری که، در نهایت هریک از اعداد ۱ تا ۹ دقیقاً یک بار در هر سطر، هر ستون، و هر مربع مشخص شدهٔ ۳×۳ ظاهر شوند. سودوکوهای مناسب راه‌حلی یکتا دارند. به کمک کامپیوترها می‌توان سودوکو طراحی کرد، سودوکوها را حل کرد و خواص آن‌ها را بررسی کرد. الگوریتم‌های نسبتاً ساده‌ای برای حالت ۹×۹ سودوکو وجود دارند که در کمتر از یک ثانیه سخت‌ترین آن‌ها را هم حل می‌کنند اما با بزرگ شدن اندازهٔ جدول سختی این مسئله به‌طور قابل توجهی افزایش می‌یابد.

روش‌های حل

روش پس‌گرد

حل یک سودوکو با روش پسگرد

این روش حالت خاصی از جستجوی جامع است. برای حل سودوکو با این تکنیک، خانه‌های خالی را با حالات مختلفی پر می‌کنیم به صورتی که قوانین نقض نشود و تا جایی اینکار را ادامه می‌دهیم که جدول کامل پر شود. به‌طور مثال از اولین خانه خالی شروع می‌کنیم، اگر در سطر و ستون و مربع ۳×۳ مربوط به این خانه عدد ۱ ظاهر نشده‌بود، این خانه را با ۱ پر می‌کنیم و ادامه می‌دهیم؛ وگرنه اعداد ۲ تا ۹ را امتحان می‌کنیم. هر بار به خانه‌ای رسیدیم که با هیچ عددی پر نمی‌شد باید اولین خانهٔ قبل از آن که می‌توانیم عددش را زیاد کنیم را زیاد کنیم. برای پیاده‌سازی این روش از الگوریتم جستجوی اول عمق استفاده می‌کنیم.

شبه‌کد

backtrack(cell):
    if cell is empty:
        for i from 1 to 9:
            if i not in row and column and box cell:
                fill cell with i
                boolean result = backtrack(next cell)
                if result is True:
                    return True
                unfill cell
        return False
    if i is last cell:
        return True
    backtrack(next cell)

مزیت‌های این روش عبارتند از:

• اگر جدول درست باشد حتماً جواب پیدا می‌شود.
• زمان حل به سختی جدول ورودی وابسته نیست.
• پیاده‌سازی آن بسیار ساده است.

سودوکویی که به شکلی طراحی شده که برای روش پسگرد بد باشد.

مشکل این روش این است که ممکن است بسیار کند عمل کند. به‌طور میانگین برای جدول‌های ۹ × ۹ حدود ۱۵۰۰۰ تغییر در حالت یک خانه در این روش ایجاد می‌شود گرچه برای حالات بد ممکن است حدود ۹۰۰ هزار دور طول بکشد. همچنین وقتی الگوریتم به ترتیب اعداد ۱ تا ۹ را برای هر خانه امتحان می‌کند می‌توان سودوکویی طراحی کرد که تعداد مراحل زیادی طول بکشد. جدول سمت چپ طوری درست شده که سطر اول اعداد ۹، ۸، ۷ … ۱ به ترتیب در سطر اول قرار می‌گیرند که این باعث می‌شود حالات خیلی زیادی بررسی شوند تا به جواب درست برسیم.

کمترین تعداد راهنمایی که جواب یکتا باشد ۱۷ است. در حالتی که تعداد راهنمایی‌ها کم باشد و اعداد را به شکلی در جدول جایگشت بدهیم که بر خلاف ترتیب الگوریتم باشد زمان اجرای این برنامه در حد چندین ساعت می‌شود. یک بهینه‌سازی ساده برای الگوریتم این است که اعداد را به ترتیب پر نکنیم و وقتی از مقدار خانه‌ای مطمئن شدیم درجا مقداردهی کنیم. یا اینکه اول روی خانه‌هایی حالت بندی کنیم که تعداد حالات کمتری دارند.

پیوندهای رقصنده

سودوکو حالت خاصی از مسئله پوشاندن کامل هم هست گرچه این مسئله ان‌پی است. روش سادهٔ حل این است که همهٔ حالات را به ترتیب خاصی امتحان کنیم ولی به کمک ایدهٔ پیوندهای رقصندهٔ کنوث کون اجرا به‌طور قابل توجهی کم می‌شود. به‌طور خلاصه پوشاندن کامل به فرم یک ماتریس دودویی ترجمه می‌شود که تعداد سطر از یک ماتریس را می‌خواهیم انتخاب کنیم تا از هر ستون دقیقاً یک ۱ داشته باشیم. با ساختن لیست‌های پیوندی از مکان یک‌ها روی ماتریس و جستجو به کمک آن‌ها جواب را بسیار سریع‌تر پیدا کرد.

جستجوی تصادفی

سودوکو به کمک روش جستجوی تصادفی هم قابل حل است. یک مثال از چنین حلی به این صورت است:

1. به صورت تصادفی به خانه‌های جدول عدد بده.
2. تعداد اشتباهات را حساب کن.
3. خانه‌های نامعلوم را طوری جایگشت بده تا تعداد اشتباهات کمتر شود؛ و در نهایت به صفر برسد.

برای الگوریتمی که اعداد نامعلوم را جایگشت دهد می‌توان از الگوریتم ژنتیک، الگوریتم تبرید شبیه‌سازی‌شده یا الگوریتم جستجوی ممنوعه استفاده کرد. الگوریتم‌های تصادفی به مراتب برای حل سودوکو از روش پسگرد سریع ترند ولی از روش‌های استدلالی کندتر هستند. با این حال بهینه‌سازی‌های تصادفی برای دستهٔ بزرگتری از مسئله‌ها قابل استفاده‌اند و نیازی نیست پازل منطقی‌ای داشته باشند. همچنین می‌توان سودوکو را به مسئلهٔ برنامه سازی خطی تبدیل کرد.

سختی مسئله

مسئله سودوکو در حالت کلی یعنی وقتی جدولی به اندازهٔ $n^{2}\times n^{2}$ داریم، ان‌پی کامل است. در واقع سودوکو معادل رنگ‌آمیزی گراف است. تعداد رنگ‌ها برابر $n^{2}$ است. همچنین ثابت شده برای $n>2$ رنگ‌آمیزی گراف ان‌پی‌ست.

جستارهای وابسته

• سودوکو
• ریاضیات سودوکو
• پیوندهای رقصنده
• رنگ‌آمیزی گراف
• پوشاندن کامل