http://kaz-orphan2.livejournal.com/ (![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png)
kaz-orphan2.livejournal.com) wrote in ![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png)
useless_faq2014-02-09 01:58 am
kaz-orphan2.livejournal.com) wrote in useless_faq2014-02-09 01:58 am
Чудо судоку, или пределы визуального воспроиятия
известно, что судоку - NP-полная задача. Следовательно единственным методом решения является полный перебор. А все увлеченно пытыются решить эту задачу типа в голове. это напоминает поиск шестого эвклидового тела.
но, с другой стороны, мы повсеместно имеем страницы в журналах и всяческие программы генерирующие экзамплы, действительно решаемые в голове. это порождает у меня вопросы:
1.(психология) а какой достоверно зарегистрированный уровень перебора реализуемый системой глаз-мозг? т.е. человек смотрит и решает, ничего никуда не записывая и впоследствии не обращаясь к записям. Здорово, если бы такие данные были бы дифференцированы как для задач решаемых перебором в ширину, так для задач решаемым перебором в глубину. в первую очередь - применительно к судоку, но применительно к любой визуально наблюдаемой задаче тоже интересно.
2.(геймдизайн, статистика) в связи с этим, не следует ли пересмотреть критерии сложности судоку? их ранжировать то, надо по глубине необходимого для решения полного перебора. 1-детский, 2-легкий и т.д. а так же процент решаемых в системе глаз-мозг задач с 17...90 предзаданными цифрами.
3. (математика,биология, физика) известно, что минимальное количество цифр при котором судоку решается - 17. какой достоверно подтвержденный процент решаемых в системе глаз-мозг решаемых задач с 17-ю предзаданными цыфрами? (и далее - с 18-ю, 19-ю и т.д.). я вот уже 3 года решаю судоки из 21-26 цифр и не могу достичь 100%-ой решаемости. решаю максимум 10% из задач (хотя они и повторяются!) и быстрее меня решают как минимум 30% участников социума. понятно, что большинство из них пользуются компютерными подсказками, но не все же!
в общем и целом - статистика выше описанная и плюс еще что-то, позволит британским ученым понять: может ли человеческий мозг решать NP-полные задачи за не NP-полное время .А это уже интересно, всем - философам, математикам, физикам, биологам.
но, с другой стороны, мы повсеместно имеем страницы в журналах и всяческие программы генерирующие экзамплы, действительно решаемые в голове. это порождает у меня вопросы:
1.(психология) а какой достоверно зарегистрированный уровень перебора реализуемый системой глаз-мозг? т.е. человек смотрит и решает, ничего никуда не записывая и впоследствии не обращаясь к записям. Здорово, если бы такие данные были бы дифференцированы как для задач решаемых перебором в ширину, так для задач решаемым перебором в глубину. в первую очередь - применительно к судоку, но применительно к любой визуально наблюдаемой задаче тоже интересно.
2.(геймдизайн, статистика) в связи с этим, не следует ли пересмотреть критерии сложности судоку? их ранжировать то, надо по глубине необходимого для решения полного перебора. 1-детский, 2-легкий и т.д. а так же процент решаемых в системе глаз-мозг задач с 17...90 предзаданными цифрами.
3. (математика,биология, физика) известно, что минимальное количество цифр при котором судоку решается - 17. какой достоверно подтвержденный процент решаемых в системе глаз-мозг решаемых задач с 17-ю предзаданными цыфрами? (и далее - с 18-ю, 19-ю и т.д.). я вот уже 3 года решаю судоки из 21-26 цифр и не могу достичь 100%-ой решаемости. решаю максимум 10% из задач (хотя они и повторяются!) и быстрее меня решают как минимум 30% участников социума. понятно, что большинство из них пользуются компютерными подсказками, но не все же!
в общем и целом - статистика выше описанная и плюс еще что-то, позволит британским ученым понять: может ли человеческий мозг решать NP-полные задачи за не NP-полное время .А это уже интересно, всем - философам, математикам, физикам, биологам.
no subject
no subject
no subject
no subject
Судоку - np-complete задача. Определение победителя в шахматной позиции - np-complete задача. Но из этого совсем не следует, что для решения конкретного судоку нужен полный перебор. А победителя в эншпиле "ферзь+король против короля" сможет определить даже новичок.
no subject
no subject
практически всегда нужны допущения.
no subject
Это не верно. Доказательство теорем (например арифметики) это вообще алгоритмически неразрешимая задача. В арифметике Пресбургера (арифметика Пеано без умножения) алгоритм доказывающий формулы существует, но требует времени как минимум 2^(2^cn), что намного сложнее чем NP..
no subject
давайте рассмотрим судоку.
есть ровно 81 конфигураций с 80 предзаданными цифрами (с точностью до переобозначений). решаются все они ровно за один ход. любым.
есть ровно 81 исходная конфигурация с одной исходной цифрой. они не решаются.
есть примерно 10^77 промежуточных вариантов. И среди них есть те, которые я решаю, а вася пупкин не решает. или наоборот. вася решает, а я нет.
с другой стооны, если мы привлечем комбираторику, то для конфигурации с 80 предзаданными цифрами глубина необходимого перебора = 0.
а для 16 предзаданных цифр,глубина перебора - бесконечность.
зададим n цифр - x% нерешаемых, y% решаемых с 1 уровнем переюора, z% с двумя и т.д.
я вопервых хотел сказать, что уровень перебора 2+ большинству людей не по силам. мне не по силам оказался, хоть я и тренировался...
а вовторых все же надеялся, что найдутся люди этот уровень преодолевшие. Ассоциативно. ну в общем интересно, какой уровень перебора с возвратом по силам чиста интеллекту? без внешней памяти.
no subject
no subject
физиологически - количество развилок "если-то".
ну например - если в паре ячеек - (х,у), то во второй паре - (z,w). ну тд.
no subject
Сижу, экспериментирую, пытаюсь осмыслить как самому посчитать уровень перебора. В простых развилках не получается )))) Получается что-то вроде: если X тут и еще X здесь, а тут X быть не может потому что он обязан быть где-то здесь, то следовательно в этой клетке точно Х.
Как это формализовать, совершенно не понимаю. Хотя давно уже интересно )))
no subject
Нет, это более сложная задача, как минимум PolySpace-complete (если используется аналог правила 50 ходов).
может ли человеческий мозг решать NP-полные задачи за не NP-полное время
Это бессмысленный вопрос. Понятно, что человек никогда не решит судоку размером 1000000х1000000. Так что в принципе нельзя узнать, требуется ли человеку для решения судоку nxn время экспоненциально зависящее от n.
no subject
Ой, и правда. Там же "отрицание" можно проверить за полиномиальное время (в смысле, что мы проиграли). Спасибо!
(frozen comment) no subject
(frozen comment) no subject
(frozen comment) no subject
(frozen comment) no subject
no subject
no subject
no subject
no subject
no subject
no subject
это чушь несусветная
no subject