حل تصویری جدول سودوکو

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

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

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

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

برای مثال تکه کد زیر ابتدا عکس ورودی را خوانده و آن را به عکس gray scale تبدیل می کند. سپس نویز آن را برطرف کرده و متد threshold را به آن اعمال می کند تا آن را به عکس باینری تبدیل کند :

>>> img =  cv2.imread(image)
>>> gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
>>> blur = cv2.GaussianBlur(gray,(5,5),0)
>>> thresh = cv2.adaptiveThreshold(blur,255,1,1,11,2)


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

کد زیر عکس threshold شده را گرفته و آن را به برداری با مشخصات خاص تبدیل می کند تا در نهایت برای شناسایی به شبکه عصبی داده شود :

>>> vector = cv2.resize(thresh,(10,10)) 
>>> vector = vector.reshape((1,100))
>>> vector = np.float32(vector)


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

نمونه ای از کد آموزش شبکه عصبی با الگوریتم KNN :

>>> model = cv2.KNearest()
>>> model.train(samples,responses)

که در اینجا samples مجموعه ای از بردارهای داده های جمع آوری شده برای آموزش شبکه عصبی و responses مجموعه بردارهای جواب متناظر با داده ها می باشد.

به منظور شناسایی یک عدد، بردار مشخصات آن طبق کد زیر به شبکه عصبی داده می شود :

>>> retval, results, neigh_resp, dists = model.find_nearest(vector, k = 1)

در اینجا k مشخص می کند شبکه عصبی با چه همسایگی عدد را تشخیص بدهد.


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

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

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

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

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

3.2.1 اسکن خط به خط :

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

عکس اول


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

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

عکس دوم


3.2.3 نقطه گذاری :

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

عکس سوم



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

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

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

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

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

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

