✅ Knight Probability in Chessboard || CPP/C++ || Detailed explanation with code
Explanation\nThe idea is, we have a knight and it has to move in 8 directions and it has k moves in  total. Also, in question it is given that, it will continue
**Explanation**\nThe idea is, we have a knight and it has to move in 8 directions and it has k moves in  total. Also, in question it is given that, it will continue moving until k becomes 0 or knight moves off the chessboard. And, we need to find the probabilitiy that knight remains on the board after it has stopped moving.\n\nNow, If you look at the problem, it generally talks about the path and exploration and stuff like that. Whenever, we talk related to exploring all the path then we should think about resursion.\n\nNow, we have decided that we are going to use recursion and we will be exploring all the paths. So, possible path for the knight is going to be given below, when the knight is at (x, y) from there it will move,\n```\n(x + 2, y + 1)\n(x + 1, y + 2)\n(x \u2013 1, y + 2)\n(x \u2013 2, y + 1)\n(x \u2013 2, y \u2013 1)\n(x \u2013 1, y \u2013 2)\n(x + 1, y \u2013 2)\n(x + 2, y \u2013 1)\n```\nin these many directions.\nNow, let\'s talk about the probability, Since knight has to move in 8 directions, for one  move of knight the probability will be 1/8.\n\n**Also, let\'s talk about the base case:**\n1. Check if the position is valid or not if not return 0.\n2. Check if k == 0 or not, if k is 0 then there is no movement from knight and Probability of knight on the borad is 1.\n\n**Code**\n**Recursive**\n```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        return helper(N, K, r, c);\n    }\n    \n    double helper(int N, int K, int row, int col){\n        \n        if(row < 0 || col < 0 || row >= N || col >= N) return 0.0;\n        \n        if(K == 0) return 1.0;\n        \n        double ans = helper(N, K-1, row+2, col+1) + helper(N, K-1, row+1, col+2) + \n                    helper(N, K-1, row-1, col+2) + helper(N, K-1, row-2, col+1) + \n                    helper(N, K-1, row-2, col-1) + helper(N, K-1, row-1, col-2) +\n                  helper(N, K-1, row+1, col-2) + helper(N, K-1, row+2, col-1);\n        \n        double result  = ans / 8.0;\n        return result;\n    }\n};\n```\n\n**Recursive + Memoization**\n***using matrix***\n```\nclass Solution {\npublic:\n    double knightProbability(int N, int K, int r, int c) {\n        vector<vector<vector<double>>> memo(N+1, vector<vector<double>>(N+1, vector<double>(K+1, -1)));\n        return helper(N, K, r, c, memo);\n    }\n    \n    double helper(int N, int K, int row, int col, vector<vector<vector<double>>>& memo){\n\n        if(row < 0 || col < 0 || row >= N || col >= N) return 0.0;\n        \n        if(K == 0) return 1.0;\n        \n        if(memo[row][col][K] != -1) return memo[row][col][K];\n        \n        double ans = \n            helper(N, K-1, row+2, col+1, memo) + helper(N, K-1, row+1, col+2, memo) +       \n            helper(N, K-1, row-1, col+2, memo) + helper(N, K-1, row-2, col+1, memo) + \n            helper(N, K-1, row-2, col-1, memo) + helper(N, K-1, row-1, col-2, memo) +\n            helper(N, K-1, row+1, col-2, memo) + helper(N, K-1, row+2, col-1, memo);\n        \n        double result  = ans / 8.0;\n        memo[row][col][K] = result;\n        return result;\n    }\n};\n```\n\n***using map***\n```\nclass Solution {\npublic:\n    unordered_map<string, double> mp;\n    double knightProbability(int N, int K, int r, int c) {\n        mp.clear();\n        return helper(N, K, r, c);\n    }\n    \n    double helper(int N, int K, int row, int col){\n\n        if(row < 0 || col < 0 || row >= N || col >= N) return 0.0;\n        \n        if(K == 0) return 1.0;\n        \n        string key = to_string(K) + "#" + to_string(row) + "#" + to_string(col);\n        if(mp.find(key) != mp.end()) return mp[key];\n        \n        double ans = helper(N, K-1, row+2, col+1) + helper(N, K-1, row+1, col+2) + \n                    helper(N, K-1, row-1, col+2) + helper(N, K-1, row-2, col+1) + \n                    helper(N, K-1, row-2, col-1) + helper(N, K-1, row-1, col-2) +\n                  helper(N, K-1, row+1, col-2) + helper(N, K-1, row+2, col-1);\n        \n        double result  = ans / 8.0;\n        mp[key] = result;\n        return result;\n    }\n};\n```\nThanks.\n**Happy Learning.**
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']