Dear Brethren, I was trying out this Google CodeJam 2019 round 1A problem PYLON, https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e03#analysis

I devised a DFS based backtracking solution, the problem is I donot know how to keep track of visited states in an efficient manner. The way I am doing is right now, I am starting from a random state and I am doing a DFS traversal and each time I push a node on to the stack I make sure it is not something we have already encountered on the path, by keeping track of a linked list! So for every update onto the I am doing a linked list traversal all the way to the root.

I am able to solve test case 1, but cannot solve test case 2. Please suggest if it is possible to do the backtracking more efficiently. Thank you!

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
struct Node {
	Node* par;
	pair<int, int> vl;
	int cnt;
};
void tracePtr(Node* nd) {
    vector<pair<int, int>> v;
	
  	while(nd) {
		v.push_back(nd->vl);
		nd = nd->par;
	}
	cout<<"POSSIBLE"<<endl;
	for (int i=v.size()-1; i >= 0; --i) {
	   cout<<v[i].first+1 << " "<<v[i].second+1<<endl;
	}
	
}
int main() {
	int t;
	cin >> t;
	for (int tt = 1; tt <= t; ++tt) {
		int nr, nc;
		cin >> nr >> nc;
		bool fnd=false;
		cout << "Case #"<<tt<<": ";
		for (int r=0; r< nr && !fnd; ++r) {
		for(int c=0; c < nc && !fnd; ++c) {
		   stack<Node*> st;
		   Node* nd = new Node;
		   nd->par=nullptr;
		   nd->vl.first=r;
		   nd->vl.second=c;
		   nd->cnt=1;
		   st.push(nd);
		   while(!st.empty()) {

			auto cur=st.top();
			st.pop();
     			//	cout << cur->cnt<< st.size() <<endl;

			if (cur->cnt == nr*nc) {
				fnd=true;
				tracePtr(cur);
				break;
			}
			for (int rr=0;rr < nr;++rr) {
			   if (rr == cur->vl.first) {
				continue;
			  }
  		       for (int cc=0; cc < nc; ++cc) {
			    if (cc == cur->vl.second) {
				continue;
			    }
 			if (((rr+cc) != (cur->vl.first+cur->vl.second)) && 
				((rr-cc) != (cur->vl.first - cur->vl.second))) {

								
					bool valid =true;
					auto curr = cur;
					while(curr) {
					if ((curr->vl.first == rr) && (curr->vl.second == cc)) {
			valid =false;
		}
		curr = curr->par;
	}
	if (valid) {
		Node* nd = new Node;
		nd->par=cur;
	        nd->vl.first=rr;
		nd->vl.second=cc;
	        nd->cnt=cur->cnt+1;
  		st.push(nd);
								}
								
							}
						}
					}
				}
			}
		}
               if (!fnd) {
			 cout << "IMPOSSIBLE"<<endl;
		}
	}
	// your code goes here
	return 0;
}