حل پازل Nonogram با Python

آشنایی با پازل Nonogram

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

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

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

واسه مثال، تو عکس بالا می‌تونید ببینید که ما به هر شکلی اگه بخوایم این سطر رو پر بکنیم، باید 6 خونه‌ی وسط پر بشن. فعلا این تنها تکنیک منطقیه که تو برنامه‌م استفاده کردم و به مرور زمان بقیه‌ی روش‌ها رو هم اضافه می‌کنم. برای دیدن بقیه روش‌های منطقی به این لینک از ویکی‌پدیا برید.

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

حل Nonogram در پایتون

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

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

1234567891011121314151617181920212223Github code

def overlap_row(tab):
    for i in range(rows):
        diff = cols - (sum(row_con[i]) + len(row_con[i]) - 1)
        n = 0
        for j in row_con[i]:
            for k in range(j):
                if k == (j - 1) and j > diff:
                    for m in range(j - diff):
                        tab[i][n - m] = 1
                n += 1
            n += 1

        row_sum = 0
        for j in tab[i]:
            if j == 1:
                row_sum += 1

        if row_sum == sum(row_con[i]):
            for j in range(cols):
                if tab[i][j] == -1:
                    tab[i][j] = 0

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

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

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

123456789101112def backtrack(tab):
    cell = empty_cell(tab)
    if not cell:
        return True
    for i in [1, 0]:
        tab[cell[0]][cell[1]] = i
        if Verify(cell, tab, i):
            if backtrack(tab):
                return True
        if i == 0:
            tab[cell[0]][cell[1]] = -1
    return False

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

• تعداد گروه های سیاه شده نباید از تعداد عددهای اون ردیف بیشتر باشه
• اگر خونه‌ای رو سیاه کردم، نباید تعداد خونه‌های پر شده از مجموع اعداد اون ردیف بیشتر بشه
• اگر خونه‌ای رو سیاه کردم، نباید طول گروه خط از عدد مربوط بهش بیشتر بشه
• اگر خونه‌ای رو سفید کردم، نباید طول گروه خط از عدد مربوط بهش کمتر بشه
• اگر به آخر اون سطر یا ستون رسیدیم، باید طول و تعداد گروه‌ها برابر باشه با عددهای مربوط به اون ردیف

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

در نهایت با استفاده از tkinter برنامه رو به صورت گرافیکی در آوردم:

دوست خوبم z9776m@ با روشی مشابه حل سودوکو های 4×4, 9×9, 16×16 رو تو پایتون نوشته که حتما وقت بگذارید و بخونید.

از اینکه وقت گذاشتید و این مطلب رو تا آخر خوندید سپاس‌گذارم. لطفا با لایک❤️ و کامنت? هاتون بهم انرژی بدید تا مطالب بیشتر و با کیفیت‌تری بذارم. امیدوارم که از این مطلب لذت برده باشید.

نویسنده مطلب: محمد سرابی

منبع مطلب