Resumen:
El objetivo de esta tesis es estudiar la complejidad computacional correspondiente al problema del ajedrez solitario, en que dada una posición el jugador sólo puede hacer jugadas de captura con el objetivo de dejar una sola pieza en el tablero. Demostramos que este problema pertenece a la clase de complejidad de los problemas NP-Completos. Mediante problemas de ciclos hamiltonianos en grafos no dirigidos, se investiga la NP-Completitud del juego restringiendo el conjunto de piezas a diferentes posibilidades utilizando peones, alfiles y torres. Para esto se presentan cuatro formas de generar las posiciones con diferentes propiedades como las piezas usadas o las maneras de representar las aristas del grafo. Se compara un método con otro para analizar ventajas de cada uno, tales como tamaño del tablero y cantidad de piezas necesarias. También se estudia la NP-Completitud de distintas variantes en que se modifican algunas reglas, así como los efectos de utilizar piezas del ajedrez antiguo. Se investiga asimismo la frontera P de este problema cuando se usa esencialmente un solo tipo de pieza.