Original title: Řešení hry Battleship Solitaire pomocí celočíselného programování
Translated title: Solving the Battleship Solitaire puzzle as an integer programming problem
Authors: Přibylová, Lenka ; Jablonský, Josef (advisor) ; Fábry, Jan (referee)
Document type: Bachelor's theses
Year: 2011
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
Bakalářská práce se zabývá logickou hrou Battleship Solitaire. Seznamuje čtenáře s historií této hry a s jejími pravidly, ze kterých následně vychází formulace hry jako úlohy celočíselného programování. Vytvořeny jsou dva matematické modely, založené na odlišných přístupech; "cell-based" model je založený na zkoumání jednotlivých polí, zatímco "ship-based" model je založený na kombinaci mřížek obsahujících právě jednu loď. Pro ověření, zda je řešení hry jedinečné, jsou do modelů přidány účelové funkce. Oba modely jsou převedeny do modelovacího systému LINGO, a řešeny pro různé rozměry herní mřížky. Z výsledků testování vyplývá, že "ship-based" model sice pracuje s menším počtem proměnných i omezení, ale je velmi náročný na práci s daty, což řešení velmi zpomaluje, a pro větší rozměry naprosto znemožňuje. Mnohem rychleji byly úlohy vyřešeny pomocí "cell-based" modelu. Řešení bylo nalezeno i pro úlohy s většími rozměry, i když se doba řešení výrazně prodloužila. The bachelor thesis deals with the Battleship Solitaire puzzle. It introduces the history and the rules of this puzzle, which are thereafter used to formulate the puzzle as an integer programming problem. Two mathematical models based on different approaches are created, a cell-based model and a ship-based model. In order to determine whether a puzzle has a unique solution an objective function is added to each model. Both models are developed in LINGO modeling language and tested with different grid sizes. The test results show that even though the ship-based model uses fewer variables and constraints, it is too demanding in terms of data processing. It results in longer solving times and the model fails to find a solution for larger grids. Solving the problem using the cell-based model is significantly faster. The solution was found even for larger grids, though the solving time was very long.
Keywords: battleship; integer programming; LINGO; recreational mathematics; battleship; celočíselné programování; LINGO; rekreační matematika

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/25116

Permalink: http://www.nusl.cz/ntk/nusl-72083


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Bachelor's theses