الگوريتم جدول سودوكو

[shahab85]

سلام
دوستان من ميخوام جدول سودوكو رو با جاوا بنويسم يعنتي در واقع يه جور بازي
موندم كه ميشه الگوريتمي نوشت كه جاوا خودش اين جدول نه در نه رو پر كنه؟
در ضمن كاربر با انتخاب مراحل سخت،متوسط و آسان خونه هاي مناسب جدول بهش نشون داده بشه و طوري اين خونه ها انتخاب بشن كه جدول قابل حل باشه
يا اينكه راهي نيست و بايد يه سري جدول هاي آماده از قبل به برنامه بدم؟

 

[Next]

سلام میشه راجع به جدول سودوکو به من توضیح بدی که چه جور جدولی ؟
ممنون

 

[shahab85]

جدول سودوكو يه جدول 9 در 9 هست كه خودشو هم به 9 تا جدول 3 در 3 تقسيم ميشه
ما بايد اعداد 1 تا 9 رو طوري توي اين جدول بچينيم كه در سطر ها و ستون هاي جدول بزرگ( 9در 9 ) تمامي اعداد فقط يكبار ديده بشن.همچنين اعداد 1 تا 9 در مربع هاي كوچك سه در سه نيز نبايد تكراري باشند.
اين جدول رو وقتي طرح كردي به طور مثال 20 تا خونه از 81 خونش رو به كاربر نشون ميدي و ميگي بقيه رو حل كن
البته يجوري بايد اين 20 تا عدد رو انتخاب كني كه جدول يقينا قابل حل باشه
اگه ميخوايد بيشتر متوجه شين فردا يه روزنامه ايران بخريد هر روز از اين جدولا داره
خوب توضيح دادم يا كسي متوجه نشد؟

 

[joody121]

