エントリー #137091

Лемма о безошибочности.

Что требуется доказать: Решатель судоку, выбирая очередной ход, исходит из того, что все предыдущие ходы были правильные.

Доказательство от противного.

Предположим, что решатель судоку при выборе очередного хода, исходит из того, что в предыдущих ходах он допустил ошибку. Как в таком предположении следует поступить решателю?

Решатель должен перебрать бесконечное множество вариантов, поскольку на каждом шагу он исходит из того, что ошибается.
Даже, если есть единственный вариант, решатель должен перебрать все 9 вариантов. Есть такие дураки? Таких дураков нет.

Ч.т.д.

Приглашаю к обсуждению леммы многоуважаемого savlanik



Для тех, кто не знает или забыл, что такое лемма - это вспомогательная теорема.