Usar una lista en donde almacene valores de tipo "J15" para representar los movimientos del juego. Recordar las posiciones que ya visitó en un conjunto. Especificar e implementar una rutina que comience en una configuración del juego y genere la lista de los movimientos que resuelven el juego. El algoritmo no tiene que ser eficiente. Se puede usar una estrategia de prueba y error para obtener la solución del juego, por lo que es válido escribir y borrar de la lista configuraciones de juego de prueba. Recordar que en algunos casos el juego no tiene solución.

Objetivos:

El objetivo de esta tarea programada es que el estudiante implemente una nueva clase usando todo lo visto en clase, especialmente la STL.

Requerimientos:

· Alguna herramienta para compilar programas ya sea; DevCpp, Visual Studio, o Borland u otro.

· Doxygen; herramienta para hacer documentación.

· Alojamiento en Internet para publicar la solución.

Resolución del problema:

           Para resolver la tarea se implemento la clase “J15” que representa los estados del tablero y la clase “Juego” que es la que ejecuta los métodos para resolver el juego.

Abstracción:

Operaciones / métodos:

        Class BoardState:

        bool IsFinalPositionCandidate(): revisa si la poscicion actual es candidata para ser la final.

Class Solver:

int GetOptimalSolution(deque<Move>& solution): Obtiene la solucion optima para el juego.

Class DrawSolution:

void SetCell(int x, int y, int value): setea la celda.

void SetBlank(int x, int y): setea el espacio en blanco.

void operator()(const Move& move): mueve las celdas.

Especificación del programa:

El programa es una rutina que resuelve el juego llamado “Juego 15”.

Especificación de la clase:

La clase “BoardState” guarda el estado del tablero después de cada movimiento.

La clase “Solver” resuelve el juego.

La clase “DrawSolution” muestra el resultado de la solución.

Implementación

Modelo de la clase:

            juego15 à  BoardState

                         à Solver

        à DrawSolution

Invariante de la clase:

            Los números que el usuario tendrá que ingresar deben ser del 1 al 15.

Compilador usado:

Microsoft Visual Studio 2005.

¿Cómo compilar el programa?

Abrir el archivo .vcproj, darle click en la opción build, ahí seleccionar build juego15.

Guía de uso del programa

Al ejecutar el programa, el usuario solamente deberá ingresar los números del 1 al 15 y al final ingresar el espacio en blanco representado con el carácter “_”. El programa puede durar algunos minutos encontrando la solución del juego dependiendo de los números ingresados.

Codigo Fuente:

#include <iostream>

#include <deque>

#include <iomanip>

#include <fstream>

#include <algorithm>

#include <string>

#include <TIME.H>

using namespace std;

using std::cout;

using std::cerr;

using std::setw;

using std::deque;

///Configuracion del programa

enum { DIMENSION = 4 };

const bool s_bTopLeftBlank = false;

/// Fin de la configuracion del programa

template<int v> struct Int2Type_

{

enum { value = v };

};

typedef unsigned int Cell;

///Obtener cambio de Manhattan

inline int GetManhattanChange(int pos, int newValue, int dir)

{

return (pos == newValue)? -1 : ((newValue < pos)? dir : -dir);

}

+-----> Y

///Mover celda

struct Move

{

int m_x, m_y;

Move(int x, int y) : m_x(x), m_y(y) {}

};

///Estado del tablero

class BoardState

{

template <int X, int Y>

struct FinalPosition

{

static bool Is(const BoardState& board)

{

return X * DIMENSION + Y == board.m_cells[X][Y]

&& FinalPosition<X, Y-1>::Is(board);

}

};

template <int X>

struct FinalPosition<X, 0>

{

static bool Is(const BoardState& board)

{

return 0 == X

|| X * DIMENSION == board.m_cells[X][0]

&& FinalPosition<X-1, DIMENSION-1>::Is(board);

}

};

template <int Y>

struct FinalPosition<-1, Y>

{

static bool Is(const BoardState&)

{

return true;

}

};

public:

bool IsFinalPositionCandidate()

{

return FinalPosition<DIMENSION-1, DIMENSION-2>::Is(*this);

}

Cell m_cells[DIMENSION][DIMENSION];

int m_emptyX, m_emptyY;

};

///Clase que resuelve el juego

class Solver