سلام
تو این لینک الگوریتمی برای تولید جداول سودوکوی قابل حل موجود است. به این صورت که ابتدا یک جدول تعداد عناصر پر شد با تعداد خاصی می گیره و بررسی می کنه که آیا قابل حل است یا نه؟ این حلقه را تا آنجا ادامه می ده که برسه به یک جدول قابل حل:
کد:
int num = GetNumberSpots();if(!IsSudokuFeasible() || num > nodes){ // The supplied data is not feasible, clear data. // - or - // The supplied data has too many nodes set, clear data. Clear(); num = 0;}
کد:
http://www.codeproject.com/KB/game/sudoku.aspx
البته کدش به سی شارپه ولی کدش رو هم گذاشتن و می تونی مطالعه کنی.

برا سختی و آسونیش هم می تونی تعداد خانه های عدد دار را انتخاب کنی. مثلاً واسه سخت 17 تا خونه رو نشون بدی.


یه راهی هم که خودم به نظرم می رسه اینه که ابتدا یک جدول کاملاً حل شده تهیه کنیم (به صورت تصادفی) و سپس مثلاً 17 خانه از آن را انتخاب کنیم (باز تصادفی!) .
تهیۀ یک جدول سودوکوی کامل در زیر آمده است (به زبان vb):
کد:
http://www.codeproject.com/KB/vb/SudokuGen.aspx
الگوریتم سرراستی هم داره.
و سپس از آرایه ای که تولید کرده به تعداد دلخواه تولید می کنی.

 

[Keivan Keihanipour]

سلام
تو این لینک الگوریتمی برای تولید جداول سودوکوی قابل حل موجود است. به این صورت که ابتدا یک جدول تعداد عناصر پر شد با تعداد خاصی می گیره و بررسی می کنه که آیا قابل حل است یا نه؟ این حلقه را تا آنجا ادامه می ده که برسه به یک جدول قابل حل:
کد:
int num = GetNumberSpots();if(!IsSudokuFeasible() || num > nodes){ // The supplied data is not feasible, clear data. // - or - // The supplied data has too many nodes set, clear data. Clear(); num = 0;}
کد:
http://www.codeproject.com/KB/game/sudoku.aspx
البته کدش به سی شارپه ولی کدش رو هم گذاشتن و می تونی مطالعه کنی.

برا سختی و آسونیش هم می تونی تعداد خانه های عدد دار را انتخاب کنی. مثلاً واسه سخت 17 تا خونه رو نشون بدی.


یه راهی هم که خودم به نظرم می رسه اینه که ابتدا یک جدول کاملاً حل شده تهیه کنیم (به صورت تصادفی) و سپس مثلاً 17 خانه از آن را انتخاب کنیم (باز تصادفی!) .
تهیۀ یک جدول سودوکوی کامل در زیر آمده است (به زبان vb):
کد:
http://www.codeproject.com/KB/vb/SudokuGen.aspx
الگوریتم سرراستی هم داره.
و سپس از آرایه ای که تولید کرده به تعداد دلخواه تولید می کنی.

بی‌نهایت سپاس برای این پست.

 

[shahab85]

من الگوريتم حلش رو پيدا كردم
ولي الگوريتمي براي طراحي خود جدول پيدا نكردم
فكر نميكنم روش انتخاب تصادفي شدني باشه
يعني هست ولي خيلي پيچيدس
بايد راه آسونتري هم باشه

 

[joody121]

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

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

 

[shahab85]

روش توليد تصادفي اونطور كه فكر ميكنيد ساده نيست
بايد سه شرط رو در نظر بگيريم اگر بخوايم توليد جدول تصادفي كنيم
1- عددي كه داريم انتخاب ميكنيم در اون سطر وجود نداشته باشه
2- همچنين در ستون مربوطه وجود نداشته باشه
3- از همه مهمتر وسخت تر اين كه ببينيم در مربع كوچك 3 در 3 وجود نداشته باشه
حالا يه خرده رو سومي فكر كنيد...
ميبينيد كه به اين سادگيا هم نيست

 

[joody121]

سلام

روش توليد تصادفي اونطور كه فكر ميكنيد ساده نيست

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

مثل خود انسان که بین دو یا سه عدد (نه کل اعداد) در تردیده و مجبور میشه یکی رو انتخاب کنه و جلو بره.

از همه مهمتر وسخت تر اين كه ببينيم در مربع كوچك 3 در 3 وجود نداشته باشه
حالا يه خرده رو سومي فكر كنيد...

اگه به دید یک ماتریس عددی به کل قضیه نگاه کنید، خیلی ساده تر هم میشه و نباید هیچ مشکلی با این مباحث داشته باشین.

=====
الگوریتم حل:

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

2)
اگه تونست پس با توجه به اینکه حداقل یه خونه که قبلاً مقدارش مشخص نبوده، الآن مقدار داره، پس امکان داره به وسیله همین مقدار جدید، بتونیم مقادیر چند خونه دیگه رو هم به دست بیاریم.
پس تا زمانی که مقدار قطعی خونه ی جدیدی رو میشه به دست آورد باید در یه حلقه مرحله 1 رو مدام تکرار کرد.

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

این فرآیند با کمک نوعی پشته میتونه با تودرتو به راحتی پیاده سازی بشه.


به عنوان یک نمونه عملی شده با همین الگوریتم میتونید نگاهی به لینک زیر بندازید:
http://www.h02.ir/Math/Sudoko.aspx


الگوریتم طرح:

1)
تعداد خونه های پر شده رو نسبت به درجه سختی و راحتی تعیین میکنیم.

2)
در یک حلقه به تعداد خونه ها و بنابر random یک خونه x و y ماتریس (ماتریس بگیم بهتره!) رو مشخص میکنیم و عددیRandom رو که با قوانین و اعداد قبل از خودش در تناقض نباشه، در خانه مربوطه قرار میدیم
برای random از اعدادی که پشت سر هم نیستن هم مثلاً ( 1و 2 و 9) میشه از آرایه و random ایندکس آرایه استفاده کرد.

3)
جهت اطمینان از جواب داشتن، یه بار با الگوریتم حل، سودوکو رو حل میکنیم. (میتونیم میزانی که الگوریتم حل به بن بست رسیده و از بند 3 استفاده کرده رو هم چک کنیم تا زیاد دور از انتظار سختی و راحتی مطلوب کار بر نباشه.)
بحرحال اگر مقادیر مناسب بود که هیچ، وگرنه مجدداً کار را از اول انجام میدهیم.
(البته خیلی بهتر میشه اگه توجه کنیم که در random ها سعی کنیم به اعداد استفاده شده در نمونه فعلی اولویت کمتری بدیم.)
=====

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

موفق باشید

​

​

​

 

[shahab85]

سعي ميكنم بشينم كدشو بنويسيم ببينم ميشه يا نه
دست شمام درد نكنه

 

[EhsanAkrami]

چطوری میشه با BST جدول سودوکو نوشت؟