نوع متداول سودوکو یک جدول 9x9 است که کل جدول هم به 9 جدول کوچکتر 3x3 تقسیم شده است. در این جدول چند عدد به طور پیش فرض قرار داده شده که باید باقی اعداد را با رعایت سه قانون زیر یافت:

• قانون اول: در هر سطر جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

• قانون دوم: در هر ستون جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

• قانون سوم: در هر ناحیه 3x3 جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

در این پژوهش از شما خواسته شده است تا با دریافت عکس جدول ورودی، حل آن را در همان عکس نمایش دهید.

۱. 1.مقدمه

سودوکو که همچنین به جور چین اعداد نیز معروف می باشد, یک پازل بر پایه منطق است. نوع متداول سودوکو یک جدول 9x9 است که کل جدول هم به 9 جدول کوچکتر 3x3 تقسیم شده است. در این جدول چند عدد به طور پیش فرض قرار داده شده که باید باقی اعداد را با رعایت سه قانون زیر یافت:

• قانون اول: در هر سطر جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

• قانون دوم: در هر ستون جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

• قانون سوم: در هر ناحیه 3x3 جدول اعداد 1 تا 9 بدون تکرار قرار گیرد.

  برای تکمیل پازل نیاز به حوصله و به کار بردن منطق می باشد. هر چند این پازل برای اولین بار در یک مجله پازل امریکایی در سال 1979 انتشار یافت، ولی انتشار آن به طور مستمر و پی گیر برای نخستین مرتبه بر می گردد به ژاپن در 1986 و در سال 2005 این سرگرمی به محبوبیت جهانی دست یافت.
  
  امروزه این بازی در تمامی کشورها به عنوان یک جدول فکری مقبولیت قابل توجهی یافته است و روز به روز به این محبوبیت افزوده می گردد. اکنون کمتر روزنامه و مجله پازلی را می توان یافت که هر روزه جداول سودوکو را در بخش سرگرمی خود نداشته باشد. این نوع جدول برخلاف اکثر دیگر جداول باعث تقویت فکر و ذهن منطقی در انسان می گردد به همین دلیل از این بازی در بسیاری از مسابقات به منظور سنجش قابلیت تعقل استفاده و در بسیاری از این فستیوال ها سودوکو به عنوان مقام نخست جهانی در بین بازی های سرگرمی دست می یابد.
  
  هدف ما در این پروژه ارایه روشی است که با دریافت عکس جدول ورودی، حل آن را در همان عکس نمایش دهد.

۲. 2. طرح کلی

این پروژه شامل دو بخش مهم و اصلی است : پردازش عکس ورودی و تفکیک اعداد ، حل جدول سودوکو.
طرح کلی برای حل این گونه مسایل به این صورت است که ابتدا با دریافت عکس ورودی و با اعمال پردازش های لازم، جدول و اعداد درون آن تفکیک می شود. در مرحله بعد با استفاده از یکی از روش های موجود به شناسایی اعداد می پردازیم که در این پروژه برای این کار از شبکه عصبی استفاده شده است. نهایتا به کمک یکی از الگوریتم های حل جدول سودوکو ، جدول را حل کرده و جواب ها روی عکس اولیه نوشته می شود.

۳. 3. کارهای مرتبط

در این قسمت مراحل و روش های موجود برای انجام مراحل اصلی پروژه ( پردازش عکس و حل جدول سودوکو ) توضیح داده خواهد شد.

۳.۱. 3/1. پردازش عکس

یکی از مهم ترین مباحث در پردازش تصویر، شناسایی الگو ¹ است. . در این حوزه شناسایی اعداد و حروف در یک تصویر ، یا همان [^2] OCR به دلیل کاربردهای مهم آن از اهمیت بالایی برخوردار است.

به طور کلی یک سیستم تشخیص الگو شامل سه مرحله زیر است :

• ### مرحله اول ( Preprocessing ) :
  در این قسمت عکس ورودی پردازش میشود، برای مثال نرمال سازی سایز،برطرف کردن نویز عکس، تبدیل عکس به باینری و ...
  برای آماده سازی عکس و تفکیک اعداد اولین کاری که باید انجام داد قطعه قطعه کردن ² عکس جدول با استفاده از Thresholding است.
  
  بعد از آن، نوبت به مشخص کردن مرزهای جدول می شود. به این صورت که قسمتی از عکس که بیشترین مساحت را دارد به عنوان جدول انتخاب می کنیم.
  
  با پیدا کردن مرزهای جدول، می توانیم جدول را از عکس جدا کرده و پس از remap کردن آن، عکسی خواهیم داشت که فقط شامل جدول سودوکو است و زاویه آن از بین رفته است. تصویر به دست آمده را به یک جدول 9x9 تقسیم می کنیم که هر کدام از خانه ها، یک خانه جدول اصلی است.
  با پردازش هر خانه می توان وجود یا عدم وجود عدد در آن خانه را تشخیص داد. اگر خانه ای شامل عدد بود، ذخیره شده و برای شناسایی عدد، توسط الگوریتمی به شبکه عصبی داده می شود.