{

template <int X, int Y, bool edge>

struct DispatchStep

{

static bool Do(Solver* pSolver, int emptyX, int emptyY)

{

if (X == emptyX && Y == emptyY)

return pSolver->DistributeStep<X, Y, 0, 0, edge>();

return DispatchStep<X, Y-1, edge>::Do(pSolver, emptyX, emptyY);

}

};

template <int X, bool edge>

struct DispatchStep<X, 0, edge>

{

static bool Do(Solver* pSolver, int emptyX, int emptyY)

{

if (X == emptyX && 0 == emptyY)

return pSolver->DistributeStep<X, 0, 0, 0, edge>();

return DispatchStep<X-1, DIMENSION-1, edge>::Do(pSolver, emptyX, emptyY);

}

};

template <int Y, bool edge>

struct DispatchStep<-1, Y, edge>

{

static bool Do(Solver*, int, int)

{

return false;

}

};

template <int oldEmptyX, int oldEmptyY,

int emptyXOffset, int emptyYOffset, bool returning, bool edge, typename Next>

struct MakeStep

{

static bool Do (Solver* pSolver)

{

return pSolver->DoMakeStep<oldEmptyX, oldEmptyY,

emptyXOffset, emptyYOffset, Next>(Int2Type_<edge>());

}

};

template <int oldEmptyY, int emptyYOffset, bool returning, bool edge, typename Next>

struct MakeStep<0, oldEmptyY, -1, emptyYOffset, returning, edge, Next>

{

static bool Do (Solver* pSolver)

{

return Next::Do(pSolver);

}

};

template <int oldEmptyX, int emptyXOffset, bool returning, bool edge, typename Next>

struct MakeStep<oldEmptyX, 0, emptyXOffset, -1, returning, edge, Next>

{

static bool Do (Solver* pSolver)

{

return Next::Do(pSolver);

}

};

template <int oldEmptyY, int emptyYOffset, bool returning, bool edge, typename Next>

struct MakeStep<DIMENSION-1, oldEmptyY, 1, emptyYOffset, returning, edge, Next>

{

static bool Do (Solver* pSolver)

{

return Next::Do(pSolver);

}

};

template <int oldEmptyX, int emptyXOffset, bool returning, bool edge, typename Next>

struct MakeStep<oldEmptyX, DIMENSION-1, emptyXOffset, 1, returning, edge, Next>

{

static bool Do (Solver* pSolver)

{

return Next::Do(pSolver);

}

};

template <int oldEmptyX, int oldEmptyY,

int emptyXOffset, int emptyYOffset, bool edge, typename Next>

struct MakeStep<oldEmptyX, oldEmptyY,

emptyXOffset, emptyYOffset, true, edge, Next>

{

static bool Do (Solver* pSolver)

{

return Next::Do(pSolver);

}

};

struct DoNothing

{

static bool Do (Solver*) { return false; }

};

BoardState m_boardState;

deque<Move> m_solution;

int m_nDerivation;

bool m_bTopLeftBlank;

public:

Solver(bool bTopLeftBlank) : m_bTopLeftBlank(bTopLeftBlank) {}

void SetCell(int x, int y, int value)

{

m_boardState.m_cells[x][y] = Cell(m_bTopLeftBlank? value : value-1);

}

void SetBlank(int x, int y)

{

m_boardState.m_emptyX = x;

m_boardState.m_emptyY = y;

}

int GetOptimalSolution(deque<Move>& solution)

{

if (m_boardState.IsFinalPositionCandidate())

{

if ((m_bTopLeftBlank? 0 : DIMENSION - 1)

== m_boardState.m_emptyX == m_boardState.m_emptyY)

return 0;

}

if (!DispatchStep<DIMENSION-1, DIMENSION-1, true>::Do(

this, m_boardState.m_emptyX, m_boardState.m_emptyY))

{

int nDerivation = 0;

while (m_nDerivation = nDerivation,

!DispatchStep<DIMENSION-1, DIMENSION-1, false>::Do(

this, m_boardState.m_emptyX, m_boardState.m_emptyY))

{

++nDerivation;

}

solution = m_solution;

return solution.size();

}

private:

template <int emptyX, int emptyY,

int emptyXOffset, int emptyYOffset, bool edge>

bool DistributeStep()

{

return

MakeStep<emptyX, emptyY, 0, 1, 0 == emptyXOffset && -1 == emptyYOffset, edge,

MakeStep<emptyX, emptyY, 0, -1, 0 == emptyXOffset && 1 == emptyYOffset, edge,

MakeStep<emptyX, emptyY, 1, 0, -1 == emptyXOffset && 0 == emptyYOffset, edge,

MakeStep<emptyX, emptyY, -1, 0, 1 == emptyXOffset && 0 == emptyYOffset, edge,

DoNothing> > > > :: Do(this);

}

template <int oldEmptyX, int oldEmptyY,

int emptyXOffset, int emptyYOffset, typename Next>

bool DoMakeStep(Int2Type_<false>)

{

enum { newEmptyX = oldEmptyX + emptyXOffset };

enum { newEmptyY = oldEmptyY + emptyYOffset };

Cell cell = m_boardState.m_cells[newEmptyX][newEmptyY];

int manhattanChange = (emptyXOffset != 0)

? GetManhattanChange(cell / DIMENSION, oldEmptyX, emptyXOffset)

: GetManhattanChange(cell % DIMENSION, oldEmptyY, emptyYOffset);

if (manhattanChange > 0)

{

if (Next::Do(this))

return true;

m_boardState.m_cells[oldEmptyX][oldEmptyY] = cell;

if ( (--m_nDerivation >= 0)

? DistributeStep<newEmptyX, newEmptyY,

emptyXOffset, emptyYOffset, false>()

: DistributeStep<newEmptyX, newEmptyY,

emptyXOffset, emptyYOffset, true>())

goto found;

++m_nDerivation;

m_boardState.m_cells[newEmptyX][newEmptyY]

= m_boardState.m_cells[oldEmptyX][oldEmptyY];

}

else

{

m_boardState.m_cells[oldEmptyX][oldEmptyY] = cell;

if (DistributeStep<newEmptyX, newEmptyY,

emptyXOffset, emptyYOffset, false>())

goto found;

m_boardState.m_cells[newEmptyX][newEmptyY]

= m_boardState.m_cells[oldEmptyX][oldEmptyY];

if (Next::Do(this))

return true;

}

return false;

found:

m_solution.push_front(Move(newEmptyX, newEmptyY));

return true;

}

template <int oldEmptyX, int oldEmptyY,

int emptyXOffset, int emptyYOffset, typename Next>

bool DoMakeStep(Int2Type_<true>)

{

enum { newEmptyX = oldEmptyX + emptyXOffset };

enum { newEmptyY = oldEmptyY + emptyYOffset };

Cell cell = m_boardState.m_cells[newEmptyX][newEmptyY];

int manhattanChange = (emptyXOffset != 0)

? GetManhattanChange(cell / DIMENSION, oldEmptyX, emptyXOffset)

: GetManhattanChange(cell % DIMENSION, oldEmptyY, emptyYOffset);

if (manhattanChange < 0)

{

m_boardState.m_cells[oldEmptyX][oldEmptyY] = cell;

if (DistributeStep<newEmptyX, newEmptyY,

emptyXOffset, emptyYOffset, true>()

|| (m_bTopLeftBlank ? (0 == newEmptyX && 0 == newEmptyY)

: (DIMENSION-1 == newEmptyX && DIMENSION-1 == newEmptyY))

&& m_boardState.IsFinalPositionCandidate())

{

m_solution.push_front(Move(newEmptyX, newEmptyY));

return true;

}

m_boardState.m_cells[newEmptyX][newEmptyY]

= m_boardState.m_cells[oldEmptyX][oldEmptyY];

}

return Next::Do(this);

}

};

///Solucion volcada

struct DumpSolution

{

void operator()(const Move& move)

{

cout << move.m_x << ' ' << move.m_y << '\n';

}

};

///Dibuja la solucion

class DrawSolution

{

Cell m_cells[DIMENSION][DIMENSION];

int m_x, m_y;

public:

void SetCell(int x, int y, int value)

{

m_cells[x][y] = (Cell) value;

}

void SetBlank(int x, int y)

{

m_x = x;

m_y = y;

}

void operator()(const Move& move)

{

m_cells[m_x][m_y] = m_cells[move.m_x][move.m_y];

m_x = move.m_x;

m_y = move.m_y;

cout << '\n';

Dump();

}

void Dump()

{

for (int i = 0; i < DIMENSION; ++i)

{

for (int j = 0; j < DIMENSION; ++j)

{

cout << ' ';

if (i != m_x || j != m_y)

cout << setw(2) << (int) m_cells[i][j];

else

cout << " ";

}

cout << '\n';

}

};

///Programa principal

int main()

{

char** numeros[512];

char* texto = new char[512];

string hilera[16];

Solver solver(s_bTopLeftBlank);

DrawSolution drawSolution;

bool wasBlank = false;

bool resp;

cout << "Digite los numeros del 1-15 y para terminar presione \"_\" " << endl;

for (int i = 0; i < DIMENSION * DIMENSION; ++i)

{

resp = true;

while (resp){

cout << "Digite el " << i+1 <<" numero: ";

cin >> texto;

int num = atoi(texto);

if ( (num < 0) || (num > 15) ){

cout << "Error, el numero debe estar entre 1-15." << endl;

}

else {

resp = false;}

}

const char* pParam = texto;

int value = 0;

if (1 == sscanf(pParam, "%d", &value))

{

solver.SetCell(i / DIMENSION, i % DIMENSION, value);

drawSolution.SetCell(i / DIMENSION, i % DIMENSION, value);

}

else

{

if (wasBlank)

{

cerr << "Wrong number arguments: only one blank symbol expected.\n";

return EXIT_FAILURE;

}

solver.SetBlank(i / DIMENSION, i % DIMENSION);

drawSolution.SetBlank(i / DIMENSION, i % DIMENSION);

wasBlank = true;

}

deque<Move> solution;

clock_t start = clock();

int nSolution = solver.GetOptimalSolution(solution);

cout << "Resuelto en " << (double)(clock() - start) / CLOCKS_PER_SEC

<< " segundos. Numero de movimientos: " << nSolution <<"\n\n";

drawSolution.Dump();

for_each(solution.begin(), solution.end(), drawSolution);

cin.get();

cin >> texto;

return 0;}

Bibliografía:

H. M. Deitel-Deitel & Associates. C++ How to Program. Fifth Edition.  Prentice Hall.  January 05, 2005.

Bjarne Stroustrup. The C+ + Programming Language. Third Edition. AT&T labs Murray Hill, New Jersey.

http://aliakseis.livejournal.com/1155.html

http://www.di-mare.com/adolfo/cursos/2007-2/p2-ta-6.htm