fork(11) download
copy 
  1. #include <string>
  2. #include <iostream>
  3. #include <stdexcept>
  4. #include <ctype.h>
  5. #include <utility>
  6. #include <vector>
  7. #include <queue>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. //
  13. // represents the position of a chess piece on a chess board in algebraic notation.
  14. // 
  15. class Position
  16. {
  17.  
  18. public:
  19.     //
  20.     // horizontal positions are known as rank and represented by letters A through H
  21.     // internally stored as capital letters, but we convert from lowercase if that was passed in the constructor
  22.     //
  23.     typedef char Rank;
  24.  
  25.     //
  26.     // vertical postion or file represented by numbers 1 through 8
  27.     // (actually stored as ascii values). 
  28.     //
  29.     typedef char File;
  30.  
  31.     //
  32.     // the Delta type is used to represent a move from  position
  33.     // can be a positive or negative offset for rank and file
  34.     //
  35.     struct Delta
  36.     {
  37.         Delta( int rankOffset, int fileOffset ) : rank(rankOffset), file(fileOffset) {}
  38.         int rank;
  39.         int file;
  40.     };
  41.  
  42.     //
  43.     // define maximum and minimum values for dimension of chessboard.
  44.     // we don't have to actually model a chessboard to solve this problem,
  45.     // however if we needed to deal with other pieces on the chessboard it might be useful to do so
  46.     //
  47.     static const Rank minRank = 'A';
  48.     static const Rank maxRank = 'H';
  49.     static const File minFile = '1';
  50.     static const File maxFile = '8';
  51.  
  52.     //
  53.     // default constructor initializes to "A1"
  54.     //
  55.     Position() : m_rank(minRank), m_file(minFile) {}
  56.  
  57.     //
  58.     // construct from a string as read from input
  59.     // PRECONDITION: pos is a 2 character string representing an chess position in algebraic notation
  60.     // may be uppercase or lowercase
  61.     //
  62.     Position( const char* strPos  )
  63.     {
  64.         if(!strPos)
  65.             throw std::invalid_argument( "strPos must point to a 2 character string in algebraic chess notaion" );
  66.  
  67.         Rank r = toupper(strPos[0]);
  68.         File f = strPos[1];
  69.  
  70.         if( isValidFile(f) && isValidRank(r) )
  71.         {
  72.             m_rank = r;
  73.             m_file = f;
  74.         }
  75.         else
  76.         {
  77.             throw std::invalid_argument( "rank and/or file are out of range" );
  78.         }
  79.     }
  80.  
  81.     //
  82.     // return true if its a legal move, ie: within the bounds of the chessboard
  83.     //
  84.     bool isValidMove( const Delta& delta ) const
  85.     {
  86.         return isValidRank( m_rank + delta.rank ) && isValidFile( m_file + delta.file);
  87.     }
  88.  
  89.     //
  90.     // move by the supplied delta
  91.     //
  92.     Position& move( const Delta& delta )
  93.     {
  94.         if ( isValidMove( delta) )
  95.         {
  96.             //
  97.             // we are relying on the property that ascii values are consecutive
  98.             // for consecutive numbers and letters, which makes the move calculation
  99.             // nice and easy
  100.             //
  101.             m_rank += delta.rank;
  102.             m_file += delta.file;
  103.         }
  104.         else
  105.         {
  106.             throw std::invalid_argument( "move is out of range" );
  107.         }
  108.  
  109.         return *this;
  110.     }
  111.  
  112.     //
  113.     // accessors for rank
  114.     //
  115.     Rank getRank() const
  116.     {
  117.         return m_rank;
  118.     }
  119.  
  120.     //
  121.     // accessors for file
  122.     //
  123.     File getFile() const
  124.     {
  125.         return m_file;
  126.     }
  127.  
  128.     //
  129.     // define equality operator which will be useful for determining when we have reached the goal
  130.     //
  131.     bool operator==(const Position &rhs) const
  132.     {
  133.         return m_rank == rhs.m_rank && m_file == rhs.m_file;
  134.     }
  135.  
  136.     //
  137.     // for completeness, define inequality operator 
  138.     //
  139.     bool operator!=(const Position &rhs) const
  140.     {
  141.         //
  142.         // use equality relationship to avoid duplicating code
  143.         //
  144.         return !( (*this) == rhs);
  145.     }
  146.  
  147.     //
  148.     // and why not an compound addition operator for moving positions by Deltas
  149.     //
  150.     Position& operator+=( const Delta &delta ) 
  151.     {
  152.         return move( delta );
  153.     }
  154.  
  155.     //
  156.     // once again for completeness we can define and addition operator using the above += definition
  157.     // returns a const Position so result cant be used as an lvalue
  158.     //
  159.     const Position operator+( const Delta& delta ) const
  160.     {
  161.         Position newPos = *this;
  162.         newPos += delta;
  163.         return newPos;
  164.     }
  165.  
  166.     //
  167.     // so we can display our positions
  168.     //
  169.     friend std::ostream& operator<< (std::ostream& stream, const Position& pos ) 
  170.     {
  171.         stream << pos.m_rank << pos.m_file;
  172.         return stream;
  173.     }
  174.  
  175.     //
  176.     // so we can read positions from standard input
  177.     //
  178.     friend std::istream& operator>> (std::istream& stream, Position& pos ) 
  179.     {
  180. 	string strPos;
  181. 	stream >> strPos;
  182. 	Position tempPos( strPos.c_str() );
  183. 	pos = tempPos;
  184.  
  185.         return stream;
  186.     }
  187.  
  188. private:
  189.  
  190.     //
  191.     // range check rank
  192.     //
  193.     bool isValidRank( Rank r ) const
  194.     {
  195.         return r <= maxRank && r >= minRank;
  196.     }
  197.  
  198.     //
  199.     // range check file
  200.     //
  201.     bool isValidFile( File f ) const
  202.     {
  203.         return f <= maxFile && f >= minFile;
  204.     }
  205.  
  206.     Rank m_rank;
  207.     File m_file;
  208.  
  209. };
  210.  
  211. //
  212. // base class representing chess pieces basic functionality
  213. //
  214. class ChessPiece
  215. {
  216.  
  217. protected:
  218.  
  219.     //
  220.     // we don't want anyone instantiating this class directly,
  221.     // they must derived from it and call initDeltas() to setup
  222.     // the allowable moves for the piece
  223.     //
  224.     ChessPiece( const Position& pos ) : m_currentPos(pos)
  225.     {}
  226.  
  227. public:
  228.  
  229.     //
  230.     // list of Deltas representing the directions and distances this piece is allowed to move
  231.     //
  232.     typedef vector<Position::Delta> Deltas;
  233.  
  234.     //
  235.     // return the rank and file offsets determining this pieces relative movements
  236.     //
  237.     const Deltas& getDeltas() const
  238.     {
  239.         return m_deltas;
  240.     }
  241.  
  242.     //
  243.     // list of positions used to represent where this piece can move to
  244.     //
  245.     typedef vector<Position> Moves;
  246.  
  247.     //
  248.     // returns a list of valid moves from the current position
  249.     //
  250.     const Moves& getValidMoves() const
  251.     {
  252.         if( !m_validMoves.size() )
  253.         {
  254.             //
  255.             // lazily calculate valid moves from current position
  256.             //
  257.             Deltas deltas = getDeltas();
  258.             for( Deltas::const_iterator i = getDeltas().begin(); i != getDeltas().end(); i++ )
  259.             {
  260.                 const Position::Delta& delta = *i;
  261.                 if( m_currentPos.isValidMove( delta ) )
  262.                 {
  263.                     Position newPos = m_currentPos + delta;
  264.                     m_validMoves.push_back( newPos );
  265.                 }
  266.             }
  267.         }
  268.         return m_validMoves;
  269.     }
  270.  
  271.     //
  272.     // return current position
  273.     //
  274.     const Position& getPosition() const
  275.     {
  276.         return m_currentPos;
  277.     }
  278.  
  279. protected:
  280.  
  281.     //
  282.     // helper so derived classes can initialize m_deltas from a
  283.     // plain old c style array
  284.     //
  285.     void initDeltas( const Position::Delta * d, size_t numberOfDeltas)
  286.     {
  287.         m_deltas = Deltas( d, d + numberOfDeltas );
  288.     }
  289.  
  290.     //
  291.     // current position
  292.     //
  293.     Position m_currentPos;
  294.  
  295.     //
  296.     // list of directions and distances the chess piece can move.
  297.     // Should be initialized by any derived classes
  298.     //
  299.     Deltas m_deltas;
  300.  
  301.     //
  302.     // all the moves in relation to the current position.
  303.     // it is defined as mutable to allow for lazy evaluation
  304.     //
  305.     mutable Moves m_validMoves;
  306.  
  307. };
  308.  
  309.  
  310. //
  311. // all valid moves for a knight
  312. //
  313. static Position::Delta deltas[] = {
  314.     Position::Delta(1,2), Position::Delta(2,1),
  315.     Position::Delta(2,-1), Position::Delta(1,-2),
  316.     Position::Delta(-2,-1), Position::Delta(-1,-2),
  317.     Position::Delta(-2,1), Position::Delta(-1,2)
  318. };
  319.  
  320. //
  321. // Knight is an instance of ChessPiece with movement deltas which allow it to move
  322. // 2 squares horizontaly and 1 square vertically and vice versa
  323. //
  324. class Knight : public ChessPiece
  325. {
  326.  
  327. public:
  328.  
  329.     Knight( const Position& pos) : ChessPiece(pos)
  330.     {
  331.         //
  332.         // setup the valid moves
  333.         //
  334.         initDeltas( deltas ,  sizeof(deltas)/sizeof(deltas[0]) );
  335.     }
  336.  
  337. };
  338.  
  339.  
  340. //
  341. // utility class for finding shortest path to goal utilizing Uniform Cost Search,
  342. // also known as Least Cost Search, a variation of Bredth First Search.
  343. // template argument must support operator= otherwise it wont compile ;)
  344. //
  345. template<class State>
  346. class UniformCostSearch
  347. {
  348. public:
  349.  
  350.     //
  351.     // path to our goal state is represented as a list of states
  352.     //
  353.     typedef vector<State> States;
  354.  
  355.     //
  356.     // abstract helper class which provide goal test function and
  357.     // successor states for the search
  358.     //
  359.     class SearchHelper
  360.     {
  361.     public:
  362.  
  363.         //
  364.         // override this function to return true if we have reached the goal
  365.         //
  366.         virtual bool isGoal( const State& s) const = 0;
  367.  
  368.         //
  369.         // override this function to return a list of successor states from the current state
  370.         //
  371.         virtual States getSuccessors( const State& s ) const = 0;
  372.  
  373.     };
  374.  
  375.     //
  376.     // constructor takes the start state and a helper function object
  377.     //
  378.     UniformCostSearch( const State& start, const SearchHelper& helper ) : m_start(start), m_helper(helper) {}
  379.  
  380.     //
  381.     // initiates a uniform cost search to find the shortest path to the goal state.
  382.     // if no path is found then it returns an empty list
  383.     //
  384.     States findShortestPathToGoal()
  385.     {
  386.  
  387.         //
  388.         // the frontier is an ordered list of paths we have blazed fro mthe start state (from shortest to longest),
  389.         // since every action has the same cost there is no need to use a priority queue
  390.         //
  391.         typedef queue<States> Frontier;
  392.  
  393.         //
  394.         // keep track of states which have already been explored.
  395.         // for larger searches a set would be better, but it requires State to support
  396.         // operator< so lets use a list even though search time is linear
  397.         //
  398.         typedef vector<State> Explored;
  399.  
  400.         //
  401.         // first check if we are already at the goal. If so we're done
  402.         //
  403.         if( m_helper.isGoal(m_start))
  404.         {
  405.             States result;
  406.             result.push_back(m_start);
  407.             return result;
  408.         }
  409.  
  410.         //
  411.         // set of states we have visited so far
  412.         //
  413.         Explored explored;
  414.  
  415.         //
  416.         // ordered list of paths which have already been blazed.
  417.         // Start with the path containing the start state only.
  418.         //
  419.         Frontier frontier;
  420.         States initialPath;
  421.         initialPath.push_back( m_start );
  422.         frontier.push(initialPath);
  423.  
  424.         //
  425.         // keep going whilst there are still unexplored paths
  426.         //
  427.         while( !frontier.empty() )
  428.         {
  429.             //
  430.             // expand the shortest path in the frontier first
  431.             //
  432.             States path = frontier.front();
  433.             frontier.pop();
  434.             State s = path.back();
  435.  
  436.             //
  437.             // now explore the successor states
  438.             //
  439.             States successors = m_helper.getSuccessors( s );
  440.             for( typename States::const_iterator i = successors.begin(); i != successors.end(); i++)
  441.             {
  442.                 const State& state = *i;
  443.  
  444.                 //
  445.                 // has this state been explored already?
  446.                 //
  447.                 if( find( explored.begin(), explored.end(), state ) == explored.end() )
  448.                 {
  449.                     //
  450.                     // no... mark it as explored
  451.                     //
  452.                     explored.push_back(state);
  453.                     //
  454.                     // construct a new path with the current state at the end
  455.                     //
  456.                     States exploredPath(path);
  457.                     exploredPath.push_back(state);
  458.                     if( m_helper.isGoal(state))
  459.                     {
  460.                         //
  461.                         // return the path to the goal
  462.                         //
  463.                         return exploredPath;
  464.                     }
  465.                     else
  466.                     {
  467.                         //
  468.                         // haven't found the path to the goal yet so add this path to the frontier and keep exploring
  469.                         //
  470.                         frontier.push( exploredPath );
  471.                     }
  472.                 }
  473.             }
  474.         }
  475.  
  476.         //
  477.         // if we got here we couldn't find a path to the goal
  478.         //
  479.         States emptyPath;
  480.         return emptyPath;
  481.     }
  482.  
  483.  
  484. private:
  485.  
  486.     //
  487.     // start state
  488.     //
  489.     State m_start;
  490.  
  491.     //
  492.     // search helper
  493.     //
  494.     const SearchHelper& m_helper;
  495.  
  496. };
  497.  
  498. //
  499. // this helper class is used to determine when we have reached the goal and also
  500. // generate the successor positions
  501. //
  502. class KnightsTravailHelper : public UniformCostSearch<Position>::SearchHelper
  503. {
  504. public:
  505.     KnightsTravailHelper( const Position& goal) : m_goal(goal) {}
  506.  
  507.     virtual bool isGoal( const Position& s) const
  508.     {
  509.         return s == m_goal;
  510.     }
  511.  
  512.     virtual UniformCostSearch<Position>::States getSuccessors( const Position& s ) const
  513.     {
  514.         Knight theKnight(s);
  515.         return theKnight.getValidMoves();
  516.     }
  517.  
  518. private:
  519.     Position m_goal;
  520. };
  521.  
  522. void solveKnightsTravail( const Position& start, const Position& end)
  523. {
  524.     Position posStart(start), posEnd(end);
  525.     KnightsTravailHelper helper(posEnd);
  526.  
  527.     UniformCostSearch<Position> solver( posStart, helper );
  528.  
  529.     UniformCostSearch<Position>::States result = solver.findShortestPathToGoal();
  530.  
  531.     for(UniformCostSearch<Position>::States::const_iterator i = result.begin(); i != result.end(); i++)
  532.     {
  533.             cout << *i << " ";
  534.     }
  535.  
  536.     cout << endl;
  537. }
  538.  
  539.  
  540.  
  541. int main()
  542. {
  543.  
  544.     Position start, end;
  545.  
  546.     try
  547.     {
  548.         cin >> start >> end;    
  549.         solveKnightsTravail( start, end );         
  550.     }
  551.     catch( exception& ex)
  552.     {
  553.         ///
  554.         // something bad happened - probably invalid arguments
  555.         //
  556.         cout << "error: " << ex.what() << endl;
  557.         return 1;
  558.     }
  559.  
  560.     return 0;
  561. }
Success #stdin #stdout 0.01s 2872KB
comments (?)
stdin
copy 
A1 H8
stdout
copy 
A1 B3 C5 D7 F8 G6 H8
https://ideone.com/B4o2c
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!