الگوریتم حل سودوکو درباره روش های حل مسئله - دوره کامل سودوکو

در مقالات قبلی با استفاده از مثال هایی از پازل سودوکو رویکردهای مختلفی را برای حل مسائل در نظر گرفته ایم. زمان آن فرا رسیده است که به نوبه خود تلاش کنیم تا امکانات رویکردهای در نظر گرفته شده را به اندازه کافی نشان دهیم. مثال پیچیدهراه حل مشکل بنابراین، امروز ما "باور نکردنی" ترین نوع سودوکو را شروع خواهیم کرد. اگر لطفاً به اصطلاحات و اطلاعات اولیه در آن نگاه کنید، در غیر این صورت درک محتوای این مقاله برای شما دشوار خواهد بود.

در اینجا چیزی است که من در مورد این گزینه فوق پیچیده در اینترنت پیدا کردم:

آرتو اینکالا، استاد دانشگاه هلسینکی (2011) ادعا می کند که دشوارترین جدول کلمات متقاطع سودوکو جهان را ساخته است. او سخت ترین پازل را به مدت سه ماه خلق کرد.

به گفته او، جدول کلمات متقاطع که او ساخته است را نمی توان تنها با منطق حل کرد. آرتو اینکالا ادعا می کند که حتی باتجربه ترین بازیکنان هم حداقل چند روز را صرف این راه حل خواهند کرد. اختراع پروفسور AI Escargot نام داشت (AI - حروف اول دانشمند، Escargot - از انگلیسی "حلزون").

برای حل این کار دشوار، به گفته آرتو اینکالا، بر خلاف پازل های معمولی که باید یک یا دو سکانس را به خاطر بسپارید، باید همزمان هشت سکانس را در ذهن خود نگه دارید.

خب، «توالی‌های نیروی بی رحم» - هنوز هم شبیه نسخه‌ای ماشینی از حل مسائل است، و کسانی که مشکل آرتو اینکال را با مغز خود حل کرده‌اند به روش‌های مختلفی در مورد آن صحبت می‌کنند. یکی چند ماه حلش کرد، یکی اعلام کرد که فقط 15 دقیقه طول کشید. خوب، یک قهرمان شطرنج جهان احتمالاً می تواند در چنین زمانی این کار را انجام دهد، و یک روانشناس، اگر در هواپیمای ما وجود داشته باشد، احتمالاً حتی سریعتر. و کسی که به طور تصادفی چند عدد خوب را برای اولین بار انتخاب کرد تا سلول های خالی را پر کند، می تواند به سرعت مشکل را حل کند. فرض کنید یکی از هزاران حل کننده مشکل می تواند در این راه خوش شانس باشد.

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

اجازه دهید یادآوری کنم کاربرگ حاوی ترکیب‌های معتبر قبلی از اعداد در سلول‌های خالی اولیه است.

پس از پردازش معمولی تقریباً معمول جداول، وضعیت کمی ساده تر شد:

من شروع به مطالعه این وضعیت کردم. خوب، از آنجایی که من قبلاً فراموش کرده ام که چگونه این مشکل را چند روز قبل حل کردم، شروع به درک آن به روشی جدید کردم. ابتدا به دو عدد 67 در سلول های بلوک چهارم توجه کردم و آنها را با مکانیسم چرخش (حرکت) سلول ها ترکیب کردم که در مقاله قبلی در مورد آن صحبت کردم. پس از بررسی تمام گزینه های چرخش سه ستون اول جدول به این نتیجه رسیدم که اعداد 6 و 7 نمی توانند در یک ستون باشند و نمی توانند به صورت ناهمزمان بچرخند، فقط می توانند در حین چرخش یکی پس از دیگری دنبال شوند. همچنین، اگر دقت کنید، به نظر می رسد که هفت و چهار در هر سه ستون به طور همزمان حرکت می کنند. بنابراین، من یک فرض قابل قبول می کنم که سلول پایین سمت چپ بلوک 4 باید شامل عدد 7 و سلول بالا سمت راست، 6 باشد.

اما در حال حاضر، من این نتیجه را فقط به عنوان یک راهنمای ممکن در آزمایش گزینه های دیگر می پذیرم. و من توجه اصلی را به عدد 59 در سلول بلوک 4 می کنم. این می تواند عدد 5 یا 9 باشد. Nine قول می دهد تعداد زیادی اعداد اضافی را از بین ببرد، i.e. برای ساده کردن مسیر بیشتر برای حل مشکل، و من با این گزینه شروع می کنم. اما به سرعت به یک "بن بست" می رسم، یعنی. سپس شما باید دوباره انتخاب کنید و چگونه بدانید انتخاب من تا چه زمانی بررسی می شود. حدس می زنم اگر نه واقعاً یک بار بود انتخاب درست، پس اینکالا به سختی می توانست چنین گزینه واضحی را در معرض دید خود بگذارد ، اگرچه مکانیسم برنامه او می توانست چنین وقفه ای را مجاز کند. به طور کلی، به هر شکلی، تصمیم گرفتم ابتدا گزینه با عدد 5 را در سلول با عدد 59 به طور کامل بررسی کنم.

