Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

04.11.2023

Аналіз поля Сапера за допомогою множин

…Вчорашнє рішення з обчисленням ймовірностей мін розвʼязує багато ситуацій, але не всі. Проте щоб досягти чогось більшого, недостатньо дивитись на комірки поодинці: ми витягли з них всю можливу інформацію. Подальший аналіз має дивитись на групи комірок з відомою кількістю мін та через операції над множинами досягати висновку про розташування мін.

????
2334
1*11

Наведу приклад: в цьому фрагменті поля ми не можемо визначити розташування мін за жодною з цифр. Але ми точно можемо сказати, що для виконання 2 перші дві комірки повинні містити одну та тільки одну міну. А для виконання 3 перші три невідомі комірки повинні містити дві міни. Можна зробити висновок, що в третій комірці міна є гарантовано. Або навпаки: якби замість 3 стояла б 2, то в третій комірці гарантовано не було б міни.

Щоб алгоритмізувати такий підхід, потрібно ввести поняття множини комірок, а далі перетинати ці множини. Кожний перетин утворює три нові множини: множину спільних комірок та множину рештки з кожного боку. Залишається обчислити кількість мін в кожній з підмножин та маємо успіх. Під успіхом маю на увазі, що в деяких випадках отримуватимемо або множину зовсім без мін, або таку де кількість мін дорівнює кількості комірок.

Є тільки одне ускладнення: не завжди ми будемо отримувати точну кількість мін. Бо, якщо подивитись на приклад де дві цифри 3 поруч, то про перетин їх множин можемо сказати тільки те, що в ньому не більше двох мін (що не дуже корисно). Та, не менше однієї — бо решткою від перетину з кожної сторони буде тільки одна комірка, значить, принаймні одна з мін припадає на спільну множину.

Такі нерівності теж можуть бути корисними, оскільки через додаткові перетини можна дійти до точних значень. Взагалі, почати можна й з одного раунду перетинів, але в ідеалі треба обробляти й новоотримані множини, поки отримуємо нову інформацію. Благо масштаб задачі дозволяє робити всілякі перебори. Особливо якщо зберігати стан між кроками, бо поки що я обчислюю все наново кожен раз.