¿Cómo Resolver Un Juego De Mesa Con C++?

Alguna vez un amigo me regaló un juego de mesa que se hace llamar Solitario.


La forma de jugar es mover una pieza por encima de otra, o sea, brincarla. Entonces la pieza que nos hemos saltado, debe desaparecer del tablero, nos la comemos. Más o menos como se juega en las damas inglesas. Al final debe quedar solo una pieza en el tablero.

Entonces tenemos un programita que puede encontrar un montón de soluciones para este problema.

#include <iostream>
#include <conio.h>

using namespace std;

int tablero[5][5];
int pila[15][4];
int piezas;

void llenarTablero () {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j <= i; j++) {
			tablero[i][j] = 1;
		}
	}
}

void imprimirTablero () {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 4 - i; j++) {
			cout << " ";
		}
		for (int j = 0; j <= i; j++) {
			cout << tablero[i][j] << " ";
		}
		cout << endl;
	}
}

void imprimirPila () {
	cout << endl;
	for (int i = 0; i < 13; i++) {
		cout << pila[i][0] << "," << pila[i][1] << " > " << pila[i][2] << "," << pila[i][3] << endl;
	}
	cout << endl;
	getch();
}

void deshacerBrinco(int y0, int x0, int y1, int x1, int y2, int x2) {
	// ocupar posición inicial
	tablero[y0][x0] = 1;
	// ocupar posision intermedia
	tablero[y1][x1] = 1;
	// desocupar posición final 
	tablero[y2][x2] = 0;
}

// 0s son posición inicial
// 1s son posición intermedia
// 2s son posición final
int hacerBrinco (int y0, int x0, int y1, int x1, int y2, int x2) {
	// posición final dentro del tablero
	if (y2 >= 0 && y2 < 5 && x2 >= 0 && x2 <= y2) {
		// posición intermedia ocupada
		// posición final vacía
		if (tablero[y1][x1] == 1 && tablero[y2][x2] == 0) {
			// desocupar posición inicial
			tablero[y0][x0] = 0;
			// desocupar posision intermedia
			tablero[y1][x1] = 0;
			// ocupar posición final 
			tablero[y2][x2] = 1;

			// guardar movimiento en pila
			pila[14 - piezas][0] = y0;
			pila[14 - piezas][1] = x0;
			pila[14 - piezas][2] = y2;
			pila[14 - piezas][3] = x2;

			void siguienteSalto();
			siguienteSalto();
			deshacerBrinco(y0, x0, y1, x1, y2, x2);
			
			return 1;
		}
	}
	return 0;
}

void siguienteSalto () {
	if (--piezas == 1) {
		imprimirTablero();
		imprimirPila();
	}

	if (piezas > 1) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j <= i; j++) {
				// posición actual ocupada
				if (tablero[i][j] == 1) {
					// izquierda
					hacerBrinco(i, j, i, j - 1, i, j - 2);
					// derecha
					hacerBrinco(i, j, i, j + 1, i, j + 2);
					// arriba izquierda
					hacerBrinco(i, j, i - 1, j - 1, i - 2, j - 2);
					// arriba derecha
					hacerBrinco(i, j, i - 1, j, i - 2, j);
					// abajo izquierda
					hacerBrinco(i, j, i + 1, j - 1, i + 2, j - 2);
					// abajo derecha
					hacerBrinco(i, j, i + 1, j, i + 2, j);
				}
			}
		}
	}

	++piezas;
}

void quitarPrimera () {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j <= i; j++) {
			tablero[i][j] = 0; // quitar
			siguienteSalto();
			tablero[i][j] = 1; // poner
		}
	}
}

int main () {
	llenarTablero();
	piezas = 15;
	quitarPrimera();
}

La representación del tablero en memoria es algo así.


La salida hasta el primer getch() es ..

    1
   0 0
  0 0 0
 0 0 0 0
0 0 0 0 0

2,2 > 0,0
2,0 > 2,2
0,0 > 2,0
3,0 > 1,0
3,3 > 1,1
4,2 > 2,0
1,0 > 3,0
4,0 > 2,0
4,4 > 4,2
4,1 > 4,3
4,3 > 2,1
2,0 > 2,2
2,2 > 0,0

.. lo que significa ..


Y eso es todo.