سودوکو با استفاده از الگوریتم عقب گرد

[zt1990]

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

[soroushp]

برای پیاده سازی از آرایه استفاده کن به علاوه حلقه چک کردن - برای اون 3 تا خونه می تونی از شبه کد زیر استفاده کنی فقط با backtracking بنویس + بررسی پشرو که از همون اول عدد رو میزاری چک کنه ببینه تو دامته مورد نظر صدق می کنه یا خیر ؟ اگر مقدار false برگردوند یعنی باید عدد عوض بشه و همین طور برای سطر و ستون و خانه 3*3 مورد نظر :
bool checksatrsotoon(int r,int c)
{
for(int i=r/n*n;i<r/n*n+n;i++)
{
for(int j=c/n*n;j<c/n*n+n;j++)
{
شرط یا ...
}

[yashar_sb_sb]

پیچیدگی این روش خیلی زیاده، برای حل مسئله با این روش سالها زمان لازمه.
برای پیاده سازی از آرایه استفاده کن به علاوه حلقه چک کردن - برای اون 3 تا خونه می تونی از شبه کد زیر استفاده کنی فقط با backtracking بنویس + بررسی پشرو که از همون اول عدد رو میزاری چک کنه ببینه تو دامته مورد نظر صدق می کنه یا خیر ؟ اگر مقدار false برگردوند یعنی باید عدد عوض بشه و همین طور برای سطر و ستون و خانه 3*3 مورد نظر :
bool checksatrsotoon(int r,int c)
{
for(int i=r/n*n;i<r/n*n+n;i++)
{
for(int j=c/n*n;j<c/n*n+n;j++)
{
شرط یا ...
}

[yashar_sb_sb]

باید از "ارضاء محدودیت" استفاده کنی (CSP)

[soroushp]

باید از "ارضاء محدودیت" استفاده کنی (CSP)
به نظرت بررسی پیشرو غیر از CSP هست ؟ :بامزه:
CSP با هر روش رو چطوری می خوای پیاده کنی؟

[yashar_sb_sb]

میایم برای هر خانه از سودوکو 9 متغیر منطقی bool تعریف میکنیم. و هر کدام رو به اعداد 1 تا 9 نسبت می دیم. ( ایندکس های آرایه )
در ابتدا همه ی 9 متغیر true هستند.
بعدش میایم اون اعدادی که امکان نداره برای اون خونه درست باشن رو false میکنیم.
بعد میایم اون آرایه هایی که فقط یک مقدار true دارن رو انتخاب می کنیم و خواب اون خونه به دست میاد.
حالا میایم از آرایه های باقی مانده اون خونه هایی رو که تعداد true های کمتری دارند رو بالای درخت بازگشتی میذاریم و به همین ترتیب تا پایان میریم.
در هر مرحله از بازگشت دوباره یک stack از bool تشکیل میدیم که اول مقادیرش مشابه stack مرحله ی قبلیه، بعد دوباره برسی می کنیم که اعدادی که امکان درست بودن ندارند رو false میکنیم. (لازم نیست همه ی خونه ها رو بررسی کنیم. فقط اونایی رو برسی می کنیم که عنصر انتخاب شده در مرحله ی بازگشی درخت می تونه روشون تاثیر بذاره. )

[soroushp]

درسته اما به نظرت این روش مهندسیه ؟

[yashar_sb_sb]

درسته اما به نظرت این روش مهندسیه ؟

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

[soroushp]

من ادعایی ندارم اما می تونستی به جای استفاده از 729 متغیر از آرایه 9*9 استفاده می کردی که bool بود و یک تابع backtracking می نوشتی که مسئله حل بشه به هرحال روش شما هم یک روشه دیگه !
موفق و موید باشید

[zt1990]

باید از "ارضاء محدودیت" استفاده کنی (CSP)
اون وقت پیچیدگی اش چقدر بهتر میشه؟
csp مخفف چیه؟

[yashar_sb_sb]

میایم برای هر خانه از سودوکو 9 متغیر منطقی bool تعریف میکنیم. و هر کدام رو به اعداد 1 تا 9 نسبت می دیم. ( ایندکس های آرایه )
در ابتدا همه ی 9 متغیر true هستند.
بعدش میایم اون اعدادی که امکان نداره برای اون خونه درست باشن رو false میکنیم.
بعد میایم اون آرایه هایی که فقط یک مقدار true دارن رو انتخاب می کنیم و خواب اون خونه به دست میاد.
حالا میایم از آرایه های باقی مانده اون خونه هایی رو که تعداد true های کمتری دارند رو بالای درخت بازگشتی میذاریم و به همین ترتیب تا پایان میریم.
در هر مرحله از بازگشت دوباره یک stack از bool تشکیل میدیم که اول مقادیرش مشابه stack مرحله ی قبلیه، بعد دوباره برسی می کنیم که اعدادی که امکان درست بودن ندارند رو false میکنیم. (لازم نیست همه ی خونه ها رو بررسی کنیم. فقط اونایی رو برسی می کنیم که عنصر انتخاب شده در مرحله ی بازگشی درخت می تونه روشون تاثیر بذاره. )


اون وقت پیچیدگی اش چقدر بهتر میشه؟
csp مخفف چیه؟


این روش که من گفتم تو کمتر از یک ثانیه جواب میده.
پیچیدگیش بسته به ورودی که بهش داده میشه متغیره.
Constraint Satisfaction Problem

[i-nostalgic]

میتونی از csp استفاده بکنی برا آشنایی بیشتر با اون میتونی کتاب هوش مصنوعی راسل صفحه 227 رو بخونی حتی روی الگوریتم سودوکو بحث کرده ولی یه روش خیلی ساده هست تنها مشکلش اینه که کل سودوکو رو طراحی نمی کنه کافی است به صورت رندوم 20 خانه را انتخاب کنی و با شرط های سو دو کو در آن خانه ها اعداد را بزاری و هر سری فقط همان سطر وستون و خانه چک میشه و هر وقت که عدد اشتباهی وارد بشه خطا می ده.

[husayn]

در مورد این سه تا خط توضیح بده تویه چند تا کد دیدم ولی نفهمیدم چطوری کار میکنه