The subject of this thesis is the algorithmic properties of one- and two-player
games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles
and games in this context are of the following type: can we design efficient computer
programs that play optimally given any opponent (for a two-player game), or solve
any instance of the puzzle in question?
We examine four games and puzzles and show algorithmic as well as intractability
results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport
a wolf, a goat, and a cabbage across a river by using a boat that can carry only one
item at a time, making sure that no incompatible items are left alone together. We
study generalizations of this puzzle, showing a close connection with the Vertex
Cover problem that implies NP-hardness as well as inapproximability results.
Second, we study the SET game, a card game where the objective is to form
sets of cards that match in a certain sense using cards from a special deck. We
study single- and multi-round variations of this game and establish interesting con-
nections with other classical computational problems, such as Perfect Multi-
Dimensional Matching, Set Packing, Independent Edge Dominating Set,
and Arc Kayles. We prove algorithmic and hardness results in the classical and
the parameterized sense.
Third, we study the UNO game, a game of colored numbered cards where players
take turns discarding cards that match either in color or in number. We extend results
by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza-
tions of the game to Edge Hamiltonian Path and Generalized Geography,
proving that a solitaire version parameterized by the number of colors is fixed param-
eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard.
Finally, we study the Scrabble game, a word game where players are trying to
form words in a crossword fashion by placing letter tiles on a grid board. We prove
that a generalized version of Scrabble is PSPACE-hard, answering a question posed
by Demaine and Hearn in 2008.
","abstract_html":"<p>The subject of this thesis is the algorithmic properties of one- and two-player </p> <p>games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles </p> <p>and games in this context are of the following type: can we design efficient computer </p> <p>programs that play optimally given any opponent (for a two-player game), or solve </p> <p>any instance of the puzzle in question? </p> <p>We examine four games and puzzles and show algorithmic as well as intractability </p> <p>results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport </p> <p>a wolf, a goat, and a cabbage across a river by using a boat that can carry only one </p> <p>item at a time, making sure that no incompatible items are left alone together. We </p> <p>study generalizations of this puzzle, showing a close connection with the Vertex </p> <p>Cover problem that implies NP-hardness as well as inapproximability results. </p> <p>Second, we study the SET game, a card game where the objective is to form </p> <p>sets of cards that match in a certain sense using cards from a special deck. We </p> <p>study single- and multi-round variations of this game and establish interesting con- </p> <p>nections with other classical computational problems, such as Perfect Multi- </p> <p>Dimensional Matching, Set Packing, Independent Edge Dominating Set, </p> <p>and Arc Kayles. We prove algorithmic and hardness results in the classical and </p> <p>the parameterized sense. </p> <p>Third, we study the UNO game, a game of colored numbered cards where players </p> <p>take turns discarding cards that match either in color or in number. We extend results </p> <p>by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza- </p> <p>tions of the game to Edge Hamiltonian Path and Generalized Geography, </p> <p>proving that a solitaire version parameterized by the number of colors is fixed param- </p> <p>eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard. </p> <p>Finally, we study the Scrabble game, a word game where players are trying to </p> <p>form words in a crossword fashion by placing letter tiles on a grid board. We prove </p> <p>that a generalized version of Scrabble is PSPACE-hard, answering a question posed </p> <p>by Demaine and Hearn in 2008. </p>","abstract_has_math":false,"creators":["Mitsou, Vasiliki Despoina"],"institution":"The Graduate School and University Center of The City University of New York","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Amotz Bar-Noy"],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-10-01T07:00:00Z","date_published":"2014-10-01T07:00:00Z","updated_at":"2026-07-24T01:58:49Z","subjects":["Computer Sciences","Algorithms","Combinatorial Game Theory","Computational Complexity","Graph Theory"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://academicworks.cuny.edu/gc_etds/326","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Amotz Bar-Noy"]},{"key":"dc:creator","label":"Author","values":["Mitsou, Vasiliki Despoina"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2001-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The Graduate School and University Center of The City University of New York"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Sciences","Algorithms","Combinatorial Game Theory","Computational Complexity","Graph Theory"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://academicworks.cuny.edu/gc_etds/326"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The subject of this thesis is the algorithmic properties of one- and two-player
games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles
and games in this context are of the following type: can we design efficient computer
programs that play optimally given any opponent (for a two-player game), or solve
any instance of the puzzle in question?
We examine four games and puzzles and show algorithmic as well as intractability
results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport
a wolf, a goat, and a cabbage across a river by using a boat that can carry only one
item at a time, making sure that no incompatible items are left alone together. We
study generalizations of this puzzle, showing a close connection with the Vertex
Cover problem that implies NP-hardness as well as inapproximability results.
Second, we study the SET game, a card game where the objective is to form
sets of cards that match in a certain sense using cards from a special deck. We
study single- and multi-round variations of this game and establish interesting con-
nections with other classical computational problems, such as Perfect Multi-
Dimensional Matching, Set Packing, Independent Edge Dominating Set,
and Arc Kayles. We prove algorithmic and hardness results in the classical and
the parameterized sense.
Third, we study the UNO game, a game of colored numbered cards where players
take turns discarding cards that match either in color or in number. We extend results
by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza-
tions of the game to Edge Hamiltonian Path and Generalized Geography,
proving that a solitaire version parameterized by the number of colors is fixed param-
eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard.
Finally, we study the Scrabble game, a word game where players are trying to
form words in a crossword fashion by placing letter tiles on a grid board. We prove
that a generalized version of Scrabble is PSPACE-hard, answering a question posed
by Demaine and Hearn in 2008.
"]},{"key":"dc:title","label":"Title","values":["The Computational Complexity of Some Games and Puzzles With Theoretical Applications"]}]}],"canonical_facts":{"dc:contributor.advisor":["Amotz Bar-Noy"],"dc:creator":["Mitsou, Vasiliki Despoina"],"dc:date.available":["2001-01-01T08:00:00Z"],"dc:description.abstract":["The subject of this thesis is the algorithmic properties of one- and two-player
games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles
and games in this context are of the following type: can we design efficient computer
programs that play optimally given any opponent (for a two-player game), or solve
any instance of the puzzle in question?
We examine four games and puzzles and show algorithmic as well as intractability
results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport
a wolf, a goat, and a cabbage across a river by using a boat that can carry only one
item at a time, making sure that no incompatible items are left alone together. We
study generalizations of this puzzle, showing a close connection with the Vertex
Cover problem that implies NP-hardness as well as inapproximability results.
Second, we study the SET game, a card game where the objective is to form
sets of cards that match in a certain sense using cards from a special deck. We
study single- and multi-round variations of this game and establish interesting con-
nections with other classical computational problems, such as Perfect Multi-
Dimensional Matching, Set Packing, Independent Edge Dominating Set,
and Arc Kayles. We prove algorithmic and hardness results in the classical and
the parameterized sense.
Third, we study the UNO game, a game of colored numbered cards where players
take turns discarding cards that match either in color or in number. We extend results
by Demaine et. al. (2010 and 2014) that connected one- and two-player generaliza-
tions of the game to Edge Hamiltonian Path and Generalized Geography,
proving that a solitaire version parameterized by the number of colors is fixed param-
eter tractable and that a k-player generalization for k greater or equal to 3 is PSPACE-hard.
Finally, we study the Scrabble game, a word game where players are trying to
form words in a crossword fashion by placing letter tiles on a grid board. We prove
that a generalized version of Scrabble is PSPACE-hard, answering a question posed
by Demaine and Hearn in 2008.
"],"dc:identifier":["https://academicworks.cuny.edu/gc_etds/326"],"dc:subject":["Computer Sciences","Algorithms","Combinatorial Game Theory","Computational Complexity","Graph Theory"],"dc:title":["The Computational Complexity of Some Games and Puzzles With Theoretical Applications"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["The Graduate School and University Center of The City University of New York"]},"updated_at":"2026-07-24T01:58:49Z"}