Hello,

I am learning to apply memoization technique but not able to figure it out. My brute force recursive back tracking solution gives correct answer but then times out quickly. I tried to search answer to this question but then I am not able to understand anything. could you please help me in this regards? I have attached my solution

Problem link below https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=802

Thanks in advance

include <bits/stdc++.h>

using namespace std;

using row_t = vector; using grid_t = vector;

bool is_ok(const grid_t &grid, int p, int q) { for(int i = p-1, j = q-1; i >= 0 && j >= 0; --i, --j) { if(grid[i][j]) { return false; } }

for(int i = p+1, j = q+1; i < grid.size() && j < grid[i].size(); ++i, ++j) { if(grid[i][j]) { return false; } }

for(int i = p-1, j = q+1; i >= 0 && j < grid[i].size(); --i, ++j) { if(grid[i][j]) { return false; } }

for(int i = p+1, j = q+1; i < grid.size() && j < grid[i].size(); ++i, ++j) { if(grid[i][j]) { return false; } } return true; }

void dfs(int p, int q, int k, grid_t &grid, int &cnt, int &total_cnt) { if(q == grid.size()) { q = 0; ++p; }

for(int i = p; i < grid.size(); ++i) { for(int j = q; j < grid[i].size(); ++j) { grid[i][j] = true; if(is_ok(grid, i, j)) { ++cnt; if(cnt == k) { ++total_cnt; } else { dfs(i, j+1, k, grid, cnt, total_cnt); } --cnt;
} grid[i][j] = false; } q = 0; } }

int main() { while(true) { int n, k; cin >> n >> k; if(n == 0 && k == 0) { break; }

grid_t grid(n, row_t(n, false));
int cnt = 0;
int total_cnt = 0;
dfs(0,0, k, grid, cnt, total_cnt);
cout << total_cnt << "\n";

} return 0; }