Knight's Tour using OpenMP

knights_tour.cc

/*
A multi-threaded brute-force search for closed Knight's tours (used OpenMP)

Usage: knights_tours [m] [n]
 to search for tour on a m x n board
 rows are denoted by letters A.., columns by numbers 0..

Compile with
  g++ -O3 -Wall -std=c++11 -fopenmp    knight_tours.cc   -o knight_tours


Jyotirmoy Bhattacharya, 2015-04-22
*/


#include <vector>
#include <iostream>
#include <iterator>
#include <cstdlib>
#include <string>
#include <sstream>
using namespace std;

// General code for brute-force search for Hamiltonian circuits

struct Graph{
  int nvertices; //No. of vertices
  vector<string> vert_names; //Human readable name for each vertex
  vector<vector<int> > neighbours; //Neighbours of each vertex
};

// Pretty print a path given as a vector of vertex indices
void print_path(ostream &os,const Graph &g,const vector<int> path)
{
  for (auto k:path)
    os<<g.vert_names[k];
}

// Try to extend a path towards a Hamiltonian circuit
// Return a count of the number of circuits found
template <class CB>
unsigned long continue_tour(const Graph &g,
                            const vector<int> &path, //Path so var
                            const vector<char> &visited, // 1 for visited, 0 for not visited
                            int depth,int remain, //How may vertices, how many remain
                            CB &cb // We will call cb(path) if we find a circuit
                            )
{
  auto last = path.back();
  unsigned long count=0;

#pragma omp parallel for reduction(+:count) if (depth==4)
  for (size_t i=0;i<g.neighbours[last].size();i++){
    auto n = g.neighbours[last][i];
    
    if (n==0 && remain==0){ //Found a circuit
      #pragma omp critical
      {
        cb(path);
      }
      count++;
      continue;
    }

    if (visited[n])
      continue;
      
    vector<char> n_visited(visited);
    vector<int> n_path(path);
    n_visited[n] = 1;
    n_path.emplace_back(n);
    count += continue_tour(g,n_path, n_visited,
                           depth+1,remain-1,
                           cb);
  }
  return count;
}
    
// Enumerate all Hamiltonian circuits in a graph
// We call cb(path) for each circuit found
// The return value is the number of circuits found
template <class CB>
unsigned long enumerate_tours(const Graph &g,CB &cb)
{
  auto visited = vector<char>(g.nvertices,0);
  vector<int> path;
  visited[0] = true;
  path.emplace_back(0);
  return continue_tour(g,path,visited,0,g.nvertices-1,cb);
}
             
// This part builds the graphs for the Knight's Tour problem
struct Knight_Moves {
  int x;
  int y;
};

vector<Knight_Moves> valid_moves =
  { {2,1},
    {2,-1},
    {-2,1},
    {-2,-1},
    {1,2},
    {1,-2},
    {-1,2},
    {-1,-2}};

Graph make_chess_graph(int m,int n)
{
  Graph g;
  g.nvertices = m*n;
  g.vert_names.resize(m*n);
  g.neighbours.resize(m*n);
  for (auto i=0;i<m;i++){
    for (auto j=0;j<n;j++){
      auto k = i*n+j;
      ostringstream s;
      s<<char(i+'A')<<j;
      g.vert_names.at(k) = s.str();
      for (auto &mv: valid_moves){
        auto nx = i+mv.x;
        auto ny = j+mv.y;
        if (nx>=0 && nx<m && ny>=0 && ny<n)
          g.neighbours.at(k).emplace_back(nx*n+ny);
      }
    }
  }
  return g;
}

// The driver
int main(int argc,char *argv[])
{
  if (argc!=3){
    cerr << "Usage: knight_tours [m] [n]";
    return 1;
  }

  int m = atoi(argv[1]);
  int n = atoi(argv[2]);

  if (m<1 || n<1){
    cerr << "Dimensions must be greater than 0";
    return 2;
  }

  auto g = make_chess_graph(m,n);
  for (auto i=0;i<g.nvertices;i++){
    cout<<g.vert_names[i]<<": ";
    for (auto k: g.neighbours[i]){
      cout<<g.vert_names[k]<<",";
    }
    cout<<'\n';
  }
  auto printer =
    [&g](const vector<int> &p){
    print_path(cout,g,p);
    cout<<'\n';
  };
  unsigned long count = enumerate_tours(g,printer);
  cout<<"\n\n Total tours = "<<count<<'\n';
  return 0;
}