اما بعداً که مشکل را حل کردم، به اصطلاح برای اینکه وجدانم را پاک کنم، با این وجود به گزینه ای با شماره 9 برگشتم تا تعیین کنم چقدر طول می کشد تا آن را بررسی کنم. خیلی طول نکشید که بررسی شد. وقتی عدد 6 را در سلول سمت راست بالای بلوک 4 داشتم، همانطور که قرار بود طبق نقطه عطف انتخاب شده قبلی باشد، عدد 19 در سلول وسط سمت راست ظاهر شد (6 از 169 حذف شد). من عدد 9 را در این سلول برای آزمایش بیشتر انتخاب کردم و به سرعت به یک نتیجه متناقض رسیدم، یعنی. انتخاب نه درست نیست. سپس شماره 1 را انتخاب می کنم و دوباره بررسی می کنم که چه چیزی از آن می آید.

یه وقتایی به این موقعیت میرسم:

جایی که دوباره باید انتخاب کنید - عدد 2 یا 8 در سلول میانی بالایی بلوک 4. من هر دو گزینه (2 و 8) را بررسی می کنم و در هر دو مورد نتیجه ناسازگار (عدم برآورده شدن شرط سودوکو) را دارم. . بنابراین من می توانم از همان ابتدا گزینه ای را با شماره 9 در خانه پایین وسط بلوک 4 بررسی کنم و زمان زیادی نمی برد. اما من همچنان همانطور که قبلاً گفتم روی عدد 5 در سلول ذکر شده توقف کردم. این من را به نتیجه زیر رساند:

مکان اعداد 4 و 7 در سه ستون (ستون) اول نشان دهنده چرخش همزمان آنها است که در واقع هنگام انتخاب عدد 7 برای سلول پایین سمت چپ بلوک 4 فرض شده است. در همان زمان، دو یا نه، چه هر یک از آنها رقم مورد نیاز در سلول وسط سمت چپ این بلوک باشد، باید به ترتیب به صورت ناهمزمان به جفت 4 و 7 حرکت کنند. در این مورد، من به عدد 2 ترجیح دادم. از آنجایی که "نوید" حذف بسیاری از ارقام اضافی از تعداد سلول ها و بر این اساس، اعتبار سنجی سریع را داده است. این گزینه. و نه به سرعت به بن بست منجر شد - به انتخاب اعداد جدید نیاز داشت. بنابراین، در سلول وسط سمت چپ بلوک با شماره 29، من ترجیحاً اعداد - 2 را نشان دادم، نه نظر من. نتیجه به شرح زیر بود:

سپس مجبور شدم یک بار دیگر یک انتخاب نیمه خودسرانه انجام دهم، به اصطلاح: یک دوشی در سلول با شماره 26 در بلوک نهم انتخاب کردم. برای انجام این کار، کافی است توجه کنید که 5 و 2 در سه ردیف پایین به طور همزمان می چرخند، زیرا 5 به طور همزمان با 1 یا 6 نمی چرخد. درست است، 2 و 1 نیز می توانند همزمان بچرخند، اما به دلایلی - قطعاً نه به یاد داشته باشید - من 2 را به جای عدد 26 انتخاب کردم، شاید به این دلیل که این گزینه، به نظر من، به سرعت آزمایش شد. با این حال، از قبل گزینه های کمی باقی مانده بود، و امکان بررسی سریع هر یک از آنها وجود داشت. همچنین می‌توان فرض کرد که به‌جای متغیر با دس، اعداد 7 و 8 به طور همزمان در سه ستون آخر (ستون) می‌چرخند، و از این نتیجه می‌توان نتیجه گرفت که فقط عدد 8 می‌تواند در خانه سمت چپ بالای بلوک نهم باشد. ، که منجر به حل سریع مشکل نیز می شود.

باید گفت که مشکل آرتو اینکال یک راه حل کاملا منطقی را در حد امکانات اجازه نمی دهد. آدم عادی- اینگونه تصور می شود - اما همچنان به شما امکان می دهد تا به برخی از گزینه های امیدوارکننده برای شمارش جایگزینی های احتمالی اعداد توجه کنید و این شمارش را به میزان قابل توجهی کاهش دهید. سعی کنید شمارش را از موقعیت‌هایی غیر از این مقاله شروع کنید، خواهید دید که تقریباً همه گزینه‌ها خیلی سریع به بن‌بست می‌رسند و باید در مورد انتخاب بعدی جایگزین‌های مناسب اعداد، مفروضات جدیدتری داشته باشید. حدود دو ماه پیش، من قبلاً سعی کردم این مشکل را بدون داشتن آمادگی هایی که در مقالات قبلی توضیح دادم، حل کنم. من ده گزینه را برای راه حل او بررسی کردم و تلاش های بیشتری را ترک کردم. آخرین بار که از قبل آمادگی بیشتری داشتم، این مشکل را برای نیم روز یا کمی بیشتر حل کردم، اما در عین حال با توجه به انتخاب، از نظر من، شاخص ترین گزینه برای خوانندگان و همچنین با بررسی اولیه متن مقاله آینده و نتیجه نهایی به شرح زیر است:

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

