BackTracking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## N Queens\n",
    "in a N*N chess board find all those configuration in which we can place N queens<br>\n",
    "if we get a solution then it's mirror image will also be answer so in first loop check upto n/2 only and take mirror image of answers (n-i)\n",
    "1. we are creating an array of n size where ith index is ith row and value inside ith row is the column at which queen is present as in each row there can only be 1 queen\n",
    "2. if we find a valid postion in ith row we move to i 1 the row and if we then doesn't get a valid position in i 1th row then we have to move back(currentrow--) and in previous row we will iterate from last used columns i.e. board[curr 1] \n",
    "3. If we finf a solution at last row then for same configuration there won't be any more coumn in last row where solutions will exist as n-1 queens have been filled so they had covered n-1 columns so only 1 column remain in lst row<br>\n",
    "**IsValidPosition:**\n",
    "1. we don't have to check that is a queen is present in same row as only one queen is present as per our board array\n",
    "2. for same column we can iterate through array and check if the same column is present in any index if it is then we have 2 queens in same column thus invalidPosition\n",
    "3. Diagonal : If horizontal distance from a point = vertical distance from that point to the index we are checking then both lie on same diagonal "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidPosition(board, Row, Column, size):\n",
    "    for i in range(Row):\n",
    "        if (Row-i == abs(board[i]-Column)) or board[i]==Column:\n",
    "            return False\n",
    "    return True\n",
    "def NQueens(size):\n",
    "    result = []\n",
    "    board = [-1]*size\n",
    "    CurrentRow = 0\n",
    "    while CurrentRow!=-1:\n",
    "        found = False\n",
    "        for i in range(board[CurrentRow] 1,size):\n",
    "            found = isValidPosition(board, CurrentRow, i, size)\n",
    "            if found:\n",
    "                board[CurrentRow] = i\n",
    "                CurrentRow =1\n",
    "                break\n",
    "        if CurrentRow == size:\n",
    "            result.append(board[:])\n",
    "            CurrentRow = size-2 #as we are at nth row so we have found one answer \n",
    "            board[-1] = -1   #for other answers\n",
    "        if not found: \n",
    "            board[CurrentRow] = -1\n",
    "            CurrentRow-=1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 3, 0, 2], [2, 0, 3, 1]]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "NQueens(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generate Parenthesis\n",
    "we can store no. of opening and no. of closing brackets left at each stage and if closing brackets < opening brackets then return False\n",
    "else use two cases one with adding ( other with adding )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def GenerateParenthesis(n):\n",
    "    ans  = []\n",
    "    curr = []\n",
    "    def gen(opening, closing):\n",
    "        if(opening == closing == 0):\n",
    "            ans.append(\"\".join(curr))\n",
    "        if(opening != 0):\n",
    "            curr.append('(')\n",
    "            gen(opening-1, closing)\n",
    "            curr.pop()\n",
    "        if opening < closing:\n",
    "            curr.append(')')\n",
    "            gen(opening, closing-1)\n",
    "            curr.pop()\n",
    "    gen(n,n)\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['((()))', '(()())', '(())()', '()(())', '()()()']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GenerateParenthesis(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other BackTracking Questions:\n",
    "- Sudoku Solver\n",
    "- Graph Colouring\n",
    "- Subset Sum"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}