3. الگوریتم Rule-based :

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

  • قانون اول ( 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 و main.py است. در این بخش توضیح مختصری در مورد هر یک از فایل ها می دهیم و در بخش بعد به ارزیابی پروژه می پردازیم.

  • فایل Image_Processing.py :
    این فایل عکس ورودی را گرفته و آن را پیش پردازش می کند تا برای شناسایی اعداد درون جدول آماده شود. سپس با پردازش هر سطر جدول مکان اعداد مشخص می شود. تابع ()image_processing این کار را انجام می دهد. این تابع خروجی خود را که همان مکان اعداد در جدول است به تابع recognizer داده تا با استفاده از الگوریتم K-Nearest Neighbour اعداد شناسایی شوند.
    خروجی این فایل یک جدول سودوکو است که در یک آرایه ذخیره شده و برای حل به فایل solve_sudoku.py داده می شود.
    لازم به ذکر است تابع ()prepare_data داده های موردنیاز برای آموزش شبکه عصبی را پردازش می کند و تابع ()train همان داده ها را برای آموزش به شبکه عصبی می دهد.
    همچنین مکان خانه های خالی جدول هم در این قسمت مشخص می شود تا در مرحله آخر اعداد در آن خانه ها نوشته شوند.

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

  • فایل main.py :
    این فایل به منزله فایل اصلی برنامه است که ارتباط بین دو فایل دیگر را برقرار می کند. . این فایل ابتدا فایل Image_Processing.py را اجرا کرده تا عکس جدول ورودی را پردازش کند؛ جدول و اعداد درون آن شناسایی می شوند و خروجی این قسمت به صورت یک آرایه با 81 عنصر (متناظر با 81 خانه جدول ) برگردانده می شود. سپس فایل solve_sudoku.py اجرا می شود که این آرایه را به عنوان ورودی می گیرد و اگر جدول قابل حل بود، حل آن را در عکس ورودی نمایش می دهد. در غیر این صورت پیغامی مبنی بر عدم حل جدول چاپ می شود.

5. آزمایش ها

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

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

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

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

خروجی های برنامه در روند پردازش جدول برای چند نمونه مختلف را می توانید در زیر مشاهده کنید( به جز نمونه اصلی، سایز سایر نمونه ها کوچک شده است ) :

نمونه شماره 1 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


نمونه شماره 2 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


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


نمونه شماره 3 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


  • بررسی:
    کد پیاده سازی شده برای عکس های دارای حاشیه نیز به خوبی عمل کرده و قادر به جدا کردن جدول اصلی از کل عکس و شناسایی صحیح اعداد آن می باشد.


نمونه شماره 4 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


  • بررسی:
    عملکرد کد پیاده سازی شده برای عکس های دارای حاشیه و همچنین زاویه دار نیز بسیار مطلوب است و جدول اصلی و اعداد آن به درستی شناسایی شده اند.


نمونه شماره 5 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


  • بررسی:
    مشاهده می شود که نتیجه آزمایش برای عکس هایی با کیفیت پایین رضایت بخش است و اعداد به درستی تشخیص داده شده اند.


نمونه شماره 6 :

  • عکس ورودی :

    عکس ورودی


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

    حذف حاشیه و زوایا


  • تشخیص اعداد در خانه های جدول:

    تشخیص اعداد


  • نمایش حل جدول در عکس :

    عکس خروجی


  • بررسی:
    مشاهده می شود که نتیجه آزمایش برای عکس هایی با کیفیت پایین، دارای حاشیه و زاویه نیز مطلوب است. البته به دلیل کیفیت پایین عکس، عدد 5 در ردیف دوم جدول شناسایی نشد (عکس سوم)؛ اما در قسمت حل جدول سودوکو، جدول به درستی حل شد که نشان دهنده دقت و کارایی کد پیاده سازی شده برای قسمت حل جدول است؛ چنانکه با وجود عدم شناسایی یکی از اعداد، باز هم قادر به حل جدول با تعداد عدد داده شده کمتر بود.


بهبود نتایج :

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


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

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

  • نتایج حاصل از آزمایش برای 5 نمونه (فاز قبل) :

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


  • نتایج حاصل از آزمایش برای 15 نمونه (فاز فعلی) :

میزان سختی جدول سودوکو تعداد نمونه ها تعداد جداول حل شده میانگین زمان اجرا (ثانیه) بیشترین زمان اجرا(ثانیه)
آسان 15 15 0.010 0.030
سخت 15 15 0.030 0.080
خیلی سخت 15 15 0.012 0.020


نتیجه :

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

جدول سودوکوی حل ناپذیر :

به عنوان آزمایشی دیگر، یک جدول سودوکوی حل ناپذیر به برنامه داده شد که 905.38 ثانیه زمان برد تا برنامه اجرا شده و پیغامی مبنی بر عدم حل جدول را چاپ کند. این زمان نسبتا زیادی است؛ اما این پروژه عملا نیازی به پوشش جداول حل ناپذیر ندارد، زیرا عکس های موجود در روزنامه ها و بازی ها همگی جدول های قابل حل می باشند. البته میانگین زمان اجرای پروژه های موجود برای حل جدول سودوکو، برای جدول های حل ناپذیر حدودا 1200 ثانیه است که باعث می شود نتیجه به دست آمده از آزمایش بالا تا حدی مطلوب واقع شود.

  • نمونه آزمایش شده :

    حل ناپذیر


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


کارهای آینده

مراجع

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

  • 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

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


  1. Pattern Recognition

  2. train

  3. deterministic

  4. stochastic

  5. heuristic

نیما همتی

کار شما برای این فاز بسیار خوب و ارزشمند می‌باشد. ضمن عرض خسته نباشد امید است با همین رویه برای فازهای بعدی نیز اقدام کنید.

موفق باشید.

نیما همتی

با سلام و خسته نباشید
به طور کلی بسیار خوب بود و برای نوشتن آن زحمت کشیده شده است. اما چندین نکته در این مورد قابل ذکر است:

  • عدم رعایت مرتب‌نویسی در ارجاعات

  • عدم رعایت مرتب‌نویسی در قسمت بیان الگوریتم‌ها

  • در قسمت بیان الگوریتم‌ها برای حل جدول، مواردی همچون الگوریتم ژنتیک که راه‌حل علمی‌تر و کارا برای مسئله می‌باشد، بیان نشده است.

  • استفاده از واژه "آموزش" بهتر "تمرین" است.

  • در نمایش شکل‌ها در حال حاضر مشکل وجود دارد. همچنین آدرس دهی آن به نظر اشتباه است، در صورت وجود لطفا اصلاح گردد.

با تشکر

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

تایید شده

با عرض سلام و خسته نباشید. در مورد پروژه تون نکات زیر به ذهنم می رسه:

  1. شکلی که برای بخش " اسکن خط به خط" گذاشتید اشتباهه چون ستون ششم علامت زده نشده! یا اگر من اشتباه متوجه شدم و نیاز به علامت گذاری نبوده, نشون دهنده ی اینه که منظورتون رو درست بیان نکردید.

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

  3. در کل به نظرم می تونستید الگوریتم پیاده سازی شده رو با جزئیات بیشتری توضیح بدید.

  4. متن پروژه تون در ظاهر خیلی مرتب به نظر می رسه, اما غلطهای املایی, کلمات اضافه و استفاده ی نادرست از فاصله و نیم فاصله تو متن به چشم می خوره.

  5. اما بخش آزمایش ها تقریباً خوب انجام شده. مخصوصا بخشی که مشکل قسمت پردازش جدول سودوکو رو برطرف کردید.

تایید شده
  1. اینکه در پرو‌‌ژه تان بعضی از کلمات تخصصی را لینک داده اید خوب است.

  2. استفاده از عکس در کنار توضیحات کار خوبی است.

  3. در کل پروژه مرتب و کامل است ولی چند غلط املایی وجود دارد. مثلا " نمومه " در جدول آزمایش ها. همچنین پاورقی شماره ۲ مشکل دارد.بهتر است اصلاح شود.

  4. قسمت آزمایش ها را خوب انجام داده اید. اینکه هر قسمت را جدا آزمایش کرده اید ایده خوبی است و باعث شده خروجی هر قسمت بهتر دیده و آزمایش شود. فقط سعی کنید در فاز بعد تعداد آزمایش ها بیشتر شود.

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

  6. بهتر است در همان فایل main.py کاربر بتواند عکس ورودی را عوض کند.

تایید شده

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

تایید شده

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

خسته نباشید:دی

تایید شده

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

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

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

تایید شده

سلام،
این پروژه یکی از جالب‌ترین پروژه‌هایی بود که دیدم. پیشنهاد می‌کنم در آینده، همین پروژه را به صورت یک نرم افزار موبایل بنویسید. کافه بازار را گشتم، چنین نرم‌افزاری وجود ندارد - ظاهرا البته. نکات زیر به ذهن بنده می‌رسد:

  • نیازی به نوشتن بخش دوم نداشتید. بهتر بود طرح کلی‌ِ کارتان را در آخرِ مقدمه یا اول کارهای مرتبط توضیح می‌دادید. بخش کارهای آینده هم توضیح داده نشده، حذفش کنید.توضیحات این قسمت متن‌، می‌توانست بهتر باشد:

    قطعه قطعه کردن ( segmentation )عکس جدول با استفاده از Thresholding است.

  • توضیحات مربوط به کدتان می‌توانست در Readme گیت‌هاب باشد. کد خیلی خوب است. آفرین

  • کارتان را بهبود که داده‌اید چرا میانگین زمان اجرا، زیادتر شده و چرا زمان حل کردن سودوکوی سخت، بیشتر از سودوکوی خیلی سخت شده؟ کاش تعداد آزمون انجام شده در مرحله اول و بهبود یکی بود که بشود مقایسه‌شان کرد.

موفق باشید:)

