حل جدول سودوکو؟

  • شروع کننده موضوع
  • #1

khoshi

کاربر حرفه‌ای
ارسال‌ها
391
امتیاز
702
نام مرکز سمپاد
حلی3
شهر
تهران
مدال المپیاد
تلاش!
یه راه برای حل جدول سودوکو میخوام
که جدول سریع حل شه
ممنون از اینکه می خواین جواب بدین
 
  • شروع کننده موضوع
  • #2

khoshi

کاربر حرفه‌ای
ارسال‌ها
391
امتیاز
702
نام مرکز سمپاد
حلی3
شهر
تهران
مدال المپیاد
تلاش!
پاسخ : حل جدول سودوکو؟

حد اقل یه فهشی یه - ای یا حتی بیاید اینو ببندید
یعنی هیچ کی یه الگوریتم سریع برای حل سودوکو نمی دونه؟
 

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
442
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : حل جدول سودوکو؟

سودوکو الگوریتم چندجمله ای نداره! باید از backtrack استفاده کنی. اگه از bound و branch های مناسب استفاده کنی توی backtrack برنامه خیلی سریع جواب می ده.
 
  • شروع کننده موضوع
  • #4

khoshi

کاربر حرفه‌ای
ارسال‌ها
391
امتیاز
702
نام مرکز سمپاد
حلی3
شهر
تهران
مدال المپیاد
تلاش!
پاسخ : حل جدول سودوکو؟

مرسی ولی میشه یه کم بیشتر توضیح بدین؟به زبون ساده تر :D
 

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
442
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : حل جدول سودوکو؟

backtrack یه جوری شیوه حل مساله هست! کلا یک شیوه، برای به جواب رسیدن توی مساثل NP هست!

توضیحش واقعا سخته اینجا! وقتی می خوان backtrack رو دقیق توضیح بدن، راحت 2-3 جلسه می تونه طول بکشه. کلی پیش زمینه لازم داره! :D

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

princess

کاربر نیمه‌فعال
ارسال‌ها
11
امتیاز
7
نام مرکز سمپاد
فرزانگان تهران
شهر
تهران
مدال المپیاد
کامپیوتر ریاضی
دانشگاه
امیرکبیر
رشته دانشگاه
علوم کامپیوتر
پاسخ : حل جدول سودوکو؟

به زبون ساده تر خواستی: backtrack میشه امتحان کردن همه ی حالت ها، با branch & bound میشه با حذف حالت هایی که می دونیم به جواب نمی رسن!
واسه این که مثلا همین سودوکو رو حل کنی می تونی یه تابع بازگشتی بنویسی که هر بار یه ماتریس ( همون جدول سودوکویی که تا اینجا حل کردی ) رو به عنوان ورودی می گیره و یه عنصر بهش اضافه می کنه و دوباره خودش رو صدا می کنه. تهش دو تا اتفاق ممکنه بیفته : یا جدول حل میشه ( ابراز شادی ) یا دیگه نمی شه عنصری بهش اضافه کرد که ما عنصر فعلی ( که اضافه کرده بودیم ) رو حذف می کنیم و یکی دیگه به جاش می ذاریم. و همین داستان رو ادامه می دیم.
کلا این مدل الگوریتم سه قسمت داره: 1-چک کردن این که به جواب رسیدیم 2- پیدا کردن حالت هایی که می تونیم ادامه بدیم اونا رو 3- گذاشتن هر کدوم از حالت های مساله ی قبل
حالا این branch and bound میاد می گه تو به یه ترتیب خوبی این راس ها رو برو که زودتر بفهمی دیگه نباید ادامه بدی یا یه چیز اضافه ای ( bound ) رو حساب کن که بفهمی کدوم راه دیگه به جواب نمی رسه. تو این مساله الآن چیزی به ذهنم نمی رسه! :D سودوکو ام هم خوب نیست..
 

stevendeljoo

داماد مسعودی
ارسال‌ها
1,351
امتیاز
2,642
نام مرکز سمپاد
شهید بهشتی نیشابور
شهر
نیشابور
سال فارغ التحصیلی
1391
مدال المپیاد
ندارم
دانشگاه
امیرکبیر
رشته دانشگاه
برق
پاسخ : حل جدول سودوکو؟

اینا سریعه؟؟؟؟؟؟؟
اینا که تقریبا آزمون و خطاست همش!


فک کنم بتونی ی سیستم امتیاز دهی خوب برای پرکردن خونه ها تعریف کنی
اول از همه آرایه تو تحلیل کن .ببین هرخونه چه اعدادی رو قبول میکنه(باتوجه به سطر و ستون و بلاکش)بعد همشو تو ی رشته بریز که مثلا هروقت به *رسیدیم توش یعنی به مشخصات خونه ی بعد وارد شدیم تو هرقسمتIوJخونه و اعداد ممکن رو بریز و جدا کن
بعد شروع کن به امتیاز دادن
اگه به جمع بندی درستی نرسیدی با توجه به خونه های سطر و ستونو بلاکش هم امتیاز بده
ی چیزی مث احتمال
درصد امکان بده!
 

BLACK HOLE

کاربر فوق‌حرفه‌ای
ارسال‌ها
826
امتیاز
2,199
نام مرکز سمپاد
فرزانگان امين
شهر
اصفهان
سال فارغ التحصیلی
1392
مدال المپیاد
نجوم
دانشگاه
University of Alberta
رشته دانشگاه
Computer Science
پاسخ : حل جدول سودوکو؟

