Sudoku_puzzle (1).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "# <b>Sudoku Puzzles using Tensorflow</b>"
      ],
      "metadata": {
        "id": "Q1jrVz3sT2Cm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "- Dataset for this notebook was uploaded from [sudoku site](https://sudoku.com/easy/)\n",
        "- Creating an Algorithm to Solve Sudoku -  backtracking algorithm to solve a Sudoku puzzle"
      ],
      "metadata": {
        "id": "L3YC4tn8UBWG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### <b>Understanding the Problem</b>\n",
        "\n",
        "Solving Sudoku involves filling a 9x9 grid with digits from 1 to 9, ensuring that each row, column, and 3x3 subgrid contains all digits without repetition. This is a classic constraint satisfaction problem.\n"
      ],
      "metadata": {
        "id": "7_8Q5wPlads3"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "- A Sudoku puzzle is represented as a 9x9 Python numpy array."
      ],
      "metadata": {
        "id": "b6dOnCXwWFGO"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "1. **`printing(arr)`**: A utility function that prints the 9x9 grid after the Sudoku has been solved."
      ],
      "metadata": {
        "id": "nWPLoi8H7_uu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# N is the size of the 2D matrix   N*N\n",
        "N = 9\n",
        "\n",
        "# A utility function to print grid\n",
        "def printing(arr):\n",
        "    for i in range(N):\n",
        "        for j in range(N):\n",
        "            print(arr[i][j], end = \" \")\n",
        "        print()"
      ],
      "metadata": {
        "id": "JvxKxC3J6Yzn"
      },
      "execution_count": 46,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "2. **`isSafe(grid, row, col, num)`**: Checks if it's safe to place a number (`num`) in the cell at position (`row`, `col`). It ensures:\n",
        "   - The number is not already in the same row.\n",
        "   - The number is not already in the same column.\n",
        "   - The number is not in the same 3x3 subgrid."
      ],
      "metadata": {
        "id": "-rgdH4q97igk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Checks whether it will be\n",
        "# legal to assign num to the\n",
        "# given row, col\n",
        "def isSafe(grid, row, col, num):\n",
        "\n",
        "    # Check if we find the same num\n",
        "    # in the similar row , we\n",
        "    # return false\n",
        "    for x in range(9):\n",
        "        if grid[row][x] == num:\n",
        "            return False\n",
        "# Check if we find the same num in\n",
        "    # the similar column , we\n",
        "    # return false\n",
        "    for x in range(9):\n",
        "        if grid[x][col] == num:\n",
        "            return False\n",
        "\n",
        "    # Check if we find the same num in\n",
        "    # the particular 3*3 matrix,\n",
        "    # we return false\n",
        "    startRow = row - row % 3\n",
        "    startCol = col - col % 3\n",
        "    for i in range(3):\n",
        "        for j in range(3):\n",
        "            if grid[i + startRow][j + startCol] == num:\n",
        "                return False\n",
        "    return True"
      ],
      "metadata": {
        "id": "kcrK1riI6d3O"
      },
      "execution_count": 47,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "3. **`solveSudoku(grid, row, col)`**: This is the core function that tries to solve the Sudoku puzzle using backtracking.\n",
        "   - If the current cell is already filled, it proceeds to the next column.\n",
        "   - If a cell is empty (denoted by 0), it tries placing numbers from 1 to 9 and recursively solves the puzzle.\n",
        "   - If placing a number leads to a valid solution, it moves to the next column.\n",
        "   - If no valid number can be placed, it backtracks by resetting the current cell and tries the next possibility."
      ],
      "metadata": {
        "id": "YCNqU7U27t3D"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Takes a partially filled-in grid and attempts\n",
        "# to assign values to all unassigned locations in\n",
        "# such a way to meet the requirements for\n",
        "# Sudoku solution (non-duplication across rows,\n",
        "# columns, and boxes) */\n",
        "def solveSudoku(grid, row, col):\n",
        "\n",
        "    # Check if we have reached the 8th\n",
        "    # row and 9th column (0\n",
        "    # indexed matrix) , we are\n",
        "    # returning true to avoid\n",
        "    # further backtracking\n",
        "    if (row == N - 1 and col == N):\n",
        "        return True\n",
        "\n",
        "    # Check if column value  becomes 9 ,\n",
        "    # we move to next row and\n",
        "    # column start from 0\n",
        "    if col == N:\n",
        "        row += 1\n",
        "        col = 0\n",
        "\n",
        "    # Check if the current position of\n",
        "    # the grid already contains\n",
        "    # value >0, we iterate for next column\n",
        "    if grid[row][col] > 0:\n",
        "        return solveSudoku(grid, row, col + 1)\n",
        "    for num in range(1, N + 1, 1):\n",
        "\n",
        "        # Check if it is safe to place\n",
        "        # the num (1-9)  in the\n",
        "        # given row ,col  ->we\n",
        "        # move to next column\n",
        "        if isSafe(grid, row, col, num):\n",
        "\n",
        "            # Assigning the num in\n",
        "            # the current (row,col)\n",
        "            # position of the grid\n",
        "            # and assuming our assigned\n",
        "            # num in the position\n",
        "            # is correct\n",
        "            grid[row][col] = num\n",
        "\n",
        "            # Checking for next possibility with next\n",
        "            # column\n",
        "            if solveSudoku(grid, row, col + 1):\n",
        "                return True\n",
        "\n",
        "        # Removing the assigned num ,\n",
        "        # since our assumption\n",
        "        # was wrong , and we go for\n",
        "        # next assumption with\n",
        "        # diff num value\n",
        "        grid[row][col] = 0\n",
        "    return False\n"
      ],
      "metadata": {
        "id": "fTMJA27d6wUT"
      },
      "execution_count": 48,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "4. **Driver Code**:\n",
        "   - A 9x9 Sudoku grid is given where `0` represents an empty cell.\n",
        "   - The function `solveSudoku` is called starting from the first cell (0, 0).\n",
        "   - If the puzzle can be solved, it prints the solved grid; otherwise, it prints \"no solution exists.\""
      ],
      "metadata": {
        "id": "wVqqIg0b8QMl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Driver Code\n",
        "\n",
        "# 0 means unassigned cells\n",
        "# insert the digits manually, empty boxes replace with zeros\n",
        "# insert digits for your puzzle\n",
        "\n",
        "\n",
        "grid = [[6, 8, 0, 0, 0, 2, 0, 4, 9],\n",
        "        [7, 3, 0, 5, 9, 0, 6, 1, 0],\n",
        "        [2, 0, 0, 7, 6, 0, 0, 5, 8],\n",
        "        [5, 6, 8, 0, 0, 0, 1, 0, 3],\n",
        "        [1, 9, 0, 0, 8, 0, 0, 0, 4],\n",
        "        [0, 4, 2, 9, 0, 0, 8, 6, 0],\n",
        "        [8, 0, 0, 0, 0, 0, 2, 0, 0],\n",
        "        [0, 0, 0, 0, 0, 1, 0, 0, 0],\n",
        "        [0, 0, 3, 0, 5, 6, 9, 8, 0]]\n",
        "\n",
        "if (solveSudoku(grid, 0, 0)):\n",
        "    printing(grid)\n",
        "else:\n",
        "    print(\"no solution  exists \")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TChRF-J0639X",
        "outputId": "cd579ad8-acb5-4c25-af06-84cac36c761a"
      },
      "execution_count": 49,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "6 8 5 1 3 2 7 4 9 \n",
            "7 3 4 5 9 8 6 1 2 \n",
            "2 1 9 7 6 4 3 5 8 \n",
            "5 6 8 4 2 7 1 9 3 \n",
            "1 9 7 6 8 3 5 2 4 \n",
            "3 4 2 9 1 5 8 6 7 \n",
            "8 5 1 3 4 9 2 7 6 \n",
            "9 2 6 8 7 1 4 3 5 \n",
            "4 7 3 2 5 6 9 8 1 \n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Get puzzles from [Sudoku.com](https://sudoku.com/easy/)"
      ],
      "metadata": {
        "id": "qEBWOZoP8sd0"
      }
    }
  ]
}