{"id":342,"date":"2024-02-01T19:12:40","date_gmt":"2024-02-01T19:12:40","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=342"},"modified":"2025-01-14T19:07:54","modified_gmt":"2025-01-14T19:07:54","slug":"backtracking","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=342","title":{"rendered":"Backtracking"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li><strong><a href=\"#back\" data-type=\"internal\" data-id=\"#back\">How does back tracking work?<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#queen\" data-type=\"internal\" data-id=\"#queen\">How to solve the N Queen problem by backtracking?<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#subset\" data-type=\"internal\" data-id=\"#subset\">How to solve the subset sum problem(or Sum of Subsets) by backtracking?<\/a><\/strong><\/li>\n\n\n\n<li><strong><a href=\"#graph\" data-type=\"internal\" data-id=\"#graph\">How to solve the graph colouring problem by backtracking?<\/a><\/strong><\/li>\n\n\n\n<li id=\"Rate\"><strong><a href=\"#Rat\" data-type=\"internal\" data-id=\"#Rat\">Rat in a Maze problem-solving by backtracking<\/a><\/strong><\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-large back\" id=\"back\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-1024x576.jpg\" alt=\"\" class=\"wp-image-343\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-1-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-1024x576.jpg\" alt=\"\" class=\"wp-image-344\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-2-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-1024x576.jpg\" alt=\"\" class=\"wp-image-345\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-3-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-1024x576.jpg\" alt=\"\" class=\"wp-image-346\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit-2_BACK-TRACKING-4-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"queen\"><strong>Solving N Queen problem by Backtracking<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"729\" height=\"1024\" data-id=\"1437\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen1-729x1024.jpeg\" alt=\"\" class=\"wp-image-1437\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen1-729x1024.jpeg 729w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen1-214x300.jpeg 214w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen1-768x1078.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen1.jpeg 1060w\" sizes=\"auto, (max-width: 729px) 100vw, 729px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"736\" height=\"1024\" data-id=\"1438\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2-736x1024.jpeg\" alt=\"\" class=\"wp-image-1438\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2-736x1024.jpeg 736w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2-216x300.jpeg 216w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2-768x1069.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2-1104x1536.jpeg 1104w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/NQueen2.jpeg 1150w\" sizes=\"auto, (max-width: 736px) 100vw, 736px\" \/><\/figure>\n<\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"909\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2-909x1024.jpeg\" alt=\"\" class=\"wp-image-1346\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2-909x1024.jpeg 909w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2-266x300.jpeg 266w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2-768x865.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2-1364x1536.jpeg 1364w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-2.jpeg 1421w\" sizes=\"auto, (max-width: 909px) 100vw, 909px\" \/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/<strong> C program : Backtracking solution for N-Queen problem   <\/strong>\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n#include &lt;stdbool.h&gt;\n\n\/\/ Function to add the current solution to the answer list\nvoid addSolution(int*** ans, int** board, int* solutionCount, int n) {\n    (*solutionCount)++;\n    *ans = (int**) realloc(*ans, (*solutionCount) * sizeof(int*));\n    (*ans)&#91;*solutionCount - 1] = (int*) malloc(n * n * sizeof(int));\n\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            (*ans)&#91;*solutionCount - 1]&#91;i * n + j] = board&#91;i]&#91;j];\n        }\n    }\n}\n\n\/\/ Function to check if it is safe to place a queen at board&#91;row]&#91;col]\nbool isSafe(int row, int col, int** board, int n) {\n    int x = row, y = col;\n\n    \/\/ Check the left row\n    while (y &gt;= 0) {\n        if (board&#91;x]&#91;y] == 1)\n            return false;\n        y--;\n    }\n\n    \/\/ Check the upper left diagonal\n    x = row, y = col;\n    while (x &gt;= 0 &amp;&amp; y &gt;= 0) {\n        if (board&#91;x]&#91;y] == 1)\n            return false;\n        x--;\n        y--;\n    }\n\n    \/\/ Check the lower left diagonal\n    x = row, y = col;\n    while (x &lt; n &amp;&amp; y &gt;= 0) {\n        if (board&#91;x]&#91;y] == 1)\n            return false;\n        x++;\n        y--;\n    }\n\n    return true;\n}\n\n\/\/ Function to solve the N-Queens problem\nvoid solve(int col, int*** ans, int** board, int* solutionCount, int n) {\n    if (col == n) {\n        addSolution(ans, board, solutionCount, n);\n        return;\n    }\n\n    for (int row = 0; row &lt; n; row++) {\n        if (isSafe(row, col, board, n)) {\n            \/\/ Place queen if it's safe\n            board&#91;row]&#91;col] = 1;\n            solve(col + 1, ans, board, solutionCount, n);\n            \/\/ Backtrack\n            board&#91;row]&#91;col] = 0;\n        }\n    }\n}\n\n\/\/ Function to print the solutions\nvoid printSolutions(int** solutions, int solutionCount, int n) {\n    for (int k = 0; k &lt; solutionCount; k++) {\n        printf(\"Solution %d:\\n\", k + 1);\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = 0; j &lt; n; j++) {\n                printf(\"%c \", solutions&#91;k]&#91;i * n + j] == 1 ? 'Q' : '.');\n            }\n            printf(\"\\n\");\n        }\n        printf(\"\\n\");\n    }\n}\n\n\/\/ Main function to find all N-Queens solutions\nint main() {\n    int n;\n    printf(\"Enter the value of N: \");\n    scanf(\"%d\", &amp;n);\n\n    \/\/ Allocate memory for the board\n    int** board = (int**) malloc(n * sizeof(int*));\n    for (int i = 0; i &lt; n; i++) {\n        board&#91;i] = (int*) calloc(n, sizeof(int));\n    }\n\n    \/\/ Initialize solution list\n    int** solutions = NULL;\n    int solutionCount = 0;\n\n    \/\/ Solve the problem\n    solve(0, &amp;solutions, board, &amp;solutionCount, n);\n\n    if (solutionCount == 0) {\n        printf(\"No solutions exist for N = %d.\\n\", n);\n    } else {\n        printf(\"Total solutions for N = %d: %d\\n\\n\", n, solutionCount);\n        printSolutions(solutions, solutionCount, n);\n    }\n\n    \/\/ Free allocated memory\n    for (int i = 0; i &lt; n; i++) {\n        free(board&#91;i]);\n    }\n    free(board);\n\n    for (int i = 0; i &lt; solutionCount; i++) {\n        free(solutions&#91;i]);\n    }\n    free(solutions);\n\n    return 0;\n}\n<strong>Output :<\/strong>\nEnter the value of N: 4\nTotal solutions for N = 4: 2\n\nSolution 1:\n. . Q .\nQ . . .\n. . . Q\n. Q . .\n\nSolution 2:\n. Q . .\n. . . Q\nQ . . .\n. . Q .\n\n\nProcess returned 0 (0x0)   execution time : 2.579 s\nPress any key to continue.<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"744\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1-744x1024.jpeg\" alt=\"\" class=\"wp-image-1342\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1-744x1024.jpeg 744w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1-218x300.jpeg 218w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1-768x1057.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1-1116x1536.jpeg 1116w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-10-at-14.31.33-1.jpeg 1163w\" sizes=\"auto, (max-width: 744px) 100vw, 744px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solving Subset sum problem(or Sum of Subsets) by Backtracking<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-2 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"698\" height=\"1024\" data-id=\"1432\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3-698x1024.jpeg\" alt=\"\" class=\"wp-image-1432\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3-698x1024.jpeg 698w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3-205x300.jpeg 205w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3-768x1126.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3-1047x1536.jpeg 1047w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1SUBSETSUM3.jpeg 1091w\" sizes=\"auto, (max-width: 698px) 100vw, 698px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"735\" height=\"1024\" data-id=\"1433\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2-735x1024.jpeg\" alt=\"\" class=\"wp-image-1433\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2-735x1024.jpeg 735w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2-215x300.jpeg 215w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2-768x1070.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2-1103x1536.jpeg 1103w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2SUBSETSUM2.jpeg 1140w\" sizes=\"auto, (max-width: 735px) 100vw, 735px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"718\" height=\"1024\" data-id=\"1435\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1-718x1024.jpeg\" alt=\"\" class=\"wp-image-1435\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1-718x1024.jpeg 718w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1-210x300.jpeg 210w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1-768x1095.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1-1077x1536.jpeg 1077w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3SUSETSUM1-1.jpeg 1122w\" sizes=\"auto, (max-width: 718px) 100vw, 718px\" \/><\/figure>\n<\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"graph\"><strong>Solving graph colouring problem by back tracking<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-1024x576.jpg\" alt=\"\" class=\"wp-image-354\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-2-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-3 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" data-id=\"1441\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1-3.jpg\" alt=\"\" class=\"wp-image-1441\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1-3.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1-3-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/1-3-768x432.jpg 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" data-id=\"1442\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2-2.jpg\" alt=\"\" class=\"wp-image-1442\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2-2.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2-2-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/2-2-768x432.jpg 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-1024x576.jpg\" alt=\"\" class=\"wp-image-360\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-1024x576.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-768x432.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-1536x864.jpg 1536w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/02\/Unit2_Graph-colouring-problem-using-backtracking-8-2048x1152.jpg 2048w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-1 wp-block-columns-is-layout-flex\" id=\"subset\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-4 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3-3.jpg\" alt=\"\" class=\"wp-image-1445\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3-3.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3-3-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/3-3-768x432.jpg 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4-2.jpg\" alt=\"\" class=\"wp-image-1446\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4-2.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4-2-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/4-2-768x432.jpg 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5-2.jpg\" alt=\"\" class=\"wp-image-1447\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5-2.jpg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5-2-300x169.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/5-2-768x432.jpg 768w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/figure>\n<\/div>\n<\/div>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc01\ud835\udc00\ud835\udc02\ud835\udc0a\ud835\udc13\ud835\udc11\ud835\udc00\ud835\udc02\ud835\udc0a\ud835\udc08\ud835\udc0d\ud835\udc06|| \ud835\udc0d \ud835\udc10\ud835\udc2e\ud835\udc1e\ud835\udc1e\ud835\udc27\ud835\udc2c || \ud835\udc12\ud835\udc2e\ud835\udc1b\ud835\udc2c\ud835\udc1e\ud835\udc2d \ud835\udc12\ud835\udc2e\ud835\udc26 || \ud835\udc06\ud835\udc2b\ud835\udc1a\ud835\udc29\ud835\udc21 \ud835\udc02\ud835\udc28\ud835\udc25\ud835\udc28\ud835\udc2b\ud835\udc22\ud835\udc27\ud835\udc20\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/Hvgu1E4riLE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"Rat\"><strong>Rat in a Maze problem-solving by backtracking<\/strong><\/h2>\n\n\n\n<p>The <strong>Rat in a Maze<\/strong> problem is a classic backtracking problem where a rat is placed in a maze and needs to find a path to reach the destination. The maze is represented by a grid of cells, where some cells are blocked, and others are open for movement. The goal is to determine all possible paths or at least one path from the source (top-left corner) to the destination (bottom-right corner).<\/p>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-5 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"766\" height=\"1024\" data-id=\"1426\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.05.20-766x1024.jpeg\" alt=\"\" class=\"wp-image-1426\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.05.20-766x1024.jpeg 766w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.05.20-224x300.jpeg 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.05.20-768x1027.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.05.20.jpeg 957w\" sizes=\"auto, (max-width: 766px) 100vw, 766px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"856\" height=\"1024\" data-id=\"1427\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.04.45-856x1024.jpeg\" alt=\"\" class=\"wp-image-1427\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.04.45-856x1024.jpeg 856w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.04.45-251x300.jpeg 251w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.04.45-768x919.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2025\/01\/WhatsApp-Image-2025-01-14-at-23.04.45.jpeg 1070w\" sizes=\"auto, (max-width: 856px) 100vw, 856px\" \/><\/figure>\n<\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code><strong>\/\/C++ backtracking solution for  Rat in a Maze problem.<\/strong>\n#include &lt;iostream&gt; \/\/ Include the iostream library for input\/output operations\n#include &lt;vector&gt;   \/\/ Include the vector library for using dynamic arrays\nusing namespace std;\n\/\/ Checks if a given cell (x, y) is valid for the rat to move to.\nbool isSafe(int x, int y, int n, vector&lt;vector&lt;int&gt;&gt;&amp; maze, vector&lt;vector&lt;int&gt;&gt;&amp; sol) {\n    return (x &gt;= 0 &amp;&amp; x &lt; n &amp;&amp; y &gt;= 0 &amp;&amp; y &lt; n &amp;&amp; maze&#91;x]&#91;y] == 1 &amp;&amp; sol&#91;x]&#91;y] == 0);\n}\n\/\/ Recursive function to solve the maze\nbool solveMaze(int x, int y, int n, vector&lt;vector&lt;int&gt;&gt;&amp; maze, vector&lt;vector&lt;int&gt;&gt;&amp; sol, vector&lt;pair&lt;int, int&gt;&gt;&amp; path) {\n    \/\/ Base case: Reached the destination\n    if (x == n - 1 &amp;&amp; y == n - 1) {\n        sol&#91;x]&#91;y] = 1; \/\/ Mark destination as visited\n        path.push_back({x, y}); \/\/ Add destination coordinates to the path\n        return true;\n    }\n    \/\/ Check if the current cell is valid\n    if (isSafe(x, y, n, maze, sol)) {\n        \/\/ Mark current cell as visited\n        sol&#91;x]&#91;y] = 1;\n        path.push_back({x, y}); \/\/ Add current coordinates to the path\n\n        \/\/ Explore all possible directions (right, down, left, up)\n        if (solveMaze(x + 1, y, n, maze, sol, path) ||\n            solveMaze(x, y + 1, n, maze, sol, path) ||\n            solveMaze(x - 1, y, n, maze, sol, path) ||\n            solveMaze(x, y - 1, n, maze, sol, path)) {\n            return true; \/\/ If any direction leads to a solution, return true\n        }\n        \/\/ Backtrack (if no solution found in any direction)\n        sol&#91;x]&#91;y] = 0; \/\/ Unmark the cell\n        path.pop_back(); \/\/ Remove coordinates from the path\n        return false;\n    }\n\n    return false; \/\/ If the cell is not safe, return false\n}\n\/\/ Prints the coordinates of the solution path\nvoid printSolution(vector&lt;pair&lt;int, int&gt;&gt;&amp; path) {\n    cout &lt;&lt; \"Solution Path Coordinates:\" &lt;&lt; endl;\n    for (auto coord : path) {\n        cout &lt;&lt; \"(\" &lt;&lt; coord.first &lt;&lt; \", \" &lt;&lt; coord.second &lt;&lt; \") \";\n    }\n    cout &lt;&lt; endl;\n}\nint main() {\n    int n;\n    cout &lt;&lt; \"Enter the size of the maze: \";\n    cin &gt;&gt; n;\n    vector&lt;vector&lt;int&gt;&gt; maze(n, vector&lt;int&gt;(n));\n    cout &lt;&lt; \"Enter the maze (1 for open path, 0 for blocked):\" &lt;&lt; endl;\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            cin &gt;&gt; maze&#91;i]&#91;j];\n        }\n    }\n    vector&lt;vector&lt;int&gt;&gt; sol(n, vector&lt;int&gt;(n, 0)); \/\/ Initialize solution matrix with 0s\n    vector&lt;pair&lt;int, int&gt;&gt; path;\n    if (solveMaze(0, 0, n, maze, sol, path)) {\n        cout &lt;&lt; \"Solution found:\" &lt;&lt; endl;\n        printSolution(path);\n    } else {\n        cout &lt;&lt; \"No solution exists.\" &lt;&lt; endl;\n    }\n    return 0;\n}\nOutput :\nEnter the size of the maze: 4\nEnter the maze (1 for open path, 0 for blocked):\n1 0 1 0\n0 1 0 1\n1 1 0 1\n1 1 1 1\nNo solution exists.\n*********************************************\nEnter the size of the maze: 4\nEnter the maze (1 for open path, 0 for blocked):\n1 0 1 1\n1 1 0 1\n1 1 1 1\n0 0 1 1\nSolution found:\nSolution Path Coordinates:\n(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (3, 2) (3, 3)<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/C code implementation of backtracking for solving Rat in a Maze problem\n#include &lt;stdio.h>\n#include &lt;stdlib.h>\n\n#define MAX 100\n\n\/\/ Checks if a given cell (x, y) is valid for the rat to move to.\nint isSafe(int x, int y, int n, int maze&#91;MAX]&#91;MAX], int sol&#91;MAX]&#91;MAX]) {\n    return (x >= 0 &amp;&amp; x &lt; n &amp;&amp; y >= 0 &amp;&amp; y &lt; n &amp;&amp; maze&#91;x]&#91;y] == 1 &amp;&amp; sol&#91;x]&#91;y] == 0);\n}\n\n\/\/ Recursive function to solve the maze\nint solveMaze(int x, int y, int n, int maze&#91;MAX]&#91;MAX], int sol&#91;MAX]&#91;MAX], int path&#91;MAX]&#91;2], int *pathIndex) {\n    \/\/ Base case: Reached the destination\n    if (x == n - 1 &amp;&amp; y == n - 1) {\n        sol&#91;x]&#91;y] = 1; \/\/ Mark destination as visited\n        path&#91;*pathIndex]&#91;0] = x;\n        path&#91;*pathIndex]&#91;1] = y;\n        (*pathIndex)++;\n        return 1;\n    }\n\n    \/\/ Check if the current cell is valid\n    if (isSafe(x, y, n, maze, sol)) {\n        \/\/ Mark current cell as visited\n        sol&#91;x]&#91;y] = 1;\n        path&#91;*pathIndex]&#91;0] = x;\n        path&#91;*pathIndex]&#91;1] = y;\n        (*pathIndex)++;\n\n        \/\/ Explore all possible directions (right, down, left, up)\n        if (solveMaze(x + 1, y, n, maze, sol, path, pathIndex) ||\n            solveMaze(x, y + 1, n, maze, sol, path, pathIndex) ||\n            solveMaze(x - 1, y, n, maze, sol, path, pathIndex) ||\n            solveMaze(x, y - 1, n, maze, sol, path, pathIndex)) {\n            return 1; \/\/ If any direction leads to a solution, return true\n        }\n\n        \/\/ Backtrack (if no solution found in any direction)\n        sol&#91;x]&#91;y] = 0; \/\/ Unmark the cell\n        (*pathIndex)--;\n        return 0;\n    }\n\n    return 0; \/\/ If the cell is not safe, return false\n}\n\n\/\/ Prints the coordinates of the solution path\nvoid printSolution(int path&#91;MAX]&#91;2], int pathIndex) {\n    printf(\"Solution Path Coordinates:\\n\");\n    for (int i = 0; i &lt; pathIndex; i++) {\n        printf(\"(%d, %d) \", path&#91;i]&#91;0], path&#91;i]&#91;1]);\n    }\n    printf(\"\\n\");\n}\n\nint main() {\n    int n;\n    printf(\"Enter the size of the maze: \");\n    scanf(\"%d\", &amp;n);\n\n    int maze&#91;MAX]&#91;MAX];\n\n    printf(\"Enter the maze (1 for open path, 0 for blocked):\\n\");\n    for (int i = 0; i &lt; n; i++) {\n        for (int j = 0; j &lt; n; j++) {\n            scanf(\"%d\", &amp;maze&#91;i]&#91;j]);\n        }\n    }\n\n    int sol&#91;MAX]&#91;MAX] = {0}; \/\/ Initialize solution matrix with 0s\n    int path&#91;MAX]&#91;2];        \/\/ To store the path coordinates\n    int pathIndex = 0;\n\n    if (solveMaze(0, 0, n, maze, sol, path, &amp;pathIndex)) {\n        printf(\"Solution found:\\n\");\n        printSolution(path, pathIndex);\n    } else {\n        printf(\"No solution exists.\\n\");\n    }\n\n    return 0;\n}\nOutput :\nEnter the size of the maze: 4\nEnter the maze (1 for open path, 0 for blocked):\n1 0 1 0\n0 1 0 1\n1 1 0 1\n1 1 1 1\nNo solution exists.\n*********************************************\nEnter the size of the maze: 4\nEnter the maze (1 for open path, 0 for blocked):\n1 0 1 1\n1 1 0 1\n1 1 1 1\n0 0 1 1\nSolution found:\nSolution Path Coordinates:\n(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (3, 2) (3, 3)<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Solving N Queen problem by Backtracking Solving Subset sum problem(or Sum of Subsets) by Backtracking Solving graph colouring problem by back tracking Rat in a Maze problem-solving by backtracking The Rat in a Maze problem is a classic backtracking problem where a rat is placed in a maze and needs to find a path to [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-342","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/342","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=342"}],"version-history":[{"count":25,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/342\/revisions"}],"predecessor-version":[{"id":1460,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/342\/revisions\/1460"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}