headerphoto

Problem n-królowych

Prolog...

Trudno powiedzieć, co tak fascynującego jest w problemie n-królowych (często zwanym też problemem 8 hetmanów), że już od ponad 150 lat zajmuje on umysły matematyków, a od niedawna także programistów komputerowych. Przecież to tylko jedna z wielu matematycznych łamigłówek, która absolutnie nie ma kluczowego znaczenia dla przetrwania gatunku ludzkiego. Zgłębianie jego tajemnic nie doprowadzi do zmniejszenia dziury ozonowej, nie sprawi też, że nastanie pokój na ziemi :). Wymiernym efektem może być jedynie słodki smak odkrywania nowych dróg do celu, jakim jest coraz sprytniejsze rozwiązywanie problemu n-królowych. Zważywszy, że w prostym algorytmie ustawiania królowych na szachownicy zaszyty jest bardzo czasochłonny i skomplikowany mechanizm milionów decyzji, prób i powrotów, przez które komputer musi przebrnąć, aby dotrzeć do rozwiązania. Ta ogromna struktura danych czekająca na przeanalizowanie to także ambitne wyzwanie dla samego programisty.

A to wszystko jest tylko po to, by poczuć trochę frajdy z rozwiązywania klasycznej zagadki matematycznej, za pomocą współczesnego sprzętu komputerowego i różnych technik programowania.

Niniejsza strona jest próbą przedstawienia problemu n-królowych w zwięzłej i jak najbardziej przystępnej formie. Ogólnie ma za zadanie wypełnić lukę w polskim internecie, w którym na próżno szukać głębszych wywodów na temat problemu n-królowych. Poza tym znalazło się tutaj (trochę jakby rykoszetem) sporo ciekawych informacji na temat teorii grafów, algorytmów z powrotami, metody Monte Carlo, programowania równoległego w OpenMP i systemu kolejkowania OpenPBS.

Materiały zamieszczone na stronie pochodzą z dwóch opracowań jakie popełniłem w czasie swojej naukowej "kariery". Pierwsza z nich, to moja praca licencjacka zatytułowana "Rozmieszczanie królowych na szachownicy metodą algorytmów z powrotami oraz oszacowanie złożoności obliczeniowej metodą Monte Carlo" (KUL). Temat był na tyle interesujący, że postanowiłem sięgnąć po niego jeszcze raz, ale już przy okazji pracy magisterskiej, która nosiła tytuł: "Realizacja obliczeń równoległych na przykładzie algorytmów z powrotami - problem n-królowych"(UMCS). Tak powstała spora porcja ciekawego materiału, okraszonego nie mniejszą ilością testów, badań i analiz. I myślę, że szkoda by było, gdyby to wszystko kisiło się na półce wśród termobindowanych kartek. Zwłaszcza, że problem n-królowych to zagadnienie wyjątkowo frapujące i zasługuje na znacznie więcej niż tylko krótkie artykuły czy wzmianki na forach internetowych.

Mam nadzieję, że strona po której własnie stąpasz pomoże w zrozumieniu, o co tak naprawdę chodzi w problemie n-królowych i z czym go się je. Mam też nadzieję, że zawarte na jej łamach informacje okażą się choć trochę pomocne w realizacji Twoich osobistych projektów i wszelkich innych fantazji programistycznych :)

Powodzenia i miłej lektury!


najtańsze artykuły reklamowe dla firm w Polsce
Wybierz pozycjonowanie wizerunkowe dla swojej firmy
Podstawowe niekonwencjonalne metody leczenia , jak bardzo są skuteczne?