Помоги бабушке — реши ей судоку

Сегодня мы с вами поговорим о том, как же помочь своей бабушке, которая уже который день сидит за решением любимых кроссвордов — судоку. К тому же, часто этот вопрос задают на разного рода собеседованиях в компаниях типа Facebook или Google.

Что ж, давай поможем бабушке решить очередной судоку!

История знает много видов решения этой задачи, но так-как мы берем во внимание не большой судоку, то решим мы его самым простым методом: backtracking. Но в целом, это такой себе брутфорс. Но помни, читатель, наш судоку всего лишь 9x9, потому даже брутфорс будет быстро работать.

Чтоб дать тебе сил, я хочу поделиться с тобой решением этой задачи, которую написал премьер-министр Сингапура! Класный чувак! Я бы сделал решение судоку обязательным экзаменом для наших политиков на проф-пригодность. Ну серьезно, как может управлять политик 20го века страной 21го. Вот и я о том же.

Но, если ты не твоя бабушка, я напомню тебе немного правила судоку:

  1. В ряду по вертикали не может быть одинаковых цифр.
  2. В ряду по горизонтали история точно такая же
  3. В каждом сегменте судоку ( квадраты 3х3 ) должны быть разные цифры.

Итак, как мы уже говорили — да здравствует брутфорс. Только из названия можно понять, что мы будем перебирать очень много вариантов, с надеждой что какой-то из них таки сработает.

Идея простая:

  1. В первую попавшуюся ячейку вставляем 1. Если это возможно — пробуем вставить 1 в следующую
  2. Если 1 нельзя вставить — вставляем двойку.

И вот таким не замысловатым образом мы пытаемся заполнить всю табличку:) Потому, давайте писать!

Для начала напишем функцию, которая проверит или можно вставить число в ячейку:

Как видим в функцию мы передаем координаты ячейки и число которое мы хотим вставить.

В линеечках 3–4 мы проверяем или такое число есть в вертикальном или горизонтальном ряде.

Линеечка 5 же проверяет или такое число есть в сегменте судоку.

Ну и конечно же сам брутфорс:

Как видим все до изумления просто: мы бегаем по каждой свободной ячейке и пробуем вставить туда разные числа.

Если мы таки находим комбинацию когда все числа встали на свои места — мы решили судоку. Бабушка свободна! И может дальше печь тебе пирожки!