سودوکو

[adel_minayi]

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

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

من که کد نخواستم آقای مدیر زود حذف میکنه پست رو،اینجا جائیه برای بحث و مبادله نظر...هر کی فکر کرد میخوام برنامه رو برام بنویسید اصلا نخونه....

[ztx4]

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


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

اگر بخوایی از آرایه استفاده کنی:

یک آرایه ی 2 بعدی 9*9 تعریف کنید.


خوب تا اینجا پیش نیاز ها.

حالا شما یک سری از خونه ها رو پر می کنید.(البته یک سری توابع نیاز داری که مراقب باشند که عدد تکراری وارد نشه!
کدی که می نویسی باید به این صورت عمل کنه:

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

البته من خودم سودوکو باز حرفه ای ام.در سودوکو زمانی هست که هیچ خونه ای یک مقدار یکتا نداره و می تونه چند مقدار داشته باشه و قرار دادن یک مقدار ر یک خونه می تونه باعث خراب شده کار بشه.
من تا حالا به حل سودوکو با نرم افزار فکر نکرده بودم.الان 5 دقیقه فکر کردم و اینا به ذهنم رسید.این الگوریتمی که در بالا نوشتم 2 تا ایراد داره:
1- خیلی پردازنده رو اشغال می کنه.
2- برای مواقعی که در بالا توضیح دادم راه حلی نداره.

بازم روش فکر می کنم چیزی به ذهنم رسید در پست های بعدی می گم.
شما هم فکر کن.

[adel_minayi]

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

[ztx4]

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

خوب دوست عزیز چه کسی این سادگی رو تضمین می کنه؟
شما از کجا مطمئنید که ترکیب اعداد ورودی به صورتی هست که حتما شرایط مذکور برقرار می شه؟
من سودوکو زیاد بازی می کنم و می دونم که نمی شه در ابتدا تشخیص داد که 10 - 15 عددی که ما وارد می کنیم طوری ترکیب شده اند که حتما همیشه خونه ای پیدا بشه که یک عدد داخلش قرار بگیره.
اگر احیانا سودوکو کمی سخت باشه برنامه ی شما می افته تو loop و نمی تونه خاتمه پیدا کنه.تو برنامه نویسی نمی شه از این ریسک ها کرد.

من کمی بیشتر فکر کردم و یک راه کار دیگه به نظرم رسید.عرض می کنم امیدوارم به دردتون بخوره:

برای نگه داری سودوکو در حافظه از یک آرایه ی 3 بعدی استفاده کنید .یک آرایه ی11*9*9
سطر و ستون آرایه می شن جدول سودوکو و اعدادی که در جدول به طور قطعی قرار گرفتن نگه داری می کنند.

می مونه ارتفاع که اون از 11 خونه تشکیل شده.
یک خونه از این 11 تا که هم سطح با جدوله و مسلما اطلاعات جدول داخل اون قرار گرفتن.
9 تای دیگه رو توانا ها نام گذاری کنیم که مربوط می شوند به اعداد 0 تا 9 که قابلیت قرار گیری در خونه ی پایینی(جدول سودوکو) رو دارا می باشند(این موضوع باعث می شه که از پیچیدگی زمانی برنامه کم بشه و بتونیم نتایج جستجو های قبلی رو نگه داری و در آینده استفاده کنیم.)
یک خانه ی مانده از ارتفاع هم پرچم نامگذاری کنیم که مربوط به وضعیت اون خونه از سودوکو می شه.یعی اگر خونه ی زیری یک مقدار قطعی به خودش گرفت مقدار این خانه به صورت 1 یعنی قطعی به خودش می گیره و دیگه نیازی نباشه که مجددا اون خانه تغییر مقدار بده.

خوب در آرایه ی بالا این اتفاق ها می افته.
1-در ابتدا توانا ها پر هستند یعنی اعداد 1 تا 9 در توانا ها قرار گرفتند و همه ی پرچم ها صفر هستند.
2-با ورود اعداد ثابت به داخل جدول توانا ها باید تغییر کنند.یعنی خونه ای که مقدار گرفته باید تمام توانا هاش 0 بشند و پرچمش 1.
3-با ورود یک عدد ثابت به یک خونه مثلا عدد 3 وارد خونه ی 4و4 بشه.در این خالت باید عدد 3 رو از تمام توانا ها ی سطر و ستون 4 و مربع کوچک اول حذف کرد.
4-در مرحله ی بعد باید به دنبال خونه ای بگردیم که فقط یک توانا داشته باشه.اونو پیدا کرده و عملیات شماره ی 2و3 رو تکرار کنیم.
5- زمانی فرار می رسه که همه ی خونه های خالی جدول بیشتر از یک توانا داشته باشند.یعنی همون شرایطی که شما گفتید پیش نمی یاد.در این حالت باید یک توانا رو به عنوان نمونه و به صورت تصادفی انتخاب و در جدول قرار بدیم و فقط عملیات 3 رو انجام بدیم یعنی پرچمش رو 1 نکنیم.چون اون خونه هنوز قطعی نشده.
جدول رو به همن صورت تا آخر حل می کنیم و اگر جدول کامل شد که تمام اگر نه عملیات 5 رو برای یک خونه ی دیگه انجام می دیم و دوباره جدول رو تا آخر حل می کنیم.


نمی دونم چه قدر توضیحاتم واضح بود.اگر سوالی داشتید بپرسید.
امیدوارم مفید بوده باشه.