به نقل از پارسا :
backtrack یه جوری شیوه حل مساله هست! کلا یک شیوه، برای به جواب رسیدن توی مساثل NP هست!

توضیحش واقعا سخته اینجا! وقتی می خوان backtrack رو دقیق توضیح بدن، راحت 2-3 جلسه می تونه طول بکشه. کلی پیش زمینه لازم داره! :D

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

NPچیه دیگه؟ :D :D

معلم‌های کامپیوتر میدونن؟

اگه فقط برنامه نویسی خونده باشن؟ :-"
 

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
442
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : حل جدول سودوکو؟

به نقل از ..AndromedA.. :
مشکل ۲تا شد!

NPچیه دیگه؟ :D :D

معلم‌های کامپیوتر میدونن؟

اگه فقط برنامه نویسی خونده باشن؟ :-"

NP مخفف Non Polynomial هست. به دسته مسائلی گفته می شه برای حلشون الگوریتم هایی از زمان چندجمله ای وجود نداره ( تعریفش این نیست در اصل، ولی همین رو می شه فرض کرد الان! مشکلی ایجاد نمی کنه)
حالا لازمه که شما ما مفهومی به نام "اُردِر" آشنایی داشته باشید، تا این تعریف رو متوجه بشید.

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

BLACK HOLE

کاربر فوق‌حرفه‌ای
ارسال‌ها
826
امتیاز
2,199
نام مرکز سمپاد
فرزانگان امين
شهر
اصفهان
سال فارغ التحصیلی
1392
مدال المپیاد
نجوم
دانشگاه
University of Alberta
رشته دانشگاه
Computer Science
پاسخ : حل جدول سودوکو؟

به نقل از پارسا :
NP مخفف Non Polynomial هست. به دسته مسائلی گفته می شه برای حلشون الگوریتم هایی از زمان چندجمله ای وجود نداره ( تعریفش این نیست در اصل، ولی همین رو می شه فرض کرد الان! مشکلی ایجاد نمی کنه)
حالا لازمه که شما ما مفهومی به نام "اُردِر" آشنایی داشته باشید، تا این تعریف رو متوجه بشید.

احتمال خیلی زیاد باید معلم های کامپیوتر بدونند! فکر می کنم که جزو واحدهای دانشگاهشون، طراحی الگوریتم هم وجود داره، که فکر می کنم این چیزا رو توش گفتن حتما.
اگه معلم المپیاد کامپیوتر (معلم الگوریتم) دارید حتما می دونه! از اون بپرس.
خوب پس سوال رو کلی‌ تر می‌کنیم! :D :D

شما این چیز هارو از کجا یاد گرفتید که من هم برم از پایه یاد بگیرم؟ :-" :-"
 

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
442
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : حل جدول سودوکو؟

به نقل از ..AndromedA.. :
خوب پس سوال رو کلی‌ تر می‌کنیم! :D :D

شما این چیز هارو از کجا یاد گرفتید که من هم برم از پایه یاد بگیرم؟ :-" :-"

المپیاد کامپیوتر :D
 

BLACK HOLE

کاربر فوق‌حرفه‌ای
ارسال‌ها
826
امتیاز
2,199
نام مرکز سمپاد
فرزانگان امين
شهر
اصفهان
سال فارغ التحصیلی
1392
مدال المپیاد
نجوم
دانشگاه
University of Alberta
رشته دانشگاه
Computer Science
پاسخ : حل جدول سودوکو؟

به نقل از پارسا :
المپیاد کامپیوتر :D

حدس میزدم... B-)

خوب حالا از روی چه کتابی‌ اینا رو خوند اید؟ :D :D
 

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
442
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : حل جدول سودوکو؟

به نقل از ..AndromedA.. :
حدس میزدم... B-)

خوب حالا از روی چه کتابی‌ اینا رو خوند اید؟ :D :D

معلم درس داد!

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

fani

کاربر نیمه‌فعال
ارسال‌ها
6
امتیاز
4
نام مرکز سمپاد
علامه حلی 1 تهران
شهر
تهران
پاسخ : حل جدول سودوکو؟

یکی از دوستام برنامش رو نوشته بود اگه میخوایش پیغام بده تا برات اپلودش کنم.
 

maziar

مازیمون
ارسال‌ها
1,962
امتیاز
6,833
نام مرکز سمپاد
علامه حلی
شهر
تهران، استانبول، کوالالامپور، اُسلو!
دانشگاه
Universitetet i Oslo
رشته دانشگاه
ریاضی، CS، نانو الکترونیک
پاسخ : حل جدول سودوکو؟

خب اگه اشتباه نكنم حل سودوكو جواب چند جمله اي نداره
و ما با يه مساله NP-Complete طرف هستي
پس تعجبي نداره كه بري سراغ راه هايي كه با توان رابطه دارن
يعني اكسپوننشيال بايد باشه
پس دنبال راه كوتاه از نظر زماني نباش
دنبال ساده كردن راه باش
خب ببين تو همه چيز رو بايد امتحان كني و بعد مي بيني تعداد خيلي زيادي از راه ها حذف ميشن

و خب اين جا مهم اينه كه تو بتون خيلي زود راه هايي كه اهميت خاصب ندارن و حتمن غلط هستن حذف كني

خب مي توني درباره مسائل اين مدلي مي توني به سوال هايي مثل vertex cover independent set يه نگاهي بندازي ايده هايه خوبي بهت ميدن
 
بالا