Учени от Университета Сейнт Ендрюс в Шотландия ще дадат 1 милион долара за успешното разгадаване на "проста" шахматна загадка.
Изследователите отправят предложението предимно към компютърни специалисти и програмисти. Те трябва да открият алгоритъм за решаването на шахматна задача, конвенционалното решение на която би отнело хиляди години. Всъщност задачата вече е решена, но само в един частен случай.
"Пъзелът в 8-те кралици" е измислен през 1850 година. 8 царици на стандартна шахматна дъска трябва да бъдат поставени така, че да не могат да се атакуват взаимно - те не трябва да са в диагонал, в колона, или в редица една спрямо друга. Тази задача е решенa в средата на миналия век. Учените сега търсят решение не върху стандартна шахматна дъска с 64 квадрата, а с n квадрата в "n-Queens puzzle". Освен това в задачата не само че дъската е по-голяма, но и някои кралици вече са поставени. Тоест, ако някои кралици вече са били поставени на борда "n-на-n", можете ли да намерите решение на "Пъзела с n кралици", без да се премествате с някоя вече поставените?
"Ако можете да напишете програма, която бързо да намери отговор на тази задача, то вашият софтуер може да са адаптира за решението на редица други проблеми, като например разшифроването на кодове и криптиране", споделя професор Ян Гент.
Сегашните програми не могат да се справят с бързото решение на подобна задача, защото трябва да анализират осъществяването на множество ходове в различни последователности.
"А това отнема много, ако се използват стандартните алгоритми", разкрива професор Гент.
"Все още никой не е успял дори да се приближи до създаването на програма, способна бързо да реши загадката. Затова предлагаме и наградата", казва пък изследователят Питър Найтингейл, докторант към катедрата по компютърни науки в Университета Сейнт Ендрюс.
The paper (Complexity of n-Queens Completion) by (Ian P. Gent, Christopher Jefferson and Peter Nightingale) is published in the (31 August 2017) issue of (Journal of Artificial Intelligence Research), available via http://jair.org/papers/paper5512.html. DOI: doi:10.1613/jair.5512
