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))) {
							//	cout << "Here"<<endl;
								
								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;
}