در مورد بقیه، برای شما آرزوی موفقیت در حل همه مشکلات دارم.

VKontakte فیس بوک Odnoklassniki

برای کسانی که دوست دارند پازل های سودوکو را خود به خود و به آرامی حل کنند، فرمولی که به شما امکان می دهد سریع پاسخ ها را محاسبه کنید، ممکن است اعتراف به ضعف یا تقلب به نظر برسد.

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

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

محققان شبکه پیچیده زولتان توروژکای و ماریا ارکسی راواز از دانشگاه نوتردام نیز توانستند توضیح دهند که چرا برخی از پازل های سودوکو از بقیه دشوارتر هستند. تنها نقطه ضعف این است که شما نیاز به یک دکترا در ریاضیات دارید تا بفهمید آنها چه چیزی ارائه می دهند.

آیا می توانید این معما را حل کنید؟ این سودوکو که توسط ریاضیدان آرتو اینکالا ساخته شده است، ادعا می شود که سخت ترین سودوکو در جهان است. عکس از سایت nature.com

Torozhkay و Erksi-Rawaz شروع به تجزیه و تحلیل سودوکو به عنوان بخشی از تحقیقات خود در مورد نظریه بهینه سازی و پیچیدگی محاسباتی کردند. آنها می گویند که بیشتر علاقه مندان به سودوکو از روش brute-force مبتنی بر تکنیک حدس زدن برای حل این مشکلات استفاده می کنند. بنابراین، عاشقان سودوکو خود را با یک مداد مسلح می کنند و تمام ترکیب های ممکن از اعداد را امتحان می کنند تا پاسخ صحیح پیدا شود. این روش به طور اجتناب ناپذیری منجر به موفقیت می شود، اما پر زحمت و زمان بر است.

در عوض، Torozhkai و Erksi-Ravaz یک الگوریتم آنالوگ جهانی را پیشنهاد کردند که کاملاً قطعی است (از حدس زدن یا شمارش استفاده نمی‌کند) و همیشه راه‌حل صحیح برای مسئله را پیدا می‌کند و خیلی سریع.

محققان برای تکمیل این سودوکو از «حل کننده آنالوگ قطعی» استفاده کردند. عکس از سایت nature.com

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

آنها مقیاسی از 1 تا 4 ایجاد کردند که در آن 1 "آسان"، 2 "متوسط"، 3 "سخت"، 4 "بسیار دشوار" است. حل یک پازل با رتبه 2 به طور متوسط ​​10 برابر بیشتر از معمایی با رتبه 1 طول می کشد. طبق این سیستم، بیشترین معمای دشواراز کسانی که تاکنون شناخته شده اند دارای امتیاز 3.6 هستند. پازل های سودوکو پیچیده تر هنوز شناخته نشده اند.

این تئوری با نگاشت احتمال برای هر مربع شروع می شود. عکس از سایت nature.com

Torozhkay می‌گوید: «تا زمانی که کار بر روی یک کلاس رضایت‌مندی عمومی‌تر از مسائل بولی را شروع کردیم، به سودوکو علاقه‌ای نداشتم. - از آنجایی که سودوکو بخشی از این کلاس است، مربع لاتین درجه 9 میدان خوبی برای آزمایش ما بود، بنابراین با آنها آشنا شدم. من و بسیاری از محققانی که چنین مسائلی را مطالعه می‌کنیم، مجذوب این سوال هستیم که ما انسان‌ها تا کجا می‌توانیم در حل سودوکو، به طور قطعی، بدون شکستن، پیش برویم، که انتخابی تصادفی است، و اگر حدس درست نیست، باید به عقب برگردید. مرحله یا چند مرحله و از نو شروع کنید. مدل تصمیم گیری آنالوگ ما قطعی است: هیچ انتخاب تصادفی یا تکراری در دینامیک وجود ندارد.

نظریه آشوب: درجه پیچیدگی پازل ها در اینجا به صورت پویایی آشفته نشان داده شده است. عکس از سایت nature.com

Torozhkai و Erksi-Ravaz بر این باورند که الگوریتم آنالوگ آنها پتانسیل استفاده برای طیف گسترده ای از مسائل در صنعت، علوم کامپیوتر و زیست شناسی محاسباتی را دارد.

تجربه تحقیقاتی نیز توروژکای را به یک طرفدار بزرگ سودوکو تبدیل کرد.