تایید شده

تمامی قسمت ها مخصوصا قسمت آزمایش ها به خوبی توضیح داده شده بودند و مطلب کاملا مفهمومی بود فقط چند نکته وجود داشت :

  • بهتر بود مراجع را در متن ارجاع میدادید .

  • بخش کارهای آینده بخش مهمی است که متاسفانه رها شده بود .

  • اگر کامنت گذاری را در کدزدن رعایت میکردید بهتر بود .

  • کلمات تخصصی مثل اسم قانون ها بدون توضیح رها شده بودند اگر لینک مثلا ویکی پدیا میدادید بهتر بود.
    موفق باشید

تایید شده

بسم الله

سلام و خسته نباشید

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

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

بهتر بود در مورد قسمت بهبود نتایج کمی بیشتر توضیح می دادید. مثلا چند راهکار مختلف را بررسی می کردید و به پیاده سازی یکی می پرداختید.

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

تکمیل قسمت کارهای آینده به علمی و کامل شدن پروژه شما کمک می کند.

نمره : 4.5

تایید شده

نکات مثبت :

  • جدا کردن ارزیابی های image proccessing و حل جدول سودوکو وقرار دادن عکس های هر مرحله باعث می شود خواننده کاملا با روند کار و نتایج آشنا شود.

  • توضیح کد پیاده سازی شده کار خواننده را راحتتر کرده است.

  • مرتب بودن متن گزارش

  • لینک دادن بعضی از کلمات تخصصی برای مطالعه بیشتر

نکات منفی:

  • خالی بودن بخش کارهای آینده، میتوانستید توضیحات بعضی از بهبودها یا موارد خاص را در این قسمت قرار دهید

  • عدم ارجاع دادن مراجع

  • کم بودن تعداد مراجع

تایید شده

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

نیما همتی

با سلام

تبریک بابت انجام خوب این پروژه، بسیار خوب بود. منتها چند نکته:

  • بخش کارهای مرتبط می‌توانست تکمیل گردد.

  • ارجاعات به درستی داده نشده است.

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

  • برای استفاده از الگوریتم‌های یادگیری ماشین در زبان پایتون می‌توانید از http://scikit-learn.org/ استفاده کنید.

با تشکر - موفق باشید.