Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
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>
#include <cassert>
using namespace std;
const int PAR_THRESHOLD=10;
struct Graph{
int nvertices;
vector<string> vert_names;
vector<vector<int> > neighbours;
};
void print_path(ostream &os,const Graph &g,const vector<int> path)
{
for (auto k:path)
os<<g.vert_names[k];
}
template <class CB>
void continue_tour_seq(const Graph &g,
vector<int> &path,
vector<char> &visited,
int remain,
CB &cb)
{
auto last = path.back();
for (auto n: g.neighbours[last]){
if (n==0 && remain==0){
#pragma omp critical
{
cb(path);
}
continue;
}
if (visited[n])
continue;
visited[n]=1;
path.emplace_back(n);
continue_tour_seq(g,path, visited,
remain-1,
cb);
visited[n]=0;
path.pop_back();
}
}
template <class CB>
void continue_tour_par(const Graph &g,
const vector<int> &path,
const vector<char> &visited,
int depth,int remain,
CB &cb)
{
assert(remain>0);
auto last = path.back();
for (auto n: g.neighbours[last]){
if (visited[n])
continue;
#pragma omp task default(shared) firstprivate(n)
{
auto nvisited=visited;
auto npath=path;
nvisited[n]=1;
npath.emplace_back(n);
if (depth<PAR_THRESHOLD){
continue_tour_par(g,npath, nvisited,
depth+1,remain-1,
cb);
}else{
continue_tour_seq(g,npath, nvisited,
remain-1,
cb);
}
}
}
#pragma omp taskwait
}
template <class CB>
void enumerate_tours(const Graph &g,CB &cb)
{
auto visited = vector<char>(g.nvertices,0);
vector<int> path;
visited[0] = true;
path.emplace_back(0);
#pragma omp parallel
{
#pragma omp single
{
continue_tour_par(g,path,visited,0,g.nvertices-1,cb);
}
}
}
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;
}
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';
}
unsigned long count;
auto printer =
[&g,&count](const vector<int> &p){
print_path(cout,g,p);cout<<'\n';
count++;
};
enumerate_tours(g,printer);
cout<<"\n\n Total tours = "<<count<<'\n';
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment