В статье "Решение судоку с помощью веб-камеры" большинство решений реализовано очень красиво, за исключением самого решателя. В одном из моих старых проектов «Решатель судоку» была попытка подобрать алгоритм с комплектом эвристик для решения стандартной задачи судоку (поле 9х9). Вариант прямого полного перебора не рассматривался.

На днях в этом блоге было опубликовано открытое письмо учёным по поводу предполагаемого полиномиального алгоритма для задачи 3-SAT. Обсуждение в том топике ещё далеко не закрыто и говорить о том, что в алгориме найдены ошибки пока преждевременно, но мне хочется написать почему «граждане учёные» не выстраиваются в очередь чтобы поскорее проверить это доказательство.

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.

Пока IBM бьётся с шахматистами, создавая всё новые и новые суперкомпьютеры, ребята из Google научили Android решать судоку. Кто же круче — чемпион по судоку или обычный человек с Nexus S? Смотрим:

Есть у спортсменов одна давно доказанная истина — когда ты один на беговой дорожке, твои результаты далеки от идеала; но когда по соседней дорожке бежит примерно равный соперник, ты способен ставить рекорды. Жажда победы проявляет в организме скрытые резервы. Применив этот же принцип к старой головоломке судоку, можно получить практически новую игру, а процесс поиска цифр способен вызывать совершенно другие эмоции.
Однажды мне пришло в голову, что решать судоку можно (и хотелось бы) одновременно с оппонентами, да еще и видеть при этом, насколько они уже продвинулись в решении. И желание это вылилось в создание небольшой браузерной игры. В этой игре Вы решаете судоку, одновременно ту же головоломку решают Ваши соперники. Цифры по мере решения задачи появляются на экранах сразу у всех игроков — разгадал один, а увидели все. Задача, естественно, — опередить соперников и разгадать как можно больше цифр. Попробовать сыграть можно здесь.
UPDATE. За время хабраэффекта найдено немалое количество мелких и не очень багов. Но за последние 20 минут в логах ни одной даже мелкой ошибки — надеюсь, можно идти спать).

Окаэри. Именно так звучит по-японски «Добро пожаловать!». Добро пожаловать в новый мир старой японской головоломки. Собственно, судоку...
Судоку — игра, знакомая практически всем. В какой-то мере уже даже и заезженная, поднадоевшая. Хочется ее немного освежить, добавить в процесс решения новых эмоций. А вот можно ли это сделать? Можно ли влить свежую струю в привычно размеренное течение японской головоломоки, не изменяя правил?
Что ж, позвольте попытаться…

С предыдущего хабратопика я понял, что хабражителям очень понравился сапер на своих батниках и поэтому рискнул написать еще одну игру, а именно — Судоку. И опять же, на своих батниках.
Как и Minesweeper, Sudoku for cmd.exe имеет ряд следующих преимуществ:

• Оригинальное лого
• Двухцветный текстовой графический интерфейс (фон — чёрный, текст — серый)
• Возможность воспроизведения программы практически на любом компьютере

В общем, это Судоку для настоящих мужчин. И скачать эту замечательную игру вы можете прямо сейчас, воспользовавшись этими ссылками: Plain Text | Google Docs

Раз пошла такая пьянка. То подброшу и я свои пять копеек. Нет-нет, не пугайтесь, это не еще один сапер. Это судоку. Японская головоломка, суть которой расставить в пустые клеточки цифры от 1 до 9 таким образом, чтобы по вертикали, горзонтали и в малых квадратах они не повторялись. Как это часто бывает, делалось все в выходные. Поиграть в судоку тут. А под катом чуть-чуть расскажу о том, как я ее делал.