او می‌گوید: «من و همسرم چندین برنامه سودوکو در آیفون‌هایمان داریم و باید هزاران بار قبلاً بازی کرده‌ایم و در زمان کمتری در هر سطح به رقابت پرداخته‌ایم. - او اغلب به طور شهودی ترکیبی از الگوها را می بیند که من متوجه آنها نمی شوم. من باید آنها را بیرون بیاورم. حل بسیاری از معماهایی که مقیاس ما آنها را سخت یا بسیار دشوار می‌داند بدون نوشتن احتمالات با مداد برای من غیرممکن می‌شود.

روش توروژکای و ارکسی-رواز ابتدا در Nature Physics و بعداً در Nature Scientific Reports منتشر شد.

سودوکو است پازل جالببرای آموزش منطق، بر خلاف کلمات اسکار، که در آن دانش و حافظه مورد نیاز است. سودوکو کشورهای مبدا زیادی دارد، به هر شکلی که در آن بازی می شد چین باستان، در ژاپن، آمریکای شمالی... برای اینکه من و شما بازی را یاد بگیریم، انتخاب کردیم چگونه سودوکو را از آسان به سخت حل کنیم.

برای شروع، بیایید بگوییم که سودوکو یک مربع 9x9 است که به نوبه خود از 9 مربع 3x3 تشکیل شده است. هر مربع باید با اعداد از یک تا نه پر شود تا هر عدد فقط یک بار به صورت عمودی و خط افقی، و فقط در یک مربع 3x3.

وقتی تمام خانه ها را پر می کنید، باید همه اعداد از 1 تا 9 را در هر 9 مربع به دست آورید، بنابراین، در امتداد خط افقی، همه اعداد از 1 تا 9. و همین مورد در طول خط عمودی، رجوع کنید به تصویر:

به نظر می رسد که، قوانین ساده، اما برای پاسخ به این سوال که چگونه سودوکو را حل کنیم، و حتی بیشتر از آن، اگر می خواهید بدانید که چگونه سودوکو پیچیده را حل کنید (مخصوصا برای کسانی که تازه سفر خود را شروع کرده اند)، باید حداقل چند مورد را حل کنید. کارهای آسان آن وقت مشخص می شود که موضوع از چه قرار است. در زیر بازی ها آمده است. سعی کنید آنها را چاپ کنید و آنها را پر کنید تا همه چیز با هم هماهنگ شود:

چگونه سودوکو دشوار را حل کنیم

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

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

چگونه سودوکو دشوار را حل کنیم؟

چگونه سودوکو را حل کنیم: راه ها؟

چگونه سودوکو را حل کنیم: راه ها و روش های سلول ها و زمینه ها؟

بنابراین، دو بازی به شما داده شد که با حل آنها مهارت کسب کردید و یک ایده کلی به دست آوردید. به منظور صرفه جویی در وقت شما، من به شما چند هک زندگی برای حل سریع سودوکو می گویم.

1. همیشه با عدد 1 شروع کنید و ابتدا در امتداد خطوط و سپس در امتداد مربع ها بروید. بنابراین مطمئناً گیج نخواهید شد و خود را در مورد بسیاری از اشتباهات هشدار می دهید.

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

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

4. از هیچ چیز نترسید، بهتر است اشتباه کنید و دلیل آن را بفهمید تا هیچ کاری نکنید!

5. بیشتر تمرین کنید و استاد خواهید شد.

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

در زیر مجموعه ای از "نحوه حل سودوکو پیچیده" را خواهید دید که پس از آن می توانید کارهای زیادی انجام دهید!

- این یک شکل محبوب اوقات فراغت است که یک پازل با اعداد است که به آن مربع جادویی نیز می گویند. راه حل آن امکان توسعه را می دهد تفکر منطقیتوجه، رویکرد تحلیلی. مزایای سودوکو تنها در فواید مغز نیست، بلکه در توانایی منحرف کردن حواس از مشکلات، تمرکز کامل روی کار است.

قوانین سودوکو

این پازل برخلاف کلمات اسکار، جدول کلمات متقاطع و غیره فضای کمی را اشغال می کند. زمین بازی، متشکل از 81 مربع، سلول ها به بلوک های کوچک به اندازه 3 * 3 تقسیم می شوند. به راحتی روی یک تکه کاغذ جا می شود. این کار مانند سلول های انتخابی پر شده به نظر می رسد که باید با مقادیر تکمیل شود و کل جدول را پر کند. در سودوکو قوانین بازی بسیار ساده است و به شما اجازه حذف می دهد راه حل های متعدد. هر سطر یا ستون شامل اعداد از 1 تا 9 است. همچنین، مقادیر در یک بلوک کوچک تکرار نمی شوند.

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

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

قوانین حل سودوکو

بدست آوردن تصمیم درست، باید چند قانون ساده را در نظر بگیرید:

• یک عدد را فقط در صورتی می توان در یک سلول نوشت که در خطوط افقی و عمودی و همچنین در مربع کوچک 3*3 نباشد.
• اگر بتوان آن را منحصراً در یک سلول نوشت.

اگر هر دو نکته در نظر گرفته شود، می توانید مطمئن شوید که سلول به درستی پر شده است.

چگونه سودوکو ساده را حل کنیم؟

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

به عنوان مثال، اعداد 3، 4، 5 در عمود مرکزی وجود ندارد. همچنین می توان سلول مرکزی خالی را حذف کرد، زیرا ما 4 را در خط افقی می بینیم. از این نتیجه می گیریم که در مربع بالایی قرار دارد. به همین ترتیب، می توانیم 3 و 5 را کنار بگذاریم و نتیجه زیر را بگیریم.

با کشیدن خطوط در مربع کوچک وسط بالایی 3 * 3، می توانید سلول هایی را که عدد 3 در آنها قرار ندارد حذف کنید.

حل در ادامه به این ترتیب، لازم است سلول های باقی مانده را پر کنید. نتیجه تنها راه حل صحیح است.

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

چگونه سودوکو دشوار را حل کنیم؟

بسیاری از مردم تعجب می کنند که چگونه سودوکو را حل کنند، اگر روش ها و استراتژی استاندارد وجود داشته باشد. همانطور که در هر پازل منطقوجود دارد. ما ساده ترین آنها را در نظر گرفته ایم. برای رفتن به ادامه مطلب سطح بالا، باید زمان، پشتکار، صبر بیشتری داشته باشید. برای حل معما، باید فرضیاتی داشته باشید و احتمالاً نتیجه اشتباهی بگیرید و به مکان انتخابی بازگردید. در اصل، سودوکو دشوار است - مانند حل یک مسئله با استفاده از یک الگوریتم. بیایید چندین تکنیک محبوب مورد استفاده توسط "Sudokuveds" حرفه ای را در مثال زیر در نظر بگیریم.

اول از همه، شما باید سلول های خالی را پر کنید گزینه های ممکنتصمیم گیری را تا حد امکان آسان کنید و تصویر کامل را در مقابل چشمان خود داشته باشید.

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

به همین ترتیب، سلول های باقی مانده را بررسی می کنیم و واحدها را در سلول های دایره ای قرار می دهیم، زیرا آنها نیز تنها در خطوط آنها هستند.

برای اینکه بفهمید چگونه سودوکوس های پیچیده را حل کنید، باید خود را با چند روش ساده مسلح کنید.

روش "جفت باز"

برای پاک کردن بیشتر میدان، باید جفت های باز را پیدا کنید که به شما امکان می دهد اعداد موجود در آنها را از سلول های دیگر در بلوک و ردیف ها حذف کنید. در مثال، این جفت ها 4 و 9 از ردیف سوم هستند. آنها به وضوح نشان می دهند که چگونه سودوکو پیچیده را حل کنیم. ترکیب آنها نشان می دهد که تنها 4 یا 9 می تواند در این سلول ها وارد شود.این نتیجه گیری بر اساس قوانین سودوکو انجام شده است.

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

روش پنهان جفت / سه / چهار

این روش برخلاف ترکیبات باز است. ماهیت آن در این واقعیت نهفته است که باید سلول هایی را پیدا کرد که در آنها اعداد در یک مربع / خط تکرار می شوند که در سلول های دیگر یافت نمی شوند. چگونه این به حل سودوکو کمک می کند؟ این تکنیک به شما امکان می دهد بقیه اعداد را خط بکشید، زیرا آنها به عنوان پس زمینه عمل می کنند و نمی توانند در سلول های انتخاب شده وارد شوند. این استراتژی چندین نام دیگر دارد، به عنوان مثال، "سلول لاستیک نیست"، "راز روشن می شود." نام ها ماهیت روش و انطباق با قانون را توضیح می دهند که از امکان قرار دادن یک رقم تک صحبت می کند.

یک مثال سلول های آبی رنگ است. اعداد 4 و 7 منحصراً در این سلول ها یافت می شوند، بنابراین بقیه را می توان با خیال راحت حذف کرد.

هنگامی که می توان مقادیری را که چندین بار در یک مجاور یا مزدوج رخ می دهند از سلول های یک بلوک / ردیف / ستون حذف کرد، سیستم کونژوگه به ​​روشی مشابه کار می کند.

طرد متقابل

اصل نحوه حل سودوکو توانایی تجزیه و تحلیل و مقایسه است. راه دیگر برای حذف گزینه‌ها این است که یک عدد در دو ستون یا خط متقاطع داشته باشید. در مثال ما، این وضعیت رخ نداده است، بنابراین بیایید وضعیت دیگری را در نظر بگیریم. تصویر نشان می دهد که "دو" یک بار در بلوک میانی دوم و سوم رخ می دهد که با ترکیبی از آنها به هم متصل می شوند و متقابلاً یکدیگر را حذف می کنند. بر اساس این داده ها، شماره 2 را می توان از سلول های دیگر در ستون های مشخص شده حذف کرد.

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

