Problem n kraljic

Avtor:

Jaka Slapar, 3.e

Mentorica:

Nataša Šuligoj

Ključne besede:

Problem n kraljic, neodvisnostne množice, klike, modularna aritmetika, kraljičini grafi, simetrije šahovnice

Povzetek:

V raziskovalni nalogi sem preučeval problem neodvisnosti kraljic ali problem n kraljic. Problem nas vpraša, na koliko različnih načinov lahko na dano šahovnico postavimo maksimalno število kraljic, tako da se med seboj ne napadajo. Izkaže se, da je problem pri večjih šahovnicah matematično dokaj kompleksen, saj zaenkrat poznamo zgolj grobe ocene za število rešitev. Najboljši način reševanja tako zaenkrat ostaja groba računalniška moč. Problem obravnavam na standardnih in na modularnih šahovnicah, pogledam pa si tudi nekaj primerov šahovnic nenavadnih oblik. Na koncu sem napisal še računalniški program, ki nam za šahovnice oblike n×n izpiše število rešitev.