Помоги бабушке — реши ей судоку
Сегодня мы с вами поговорим о том, как же помочь своей бабушке, которая уже который день сидит за решением любимых кроссвордов — судоку. К тому же, часто этот вопрос задают на разного рода собеседованиях в компаниях типа Facebook или Google.
Что ж, давай поможем бабушке решить очередной судоку!
История знает много видов решения этой задачи, но так-как мы берем во внимание не большой судоку, то решим мы его самым простым методом: backtracking. Но в целом, это такой себе брутфорс. Но помни, читатель, наш судоку всего лишь 9x9, потому даже брутфорс будет быстро работать.
Чтоб дать тебе сил, я хочу поделиться с тобой решением этой задачи, которую написал премьер-министр Сингапура! Класный чувак! Я бы сделал решение судоку обязательным экзаменом для наших политиков на проф-пригодность. Ну серьезно, как может управлять политик 20го века страной 21го. Вот и я о том же.
Но, если ты не твоя бабушка, я напомню тебе немного правила судоку:
- В ряду по вертикали не может быть одинаковых цифр.
- В ряду по горизонтали история точно такая же
- В каждом сегменте судоку ( квадраты 3х3 ) должны быть разные цифры.
Итак, как мы уже говорили — да здравствует брутфорс. Только из названия можно понять, что мы будем перебирать очень много вариантов, с надеждой что какой-то из них таки сработает.
Идея простая:
- В первую попавшуюся ячейку вставляем 1. Если это возможно — пробуем вставить 1 в следующую
- Если 1 нельзя вставить — вставляем двойку.
И вот таким не замысловатым образом мы пытаемся заполнить всю табличку:) Потому, давайте писать!
Для начала напишем функцию, которая проверит или можно вставить число в ячейку:
Как видим в функцию мы передаем координаты ячейки и число которое мы хотим вставить.
В линеечках 3–4 мы проверяем или такое число есть в вертикальном или горизонтальном ряде.
Линеечка 5 же проверяет или такое число есть в сегменте судоку.
Ну и конечно же сам брутфорс:
Как видим все до изумления просто: мы бегаем по каждой свободной ячейке и пробуем вставить туда разные числа.
Если мы таки находим комбинацию когда все числа встали на свои места — мы решили судоку. Бабушка свободна! И может дальше печь тебе пирожки!