روش کاهش

در نتیجه هر عمل، تعداد گزینه های موجود در سلول ها کاهش می یابد و راه حل به روش "Singleman" کاهش می یابد. این فرآیند را می توان کاهش نامید و یک روش جداگانه است، زیرا شامل تجزیه و تحلیل کامل تمام سطرها، ستون ها و مربع های کوچک با محرومیت متوالیگزینه ها. در نتیجه به یک راه حل واحد می رسیم.

روش رنگ

این استراتژی با استراتژی توضیح داده شده کمی متفاوت است و شامل نشان دادن رنگ سلول ها یا اعداد است. این روش به تجسم کل دوره راه حل کمک می کند، با این حال، برای همه مناسب نیست. برخی از رنگ ها از بین می روند و تمرکز را دشوار می کنند. برای استفاده صحیح از وسعت، باید دو یا سه رنگ را انتخاب کنید و همان گزینه ها را در بلوک ها / خطوط مختلف و همچنین سلول های بحث برانگیز رنگ کنید.

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

هدف سودوکو این است که تمام اعداد را طوری مرتب کند که در مربع ها، ردیف ها و ستون های 3×3 اعداد یکسانی وجود نداشته باشد. در اینجا یک مثال از سودوکو که قبلاً حل شده است:

می توانید بررسی کنید که در هر یک از 9 مربع و همچنین در تمام سطرها و ستون ها اعداد تکراری وجود نداشته باشد. هنگام حل سودوکو، باید از این قانون "یکتا بودن" اعداد استفاده کنید و با حذف متوالی نامزدها (اعداد کوچک در یک سلول نشان می دهد که کدام اعداد، به نظر بازیکن، می توانند در این سلول قرار گیرند)، مکان هایی را پیدا کنید که فقط یک عدد می تواند ایستاده باشد.

وقتی سودوکو را باز می کنیم، می بینیم که هر سلول حاوی تمام اعداد خاکستری کوچک است. می توانید بلافاصله علامت اعداد تنظیم شده را بردارید (علامت ها با کلیک راست روی یک عدد کوچک حذف می شوند):

من با شماره ای که در این جدول کلمات متقاطع در یک نسخه وجود دارد شروع می کنم - 6 تا نشان دادن حذف نامزدها راحت تر باشد.

اعداد در مربع با عدد حذف می شوند، در سطر و ستون، نامزدهای حذف شده با رنگ قرمز مشخص می شوند - ما روی آنها کلیک راست می کنیم، توجه داشته باشیم که در این مکان ها نمی توانند شش عدد باشند (در غیر این صورت دو عدد شش وجود خواهد داشت. در مربع / ستون / ردیف، که خلاف قوانین است).

حال اگر به واحدها برگردیم، الگوی استثناها به صورت زیر خواهد بود:

ما نامزدهای 1 را در هر خانه آزاد مربعی که قبلاً 1 وجود دارد، در هر ردیف که در آن 1 وجود دارد و در هر ستون که یک عدد 1 وجود دارد، حذف می کنیم. در مجموع، برای سه واحد، 3 مربع، 3 ستون وجود خواهد داشت. و 3 ردیف

بعد، بیایید مستقیم به 4 برویم، اعداد بیشتری وجود دارد، اما اصل یکسان است. و اگر دقت کنید، می بینید که در مربع 3x3 بالا سمت چپ فقط یک سلول آزاد وجود دارد (که با رنگ سبز مشخص شده است) که 4 می تواند ایستاده باشد. بنابراین، عدد 4 را در آنجا قرار دهید و همه نامزدها را پاک کنید (دیگر نمی توان وجود داشت). اعداد دیگر باشد). در سودوکو ساده، تعداد زیادی فیلد را می توان به این روش پر کرد.

پس از تنظیم یک عدد جدید، می توانید شماره های قبلی را دوبار بررسی کنید، زیرا با افزودن یک عدد جدید دایره جستجو را باریک می کند، به عنوان مثال، در این جدول کلمات متقاطع، به لطف مجموعه چهار، تنها یک خانه در این مربع باقی مانده است ( سبز):

از سه سلول موجود، تنها یک سلول توسط واحد اشغال نشده است و ما واحد را در آنجا قرار می دهیم.

بنابراین، ما همه نامزدهای واضح برای همه اعداد (از 1 تا 9) را حذف می کنیم و در صورت امکان اعداد را می گذاریم:

پس از حذف همه نامزدهای بدیهی نامناسب، سلولی به دست آمد که در آن فقط 1 کاندید (سبز) باقی مانده بود، به این معنی که این تعداد سه است و ارزشش را دارد.

