هوالحبیب
پروژه بوسیله زبان برنامه نویسی جاوا پیاده سازی شده است که در فاز بعدی به توضیح روند انجام پروژه و مقایسه نتایج آن با روشهایی که بااستفاده از پردازش تصویر به دریافت مساله و حل مساله بااستفاده از دیگر الگوریتم ها و تاثیر زبان برنامه نویسی در روند حل پرداخته خواهد شد.
https://github.com/Motallem/Sodoku
# **1. مقدمه**
پازل سودوکو که به جدول اعداد معروف است، نوع متداول آن یک جدول 9x9 است که این جدول شامل 9 جدول کوچکتر 3x3 است. در ابتدا جدول شامل اعدادی بطور پیش فرض می‌باشد که با کمک سه قانون زیر می‌توان باقی اعداد را یافت:
قانون اول: در هر ناحیه 3x3 جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.
قانون دوم: در هر سطر جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.
قانون سوم: در هر ستون جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.
در این پروژه از شما خواسته می‌شود با وارد کردن اعداد سوال مورد نظر در جدول، حل مساله را در همان جدول مشاهده نمایید.
برای حل پازل (جدول سودوکو) نیاز به حوصله و بکارگیری منطق می‌باشد.
این پازل برای اولین بار در یک مجله آمریکایی در سال 1979 منتشر شد، ولی انتشار مستمر برای نخستین بار برمی‌گردد به سال 1986 در ژاپن که امروزه در تمامی کشورها به عنوان یک بازی فکری دارای مقبولیت قابل توجهی می‌باشد.
هدف در این پروژه ارائه راهکاری است که با دریافت مساله اقدام به حل مساله در همان جدول ورودی بکند.
**
# 2. طرح کلی
این پروژه سه بخش را دربرمی‌گیرد :
بخش اول: ظاهر گرافیکی
بخش دوم: دریافت مساله
بخش سوم: حل مساله
طرح کلی برای حل اینگونه مسائل به این صورت است که ابتدا با دریافت اعداد جدول از کاربر و با انجام عملیات لازم، اعداد درون آن را شناسایی می‌کند. در مرحله بعد با استفاده از یکی از الگوریتم‌های موجود به حل پازل سودوکو پرداخته و روند حل و محاسبه اعداد برروی مساله نمایش داده می‌شود.
**
**
# 3. کارهای مرتبط
در این قسمت روش‌هاو الگوریتم‌های موجود برای انجام پروژه توضیح داده خواهد شد.
# **حل پازل سودوکو:**
مهم ترین عامل در رسیدن به جواب نهایی در بازی هایی به مانند سودوکو بی تردید به کار بردن منطق و استدلال های منطقی می باشد. با تمرکز بر روی جدول ودنبال کردن ردیف ها و ستون ها و اعمال قوانین حاکم بر بازی می توان خانه ها را یکی پس از دیگری پر و راه را برای تکمیل جدول هموارتر نمود. گاهی برای پرکردن تنها یک خانه از جدول نیاز به کنار هم قرار دادن اطلاعات فراوان و مقایسه بخش های به طور کل متمایز از یکدیگر می باشد.به طور کلی می توان سه استراتژی جدا از هم را به منظور حل یک جدول سودوکو در نظر گرفت که جزء پایه ای ترین روش ها هستند :
**1.اسکن خط به خط:**
ساده ترین و در عین حال اصلی ترین روش رسیدن به جواب، روش اسکن خط به خط می باشد. در این روش ما با توجه به اینکه در هر سطر، ستون و ناحیه دارای هیچ تکراری نمی باشیم، می توانیم جواب مورد نظر خود را پیدا کنیم. در اینجا ما با هدف قرار دادن یک عدد و جستجو در جدول به منظور پیدا نمودن مکان مناسب برای آن می توانیم تمامی اعداد 1 الی 9 را در خانه های جدول مرتب کنیم.
**2.آنالیز ترکیبی:**
روش دیگر استفاده از اصل اساسی بازی سودوکو می باشد. یعنی عدم تکرار اعداد در ردیف ها، ستون ها و نواحی جدول، که با ترکیب این عوامل و قرار دادن منطقی در کنار یکدیگر می توان به جواب رسید.
**3.نقطه‌گذاری:**
این استراتژی در واقع سیستمی کمکی به منظور تسهیل در رسیدن به پاسخ مناسب می باشد و می توان گفت روشی تکمیلی است. در اینجا با گذاشتن نقطه در خانه های خالی می توان جواب های احتمالی را برای آن خانه بخصوص مشخص نمود.
حال در این بخش به معرفی چندی از الگوریتم‌های موجود برای حل جدول سودوکو می‌پردازیم. بعد از توضیح مختصری که درمورد هرکدام از الگوریتم‌ها ارائه شد به بررسی نتایج بدست آمده از هرکدام خواهیم پرداخت.
**الف) الگوریتم Backtracking:**
این الگوریتم یکی از ساده ترین استراتژی های حل سودوکو برای کامپیوتر است و یک الگوریتم قطعی است. این الگوریتم یک متد brute-force است که در هر مرحله یکی از اعداد کاندید در خانه های جدول را انتخاب کرده و سعی در حل جدول می کند. اگر این انتخاب به حل جدول نینجامید، بازگشته و عدد کاندید دیگری را انتخاب می کند. این روش تضمین می کند که اگر زمان کافی در اختیار داشته باشد، قطعا به جواب خواهد رسید.
**ب) الگوریتم Boltzmann machine:**
این الگوریتم جدول سودوکو را با یک شبکه عصبی مصنوعی مدل می کند. جدول به عنوان یک constraint دیده می شود که نود هایی را مشخص می کند که نمی توانند به هم وصل شوند. این محدودیت ها به عنوان وزن های شبکه عصبی رمزگذاری شده و زمانی که یک راه حل پیدا شد، رمزگشایی می شوند.این الگوریتم یک الگوریتم احتمالی است.
**ج) الگوریتم Rule-based:**
این الگوریتم به نوعی یک الگوریتم _اکتشافی است. این الگوریتم چند قانون را بررسی و آزمایش می کند تا با توجه به آنها خانه ها را پر کند و یا برخی از جواب های کاندید را حذف کند . این قوانین عبارتند از :
1. **قانون اول ( Naked Single) :**این به این معنی است که یک خانه فقط یک عدد کاندید دارد. پس عدد کاندید در خانه موردنظر نوشته می شود.
2. **قانون دوم ( Hidden Single ) :**اگر در یک مربع 3x3 فقط یک خانه باشد که بتواند عدد خاصی را شامل شود، آن عدد باید در آن خانه نوشته شود.
3. **قانون سوم ( Naked Pair ):**اگر در یک مربع 3x3 دو خانه باشند که هر کدام فقط شامل 2 عدد کاندید باشند، این عدد باید از سایر خانه های آن مربع که علاوه بر این دو عدد، اعداد کاندید دیگری هم دارند، حذف شوند. این قانون میتواند به سه یا چهار خانه هم گسترش پیدا کند.
4. **قانون چهارم ( Hidden Pair ):**اگر در یک مربع 3x3 فقط دو خانه باشند که هر کدام شامل دو عدد کاندید خاص باشند که در سایر خانه های خالی آن مربع نیستند، باید سایر عددهای کاندید از این دو خانه حذف شوند. این قانون هم میتواند به سه یا چهار خانه گسترش پیدا کند.
5. **قانون پنجم( ( Guessing (Nishi) :**کامپیوتر یک خانه خالی را انتخاب می کند و آن را با یکی از عددهای کاندیدش پر می کند. سپس از اینجا شروع کرده و می بیند که آیا این انتخاب منجر به حل جدول می شود یا خیر. اگر عدد انتخابی اشتباه بود، دوباره برمی گردد به همان خانه و عدد کاندید دیگری را جایگزین آن می کند. این کار شبیه روشی است که در الگوریتم Backtracking استفاده می شود. این الگوریتم مانند Backtracking یک الگوریتم قطعی است.
**بررسی نتایج:**
*جایگاه *اول* :* الگوریتم Rule-based سریع ترین الگوریتم از بین سایر روش هاست و میانگین زمان رسیدن به جواب آن حدودا 0.02 ثانیه است. پیچیدگی زمانی این الگوریتم در قسمت چک کردن قوانین به صورت خطی است و زمانی که وارد قسمت guessing می شود پیچیدگی آن به صورت توانی می شود.
جایگاه دوم: بعد از الگوریتم‌های Rule-based ،الگوریتم Backtracking جایگاه دوم را از نظر سرعت جوابگویی را دارد و میانگین زمان رسیدن به جواب آن 1.66 ثانیه است.
*جایگاه سوم:*الگوریتم Boltzmann machine می‌باشد.
**
**
# 4. پیاده‌سازی:
این پروژه شامل 3 فایل است: Table.java, MainFrame.java , Cookie.java
در این قسمت توضیح مختصری درباره هرکدام ارائه خواهد شد:
**فایل MainFrame:**
این فایل شمای کلی برنامه را مشخص می‌کند، بوسیله کتابخانه‌های زیر در تابع MainFrame ظاهر گرافیکی برنامه در قسمت ساخته می‌شود.
از کتابخانه‌های زیر در ساختن آن استفاده شده است:
import java.awt.Color;
import java.awt.Font;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.FocusAdapter;
import java.awt.event.FocusEvent;
import javax.swing.BorderFactory;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTextField;
import javax.swing.UIManager;
import javax.swing.UnsupportedLookAndFeelException;
import javax.swing.UIManager.LookAndFeelInfo;
فایل Table.java:
شاکله اصلی برنامه را دربرمی‌گیرد که شامل Methodهایی است که مهم‌ترین آنها عبارتند است از: check , printLMAP , solveRec , solve , ... است.
بعد از تشکیل جدول با اجرا شدن برنامه به بررسی اعداد وارد شده در سطر و ستون جدول پرداخته ( مختصات خانه‌های خالی و پر را پیدا می‌کند.) و آنها را شناسایی می‌کند و پس از آن به حل مساله می‌پردازد.
**فایل Cookie.java:**
در این قسمت مشخصات نقطه و داده درون آن مشخص می‌شود و در Methodهای فایل Table.java مورد استفاده قرار می‌گیرد.
**
**
# 5. بررسی نتایج:
***نمونه اول:***
**داده‌های ورودی :**
**حل جدول:**
***نمونه دوم:***
**داده‌های ورودی:**
**حل جدول:**
***نمونه سوم:***
**داده‌های ورودی:**
**حل جدول:**
***نمونه چهارم:***
**داده‌های ورودی:**
**حل جدول:**
***نمونه پنجم:***
**داده‌های ورودی:**
**حل جدول:**
**
**
# 6. ارزیابی نتایج با نتایج روش‌های دیگر (پردازش تصویر):
در این قسمت به بررسی نمونه‌های مشترک که به دو روش مورد حل قرار گرفته است، پرداخته می‌شود و نتایج این روش با روشی که مساله به کمک پردازش تصویر از کاربر دریافت می‌شود و به زبان برنامه نویسی Python نوشته شده است، مقایسه می‌شود.
از چند نظر بررسی نتایج قابل تامل است:
1. زمان حل مساله
2. بازده حل مساله (تعداد جداولی که منتج به نتیجه شده است به کل جداولی که از کاربر دریافت کرده است.)
از نظر زمانی باتوجه به اینکه در روش اول اعمال مربوط به پردازش تصویر صورت نمی‌گیرد و روی مساله بطور دستی وارد می‌شود، طبیعی می‌باشد که از نظر فرآیند زمانی روش بالا از روش پردازش تصویر میتواند بهتر باشد. (به شرط اینکه الگوریتم مورد استفاده و همچنین زبان برنامه‌نویسی چه باشد.)
دیگر مشکل پردازش تصویر این باشد که ممکن در همان مرحله اول یعنی دریافت ورودی مساله دچار مشکل شود.(بنا به هر دلیلی از قبیل کیفیت پایین عکس ورودی نتواند ورودی را بخواند.) که همانطور که در نمونه‌های پایین نیز آورده شده است، نمونه شماره پنج توسط این روش موفق به حل مساله نشده است.
***نمونه اول:***
**حل جدول:**
***نمونه دوم:***
**حل جدول:**
***نمونه سوم:***
**حل جدول:**
***نمونه چهارم:***
**حل جدول:**
***نمونه پنجم:***
**حل جدول:**
**