• ### مرحله دوم ( Feature extraction ) :
  در این مرحله عکس پردازش شده تبدیل به برداری با مشخصات خاص میشود تا آماده طبقه بندی شود.
  لازم به ذکر است هم عکس ورودی و هم عکس هایی که برای آموزش به شبکه عصبی داده می شوند، باید این دو مرحله را طی کنند.

• ### مرحله سوم ( Classification ) :
  در این مرحله با استفاده از بردار به دست آمده از قسمت قبل، سیستم تمرین ³ داده می شود و یا یک بردار ورودی با استفاده از یک classify method، خوشه بندی میشود. به این صورت که شبکه عصبی آن را با تصاویری که هنگام آموزش شبکه ایجاد شده اند مقایسه کرده و پس از الگوریتم های درونیابی ، تقریب و تصمیم، مشخص می کند که به کدام عدد نزدیک تر است.
  برای آموزش شبکه عصبی روش های متعددی وجود دارد که از شناخته شده ترین آنها میتوان به K-Nearest Neighbour و SVM اشاره کرد.
  تفاوت مهم این دو روش این است که در الگوریتم KNN ما مستقیما از پیکسل ها به عنوان بردار مشخصات استفاده می شود، اما در الگوریتم SVM از (Histogram of Oriented Gradients (HOG به عنوان بردار مشخصات استفاده می شود.
  ما در این پروژه از الگوریتم KNN استفاده کرده ایم. به این صورت که ابتدا عکس هایی که برای آموزش سیستم هستند ، پردازش شده و به شبکه عصبی داده میشوند. بعد از اتمام این کار عکس ورودی پردازش شده و به شبکه عصبی داده میشود تا اعداد درون آن شناسایی شوند.

بعد از طی این مراحل جدول سودوکو ما آماده است و باید آن را حل کنیم.

لازم به ذکر است پروژه های بسیاری مشابه به پروژه حال حاضر انجام شده اند که معروفترین آنها تشخص ماشین ها در تصویر، تشخیص پلاک خودرو، خواندن پلاک خودرو، شکستن کپچا، تشخیص چهره و ... هستند.
روش کلی برای حل این مسائل همانند مراحل گفته شده در بالا است، فقط در جزئیات پیاده سازی تفاوت هایی وجود دارد. مثلا برای خواندن پلاک خودرو ابتدا باید ماشین را در تصویر پیدا کنیم ، پس از آن پلاک باید تشخیص داده شود و در نهایت اعداد و حروف پلاک تفکیک و شناسایی میشوند. اما برای شکستن کپچا باید اعداد و حروفی را پیدا و شناسایی کنیم که شکل آنها تغییر کرده است.

۳.۲. 3/2. حل جدول سودوکو

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

گاهی برای پرکردن تنها یک خانه از جدول نیاز به کنار هم قرار دادن اطلاعات فراوان و مقایسه بخش های به طور کل متما یز از یکدیگر می باشد.
به طور کلی می توان سه استراتژی جدا از هم را به منظور حل یک جدول سودوکو در نظر گرفت که جزء پایه ای ترین روش ها هستند :

• ### اسکن خط به خط :
  ساده ترین و در عین حال اصلی ترین روش رسیدن به جواب, روش اسکن خط به خط می باشد. در این روش ما با توجه به اینکه در هر سطر, ستون و ناحیه دارای هیچ تکراری نمی باشیم, می توانیم جواب مورد نظر خود را پیدا کنیم. در اینجا ما با هدف قرار دادن یک عدد و جستجو در جدول به منظر پیدا نمودن مکان مناسب برای ان می توانیم تمامی اعداد 1 الی 9 را در خانه های جدول مرتب کنیم. به طور مثال به شکل زیر توجه کنید:
  

![strategy1] ( http://upload7.ir/imgs/2014-03/39953003595474938380.gif )

• ### آنالیز ترکیبی :
  روش دیگر استفاده از اصل اساسی بازی سودوکو می باشد. یعنی عدم تکرار اعداد در ردیف ها, ستون ها و نواحی جدول, که با ترکیب این عوامل وقرار دادن منطقی در کنار یکدگر می توان به جواب رسید. برای درک بهتر به شکل زیر توجه کنید:
  

![strategy2] ( http://upload7.ir/imgs/2014-03/66849541782639946232.gif )

• ### نقطه گذاری :
  این استراتژی در واقع سیستمی کمکی به منظور تسهیل در رسیدن به پاسخ مناسب می باشد و می توان گفت روشی تکمیلی است. در اینجا با گذاشتن نقطه در خانه های خالی می توان جواب های احتمالی را برای ان خانه بخصوص مشخص نمود. برای درک بهتر به تصویر زیر توجه فرمایید:
  

![strategy3] ( http://upload7.ir/imgs/2014-03/38485433064370255983.gif )

در اینجا با تعیین پاسخ های احتمالی که می تواند در خانه ما قرار بگیرد عمل نقطه گذاری طبق تصویر بالا را انجام می دهیم. در تصویر بالا محل قرار گرفتن هر عدد را در خانه نظیر ان مشاهده می فرمایید. بسته به تعداد احتمالات ممکن, تعداد نقاط و محل انها متفاوت می باشد.

الگوریتم های زیادی تا کنون برای حل سودوکو ارایه شده اند، از جمله : Boltzmann machine, Rule-based , Backtracking و ... .
در این قسمت هر کدام از روش ها به طور مختصر توضیح داده شده و نتایج به دست آمده از آنها با هم مقایسه می شود.

3.2.1. 1. Backtracking :

این الگوریتم یکی از ساده ترین استراتژی های حل سودوکو برای کامپیوتر است و یک الگوریتم قطعی ⁴ است. این الگوریتم یک متد brute-force است که در هر مرحله یکی از اعداد کاندید در خانه های جدول را انتخای کرده و سعی در حل جدول می کند. اگر این انتخاب به حل جدول نینجامید، بازگشته و عدد کاندید دیگری را انتخاب می کند. این روش تضمین می کند که اگر زمان کافی در اختیار داشته باشد، قطعا به جواب خواهد رسید.

3.2.2. 2. Boltzmann machine :

این الگوریتم جدول سودوکو را با یک شبکه عصبی مصنوعی مدل می کند. جدول به عنوان یک constraint دیده می شود که نود هایی را مشخص می کند که نمی توانند به هم وصل شوند. این محدودیت ها به عنوان وزن های شبکه عصبی رمزگذاری شده و زمانی که یک راه حل پیدا شد، رمزگشایی می شوند.
این الگوریتم یک الگوریتم احتمالی ⁵ است.

3.2.3. 3. Rule-based :

این الگوریتم به نوعی یک الگوریتم اکتشافی ⁶ است. این الگوریتم چند قانون را بررسی و آزمایش می کند تا با توجه به آنها خانه ها را پر کند و یا برخی از جواب های کاندید را حذف کند . این قوانین عبارتند از :

Naked Single :

این به این معنی است که یک خانه فقط یک عدد کاندید دارد.

Hidden Single :

اگر در یک مربع 3x3 فقط یک خانه باشد که بتواند عدد خاصی را شامل شود، آن عدد باید در آن خانه نوشته شود.

Naked Pair :

اگر در یک مربع 3x3 دو خانه باشند که هر کدام فقط شامل 2 عدد کاندید باشند ،این رو عدد باید از سایر خانه های آن مربع که علاوه بر این دو عدد، اعداد کاندید دیگری هم دارند، حذف شوند. این قانون میتواند به سه یا چهار خانه هم گسترش پیدا کند.

Hidden Pair :

اگر در یک مربع 3x3 فقط دو خانه باشند که هر کدام شامل دو عدد کاندید خاص باشند که در سایر خانه های خالی آن مربع نیستند، باید سایر عددهای کاندید از این دو خانه حذف شوند. این قانون هم میتواند به سه یا چهار خانه گسترش پیدا کند.

( Guessing (Nishi :

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

۳.۳. بررسی نتایج

الگوریتم Rule-based سریع ترین الگوریتم از بین سایر روش هاست و میانگین زمان رسیدن به جواب آن 0.02 ثانیه است. پیچیدگی زمانی این الگوریتم در قسمت چک کردن قوانین به صورت خطی است و زمانی که وارد قسمت guessing می شود پیچیدگی آن به صورت توانی می شود.
بعد از آن الگوریتم Backtracking جایگاه دوم از نظر سرعت جوابگویی را دارد و میانگین زمان رسیدن به جواب آن 1.66 ثانیه است.

در این پروژه روش Rule-based استفاده شده ، چون طبق مطالعات انجام شده عملکرد و کارایی بهتری نسبت به بقیه داراست و در زمان کمتری به جواب می رسد.

پروژه انجام شده را اینجا می توانید مشاهده کنید. لازم به ذکر است که داده استفاده شده برای قسمت آموزش شبکه عصبی بسیار کوچک است و در مراحل بعدی باید از داده های بیشتر و بهتری استفاده شود. کد پیاده سازی شده نیاز به اصلاحاتی دارد که در فازهای بعدی این اصلاحات انجام می گیرد.

۴. آزمایش‌ها

۵. کارهای آینده

۶. مراجع

• محسن مشکی، ‌بررسی کاربردهای شبکه هایی عصبی مصنوعی در بازشناسی شناسه های دست نویس

• 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

۷. پیوندهای مفید

• کتابخانه اپن‌سی‌وی

• اپن‌سی‌وی در پایتون