Solving the Battleship Solitaire puzzle as an integer programming problem
| Thesis title: | Řešení hry Battleship Solitaire pomocí celočíselného programování |
|---|---|
| Author: | Přibylová, Lenka |
| Thesis type: | Bakalářská práce |
| Supervisor: | Jablonský, Josef |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | rekreační matematika; battleship; LINGO; celočíselné programování |
| Thesis title: | Solving the Battleship Solitaire puzzle as an integer programming problem |
|---|---|
| Author: | Přibylová, Lenka |
| Thesis type: | Bachelor thesis |
| Supervisor: | Jablonský, Josef |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | 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; LINGO; recreational mathematics; integer programming |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 25. 2. 2011 |
|---|---|
| Date of submission: | 10. 5. 2011 |
| Date of defense: | 1. 6. 2011 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/30787/podrobnosti |