דוגמה למימוש חידת מסע הפרש ב-C++

נכתב עבור הערך חידת מסע הפרש בויקיפדיה.

// By Yavhush for The Hebrew Wikipedia

#include <iostream> 
#include <vector>
using namespace std; 

int moves[8][2] = {
  {1,2},{2,1}, 
  {-1,-2},{-2,-1}, 
  {-1,2},{-2,1}, 
  {1,-2},{2,-1}
}; 

class Knight {
  vector<vector<int> > _board;
  const int _size,_size2; 
  void solve(int i, int j, int d) {
     _board[i][j] = d; 
    if (d== _size2) {
      print(); 
      cout << "Another solution? (y/n) "; 
      char c; 
      cin >> c; 
      if(c == 'n') 
        exit(0);
      cout << '\n'; 
      _board[i][j] = 0; 
      return; // backtracking 
    }
    for(int k=0; k < 8; ++k) {
      int i1 = i + moves[k][0]; 
      int j1 = j + moves[k][1]; 
      if((i1 >= 0) && (i1 < _size) && (j1 >= 0) && (j1 < _size) && (_board[i1][j1] == 0))
        solve(i1,j1,d+1);
    }
    _board[i][j] = 0; // backtracking 
  }

  void print() {
    for(int i=0; i<_size; ++i) {
      for(int j=0; j<_size; ++j)
        cout << _board[i][j] << '\t'; 
      cout << '\n'; 
    }
  }
public:
  Knight(int size): _size(size),_size2(size*size),_board(size,vector<int>(size)) {
  }

  void solve () {
    for(int i=0; i<_size; ++i)
      for(int j=0; j<_size; ++j)
        solve(i,j,1);
  }

}; 

int main() {
  Knight k(5); // try 6 also 
  k.solve();
  return 0;
}