نوع متداول سودوکو یک جدول 9x9 است که کل جدول هم به 9 جدول کوچکتر 3x3 تقسیم شده است. در این جدول چند عدد به طور پیش فرض قرار داده شده که باید باقی اعداد را با رعایت سه قانون زیر یافت: + قانون اول: در هر سطر جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. + قانون دوم: در هر ستون جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. + قانون سوم: در هر ناحیه 3x3 جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. در این پژوهش از شما خواسته شده است تا با دریافت عکس جدول ورودی، حل آن را در همان عکس نمایش دهید.   # مقدمه سودوکو که همچنین به جور چین اعداد نیز معروف می باشد, یک پازل بر پایه منطق است. نوع متداول سودوکو یک جدول 9x9 است که کل جدول هم به 9 جدول کوچکتر 3x3 تقسیم شده است. در این جدول چند عدد به طور پیش فرض قرار داده شده که باید باقی اعداد را با رعایت سه قانون زیر یافت: + قانون اول: در هر سطر جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. + قانون دوم: در هر ستون جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. + قانون سوم: در هر ناحیه 3x3 جدول اعداد 1 تا 9 بدون تکرار قرار گیرد. برای تکمیل پازل نیاز به حوصله و به کار بردن منطق می باشد. هر چند این پازل برای اولین بار در یک مجله پازل امریکایی در سال 1979 انتشار یافت، ولی انتشار آن به طور مستمر و پی گیر برای نخستین مرتبه بر می گردد به ژاپن در 1986 و در سال 2005 این سرگرمی به محبوبیت جهانی دست یافت. <br/> امروزه این بازی در تمامی کشورها به عنوان یک جدول فکری مقبولیت قابل توجهی یافته است و روز به روز به این محبوبیت افزوده می گردد. اکنون کمتر روزنامه و مجله پازلی را می توان یافت که هر روزه جداول سودوکو را در بخش سرگرمی خود نداشته باشد. این نوع جدول برخلاف اکثر دیگر جداول باعث تقویت فکر و ذهن منطقی در انسان می گردد به همین دلیل از این بازی در بسیاری از مسابقات به منظور سنجش قابلیت تعقل استفاده و در بسیاری از این فستیوال ها سودوکو به عنوان مقام نخست جهانی در بین بازی های سرگرمی دست می یابد. <br/> هدف ما در این پروژه ارایه روشی است که با دریافت عکس جدول ورودی، حل آن را در همان عکس نمایش دهد. # کارهای مرتبط طرح کلی برای حل این گونه مسایل به این صورت است که ابتدا با دریافت عکس ورودی و با اعمال پردازش های لازم، جدول و اعداد درون آن تفکیک می شود. در مرحله بعد با استفاده از یکی از روش های موجود به شناسایی اعداد می پردازیم که در این پروژه برای این کار از [شبکه عصبی] استفاده شده است. نهایتا به کمک یکی از الگوریتم های حل جدول سودوکو ، جدول را حل کرده و جواب ها روی عکس اولیه نوشته می شود. ## پردازش عکس به طور کلی یک سیستم تشخیص الگو شامل سه مرحله زیر است : + ### مرحله اول ( Preprocessing ) : در این قسمت عکس ورودی پردازش میشود، برای مثال نرمال سازی سایز، تبدیل عکس به باینری و ... + ### مرحله دوم ( Feature extraction ) : در این مرحله عکس پردازش شده تبدیل به برداری با مشخصات خاص میشود تا آماده طبقه بندی شود. + ### مرحله سوم ( Classification ) : در این مرحله با استفاده از بردار به دست آمده از قسمت قبل، سیستم تمرین [^1] داده می شود و یا یک بردار ورودی با استفاده از یک classify method، [خوشه بندی] میشود. برای آماده سازی عکس و تفکیک اعداد اولین کاری که باید انجام داد قطعه قطعه کردن [^2] عکس جدول با استفاده از Thresholding است. <br/> بعد از آن، نوبت به مشخص کردن مرزهای جدول با بهره گیری از تکنیک Hough Transfrom می شود. <br/> در نهایت و البته پس از remap کردن عکس، تصویر نهایی را به یک جدول 9x9 تقسیم می کنیم که هر کدام از خانه ها، یک خانه جدول اصلی است. با پردازش هر خانه می توان وجود یا عدم وجود عدد در آن خانه را تشخیص داد. اگر خانه ای شامل عدد بود، ذخیره شده و برای شناسایی عدد، توسط الگوریتمی به [شبکه عصبی] داده می شود. آنگاه [شبکه عصبی] آن را با تصاویری که هنگام آموزش شبکه ایجاد شده اند مقایسه کرده و پس از الگوریتم های درونیابی ، تقریب و تصمیم، مشخص می کند که به کدام عدد نزدیک تر است. ## حل جدول سودوکو بعد از طی مراحل بالا، نوبت به حل کردن جدول می رسد. مهمترین عامل در رسیدن به جواب نهایی در بازی هایی به مانند سودوکو بی تردید به کار بردن منطق و استدلا لهای منطقی می باشد. با تمرکز بر روی جدول ودنبال کردن ردیف ها و ستون ها و اعمال قوانین حاکم بر بازی می توان خانه ها را یکی پس از دیگری پر و راه را برای تکمیل جدول هموارتر نمود. <br/> گاهی برای پرکردن تنها یک خانه از جدول نیاز به کنار هم قرار دادن اطلاعات فراوان و مقایسه بخش های به طور کل متما یز از یکدیگر می باشد. به طور کلی می توان سه استراتژی جدا از هم را به منظور حل یک جدول سودوکو در نظر گرفت که جزء پایه ای ترین روش ها هستند : + ### اسکن خط به خط : ساده ترین و در عین حال اصلی ترین روش رسیدن به جواب, روش اسکن خط به خط می باشد. در این روش ما با توجه به اینکه در هر سطر, ستون و ناحیه دارای هیچ تکراری نمی باشیم, می توانیم جواب مورد نظر خود را پیدا کنیم. در اینجا ما با هدف قرار دادن یک عدد و جستجو در جدول به منظر پیدا نمودن مکان مناسب برای ان می توانیم تمامی اعداد 1 الی 9 را در خانه های جدول مرتب کنیم. به طور مثال به شکل زیر توجه کنید:<br/> ![strategy1] ( http://upload7.ir/imgs/2014-03/39953003595474938380.gif ) <br/> + ### آنالیز ترکیبی : روش دیگر استفاده از اصل اساسی بازی سودوکو می باشد. یعنی عدم تکرار اعداد در ردیف ها, ستون ها و نواحی جدول, که با ترکیب این عوامل وقرار دادن منطقی در کنار یکدگر می توان به جواب رسید. برای درک بهتر به شکل زیر توجه کنید:<br/> ![strategy2] ( http://upload7.ir/imgs/2014-03/66849541782639946232.gif ) <br/> + ### نقطه گذاری : این استراتژی در واقع سیستمی کمکی به منظور تسهیل در رسیدن به پاسخ مناسب می باشد و می توان گفت روشی تکمیلی است. در اینجا با گذاشتن نقطه در خانه های خالی می توان جواب های احتمالی را برای ان خانه بخصوص مشخص نمود. برای درک بهتر به تصویر زیر توجه فرمایید: <br/> ![strategy3] ( http://upload7.ir/imgs/2014-03/38485433064370255983.gif ) <br/> در اینجا با تعیین پاسخ های احتمالی که می تواند در خانه ما قرار بگیرد عمل نقطه گذاری طبق تصویر بالا را انجام می دهیم. در تصویر بالا محل قرار گرفتن هر عدد را در خانه نظیر ان مشاهده می فرمایید. بسته به تعداد احتمالات ممکن, تعداد نقاط و محل انها متفاوت می باشد. <br/> > الگوریتم های زیادی برای حل سودوکو ارایه شده اند، از جمله : Backtracking , Rule-based , Boltzmann machine , Genetic Algorithm و ... که در این پروژه روش** Rule-based** استفاده شده ، چون طبق مطالعات انجام شده عملکرد و کارایی بهتری نسبت به بقیه داراست و در زمان کمتری به جواب می رسد. <br/> این الگوریتم به نوعی یک الگوریتم *اکتشافی* [^3] است. این الگوریتم چند قانون را بررسی و آزمایش می کند تا با توجه به آنها خانه ها را پر کند و یا برخی از جواب های کاندید را حذف کند. این قوانین عبارتند از : <br/> > ### 1. Naked Single : این به این معنی است که یک خانه فقط یک عدد کاندید دارد. > ### 2. Hidden Single : اگر در یک مربع 3x3 فقط یک خانه باشد که بتواند عدد خاصی را شامل شود، آن عدد باید در آن خانه نوشته شود. > ### 3. Naked Pair : اگر در یک مربع 3x3 دو خانه باشند که هر کدام فقط شامل 2 عدد کاندید باشند ،این رو عدد باید از سایر خانه های آن مربع که علاوه بر این دو عدد، اعداد کاندید دیگری هم دارند، حذف شوند. این قانون میتواند به سه یا چهار خانه هم گسترش پیدا کند. > ### 4. Hidden Pair : اگر در یک مربع 3x3 فقط دو خانه باشند که هر کدام شامل دو عدد کاندید خاص باشند که در سایر خانه های خالی آن مربع نیستند، باید سایر عددهای کاندید از این دو خانه حذف شوند. این قانون هم میتواند به سه یا چهار خانه گسترش پیدا کند. > ### 5. ( Guessing (Nishi : کامپیوتر یک خانه خالی را انتخاب می کند و آن را با یکی از عددهای کاندیدش پر می کند. سپس از اینجا شروع کرده و می بیند که آیا این انتخاب منجر به حل جدول می شود یا خیر. اگر عدد انتخابی اشتباه بود، دوباره برمی گردد به همان خانه و عدد کاندید دیگری را جایگزین آن می کند. این کار شبیه روشی است که در الگوریتم Backtracking استفاده می شود. # آزمایش‌ها # کارهای آینده # مراجع + محسن مشکی، بررسی کاربردهای شبکه هایی عصبی مصنوعی در بازشناسی شناسه های دست نویس + Ramana, K.V., Basha, K., Neural Image Recognition System with Application to Tuberculosis Detection,IEEE proceeding of International Conference of Information Technology + Patrik Berggren and David Nilsson , A study of Sudoku solving algorithms + Bertram Felgenhauer and Frazer Jarvis, Enumerating possible Sudoku grids + Zong Woo Geem, Harmony Serch Algorithm for Solving Sudoku # پیوندهای مفید + [کتابخانه اپن‌سی‌وی](http://opencv.org) + [اپن‌سی‌وی در پایتون](http://docs.opencv.org/trunk/doc/py_tutorials/py_tutorials.html) [شبکه عصبی]: http://fa.wikipedia.org/wiki/%D8%B4%D8%A8%DA%A9%D9%87_%D8%B9%D8%B5%D8%A8%DB%8C [خوشه بندی]: http://fa.wikipedia.org/wiki/%D8%AE%D9%88%D8%B4%D9%87%E2%80%8C%D8%A8%D9%86%D8%AF%DB%8C [^1]: train [^2]: segmentation [^3]: heuristic