**به نام خداوند بخشنده مهربان**
# چکیده
در این پژوهش قصد داریم تا تصویری از یک جدول سودوکو را دریافت کرده و جدول حل شده را بر روی تصویر ورودی نمایش دهیم. برای این منظور، ابتدا پردازش هایی بر روی تصویر ورودی انجام می دهیم و اعداد و مکان آنها را در جدول سودوکو مشخص می نماییم. با توجه به اطلاعات بدست آمده از پردازش تصویر جدول مورد نظر، آن را حل نموده و در انتها خانه های خالی جدول را با اعداد مناسب پر می نماییم.
تمرکز اصلی این پژوهش، بر روی پردازش تصویر ورودی به منظور تشخیص اعداد و مکان آنها در جدول می باشد.
# مقدمه
در گذشته داده های ورودی رایانه ها به صورت متنی و عددی بود. با گذشت زمان و پیشرفت رایانه ها، استفاده از آن ها در زمینه های مختلف گسترش یافت. همزمان با گسترش این کاربردها، نیاز به داده های ورودی غیر متنی و عددی به ویژه داده های صوتی و تصویری حس گردید. بدین ترتیب فعالیت های مختلفی در بخش های گوناگون جهت پردازش چنین داده هایی توسط رایانه ها، آغاز گردید.
امروزه کاربرد های فراوان پردازش تصویر را در زمینه های مختلف شاهد هستیم. از جمله کاربرد های پردازش تصویر می توان به سرعت سنجی خودرو ها، تشخیص پلاک خودرو ها، تشخیص چهره و ... اشاره نمود.
در این پژوهش قصد داریم نمونه ای از کاربرد های پردازش تصویر را در حل جدول سودوکو به کار گیریم.
[سودوکو](https://en.wikipedia.org/wiki/Sudoku) به جدول اعدادی گفته می‌شود که امروزه یکی از سرگرمی های رایج در کشورهای مختلف جهان به شمار می‌آید.
این معمای عددی- منطقی نخستین بار توسط Howard Garns در قرن 18 اختراع گردید و پس از مدتی در ژاپن از آن رونمایی شد.
سودوکو مخفف یک عبارت ژاپنی (数字は独身に限る ) می باشد که به صورت **S**UUJI WA **DO**KUSHIN NI **K**AGIR**U** خوانده می شود. سودوکو در لغت به معنای "ارقام باید تنها باشند" می باشد.
امروزه جدول سودوکو در انواع مختلفی وجود دارد اما متداول ترین نوع آن یک جدول 81 خانه ای$ 9 *9$ می باشد که شامل 9 خانه ی$3*3$ می باشد. برخی از خانه های این جدول در ابتدا حاوی اعدادی از 1 تا 9 بوده و بقیه خانه های جدول خالی می باشند. برای پر کردن خانه دیگر جدول بایستی به نحوی عمل نماییم که سه قانون زیر رعایت گردند:
1- در هر سطر جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
2- در هر ستون جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
3- در هر ناحیه$ 3*3 $جدول، اعداد 1 الی 9 بدون تکرار قرار گیرند.
وجود روابط فوق بین خانه های جدول سودوکو، سبب به کارگیری روابط منطقی در حل این جدول شده و آن را به یک سرگرمی و معمای لذت بخش تبدیل نموده است.
جداول سودوکو یکی از بخش های جدایی ناپذیر روزنامه های امروزی می باشند. اکثر مخاطبان این جداول پس از حل جدول بایستی تا روز بعد منتظر بمانند تا درستی جدول حل شده خود را بررسی نمایند.
در این پژوهش قصد داریم تا با استفاده از مبانی نظری که ارائه می گردد، برنامه ای برای تلفن های همراه توسعه دهیم تا بتواند تصویر جدول سودوکو را گرفته و جدول حل شده را به صورت خروجی ارائه دهد.
با توجه به این که تصویر ورودی به توسط دوربین گرفته می شود در نتیجه این تصویر در مقایسه با تصویر اسکن شده، دارای ضعف هایی می باشد.
چالش های اصلی که در این مسیر با آنها رو به رو هستیم عبارتند از:[3]
1 - کیفیت دوربین ها متفاوت است و برای یک صحنه مشخص، عکس هایی با کیفیت های متفاوت بدست می آید.
2- شرایط نوری محیط تغییر می کند.
3- زاویه عکس گرفته شده از تصویری به تصویر دیگر تغییر می کند.
4- صفحه روزنامه ها اغلب مسطح نمی باشد و در نتیجه تصویری غیر مسطح گرفته می شود.
5- فونت های متفاوت در روزنامه های مختلف به کار می رود.
# طرح کلی
طرح کلی پژوهش بدین صورت می باشد که، ابتدا تصویر جدول سودوکو را به صورت ورودی دریافت کرده و سپس پردازش های لازم را جهت تعیین اعداد و مکان آنها در جدول انجام می دهیم و پس از آن لیستی از اعداد شناسایی شده، به صورت ورودی به بخش حل جدول داده شده و جدول حل می گردد. در انتها نیز جدول حل شده، بر روی تصویر اولیه نمایش داده خواهد شد.
در شکل زیر مسیری که در طول این پژوهش طی خواهد شد، نشان داده شده است.
# کارهای مرتبط
در این بخش قصد داریم تا راه حل های ارائه شده در مقالات مختلف، برای هر یک از مراحل طرح کلی را مطرح و بررسی نماییم.
**1. تبدیل به عکس سیاه و سفید:**
تمامی برنامه های بصری رایانه ای جهت پردازش تصویر، ابتدا تصویر ورودی را تک رنگ می کنند. البته ممکن است در آینده روش هایی برای پردازش تصاویر به صورت رنگی نیز پیدا شود اما تمامی پردازش های تصویری کنونی مبتنی بر تک رنگ می باشند.[89]
در این مرحله ابتدا تصویر ورودی را برش می دهیم و اندازه آن را کوچکتر می کنیم. دلیل این برش نیز آن است که ممکن است تصویر ورودی یه همراه ناحیه های دیگری باشد که مرتبط با جدول سودوکو نمی باشد و تنها زمان پردازش را طولانی تر می کنند.[1]
پس از برش تصویر ورودی، فیلتر پایین گذر گاشن را بر روی آن اعمال می کنیم. با اعمال این فیلتر اجزایی از تصویر که دارای فرکانس بالا می باشند، هموار تر می شوند و همین امر سبب می گردد تا در مراحل بعد به ویژه تشخیص اعداد خطای کمتری داشته باشیم.[2]
حال تصویر فیلتر شده را به یک تصویر دودویی تبدیل می کنیم. روش های مختلفی برای این تبدیل وجود دارد. از جمله این روش ها، روش استفاده از آستانه سراسری و آستانه انطباقی می باشد.[89]
در روش آستانه سراسری یک حد آستانه به صورت سراسری برای کل تصویر استفاده می شود. با توجه به این که گستره شدت رنگی از 0 تا 255 می باشد، این آستانه 128=2/256 در نظر گرفته می شود. چنانچه شدت رنگی یک پیکسل در تصویر، بیشتر از این آستانه باشد، تبدیل به رنگ سفید می شود و در غیر این صورت تبدیل به رنگ سیاه می شود.
استفاده از حد آستانه سراسری برای کل تصویر اغلب نتایج مناسبی را نمی دهد. به عنوان مثال چنانچه سایه ای بر روی تصویر وجود داشته باشد، استفاده از آستانه سراسری سبب حذف جزئیات گشته و تشخیص اعداد را ناممکن می سازد.[1] [910]
برای رفع مشکل آستانه سراسری از روش آستانه انطباقی استفاده می کنیم. در روش آستانه انطباقی برای هر پیکسل یک آستانه به صورت محلی بدست می آید و با توجه به این آستانه تبدیل صورت می گیرد. ناحیه ای از تصویر که از روی آن این آستانه محاسبه می شود، 30% اندازه یک بلوک 1*1 از جدول در نظر گرفته می شود.[2]
**2. حذف نویز های تصویر:**
در این مرحله نویز های تصویر دودویی حاصل از مرحله قبل را از بین می بریم تا بتوانیم نتایج بهتری را در مراحل بعد بدست آوریم.
**3. تعیین خطوط مرزی جدول:**
برای تعیین خطوط مرزی جدول این فرض را در نظر می گیریم که بزرگترین جزء متصل در تصویر ورودی همان ناحیه مرزی جدول می باشد. در نظر داشتن این فرض در اکثر موارد نتایج درستی به دنبال داشته است البته در مواردی نیز موجب شکست شده است.[2]
روشی که برای تعیین خطوط مرزی استفاده می شود بدین صورت می باشد که ناحیه در برگرفته شده توسط هر یک از اجزا متصل را بدست می آوریم و با توجه فرض گفته شده، بزرگترین مقدار برای ناحیه ها همان ناحیه ای است که توسط خطوط مرزی در بر گرفته شده است. در نتیجه خطوط تشکیل دهنده این ناحیه همان خطوط مرزی می باشند.[1]
استفاده از روش فوق سبب می شود تا زاویه دار بودن تصویر باعث خطا در تشخیص خطوط مرزی نگردد.
**4. تعیین زاویه تصویر:**
با توجه به این که تصویر ورودی توسط انسان ها گرفته می شود در اغلب موارد شاهد هستیم که تصویر ورودی دارای چرخش می باشد. این زاویه دار بودن سبب می شود که در مرحله ی تشخیص خطوط داخلی جدول دچار اشتباهاتی شویم. از این رو پیش از ورود به مرحله ی تشخیص خطوط داخلی این زاویه را محاسبه می کنیم.
همان طور که می دانیم، جدول سودوکو از تعدادی خط عمودی و افقی تشکیل شده است. با استفاده از این حقیقت ابتدا گویا ترین خط از جدول را پیدا می کنیم و سپس زاویه چرخش تصویر را از روی این خط به صورت زیر محاسبه می کنیم:[89]
$$ y=(x * cos(theta) + rho) / sin(theta) $$
**5. تعیین خطوط داخلی جدول:**
سوالی که در اینجا مطرح می گردد این است که چه نیازی به تعیین خطوط داخلی داریم؟ در پاسخ به این سوال بایستی به این نکته توجه داشته باشیم که خطوط داخلی اغلب در مرحله حذف نویز های تصویر از بین می روند، این در حالی است که ما برای تعیین مکان اعداد جدول به آن ها نیاز داریم. به همین دلیل بایستی در این مرحله این خطوط را به صورت مجازی دوباره ایجاد نماییم.[1]
روشی که در اینجا برای تعیین خطوط از آن استفاده می کنیم بدین صورت می باشد که ابتدا با استفاده از الگوریتم کنی لبه ها را مشخص می کنیم و پس از آن تکه خطوط را به وسیله تبدیل احتمال تکاملی حاق بر روی لبه های تشخیص داده شده، مشخص می کنیم. دلیل استفاده از تبدیل احتمالی به جای نوع استاندارد، آن است که تبدیل احتمالی توانایی تشخیص تکه ها را علاوه بر خطوط کامل دارا می باشد.
پس از آن که تکه ها مشخص گردید، با استفاده از تحلیل جزء متصل، تکه ها را خوشه بندی می نماییم و تنها بزرگترین خوشه ها را نگه می داریم. در انتها نیز تکه هایی که بر روی یک خط قرار می گیرند را به یکدیگر متصل می کنیم.[3]
مشکلی که در اینجا ممکن است با آن مواجه شویم آن است که تعداد خطوط تشخیص داده شده ممکن است بیش از تعداد واقعی باشد.
در این صورت از دو فیلتر زیر برای تشخیص خطوط واقعی استفاده می کنیم:
1- با توجه به این که خطوط واقعی جدول با یکدیگر موازی هستند، خطوطی که دارای زاویه ی متفاوت هستند را حذف می کنیم.
2- خطوطی که در فاصله دور تری نسبت به همسایه خود هستند را حذف می کنیم.
روش دیگری نیز برای تعیین خطوط داخلی وجود دارد. در این روش ابتدا طول خط مرزی را بدست می آوریم سپس با توجه به این که در هر سطر و ستون جدول 9 خانه وجود دارد، طول این خط را تقسیم بر 9 می کنیم و در فواصل مساوی با عدد بدست آمده خطوط مجازی رسم می نماییم.[1]
استفاده از این روش در تصاویری که دارای تغییر در چشم انداز و زاویه هستند، دارای خطا می باشد.
**6. تعیین خانه ها:**
در این مرحله از خطوطی که در مرحله قبل بدست آمدند استفاده می نماییم. برای تعیین خانه های جدول از اشتراک میان ناحیه میان خطوط استفاده می کنیم و اشتراکاتی که بسیار به هم نزدیک می باشند را به یکدیگر متصل می کنیم. در صورتی که این کار درست انجام شده باشد بایستی در این مرحله 100 ناحیه اشتراکی تشخیص داده شده باشد در غیر این صورت از الگوریتم تشخیص کانتور برای تشخیص بزرگترین کانتور تصویر استفاده می کنیم.[3]
چنانچه از روش دوم برای تعیین خطوط استفاده شود، در همان مرحله خانه های جدول بدست می آید.[1]
در انتها اعدادی به هر خانه نسبت داده می شود تا بتوانیم در مراحل بعد برای تعیین مکان اعداد جدول از آنها استفاده کنیم.
**7. تعیین خانه های عددی:**
در این مرحله بایستی خانه های عددی را مشخص نماییم تا بتوانیم در مرحله بعدی اعداد موجود در این خانه ها را تشخیص دهیم.
برای تعیین خانه های عددی از این حقیقت استفاده می کنیم که در خانه هایی که عدد وجود دارد شدت رنگی پیکسلی کمتر می باشد زیرا پس از آنکه تصویر به صورت دودویی در آمد اعداد با رنگ سیاه در تصویر دودویی مشخص می شوند و با توجه به این نکته، چنانچه میانگین شدت رنگی پیکسل های یک خانه بدست آید، می توان درباره وجود یا عدم وجود عدد در آن خانه تصمیم گیری نمود
**8. تعیین مقدار عدد:**
روش های مختلفی برای تشخیص اعداد از روی تصاویر موجود می باشد. از جمله این روش ها می توان روش های SVM[112] ،K-NearestNeighbour[101] ، Template Matching و[Deep Belief Network [3 را نام برد.
تمامی الگوریتم های تشخیص دارای مراحل زیر می باشند:[89]
1- تعیین ویژگی ها
2- آموزش (مرحله یادگیری)
3- دسته بندی (اجرا تشخیص)
در مرحله تعیین ویژگی ها، ویژگی های متمایز کننده مشخص می شوند. به عنوان مثال برای عدد 1 ویژگی بلند بودن و لاغری در نظر گرفته می شود و برای عدد 8 این ویژگی که از دو دایره روی هم تشکیل شده است در نظر گرفته می شود. این مرحله یکی از دشوار ترین مراحل می باشد.[89]
در مرحله آموزش از یک مجموعه داده برای یادگیری سیستم استفاده می شود. با توجه به این که داده های مورد نظر ما عدد می باشند و تعداد آن ها برای یادگیری سیستم زیاد می باشد، برای کاهش حجم و افزایش سرعت یادگیری اندازه این مجموعه داده را کوچک می کنیم.
پس از تغییر اندازه، این مجموعه داده نرمال سازی شده و در یک آرایه استاتیک به صورت زیر ذخیره می شوند:
هنگامی که یک تصویر حاوی عدد وارد این سیستم می شود ابتدا اندازه آن تغییر داده می شود و هم اندازه تصاویر آموزش داده شده به سیستم می گردد. سپس میان این تصویر و تصاویر آموزش داده شده به سیستم مقایسه صورت می گیرد. هدف در این مقایسه پیدا کردن کمترین اختلاف در شدت پیکسلی می باشد. در انتها کمترین اختلاف به عنوان نتیجه انتخاب می شود.
روش دیگری که از آن برای تعیین ویژگی اعداد استفاده می شود، بهره گیری از ویژگی های طولی و عرضی اعداد می باشد. روش کار به این صورت می باشد که ابتدا با استفاده از یک ضریب مقیاس تصویر ورودی را هم اندازه تصاویری که برای آموزش سیستم به کار برده شده است، می کنیم. سپس با در نظر گرفتن ارتفاع یکسان برای تمام اعداد، با استفاده از ویژگی های عرضی میان آنها تمایز قائل می شویم.[1] [89]
در مرحله دسته بندی نیز از روش k-nearest neighbor با K=1 استفاده می کنیم یعنی نزدیک ترین خانه را در تشخیص به کار می بریم.
**9. تشکیل جدول و حل آن:**
پس از آن که اعداد و مکان آنها مشخص گردید، آرایه ای از اعداد به صورت ورودی برای بخش حل جدول ارسال می شوند. در این آرایه برای خانه های خالی جدول عدد صفر را در نظر می گیریم.
در اینجا این نکته را یادآوری می نماییم که مکان اعداد از روی اعداد نسبت داده شده به خانه های جدول در مرحله تشخیص خانه ها بدست می آید.
حال به الگوریتم های موجود برای حل جدول سودوکو می پردازیم.
روش های مختلفی برای حل جدول ارائه شده اند که از آن جمله می توان به Brute force ، Backtracking ، Rule-based ، Boltzmann Machine Genetic Algorithm ، Dancing List اشاره نمود.
**Brute force :** در این روش همان طور که از نامش پیداست تمامی حالت ها را بررسی می کنیم. این روش با توجه به این که تمامی حالت ها را بررسی می کند، سرعت پایینی داشته و روش کارآمدی نمی باشد.
**Backtracking:** این روش پایه ای ترین روش حل سودوکو می باشد. این روشی نیز نوعی Brute force می باشد که اعداد مختلف را آزمایش می کند با این تفاوت که هنگامی که شکست می خورد، عقبگرد کرده و عدد دیگری را آزمایش می کند.[5]
**Rule-based:** این روش شامل تعدادی قاعده می باشد که بر اساس این قواعد اثبات می نماید که آیا عددی مشخص می تواند در خانه ای از جدول باشد یا خیر. این روش همان روشی است که انسان ها برای حل جدول سودوکو از آن استفاده می کنند. این روش یک روش اکتشافی می باشد و به همین دلیل نمی توان تمامی مسائل را با آن حل نمود. برای رفع این مشکل می توان از ترکیب اکتشاف و Brute force استفاده نمود. [5]
همان طور که در مقدمه گفته شد، تمرکز اصلی این پژوهش بر روی پردازش تصویر می باشد. از این رو برای کسب اطلاعات درباره روش Boltzmann Machine به مرجع [5] و Genetic Algorithm به مرجع [6] و Dancing List به مرجع [7] می توانید رجوع نمایید.
**10. نمایش جدول حل شده:**
پیش از نمایش حل جدول، ابتدا مرکز خانه ها را بدست می آوریم. درباره چگونگی بدست آوردن مرکز خانه ها در [4] به تفصیل سخن گفته شده است. به طور خلاصه از دو عنصر ساختاری یکی برای جهت عمودی و دیگری برای جهت افقی استفاده می شود تا بتوانیم با تعیین دقیق محدوده خانه، مرکز آن را بدست آوریم.
در تصویر زیر یک نمای کلی از این روش را مشاهده می کنید:
پس از تعیین مرکز خانه ها، اعداد حاصل از حل جدول را در خانه های خود قرار داده و نتیجه را بر روی تصویر اولیه نمایش می دهیم.
# آزمایش‌ها
در این بخش قصد داریم تا مطالب نظری (تئوری) که در بالا گفته شد را پیاده سازی نموده و نتایج را در عمل مشاهده نماییم.
کد های استفاده شده از [اینجا](https://drive.google.com/file/d/0B_HZkHA9_0htYXNCZU9LaHJRMnc/view?usp=sharing) قابل دریافت می باشد.
همان طور که در بخش قبل گفته شده، این پژوهش از دو بخشِ پردازش تصویر ورودی و حل جدول سودوکو مربوطه تشکیل شده است. این دو بخش از یکدیگر مستقل می باشند لذا نتایج آزمایش های انجام شده در هر یک از بخش ها به صورت جداگانه گزارش می شوند.
**سیستم استفاده شده برای آزمایش ها:**
برای پیاده سازی این الگوریتم ها از زبان برنامه نویسی پایتون 2.7.9 استفاده شده است.
گزارش های بدست آمده حاصلِ اجرای آزمایش های مربوطه بر روی یک رایانه شخصی با مشخصات زیر می باشد:
حافظه اصلی : 4 GB
پردازنده :CPU @ 1.80 GHz Intel ® Core ™ i5-3337U
سیستم عامل : Windows 8.1 Enterprise X64
**1.آزمایش های پردازش تصویری جدول سودوکو:**
برای انجام آزمایش های مربوط به پردازش تصویر، از کتابخانه های OpenCV 3.0.0 و Numpy 1.9.2 استفاده شده است که برای اجرای کد های مربوط به پردازش تصویر می بایستی این کتابخانه ها را بر روی سیستم نصب نمایید.
درباره مراحلی که می بایست برای پردازش تصویر صورت بگیرد، در بخش قبل به تفصیل سخن به میان رفت. تمام مطالب گفته شده، توسط توابعی در کتابخانه OpenCV پیاده سازی شده اند که تنها می بایستی برای انجام عملیات های مورد نظر خود، از آن ها استفاده نماییم.
برای انجام آزمایش های مربوطه از یک مجموعه داده ای 388 تایی برای آموزش سیستم استفاده شده است که به طور متوسط 38 نمونه از هر عدد در آن وجود دارد.
مجموعه داده ای به گونه ای انتخاب شده است که اغلب فونت های رایج که در چاپ جدول های سودوکو موجود در مجلات استفاده می شود را پوشش دهد.
تعداد زیادی از نمونه های این مجموعه داده ای از [13] دریافت شده اند و تعداد محدودی نیز توسط نویسنده تهیه شده است.
برای انجام آزمایش های مربوط به تشخیص جدول نیز از یک مجموعه داده ای 207 تایی که در [3] از آن استفاده شده است، بهره بردیم. این مجموعه داده از [16] قابل دریافت می باشد.
برای انجام پردازش تصویر از قطعه برنامه های زیر استفاده شده است:
knnTrainer.py: از این برنامه برای آموزش دادن اعداد به سیستم استفاده می شود.
knnTester.py: از این برنامه برای تعیین عدد از روی تصویر استفاده می شود.
imageProcessing: از این برنامه برای انجام پردازش های تصویری مربوط به جدول سودوکو استفاده می شود.
نحوه انجام پردازش تصویر به صورت زیر می باشد:
ابتدا توسط برنامه knnTrainer.py و با استفاده از مجموعه داده گردآوری شده، سیستم را آموزش می دهیم. سپس با استفاده از برنامه imageProcessing.py تصویر جدول سودوکو در یافت می شود. پس از اجرای مراحل گفته شده در بخش قبل، تصویر تک تک خانه های جدول برای تعیین محتوی داخل آن خانه به knnTester.py ارسال می شود. خروجی بدست آمده از knnTester.py عدد موجود در آن خانه را مشخص می کند.(در صورتی که خانه مورد نظر خالی باشد عدد صفر برگردانده خواهد شد.) پس از تعیین محتوی خانه های جدول می توانیم جدول را تشکیل داده و برای حل، از برنامه های نوشته شده برای حل جدول که در ادامه گفته شده است، استفاده نماییم.
در زیر خروجی های بدست آمده از مراحل پردازش تصویر نشان داده شده است:
روشی که در بالا گفته شد، بر روی تصاویر جدول های سودوکو اجرا گردید. با توجه به این که اکثر تصاویر مجموعه داده توسط دوربین تلفن های همراه قدیمی بدست آمده بود، نتایج در اکثر موارد اشتباه بود. اما اجرای برنامه بر روی تصاویری با کیفیت نسبتاً بالا در تمامی مواردی توسط بنده آزمایش گردید موفقیت آمیز بود و تصاویر به درستی پردازش می شدند.
با توجه به این که تصاویر بدست آمده با دوربین های امروزی به ویژه تلفن های همراه کیفیت مناسبی دارند لذا عملکرد این برنامه قابل قبول خواهد بود.
در آزمایش های بالا اثر زاویه دار بودن تصویر ورودی بر روی نتیجه خروجی بررسی نگردید و می بایست این قابلیت به برنامه افزوده شود.
**2.آزمایش های حل جدول سودوکو:**
در این بخش الگوریتم های Brute force ، Backtrack ، Rule-based را جهت حل جدول سودوکو به کار می بریم و در انتها نتایج بدست آمده از هر الگوریتم را نشان خواهیم داد.
پیاده سازی های انجام شده را می توانید در اینجا مشاهده نمایید.
**پیاده سازی محیط آزمایش:**
جهت راحتی و انعطاف پذیری در اجرای آزمایش های مربوطه، یک چارچوب آزمایشی (Test Framework.py) ایجاد نمودیم تا بتوانیم نتایج حاصل از آزمایش های مربوط به هر الگوریتم را مستقل از پیاده سازی آن الگوریتم گزارش نماییم.
**متد های مقایسه:**[5]
*حل جدول:*
مهم ترین جنبه لحاظ شده در مقایسه الگوریتم ها، توانایی حل جدول سودوکو می باشد. آنچه که معیار ارزیابی در این جنبه از مقایسه می باشد، زمانی است که طول می کشد تا جدول حل شده بدست آید. درجه سختی جدول ورودی در این مقایسه لحاظ نشده است. لذا ممکن است یک الگوریتم به طور متوسط بر روی همه جدول ها با درجه های سختی متفاوت عملکرد خوبی را داشته باشد در حالی که الگوریتم دیگری در بعضی از جدول ها عملکرد بسیار خوب و در برخی دیگر عملکرد ضعیفی را از خود نشان دهد. به همین دلیل در نتایج نهایی مقدار متوسط در نظر گرفته می شود.
*درجه سختی:*
در اغلب جدول هایی که در روزنامه ها مشاهده می کنیم، درجه سختی برای جدول سودوکو مشخص شده است. این درجه سختی بر اساس عملکرد انسان ها در حل جدول تعیین می شود.
جدول های مورد استفاده برای آزمایش به صورت تصادفی تولید شده اند، به همین دلیل درجه سختی جدول ها در نظر گرفته نشده است. اما می بایست خاطر نشان نمود که درجه سختی یک جدول وابسته به الگوریتم مورد استفاده می باشد. به عبارت دیگر ممکن است جدولی برای یک الگوریتم سخت و همان جدول برای الگوریتمی دیگر آسان در نظر گرفته شود. البته ممکن است درجه سختی جدولی توسط همه الگوریتم ها، سخت در نظر گرفته شود که در آن صورت آن جدول را ذاتاً سخت می نامیم.
*تولید و موازی سازی:*
راه حل اصلی برای تولید جدول سودوکو آن است که چند عدد را به صورت تصادفی تولید نموده و در خانه های جدول قرار دهیم و سپس سعی نماییم جدول تولید شده را حل نماییم.
برای تهیه جدول به صورت تصادفی بایستی دقت نماییم که اولاً حداقل 17 عدد از اعداد جدول می بایست مشخص شوند.( نشان داده شده است که حداقل 17 عدد از اعداد جدول سودوکو برای آن که جدول دارای جواب منحصر به فرد باشد، نیاز است.)[5] ثانیاً جدولی تولیدی می بایست قوانین جدول سودوکو را نقض ننماید.
از آن جا که تمرکز این پژوهش بر روی تولید تصادفی جدول های سودوکو نمی باشد لذا از یک مجموعه داده ای شامل 255 جدول سودوکو برای انجام آزمایش ها استفاده شده است.
این مجموعه داده ای250 تایی از تارنمایی آقای Norving به نشانی [15] دریافت شده است.
مجموعه داده ای دیگری نیز از تار نمای آقای Gordon Royle به نشانی [14] جهت انجام آزمایش های بیشتر قابل دریافت می باشد.
برای انجام آزمایش های مربوط به دو الگوریتم Bruteforce و Backtrack از یک مجموعه جدول آسان 250 تایی استفاده شده است. دلیل استفاده از مجموعه داده ای متفاوت برای آزمایش این دو الگوریتم عملکرد ضعیفی است که این دو الگوریتم در حل جدول های سخت از خود نشان دادند.
این مجموعه داده ای 250 تایی از تارنمایی آقای Norving به نشانی [15] دریافت شده است.
جنبه دیگر استفاده از موازی سازی می باشد. شاید در ابتدا این سوال به ذهن برسد که چه نیازی به استفاده از موازی سازی برای حل جدولی که حداکثر چند ثانیه طول می کشد، باشد؟ برای حل جدول های سودوکو متعارف که دارای اندازه 9*9 می باشند، نیازی به استفاده از موازی سازی نمی باشد اما چناچه جدول مورد نظر N*N در نظر گرفته شود آنگاه با افزایش N، پیچیدگی جدول بدست آمده نیز افزایش می یابد.[5]
با توجه به این که جدوال مورد استفاده در این آزمایش ها 9*9 می باشند، نیازی به استفاده از موازی سازی نمی باشد.
**نتایج آماری آزمایش ها:**
توزیع کارایی پردازنده در زمان های مختلف نامشخص می باشد لذا برای کاهش تاثیر این موضوع بر روی نتایج، هر جدول چندین بار توسط یک الگوریتم حل می شود و سپس میانگین زمان های بدست آمده لحاظ خواهد شد. با استفاده از این روش نتایج بدست آمده با احتمال 95% در بازه اطمینان زمانی 0.05 می باشند.
موضوع دیگری که ممکن است مشکل ساز شود عملکرد متفاوت الگوریتم ها در زمان های مختلف می باشد. این موضوع در الگوریتم های مورد بررسی در این گزارش تاثیر گذار نمی باشد چرا که تمامی این الگوریتم ها بر خلاف الگوریتم حل جدول Boltzmann machine، دارای رویکردی قاطعانه می باشند.
الگوریتم Boltzmann machine دارای رویکردی تصادفی در حل جدول های سودوکو می باشد. این الگوریتم کارایی مناسبی برای حل جدول سودوکو ندارد لذا در این پژوهش مورد بررسی قرار نگرفته است.[5]
مقایسه الگوریتم ها با یکدیگر نیازمند روش های توزیع آماری می باشد که در این جا مطرح نشده است. لذا تنها نتایج حاصل از هر الگوریتم به صورت مجزا نشان داده شده است.[5]
**نتیجه آزمایش الگوریتم Bruteforce :**
این الگوریتم برای حل جدول سودوکو بسیار ضعیف عمل نمود به طوری که حتی برای جدول ها بسیار آسان نیز که تعداد خانه های خالی آن کم است، مدت زمان بسیار زیادی را صرف می نمود تا نتیجه را بدست آورد. با توجه به عملکرد بسیار ضعیف این الگوریتم در حل جدول، تنها چند نمونه جدول بسیار آسان توسط این الگوریتم مورد بررسی قرار گرفت.
**نتیجه آزمایش الگوریتم Backtrack :**
این الگوریتم در مقایسه با الگوریتم Bruteforce عملکرد بسیار بهتری را از خود نشان داد. دلیل برتری این الگوریتم آن است که زمانی که می فهمد که مسیری را که در پیش گرفته بن بست است و به نتیجه نمی رسد، عقب گرد می کند و مسیر دیگری را در درخت فضای حالت جدول سودوکو در پیش می گیرد.
البته بهتر بودن عملکرد این الگوریتم در مقابل Bruteforce پیش از انجام آزمایش نیز روشن بود اما با اجرای آزمایش، این تمایز و برتری در عمل کاملا احساس شد.
الگوریتم Bruteforce حتی برای حل جدول های بسیار ساده زمان زیادی را صرف می کرد تا جدول حل شده را بدست آورد اما همان جدول ساده توسط الگوریتم Backtrack به سرعت قابل حل بود.
البته در انجام آزمایش های مربوط به الگوریتم Backtrack ، تنها به این حد اکتفا نشد بلکه جدول هایی با درجه سختی بالاتر نیز برای حل به این الگوریتم داده شد که به طور میانگین این الگوریتم برای حل جدول زمانی مابین 1 ثانیه الی 3 دقیقه را صرف نمود.
عملکرد این الگوریتم برای حل جدول هایی با درجه سختیِ سخت مناسب نبود و حتی پس از گذشت چندین دقیقه راه حلی بدست نمی آمد.
با توجه به این که حل تعداد زیادی جدول سودوکو با استفاده از این الگوریتم بسیار زمان بر می باشد، لذا تنها 20 نمونه آزمایش گردید که نتیجه آن درنمودار زیر نشان داده شده است.
برای آنکه دید بهتری نسبت به عملکرد این الگوریتم بدست آوریم، نتایج آزمایش هایی را که در [9] بدست آمده است را در زیر مشاهده می نمایید.
با توجه به جدول بالا می توانیم دریابیم که اگر از زبان سی که زبان سطح پایین تری در مقایسه با پایتون می باشد استفاده نماییم، نتایج بدست آمده بسیار بهتر خواهد بود.
**نتیجه آزمایش الگوریتم Rule-based:**
مسئله حل جدول سودوکو یک مسئله ارضای محدودیت می باشد که در آن محدویت ها همان قوانین جدول در پر کردن خانه های خالی می باشد.
الگوریتم Backtrack که در بالا بررسی شد، تنها زمانی مسیر خود را تغییر می داد که متوجه می شد که ادامه مسیر جاری به راه حلی نخواهد رسید. آن چه که باعث می شد این الگوریتم زمان زیادی را صرف پیدا کردن جواب کند آن است که می بایست تعداد زیادی از خانه های خالی جدول را پر می کرد تا دریابد که مسیری که در پیش گرفته است به بن بست می رسد.
برای آنکه بتوانیم سریع تر مسیر بن بست را تشخیص دهیم، می توانیم پس از آنکه خانه ای از جدول را مقدار دهی نمودیم، محدودیت جدید را در سراسر جدول متنشر کنیم تا با توجه به محدودیت های جدیدی که برای سایر خانه ها به وجود می آید، مسیر بن بست زود تر تشخیص داده شود.
این موضوع در الگوریتم Rule-based مورد توجه قرار گرفته است. لذا این الگوریتم در عمل عملکرد بسیار بهتری نسبت به الگوریتم Backtrack از خود نشان داد. جدول هایی که با الگوریتم Backtrack حتی پس از چند دقیقه قابل حل نبودند، در طی چند ثانیه با الگوریتم Rule-based حل شدند.
کد استفاده شده برای آزمایش های این بخش از [15] دریافت شده است. نتایج زیر بر اساس آزمایش های صورت گرفته با این الگوریتم بدست آمده اند.
# کارهای آینده
# مراجع
[1] P. Simha, K. Suraj, and T. Ahobala, “Recognition of numbers and position using image processing techniques for solving sudoku puzzles,” in Advances in Engineering, Science and Management (ICAESM), 2012. IEEE, 2012
[2]Divya Sagar, Ujwal Adhav, Pruthvijadhav and Anupam Bhatt Under the guidance of Prof. Shiburaj Pappu "A synopsis report on smart sudokusolver using image processing" Department of Computer Engineering Rizvi 2013-2014
[3] Baptiste Wicht, Jean Hennebert "Camera-based Sudoku recognition with Deep Belief Network" Soft Computing and Pattern Recognition (SoCPaR), 2014 6th International Conference
[4] Yixin Wang "Sudoku Solver " , Stanford University
[5] Patrik Berggren, David Nilsson "A study of Sudoku solving algorithms" Bachelor’s Thesis at NADA,Supervisor: Alexander Baltatzis
[6] Timo Mantere and Janne Koljonen "Solving, Rating and Generating Sudoku Puzzles with GA" Evolutionary Computation, CEC 2007. IEEE Congress on 2007
[7] Mattias Harrysson, Hjalmar Laestander "Solving Sudoku efficiently with Dancing Links", Degree Project in Computer Science , Supervisor: Vahid Mosavat
[8] Rohit Iyer, Amrish Jhaveri, Krutika Parab "A Review of Sudoku Solving using Patterns" , Vidyalankar Institute of Technology Mumbai, India
**+پیوند های مفید:**
[89] [http://www.codeproject.com/Articles/238114/Realtime-Webcam-Sudoku-Solver](http://www.codeproject.com/Articles/238114/Realtime-Webcam-Sudoku-Solver)
[910] [http://docs.opencv.org/master/d7/d4d/tutorial_py_thresholding.html#gsc.tab=0](http://docs.opencv.org/master/d7/d4d/tutorial_py_thresholding.html#gsc.tab=0)
[101] [http://www.boute.ir/iust-ai-92/sudoku-solver](http://www.boute.ir/iust-ai-92/sudoku-solver)
[112] [http://www.boute.ir/iust-pr-93/handwritten-digit-classification](http://www.boute.ir/iust-pr-93/handwritten-digit-classification)
[13] http://research.cs.queensu.ca/home/xiao/pr.html
[14] http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php
[15] http://norvig.com/sudoku.html
[16] https://github.com/wichtounet/sudoku_dataset