حل سودوکو به روش بک‌ ترک

سلام.

بعد از مدت زیادی که از کدنویسی فاصله گرفته بودم تصمیم گرفتم زبان پایتون رو یاد بگیرم و اولین پروژه‌ای که بالا آوردم این شد: حل پازل سودوکو

میخوام اینجا الگوریتم استفاده شده و نحوه پیاده سازی این برنامه رو باهاتون به اشتراک بزارم.

روش‌های متفاوتی برای حل سودوکو وجود داره که من یکی از ساده‌ترین هارو انتخاب کردم. اول یه توضیح کوچولو راجب روش حل معمول میدم و بعد تبدیلش به الگوریتم کد نویسی.

سودوکو چطور حل میشه؟

یه سودوکو 4x4 رو در نظر بگیرید. سودوکو باید با اعداد 1 تا 4 طوری پر شه که توی هیچ سطر و ستون و باکسی عدد تکراری نداشته باشیم. یه نکته ای که واسه حل سودوکو هست اینه که همیشه یه نقطه شروع داشته باشیم و از اونجا پیشروی کنیم.

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

برای پر کردن خونه آبی که داخل عکس مشخص کردم یه نگاه به سطر و ستون و باکس این خونه میندازیم، اعداد 1 و 3 و 4 استفاده شدن در نتیجه عددی که قرار میگیره 2 هست.

بعد خونه‌های بعدی رو بررسی می‌کنیم و به همین ترتیب پیش میریم تا به خونه آخر برسیم.

الگوریتم من:

همین روشی که توضیح دادم رو به کد تبدیل کردم.

قبلش بگم که برای کار با سودوکو از ماتریس استفاده کردم.(لیست دو بعدی) و بعد:

1. دونه دونه خونه ها رو چک کن. اگه خونه پر بود ازش رد شو و اگه خالی بود جوابای احتمالی رو چک کن

2. "چک کردن جوابای احتمالی" به این صورته که به ازای هر ایندکس از سودوکو، یه لیست از "جوابهای احتمالی" داریم که داخلش اعداد 1 تا n نوشته شده(n سایز سودوکو). ما سطر و ستون و باکس ایندکس مورد نظر رو بررسی می‌کنیم. اگه توی هر کدوم از خونه‌هایی که بررسی می‌شه عددی وجود داشت، اون عدد رو از لیست جوابهامون حذف می‌کنیم چون نباید از اعداد تکراری استفاده کنیم.

3. بعد از اینکه سطر و ستون و باکس رو چک کردیم، اگه لیست جوابهامون فقط شامل یک عدد بود، اون عدد پاسخ خونه مورد نظر ماست. درنتیجه جواب رو داخل سودوکو می‌نویسیم.

4. در غیر اینصورت به خونه بعد میریم و اینکار رو تا آخرین خونه سودوکو انجام میدیم.

5. وقتی همه‌‌ی خونه‌های سودوکو رو چک کردیم، اگه برای حداقل یه خونه جوابی پیدا کرده بودیم، "لیست جوابای احتمالی" رو دوباره برای همه‌ی خونه‌های سودوکو چک می‌کنیم و اینکار رو انقدر ادامه می‌دیم که دیگه تغییری واسه جواب‌هامون ایجاد نشه

تیکه کد زیر مشخص می‌کنه که لازمه دوباره "لیست جوابای احتمالی" رو چک کنیم یا نه:

if flag == num_of_row_col - 1:
    sudoku[i][j] = temp       # ..... set answer of the cell
    continue_flag = True
else:
    continue_flag = False

وقتی به این مرحله می‌رسیم، اگه سودوکویی که به برنامه دادیم درجه‌ش آسون باشه همینجا سودوکو حل می‌شه و تموم!

اما اگه سودوکو سخت باشه این الگوریتم تا یه جایی جلو میره و بعد اون دیگه نمیتونه جوابی به دست بیاره چون هنوزم خونه ای وجود داره که نمیتونیم با قطعیت جوابش رو بنویسیم.

سودوکو و بک ترک:

از اینجا به بعد من از الگوریتم بک ترک استفاده کردم. شاید این سوال براتون پیش بیاد که چرا از همون اول بک ترک نزاشتم؟ چون بک ترک همونطور که از اسمش پیداست یه الگوریتم بازگشتیه و چندان بهینه نیست.

پس واسه پایین اومدن زمان اجرا و استفاده درست از حافظه قبل از اینکه از بک ترک استفاده کنم تا جایی که تونستم سودوکو رو حل کردم و بعد بک ترک رو اجرا کردم.

راستی اگه می‌خواین درمورد الگوریتم بک ترک بیشتر بدونین و یا سوالی در موردش دارین اینجا رو ببینین. محمد دوست خوبم خیلی واضح و آسون در مورد بک ترک توضیح داده.

در ضمن زحمت توضیح دادن الگوریتم بک ترک رو برای پیاده سازی سودوکو هم کشیده که من اینجا دیگه چیزی راجع بهش نمی‌نویسم.

کار دیگه‌ای که انجام دادم برای بهینگی بیشتر کد، این بود که برای قسمت بک ترک از داده‌های بخش قبل استفاده کردم. چطوری؟

الان توضیح می‌دم:

ما توی بخش قبلی یه لیست داشتیم به اسم "جوابای احتمالی". گفتیم که داخل این لیست اعدادی رو داریم که ممکنه جواب مساله باشن. و طبق الگوریتمی که بالا توضیح دادم هر کدوم از اعدادی که مطمئن هستیم نمیتونه پاسخ مورد نظر باشه از لیست حذف میشه.

اگه ما از اول بدون بهینه کردن کد از بک ترک استفاده میکردیم، بک ترک برای هر خونه ماتریس همه‌ی اعداد ممکن رو بررسی می‌کرد (مثلا برای سودوکوی ۹x۹ اعداد ۱ تا ۹ بررسی می‌شد که واقعا محاسبه‌ش زمانبره! ) .

اما وقتی "لیست جوابای احتمالی" رو به عنوان ورودی بک ترک در نظر بگیریم، بخاطر محدودتر شدن اعدادمون برنامه خیلی سریعتر اجرا می‌شه.

اینم کد بخش بک ترک:

def back_track():            # .....use backtrack algorithm
    empty = find_empty()          # .....this function returns index of the empty cell 
    if not find_empty():
        return True
    for i in may_be_ans[empty[0]][empty[1]]:
        if i == 0:
            continue
        sudoku[empty[0]][empty[1]] = i
        # ...... this Condition for to sure the number does not exist in the row, column and box
        if find_row(empty[0], empty[1]) and find_column(empty[0], empty[1]) and find_box(empty[0], empty[1]):   
            if back_track():
                return True
    sudoku[empty[0]][empty[1]] = 0
    return False

راستی من این برنامه رو بصورت ویژوال بالا آوردم که کار باهاش راحت‌تر و ظاهر زیبایی داشته باشه. برای اینکار از کتابخونه tkinter استفاده کردم که استفاده ازش خیلی راحت بود و سریع میشه یادش گرفت.

و اینکه می‌تونین از اینجا کد کامل پروژه رو ببینید. مشخصا خالی از ایراد نیست و کلی جای پیشرفت داره پس اگه خواستید تغییری ایجاد کنید که کدم بهتر شه باعث افتخاره :)

امیدوارم این مقاله مورد استفاده‌تون باشه و خوشتون بیاد. اگه در موردش سوالی و یا پیشنهادی داشتین خوشحال می‌شم برام کامنت بزارید.