Niejeden z nas grał, a na pewno zna łamigłówki Sudoku czy Polyomino. To drugie od czasu wprowadzenia przez Solomona Golomba wzbudziło zainteresowanie matematyków zajmujących się nauką i rekreacją. Liczne gry – jak np. Tetris czy Ubongo – łamigłówki i nierozwiązane problemy oparte są na tych zachwycających elementach, które powstają przez połączenie wzdłuż krawędzi wielu nie nachodzących na siebie kwadratów jednostkowych...

Zagadnienia poruszane w tym artykule:

• Problem Dokładnego Pokrycia;
• Algorytm niedeterministyczny;
• Algorytm deterministyczny, czyli algorytm brute-force dla problemu ECP;
• Postać macierzowa ECP;
• Algorytm X Knutha;
• Dancing links, Algorytm DLX;
• Dancing links w działaniu;
• Przykład rozwiązania Tetromino za pomocą ECP;
• Przykład rozwiązania Sudoku za pomocą ECP;
• Testowanie algorytmu i szybkości działania;
• Monte Carlo w pomiarze szybkości;
• Czy można jeszcze szybciej...?
• Algorytm DLX + ZDD;
• Podstawowy algorytm rozproszony.

Artukuł pochodzi z magazynu Programista nr 96 (2/2021). Jest to wydanie kwiecień/maj 2021 r.

Szczegółowy spis treści wydania nr 96: https://programistamag.pl/programista-2-2021-96/

Autorem artykułu jest Łukasz Grządko. Autor przygodę z komputerem zaczął w wieku 8 lat. Mając 10 lat, programował interaktywne gry video w języku Basic. Uczestnik wielu konkursów matematyczno-programistycznych. Swoje umiejętności matematyczne i informatyczne poszerzył i wzmocnił, kończąc studia na Uniwersytecie Wrocławskim. Zainteresowany teoretycznymi podstawami informatyki i matematyką, algorytmami i strukturami danych oraz inżynierią oprogramowania. Ponadto aktywny uczestnik TopCoder Algorithms od ponad 16 lat. Obecnie pracuje jako Software Development Engineer w technologiach LTE i 5G Mobile Broadband we wrocławskim oddziale Nokii.

>>FRAGMENT ARTYKUŁU DO POBRANIA<<