نوع متداول سودوکو یک جدول 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. حل جدول سودوکو

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

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

۳.۲.۱. 3.2.1 اسکن خط به خط :

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

۳.۲.۲. 3.2.2 آنالیز ترکیبی :

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

۳.۲.۳. 3.2.3 نقطه گذاری :

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

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

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

۳.۲.۴. 1. الگوریتم Backtracking :

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

۳.۲.۵. 2. الگوریتم Boltzmann machine :

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

۳.۲.۶. 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 استفاده شده ، چون طبق مطالعات انجام شده عملکرد و کارایی بهتری نسبت به بقیه داراست و در زمان کمتری به جواب می رسد.

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

۴. 4. پیاده سازی

برای پیاده سازی این پروژه هر بخش به طور جدا پیاده سازی شده است. پروژه شامل 3 فایل اصلی Image_Processing.py ، solve_sudoku.py و project.py است. در این بخش توضیح مختصری در مورد هر یک از فایل ها می دهیم و در بخش بعد به ارزیابی پروژه می پردازیم.

۴.۱. فایل Image_Processing.py :

این فایل عکس ورودی را گرفته و آن را پیش پردازش می کند تا برای شناسایی اعداد درون جدول آماده شود. سپس با پردازش هر سطر جدول مکان اعداد مشخص می شود. تابع ()image_processing این کار را انجام می دهد. این تابع خروجی خود را که همان مکان اعداد در جدول است به تابع recognizer داده تا با استفاده از الگوریتم K-Nearest Neighbour اعداد شناسایی شوند.

خروجی این فایل یک جدول سودوکو است که در یک آرایه ذخیره شده و برای حل به فایل solve_sudoku.py داده می شود.

لازم به ذکر است تابع ()prepare_data داده های موردنیاز برای آموزش شبکه عصبی را پردازش می کند و تابع ()train همان داده ها را برای آموزش به شبکه عصبی می دهد.

همچنین مکان خانه های خالی جدول هم در این قسمت مشخص می شود تا در مرحله آخر اعداد در آن خانه ها نوشته شوند.

۴.۲. فایل solve_sudoku.py :

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

۴.۳. فایل project.py :

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

۵. 5. آزمایش ها

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

۵.۱. 5.1 ارزیابی قسمت پردازش جدول سودوکو :

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

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

خروجی های برنامه در روند پردازش جدول را می توانید در زیر مشاهده کنید :

۵.۱.۱. عکس ورودی :

۵.۱.۲. جدول پس از حدف حاشیه ها و remap کردن به منظور از بین بردن زاویه عکس:

۵.۱.۳. تشخیص اعداد در خانه های جدول:

۵.۱.۴. نمایش حل جدول در عکس :

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

۵.۲. 5.2 ارزیابی قسمت حل جدول سودوکو :

در بخش حل جدول سودوکو همانطور که در قسمت کارهای مرتبط گفته شد، از الگوریتم Rule-based استفاده شده است. این الگوریتم توانست تمامی جداول سودوکوی ورودی را حل کند. برای اینکه بتوانیم بهتر این قسمت را مورد آزمایش قرار بدهیم، از سه دسته جداول سودوکوی آسان، سخت و خیلی سخت، هرکدام 5 جدول را انتخاب کرده و به سیستم داده شد. البته به دلیل اینکه این جداول به صورت تصویری نبودند، برای آزمایش این قسمت جدول ها به صورت دستی به برنامه داده شدند.

جدول زیر نتایج حاصل از این آزمایش را نشان می دهد :

میزان سختی جدول سودوکو	تعداد نمومه ها	تعداد جداول حل شده	میانگین زمان اجرا (ثانیه)
آسان	5	5	0.008
سخت	5	5	0.010
خیلی سخت	5	5	0.012

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

• پروژه انجام شده را اینجا می توانید مشاهده کنید.

۶. آزمایش‌ها

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

۸. مراجع

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

• 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

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

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

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