Printable View
سلام
دوستان من ميخوام جدول سودوكو رو با جاوا بنويسم يعنی در واقع يه جور بازي
موندم كه ميشه الگوريتمي نوشت كه جاوا خودش اين جدول نه در نه رو پر كنه؟
در ضمن كاربر با انتخاب مراحل سخت،متوسط و آسان خونه هاي مناسب جدول بهش نشون داده بشه و طوري اين خونه ها انتخاب بشن كه جدول قابل حل باشه
يا اينكه راهی نيست و بايد يه سری جدول های آماده از قبل به برنامه بدم؟
جدول سودوكو يه جدول 9 در 9 هست كه خودش هم به 9 تا جدول 3 در 3 تقسيم ميشه
ما بايد اعداد 1 تا 9 رو طوری توی اين جدول بچينيم كه در سطر ها و ستون های جدول بزرگ( 9در 9 ) تمامی اعداد فقط يكبار ديده بشن.همچنين اعداد 1 تا 9 در مربع های كوچك سه در سه نيز نبايد تكراریباشند.
اين جدول رو وقتي طرح كردی به طور مثال 20 تا خونه از 81 خونش رو به كاربر نشون ميدی و ميگی بقيه رو حل كن!
البته يه جوری بايد اين 20 تا عدد رو انتخاب كنی كه جدول يقينا قابل حل باشه!
اگه ميخوايد بيشتر متوجه شين فردا يه روزنامه ايران بخريد هر روز از اين جدولا داره!
خوب توضيح دادم يا كسي متوجه نشد؟لطفاً یه نظری،پیشنهدای راجع به سوالم بدین:41:
مرسی
سلام
تو این لینک الگوریتمی برای تولید جداول سودوکوی قابل حل موجود است. به این صورت که ابتدا یک جدول تعداد عناصر پر شد با تعداد خاصی می گیرد و بررسی می کند که آیا قابل حل است یا نه؟ این حلقه را تا آنجا ادامه می دهد که برسد به یک جدول قابل حل:
کد: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
و سپس از آرایه ای که تولید کرده به تعداد دلخواه تولید می کنی.
سلام
من الگوريتم حلش رو پيدا كردم،ولی الگوريتمی برای طراحی خود جدول پيدانكردم!
فكر نميكنم روش انتخاب تصادفی، شدنی باشه،يعنی هست ولی خيلی پيچيدس!
بايد راه آسونتری هم باشه،درسته؟
سلام
اگر شما یک کد قوی و ناب برای حل سودوکو داشته باشید، روش اعداد تصادفی به خوبی عمل میکند و فقط کافی است اعداد در همان اول در تناقض با هم نباشند.
تقریباً هر جدول سودوکویی که نیم از آن خالی باشد و تضاد مشهود در ان نباشد قابل حل است، در نتیجه همان اعداد تصادفی که نصف جدول را گرفته باشند، راه خوبی است.
درجه سختی و راحتی هم باز میگردد به همان کد حل سودوکو
کافیست یک بار کدتان سودوکو را حل کند....
در حل سودوکو یک جاهایی قوانین ساده ریاضی حاکم میشود و عدد خانه ای را مشخص میکند ولی گاهاً با هیچ قانونی نمیتوان عدد را فهمید و بین دو یا بیشتر باید شانسی یا به ترتیب انتخاب کرد، تعداد این گزینه های شانسی و چند انتخابی دقیقاً مشخص کنند میزان سختی و سادگی جدول است و پارامتر بعدی سختی و آسانی درصد خانه های خالی جدول است.
سلام
قبل از هر چیز لازم می دونم که تشکر ویژه داشته باشم بابت وقتی که می ذارید و جوابمو میدید:20:
راستش روش توليد تصادفي اونطورا هم ساده نيست!
بايد سه شرط رو در نظر بگيريم اگر بخوايم توليد جدول تصادفي كنيم
1- عددي كه داريم انتخاب ميكنيم در اون سطر وجود نداشته باشه
2- همچنين در ستون مربوطه وجود نداشته باشه
3- از همه مهمتر وسخت تر اين كه ببينيم در مربع كوچك 3 در 3 وجود نداشته باشه
حالا يه خرده رو سومي فكر كنيد...
ميبينيد که یه کم سخت شد!
با تشکر
سلام
در مواقعی که واقعاً الگوریتم به بن بست میرسه باید به انتخاب تن داد، و خیلی بدیهی است که انتخاب باید از بین اعداد مجاز باشد و اعدادی که همه میتوانند باشند ولی ما نمیتوانیم گزینه های دیگر را حذف کنیم.نقل قول:
راستش روش توليد تصادفي اونطورا هم ساده نيست!
یعنی این بحث شما دو جنبه دارد، حل سودوکو و طرح سودوکو.
در random و قضیه در زمان حل آنچنان هم تصادفی و شانسی نیست! ولی برای طرح سودوکو شاید بیشتر تصادفی و شانسی باشد ولی در هر دو صورت قائده و قوانین سودوکو باید رعایت شود.
مثل خود انسان که بین دو یا سه عدد (نه کل اعداد) در تردید است و مجبور میشود یکی را انتخاب کند و جلو برورد.
اگر به دید یک ماتریس عددی به کل قضیه نگاه کنید، خیلی ساده تر هم میشود و نباید هیچ مشکلی با این مباحث داشته باشید.نقل قول:
- از همه مهمتر وسخت تر اين كه ببينيم در مربع كوچك 3 در 3 وجود نداشته باشه
حالا يه خرده رو سومي فكر كنيد...
=====
الگوریتم حل:
1)
شما اول نیاز به یک کد ساده دارید که با توجه به خانه های جاری و طبق قوانین سودوکو، سعی کند جواب قطعی برای خانه های خالی به دست آورد، این کد یا میتواند از محتویات جاری جدول و طبق قوانین، مقدار خانه جدید را به دست آورد یا نمیتواند.
2)
اگر توانست پس با توجه به اینکه حداقل یک خانه که قبلاً مقدارش مشخص نبوده، الآن مقدار دارد، پس امکان دارد به وسیله همین مقدار جدید، بتوان مقادیر چند خانه دیگر را هم به دست آورد.
پس تا زمانی که مقدار قطعی خانه ی جدیدی را میتوان به دست آورد باید در یک حلقه مرحله 1 را مدام تکرار کرد.
3)
اگر در نتیجه مرحله یک دیگر به بن بست رسیدیم و مقدار قطعی هیچ خانه ای را نتوانستیم به دست آوریم.
حال باید یک تصویر از مقادیر جاری را در یک حافظه پشته مانند ذخیره کنیم و برویم سراغ اولین خانه خالی و اولین عدد مجازی که میتواند در آن قرار گیرد
آن عدد را قرار میدهیم و به مرحله 1 باز میگردیم، اگر به جواب رسیدیم که هیچ، وگرنه اگر به جایی رسیدیم که الگوریتم به بن بست رسید، باز میگردیم و از آخرین تصویر را از پشته میخوانیم و عدد بعدی را تست میکنیم.
این فرآیند با کمک نوعی پشته میتواند با تودرتودر به راحتی پیاده سازی شود.
به عنوان یک نمونه عملی شده با همین الگوریتم میتوانید نگاهی به لینک زیر بی اندازید:
h02.ir/Math/Sudoko.aspx
الگوریتم طرح:
1)
تعداد خانه های پر شده را نسبت به درجه سختی و راحتی تایین میکنیم.
2)
در یک حلقه به تعداد خانه ها و بنابر random یک خانه x و y ماتریس (ماتریس بگیم بهتره!) را مشخص میکنیم و عددیRandom را که با قوانین و اعداد قبل از خودش در تناقض نباشد، در خانه مربوطه قرار میدهیم
برای random از اعدادی که پشت سر هم نیستند هم (مثلاً 1و 2 و 9) میتوان از آرایه و random ایندکس آرایه استفاده کرد.
3)
جهت اطمینان از جواب داشتن یک بار با الگوریتم حل، سودوکو را حل میکنیم. (میتوان میزانی که الگوریتم حل به بن بست رسیده و از بند 3 استفاده کده را هم چک کنیم تا زیاد دور از انتظار سختی و راحتی مطلوب کار بر نباشد.)
بحرحال اگر مقادیر مناسب بود که هیچ، وگرنه مجدداً کار را از اول انجام میدهیم.
(البته خیلی بهتر میشود اگر توجه کنیم که در random ها سعی کنیم به اعداد استفاده شده در نمونه فعلی اولویت کمتری دهیم.)
=====
پیشنهاد میکنم، همواره سعی کنید، خود انسانیتان را جای الگوریتم بگذارید و ببینید اگر شما بودید چه میکردید؟
حتی میتوانید یکبار روی ورق کاغذ کارها را انجام دهید و بعد برگردید و چک کنید و ببینید از چه فرمول و منطقی کار را انجام دادی و ب جواب رسیدید، بعد همان قائده و روش را در الگوریتم تان به زبان برنامه نویسی پیاده سازی کنید.
با همین تک اصل ساده اکثر الگوریتم های بسیار پیچیده تر هم قابل حل است.