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

واضح آرشیو وب فارسی:سایت ریسک: bahareh65515-09-2008, 03:21 AMسلام دوستان من ميخوام جدول سودوكو رو با جاوا بنويسم يعنی در واقع يه جور بازي موندم كه ميشه الگوريتمي نوشت كه جاوا خودش اين جدول نه در نه رو پر كنه؟ در ضمن كاربر با انتخاب مراحل سخت،متوسط و آسان خونه هاي مناسب جدول بهش نشون داده بشه و طوري اين خونه ها انتخاب بشن كه جدول قابل حل باشه يا اينكه راهی نيست و بايد يه سری جدول های آماده از قبل به برنامه بدم؟ bahareh65515-09-2008, 07:42 PMجدول سودوكو يه جدول 9 در 9 هست كه خودش هم به 9 تا جدول 3 در 3 تقسيم ميشه ما بايد اعداد 1 تا 9 رو طوری توی اين جدول بچينيم كه در سطر ها و ستون های جدول بزرگ( 9در 9 ) تمامی اعداد فقط يكبار ديده بشن.همچنين اعداد 1 تا 9 در مربع های كوچك سه در سه نيز نبايد تكراریباشند. اين جدول رو وقتي طرح كردی به طور مثال 20 تا خونه از 81 خونش رو به كاربر نشون ميدی و ميگی بقيه رو حل كن! البته يه جوری بايد اين 20 تا عدد رو انتخاب كنی كه جدول يقينا قابل حل باشه! اگه ميخوايد بيشتر متوجه شين فردا يه روزنامه ايران بخريد هر روز از اين جدولا داره! خوب توضيح دادم يا كسي متوجه نشد؟لطفاً یه نظری،پیشنهدای راجع به سوالم بدین:41: مرسی hamidreza_buddy16-09-2008, 02:00 PMسلام تو این لینک الگوریتمی برای تولید جداول سودوکوی قابل حل موجود است. به این صورت که ابتدا یک جدول تعداد عناصر پر شد با تعداد خاصی می گیرد و بررسی می کند که آیا قابل حل است یا نه؟ این حلقه را تا آنجا ادامه می دهد که برسد به یک جدول قابل حل: !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! البته کدش به سی شارپه ولی کدش رو هم گذاشتن و می تونی مطالعه کنی. برا سختی و آسونیش هم می تونی تعداد خانه های عدد دار را انتخاب کنی. مثلاً واسه سخت 17 تا خونه رو نشون بدی. یه راهی هم که خودم به نظرم می رسه اینه که ابتدا یک جدول کاملاً حل شده تهیه کنیم (به صورت تصادفی) و سپس مثلاً 17 خانه از آن را انتخاب کنیم (باز تصادفی!) . تهیۀ یک جدول سودوکوی کامل در زیر آمده است (به زبان vb): !!!! برای مشاهده محتوا ، لطفا ثبت نام کنید / وارد شوید !!!! الگوریتم سرراستی هم داره. و سپس از آرایه ای که تولید کرده به تعداد دلخواه تولید می کنی. bahareh65518-09-2008, 02:14 AMسلام من الگوريتم حلش رو پيدا كردم،ولی الگوريتمی برای طراحی خود جدول پيدانكردم! فكر نميكنم روش انتخاب تصادفی، شدنی باشه،يعنی هست ولی خيلی پيچيدس! بايد راه آسونتری هم باشه،درسته؟ _H2_19-09-2008, 02:04 AMسلام اگر شما یک کد قوی و ناب برای حل سودوکو داشته باشید، روش اعداد تصادفی به خوبی عمل میکند و فقط کافی است اعداد در همان اول در تناقض با هم نباشند. تقریباً هر جدول سودوکویی که نیم از آن خالی باشد و تضاد مشهود در ان نباشد قابل حل است، در نتیجه همان اعداد تصادفی که نصف جدول را گرفته باشند، راه خوبی است. درجه سختی و راحتی هم باز میگردد به همان کد حل سودوکو کافیست یک بار کدتان سودوکو را حل کند.... در حل سودوکو یک جاهایی قوانین ساده ریاضی حاکم میشود و عدد خانه ای را مشخص میکند ولی گاهاً با هیچ قانونی نمیتوان عدد را فهمید و بین دو یا بیشتر باید شانسی یا به ترتیب انتخاب کرد، تعداد این گزینه های شانسی و چند انتخابی دقیقاً مشخص کنند میزان سختی و سادگی جدول است و پارامتر بعدی سختی و آسانی درصد خانه های خالی جدول است. bahareh65522-09-2008, 08:38 PMسلام قبل از هر چیز لازم می دونم که تشکر ویژه داشته باشم بابت وقتی که می ذارید و جوابمو میدید:20: راستش روش توليد تصادفي اونطورا هم ساده نيست! بايد سه شرط رو در نظر بگيريم اگر بخوايم توليد جدول تصادفي كنيم 1- عددي كه داريم انتخاب ميكنيم در اون سطر وجود نداشته باشه 2- همچنين در ستون مربوطه وجود نداشته باشه 3- از همه مهمتر وسخت تر اين كه ببينيم در مربع كوچك 3 در 3 وجود نداشته باشه حالا يه خرده رو سومي فكر كنيد... ميبينيد که یه کم سخت شد! با تشکر _H2_23-09-2008, 01:37 AMسلام راستش روش توليد تصادفي اونطورا هم ساده نيست! در مواقعی که واقعاً الگوریتم به بن بست میرسه باید به انتخاب تن داد، و خیلی بدیهی است که انتخاب باید از بین اعداد مجاز باشد و اعدادی که همه میتوانند باشند ولی ما نمیتوانیم گزینه های دیگر را حذف کنیم. یعنی این بحث شما دو جنبه دارد، حل سودوکو و طرح سودوکو. در 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 ها سعی کنیم به اعداد استفاده شده در نمونه فعلی اولویت کمتری دهیم.) ===== پیشنهاد میکنم، همواره سعی کنید، خود انسانیتان را جای الگوریتم بگذارید و ببینید اگر شما بودید چه میکردید؟ حتی میتوانید یکبار روی ورق کاغذ کارها را انجام دهید و بعد برگردید و چک کنید و ببینید از چه فرمول و منطقی کار را انجام دادی و ب جواب رسیدید، بعد همان قائده و روش را در الگوریتم تان به زبان برنامه نویسی پیاده سازی کنید. با همین تک اصل ساده اکثر الگوریتم های بسیار پیچیده تر هم قابل حل است. سایت ما را در گوگل محبوب کنید با کلیک روی دکمه ای که در سمت چپ این منو با عنوان +1 قرار داده شده شما به این سایت مهر تأیید میزنید و به دوستانتان در صفحه جستجوی گوگل دیدن این سایت را پیشنهاد میکنید که این امر خود باعث افزایش رتبه سایت در گوگل میشود

این صفحه را در گوگل محبوب کنید

[ارسال شده از: سایت ریسک]

[مشاهده در: www.ri3k.eu]

[تعداد بازديد از اين مطلب: 2490]