Proving The NP-Completeness of The Crew: The Quest for Planet Nine

Abstract: In this post I prove the NP-Completeness of The Crew: The Quest for Planet Nine. First we define the unbounded version of the problem statement along with what a brief review on NP as a complexity group. Next, I show a reduction from the Hamilton Path Problem. Finally, a proof is given on theContinue reading “Proving The NP-Completeness of The Crew: The Quest for Planet Nine”

Ticket to Ride and the Traveling Salesperson Problem.

Abstract: In this post, we look at how to find the shortest path through a subset of nodes. We reduce the problem to the Traveling Salesperson Problem, and show how our solution is optimal. There is also a discussion on what NP-hard problems are, and why finding a solution to our problem is hard. TicketContinue reading “Ticket to Ride and the Traveling Salesperson Problem.”

Generating Solutions to The Crew: The Quest for Planet Nine Final

Abstract: In this post we fully discus the current iteration of my algorithm for generating solutions to The Crew: The Quest for Planet. We look at the challenges of such and algorithm, the main flaws of its current system, and what needs to be worked on. We also discuss the Time-Complexity of this problem andContinue reading “Generating Solutions to The Crew: The Quest for Planet Nine Final”

Generating Solutions to The Crew: The Quest for Planet Nine Part 2

Abstract: In this post we continue our development of a solution generator for The Crew: The Quest for Planet Nine. We begin to create an algorithm for choosing which objective players should take, as well as start work on an algorithm for actually generating the solutions. For those who have not read the previous post,Continue reading “Generating Solutions to The Crew: The Quest for Planet Nine Part 2”

Generating Solutions to The Crew: The Quest for Planet Nine Part 1

Abstract: In this post we create the foundation needed to formulate an algorithm that generates a “solution” for the board game: The Crew: The Quest for Planet Nine. To do so, we create a number of classes to help model the game, as well as some useful calculation tools. Finally we start creating the solutionContinue reading “Generating Solutions to The Crew: The Quest for Planet Nine Part 1”

A Chopsticks Solution Part 1

Abstract: In this post, we start writing a solution to a variation of the hand game “Chopsticks”. In this post, we create a graph that maps all of the possible moves and states. We also implement a version of minimax called negamax. Chopsticks is a popular hand game for two or more players. In Chopsticks,Continue reading “A Chopsticks Solution Part 1”