Чудо судоку, или пределы визуального воспроиятия

[kaz-orphan2.livejournal.com]

известно, что судоку - NP-полная задача. Следовательно единственным методом решения является полный перебор. А все увлеченно пытыются решить эту задачу типа в голове. это напоминает поиск шестого эвклидового тела.

но, с другой стороны, мы повсеместно имеем страницы в журналах и всяческие программы генерирующие экзамплы, действительно решаемые в голове. это порождает у меня вопросы:

1.(психология) а какой достоверно зарегистрированный уровень перебора реализуемый системой глаз-мозг? т.е. человек смотрит и решает, ничего никуда не записывая и впоследствии не обращаясь к записям. Здорово, если бы такие данные были бы дифференцированы как для задач решаемых перебором в ширину, так для задач решаемым перебором в глубину. в первую очередь - применительно к судоку, но применительно к любой визуально наблюдаемой задаче тоже интересно.

2.(геймдизайн, статистика) в связи с этим, не следует ли пересмотреть критерии сложности судоку? их ранжировать то, надо по глубине необходимого для решения полного перебора. 1-детский, 2-легкий и т.д. а так же процент решаемых в системе глаз-мозг задач с 17...90 предзаданными цифрами.

3. (математика,биология, физика) известно, что минимальное количество цифр при котором судоку решается - 17. какой достоверно подтвержденный процент решаемых в системе глаз-мозг решаемых задач с 17-ю предзаданными цыфрами? (и далее - с 18-ю, 19-ю и т.д.). я вот уже 3 года решаю судоки из 21-26 цифр и не могу достичь 100%-ой решаемости. решаю максимум 10% из задач (хотя они и повторяются!) и быстрее меня решают как минимум 30% участников социума. понятно, что большинство из них пользуются компютерными подсказками, но не все же!

в общем и целом - статистика выше описанная и плюс еще что-то, позволит британским ученым понять: может ли человеческий мозг решать NP-полные задачи за не NP-полное время .А это уже интересно, всем - философам, математикам, физикам, биологам.

Comments

[schumacher.livejournal.com]

Утверждение про полный перебор - неверно.

[sbat.livejournal.com]

Мне кажется вы идете не совсем в правильном направлении.

Судоку - np-complete задача. Определение победителя в шахматной позиции - np-complete задача. Но из этого совсем не следует, что для решения конкретного судоку нужен полный перебор. А победителя в эншпиле "ферзь+король против короля" сможет определить даже новичок.

(frozen comment)

[wordsmsdnua.livejournal.com]

судоку полный отстой. шахматы куда лучше.

[nishi-miller.livejournal.com]

в судоку не 90, а 81 цифра, есличо....

[toboroib.livejournal.com]

Для NP-полных задач бывают очень неплохие эвристики. А мозги с эвристиками справляются, порой, получше всяких компьютеров.

[parking-brake.livejournal.com]

Очень жалко людей, которые решают судоку перебором. Хотя часто бывают судоку, которые недостаточно заполнены(

[igor-eta.livejournal.com]

"известно, что судоку - NP-полная задача. Следовательно единственным методом решения является полный перебор"
это чушь несусветная

[igor-eta.livejournal.com]

Мозг эквивалентен детерменистической машине тьюринга, дальше понятно