اگر نامزد آخرین نفر در مربع، سطر یا ستون باشد، اعداد نیز درج می شوند:

اینها نمونه هایی از پنج ها هستند، می توانید ببینید که هیچ پنجی در سلول های نارنجی وجود ندارد و تنها نامزد منطقه در سلول های سبز باقی می ماند، به این معنی که پنج ها آنجا هستند.

این‌ها ابتدایی‌ترین راه‌های قرار دادن اعداد در سودوکو هستند، می‌توانید با حل سودوکو روی مشکل ساده (یک ستاره) آنها را امتحان کنید، به عنوان مثال: سودوکو شماره 12433، سودوکو شماره 14048، سودوکو شماره 526. سودوکوس های نشان داده شده به طور کامل با استفاده از اطلاعات بالا حل می شوند. اما اگر نمی توانید شماره بعدی را پیدا کنید، می توانید به روش انتخاب متوسل شوید - سودوکو را ذخیره کنید، و سعی کنید تعدادی را به صورت تصادفی قرار دهید، و در صورت شکست، سودوکو را بارگیری کنید.

اگر می خواهید روش های پیچیده تری را یاد بگیرید، ادامه مطلب را بخوانید.

کاندیداهای قفل شده

نامزد قفل شده در یک میدان

وضعیت زیر را در نظر بگیرید:

در مربع مشخص شده با رنگ آبی، نامزدهای شماره 4 (سلول های سبز) در دو خانه در یک خط قرار دارند. اگر عدد 4 روی این خط باشد (سلول های نارنجی)، پس جایی برای قرار دادن 4 در مربع آبی وجود نخواهد داشت، به این معنی که ما 4 را از تمام سلول های نارنجی حذف می کنیم.

مثال مشابه برای عدد 2:

نامزد قفل شده در یک ردیف

این مثال مشابه نمونه قبلی است، اما در اینجا در ردیف (آبی) نامزدهای 7 در یک مربع هستند. این بدان معنی است که هفت ها از تمام سلول های باقی مانده مربع (نارنجی) حذف می شوند.

نامزد قفل شده در یک ستون

مشابه مثال قبلی، فقط در ستون 8 نامزدها در همان مربع قرار دارند. تمام نامزدهای 8 از سلول های دیگر مربع نیز حذف می شوند.

با تسلط بر کاندیداهای قفل شده، می توانید سودوکو با سختی متوسط ​​را بدون انتخاب حل کنید، به عنوان مثال: سودوکو شماره 11466، سودوکو شماره 13121، سودوکو شماره 11528.

گروه های اعداد

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

زوج های برهنه

ساده ترین زیرگونه گروه ها دو جفت اعداد یکسان در یک مربع، ردیف یا ستون هستند. به عنوان مثال، یک جفت اعداد خالی در یک رشته:

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

مثالی دیگر:

یک زوج برهنه در همان زمان در یک ستون و در یک مربع هستند. نامزدهای اضافی (قرمز) هم از ستون و هم از مربع حذف می شوند.

یک نکته مهم - گروه باید دقیقاً "برهنه" باشد، یعنی نباید شامل اعداد دیگری در این سلول ها باشد. یعنی، و یک گروه برهنه هستند، اما و نیستند، چون این گروه دیگر برهنه نیست، یک عدد اضافی وجود دارد - 6. آنها همچنین یک گروه برهنه نیستند، زیرا اعداد باید یکسان باشند، اما اینجا 3 اعداد مختلفدر یک گروه.

سه قلوهای برهنه

سه گانه های برهنه شبیه به جفت های برهنه هستند، اما تشخیص آنها دشوارتر است - اینها 3 عدد برهنه در سه سلول هستند.

در مثال، اعداد در یک خط 3 بار تکرار شده اند. در گروه فقط 3 عدد وجود دارد و روی 3 سلول قرار دارند، به این معنی که اعداد اضافی 1، 2، 6 از سلول های نارنجی حذف می شوند.

یک سه گانه برهنه ممکن است شامل یک عدد نباشد با قدرت کاملبه عنوان مثال، ترکیب مناسب خواهد بود:، و - اینها همه همان 3 نوع اعداد در سه خانه هستند، فقط در یک ترکیب ناقص.

چهار نفر برهنه

پسوند بعدی گروه های برهنه چهارتایی برهنه است.

اعداد , , , چهار ضلعی خالی از چهار عدد 2 ، 5 ، 6 و 7 را تشکیل می دهند که در چهار خانه قرار دارند. این چهار در یک مربع قرار دارد، به این معنی که تمام اعداد 2، 5، 6، 7 از سلول های باقی مانده مربع (نارنجی) حذف می شوند.

زوج های پنهان

تنوع بعدی گروه ها گروه های پنهان هستند. به یک مثال توجه کنید:

