نونوگرام یه پازل جدولیه که مثل خیلی از پازل‌های این مدلی اصلش به ژاپن بر‌می‌گرده. حلش به این شکله که کنار هر سطر و ستون اعدادی نوشته شده که نشون میدن چه تعداد خونه از جدول و به چه ترتیبی باید پر بشه. بعد از اینکه جدول کامل پر شد تصویری به دست میاد که جواب پازلمونه.
حل کردن این پازل خیلی لذت بخشه که گاهی میتونه خیلی چالش‌برانگیز هم بشه. من یه مدت مدام در حال حل کردن نونوگرام بودم تا اینکه تصمیم گرفتم با استفاده از پایتون برنامه‌ای بسازم که خودش پازل رو برام حل کنه (البته الآن دارم معتاد کدنویسی میشم?). کد کامل برنامه رو میتونید تو این لینک گیت‌هاب ببینید. اینجا سعی می‌کنم تا حدی روش‌های حل و قسمت‌هایی از کد رو براتون توضیح بدم.
مثل سودوکو تکنیک‌های مختلفی هم برای حل پازل Nonogram استفاده میشه. ساده‌ترین تکنیک اینه که تو یه سطر یا ستون خونه‌های مربوط به یه عدد رو پیدا کنیم که به هر شکل منطقی اون سطر رو پر کنیم اون خونه ها باید سیاه بشن.
واسه مثال، تو عکس بالا میتونید ببینید که ما به هر شکلی اگه بخوایم این سطر رو پر بکنیم، باید 6 خونه‌ی وسط پر بشن. فعلا این تنها تکنیک منطقیه که تو برنامه‌م استفاده کردم و به مرور زمان بقیه‌ی روش‌ها رو هم اضافه می‌کنم. برای دیدن بقیه روش‌های منطقی به این لینک از ویکی‌پدیا برید.
تو برنامه ای که نوشتم برای حل سودوکو از این تکنیک ساده استفاده کردم تا جایی که دیگه نشه خونه‌ی جدیدی رو پر کرد. بعد از اون اومدم و به روش بازگشتی (Backtracking) جواب پازل رو به دست آوردم. برای آشنایی با روش بازگشتی میتونید این مطلب رو که در مورد الگوریتم Backtracking نوشتم بخونید.
خب حالا که با پازل و نحوه‌ی حلش آشنا شدیم و می‌رسیم به قسمت کدنویسی
کد زیر قسمتی از برنامه‌ست که با روش ساده‌ی منطقی که بالا توضیح دادم میاد و خونه‌هایی رو پیدا می‌کنه که باید پر بشه (مقادیر 1).
Github 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 برای حل کامل جدول استفاده کردم.
یه نکته‌ای رو باید اضافه کنم که با استفاده از روش بازگشتی اولین جوابی که پیدا کردم رو ارایه دادم و دنبال جواب‌های دیگه نگشتم. همین باعث شده که اگه پازلی چند جواب مختلف داشته باشه، فقط یکی از اونا رو پیدا می‌کنه.
def 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@ با روشی مشابه حل سودوکو های 4x4, 9x9, 16x16 رو تو پایتون نوشته که حتما وقت بگذارید و بخونید.
از اینکه وقت گذاشتید و این مطلب رو تا آخر خوندید سپاس‌گذارم. لطفا با لایک❤️ و کامنت? هاتون بهم انرژی بدید تا مطالب بیشتر و با کیفیت‌تری بذارم. امیدوارم که از این مطلب لذت برده باشید.
