Solitaire Puzzle with Backtracking

/*=============================================================================

	Solitaire.h - Header file for Solitaire.cpp
	Copyright � 2000 Paolo Martinoli

	This file is part of Solitaire Puzzle.

	LICENSE - TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
	You may copy and distribute verbatim or modified copies of this source
	code in respect of the following conditions:
	-  you must keep intact this notice and all the other notices that refer
	to the copyright of the author and to the absence of any warranty;
	-  you must cause the modified files to carry prominent notices stating
	that you changed the files and the date of any change.

	This program is distributed "AS IS" WITHOUT WARRANTY OF ANY KIND, either
	express or implied, including, but not limited to, the implied warranties
	of merchantability and fitness for a particular purpose.

	For comments, questions or suggestions please write to:
	Paolo Martinoli
	pmartinoli@programmer.net
	Via Valsolda, 169 - 00141 Rome (Italy)

=============================================================================*/

#if !defined(_SOLITAIRE_H_INCLUDED_)
#define _SOLITAIRE_H_INCLUDED_


#undef OUT


class Move : public Step, public CObject
{
public:
	Move();
	
	// PRE: i and j between 1 and 7
	// PRE: dir between 0 and 3
	Move(int i, int j, int dir);

	Move(const Move& move);
	virtual ~Move();

	int i() const;
	int j() const;
	int dir() const;

	// POST: ignore m_symms
	bool operator==(const Move& move) const;
	bool operator!=(const Move& move) const;

private:
	struct Symms
	{
		bool horz;
		bool vert;
		bool diagAsc;
		bool diagDesc;

		Symms(bool symm = false) : horz(symm), vert(symm), diagAsc(symm), diagDesc(symm) {}
		Symms(const Symms& symms) : horz(symms.horz), vert(symms.vert), diagAsc(symms.diagAsc), diagDesc(symms.diagDesc) {}
	};

	int m_i, m_j; // between 1 and 7
	int m_dir; // between 0 and 3 (right, down, left, up)
	Symms m_symms;

	// PRE: i and j between 1 and 7
	// PRE: dir between 0 and 3
	Move(int i, int j, int dir, Symms symms);


// === methods overridden from class CObject
public:
	virtual void Serialize(CArchive& ar);


friend class Solitaire;
};


class Solitaire : public Backtrack
{
public:
	enum Square
	{
		OUT,
		HOLE,
		PEG
	};

	typedef Square Board[9][9];

	Solitaire();
	virtual ~Solitaire();

	// POST: from_i, from_j, middle_i, middle_j, to_i and to_j between 1 and 7
	void undoMove(int& from_i, int& from_j, int& middle_i, int& middle_j, int& to_i, int& to_j);

	// POST: from_i, from_j, middle_i, middle_j, to_i and to_j between 1 and 7
	// POST: returns false if the solution hasn't been searched yet, if there is no solution or if the game is already solved (only one peg left)
	// POST: when false is returned, from_i, from_j, middle_i, middle_j, to_i and to_j are not set
	bool doRightMove(int& from_i, int& from_j, int& middle_i, int& middle_j, int& to_i, int& to_j);

	// PRE: shiftDir between 0 and 3
	void setShiftDir(int shiftDir);

	// PRE: i and j between 1 and 7
	// POST: returns false if ma_board[i][j] == OUT
	bool togglePeg(int i, int j);

	// PRE: from_i and from_j between 1 and 7
	// PRE: to_i and to_j between 1 and 7
	// PRE: ma_board[from_i][from_j] == PEG
	// POST: middle_i and middle_j between 1 and 7
	// POST: dir between 0 and 3
	// POST: returns true if (from_i, from_j, to_i, to_j) is a valid move
	// POST: when false is returned, middle_i, middle_j and dir are not set
	bool checkMove(int from_i, int from_j, int to_i, int to_j, int& middle_i, int& middle_j, int& dir) const;

	void solve();
	const Board *board(bool backup = false) const;
	void doMove(const Move *pc_move);
	bool noMoves() const;
	bool validSolution() const;
	bool noSolution() const;
	int getShiftDir() const;

protected:
	Board m_board;
	int m_numPegs;
	Stack<Move> m_solution;
	bool m_validSolution;

	void reset();

private:
	Board m_backupBoard;
	Stack<Move> m_moves;
	int m_shiftDir; // between 0 and 3

	// PRE: dir between 0 and 3
	// POST: move_i and move_j between -1 and 1
	inline void moveDir(int dir, int& move_i, int& move_j) const;

	// PRE: i and j between 1 and 7
	// PRE: ma_board[i][j] == PEG
	// PRE: dir between 0 and 3
	// POST: returns true if (i, j, dir) is a valid move
	inline bool checkMove(int i, int j, int dir) const;

	void clear();
	void init();
	void clearMoves();
	void clearSolution();


// === methods overridden from class Backtrack
private:
	// POST: if no step is possible, returns NULL
	virtual Step *firstStep() const;

	// PRE: p_step not NULL
	// POST: if no next step is possible, returns false and leaves p_step unchanged
	virtual bool nextStep(Step *p_step) const;

	// PRE: pc_step not NULL
	virtual void doStep(const Step *pc_step);
	virtual void undoStep(const Step *pc_step);

	// PRE: pc_step not NULL
	// PRE: level >= 1
	virtual void saveStep(const Step *pc_step, int level);

	virtual bool solved() const;
};


#endif