در بالاترین خط، اعداد 6 و 9 فقط در دو خانه قرار دارند، در خانه های دیگر این خط چنین اعدادی وجود ندارد. و اگر عدد دیگری را در یکی از سلول های سبز (مثلاً 1) قرار دهید، دیگر جایی در خط برای یکی از اعداد باقی نمی ماند: 6 یا 9، بنابراین باید تمام اعداد سبز را حذف کنید. سلول ها، به جز 6 و 9.

در نتیجه، پس از حذف اضافی، فقط یک جفت اعداد خالی باید باقی بماند.

سه قلوهای پنهان

مشابه جفت های مخفی - 3 عدد در 3 خانه یک مربع، ردیف یا ستون و فقط در این سه خانه قرار دارند. ممکن است اعداد دیگری در همان سلول ها وجود داشته باشد - آنها حذف می شوند

در مثال، اعداد 4، 8 و 9 پنهان هستند، این اعداد در سلول های دیگر ستون وجود ندارد، به این معنی که ما نامزدهای غیر ضروری را از سلول های سبز حذف می کنیم.

چهار تایی پنهان

به طور مشابه با سه گانه پنهان، فقط 4 عدد در 4 سلول.

در مثال، چهار عدد 2، 3، 8، 9 در چهار خانه (سبز) یک ستون، چهار عدد پنهان را تشکیل می دهند، زیرا این اعداد در سلول های دیگر ستون (نارنجی) نیستند. نامزدهای اضافی از سلول های سبز حذف می شوند.

این در نظر گرفتن گروه هایی از اعداد را به پایان می رساند. برای تمرین سعی کنید جدول کلمات متقاطع زیر را (بدون انتخاب) حل کنید: سودوکو شماره 13091، سودوکو شماره 10710

بال ایکس و شمشیر ماهی

این کلمات عجیب نام دو روش مشابه برای حذف نامزدهای سودوکو است.

بال ایکس

X-wing برای نامزدهای یک عدد در نظر گرفته می شود، 3 را در نظر بگیرید:

فقط 2 سه تایی در دو ردیف (آبی) وجود دارد و این سه تایی فقط روی دو خط قرار می گیرند. این ترکیب فقط 2 راه حل سه گانه دارد و سه گانه های دیگر در ستون های نارنجی با این راه حل در تضاد هستند (چرا را بررسی کنید)، بنابراین کاندیدهای سه گانه قرمز باید حذف شوند.

به طور مشابه برای نامزدهای 2 و ستون.

در واقع، X-wing بسیار رایج است، اما اغلب اوقات مواجهه با این وضعیت نوید حذف اعداد اضافی را می دهد.

این یک نسخه پیشرفته از X-wing برای سه ردیف یا ستون است:

ما همچنین 1 عدد را در نظر می گیریم، در مثال آن 3 است. 3 ستون (آبی) شامل سه تایی هستند که به همان سه ردیف تعلق دارند.

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

تجزیه و تحلیل اضافی

رابطه بین گروه های پنهان و برهنه.

و همچنین پاسخ به این سوال: چرا دنبال پنج و شش و غیره پنهان / برهنه نمی گردند؟

بیایید به 2 مثال زیر نگاه کنیم:

این یک سودوکو است که در آن یک ستون عددی در نظر گرفته می شود. 2 عدد 4 (با رنگ قرمز مشخص شده است) از 2 حذف شده است روش های مختلف- با کمک یک جفت پنهان یا با کمک یک جفت برهنه.

مثال بعدی:

سودوکو دیگری، جایی که در همان مربع هم یک جفت خالی و هم یک سه پنهان وجود دارد که اعداد یکسان را حذف می کنند.

اگر به نمونه‌های گروه‌های لخت و مخفی در پاراگراف‌های قبل نگاه کنید، متوجه می‌شوید که با 4 سلول آزاد با یک گروه خالی، 2 سلول باقی‌مانده الزاماً یک جفت خالی خواهند بود. با 8 سلول آزاد و چهار سلول برهنه، 4 سلول باقیمانده یک چهار سلول پنهان خواهند بود:

اگر رابطه بین گروه‌های برهنه و پنهان را در نظر بگیریم، می‌توانیم دریابیم که اگر در سلول‌های باقی‌مانده یک گروه برهنه وجود داشته باشد، لزوماً یک گروه پنهان وجود خواهد داشت و بالعکس.

و از اینجا می توان نتیجه گرفت که اگر 9 سلول آزاد در یک ردیف داشته باشیم و در بین آنها قطعاً شش سلول برهنه وجود داشته باشد، پیدا کردن یک سه گانه پنهان آسان تر از جستجوی رابطه بین 6 سلول خواهد بود. در مورد پنج پنهان و برهنه هم همینطور است - پیدا کردن چهار برهنه / پنهان راحت تر است، بنابراین حتی به دنبال پنج ها هم نمیگردند.

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

کلام پایانی

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