alex_tlt
2017-01-17 21:53
Лемма о безошибочности.
Что требуется доказать: Решатель судоку, выбирая очередной ход, исходит из того, что все предыдущие ходы были правильные.
Доказательство от противного.
Предположим, что решатель судоку при выборе очередного хода, исходит из того, что в предыдущих ходах он допустил ошибку. Как в таком предположении следует поступить решателю?
Решатель должен перебрать бесконечное множество вариантов, поскольку на каждом шагу он исходит из того, что ошибается.
Даже, если есть единственный вариант, решатель должен перебрать все 9 вариантов. Есть такие дураки? Таких дураков нет.
Ч.т.д.
Приглашаю к обсуждению леммы многоуважаемого savlanik
Для тех, кто не знает или забыл, что такое лемма - это вспомогательная теорема.
Нравится 0
0