Sudoku Optimization.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Копия блокнота \"Final Project - Numerical Optimization with Python.ipynb\"",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/aruay99/Sudoku/blob/main/Sudoku%20Optimization.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qoc3SpWxmnF7"
      },
      "source": [
        "Discrete Optimization - Sudoku Solver"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rIc6VJx5qWSB",
        "outputId": "4e169193-a8af-4051-9a18-7c3734795b62"
      },
      "source": [
        "import time\n",
        "!pip install pulp\n",
        "from pulp import *"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: pulp in /usr/local/lib/python3.7/dist-packages (2.4)\n",
            "Requirement already satisfied: amply>=0.1.2 in /usr/local/lib/python3.7/dist-packages (from pulp) (0.1.4)\n",
            "Requirement already satisfied: pyparsing in /usr/local/lib/python3.7/dist-packages (from amply>=0.1.2->pulp) (2.4.7)\n",
            "Requirement already satisfied: docutils>=0.3 in /usr/local/lib/python3.7/dist-packages (from amply>=0.1.2->pulp) (0.17.1)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hwIO7S-Rm7rJ"
      },
      "source": [
        "## Naive Approach\n",
        "Generate all possible configurations of numbers from 1 to 9 to fill the empty cells. Try every configuration one by one until the correct configuration is found, i.e. for every unassigned position fill the position with a number from 1 to 9. After filling all the unassigned position check if the matrix is safe or not. If safe print else recurs for other cases.*italicised text*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pA8aPF4NmxR6",
        "outputId": "a5d896ee-6ac1-40fa-8af6-8b64de25cb05"
      },
      "source": [
        "# code adapted from source: https://www.geeksforgeeks.org/sudoku-backtracking-7/\n",
        "\n",
        "# A utility function to print grid\n",
        "def printing(sudoku):\n",
        "    for i in range(len(sudoku)):\n",
        "        line = \"\"\n",
        "        if i == 3 or i == 6:\n",
        "            print(\"---------------------\")\n",
        "        for j in range(len(sudoku[i])):\n",
        "            if j == 3 or j == 6:\n",
        "                line += \"| \"\n",
        "            line += str(sudoku[i][j])+\" \"\n",
        "        print(line)\n",
        " \n",
        "# 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",
        " \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\n",
        " \n",
        "# 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 solveSuduko(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 == 9 - 1 and col == 9):\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 == 9:\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 solveSuduko(grid, row, col + 1)\n",
        "    for num in range(1, 9 + 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 assined\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 solveSuduko(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",
        " \n",
        "\n",
        "\n",
        "if (solveSuduko(grid, 0, 0)):\n",
        "    printing(grid)\n",
        "    print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
        "else:\n",
        "    print(\"no solution  exists \")\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "no solution  exists \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etaSQl4BryMG"
      },
      "source": [
        "## Backtracking Approach\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PAWP3XoFsP5d"
      },
      "source": [
        "# code adapted from source: https://www.techwithtim.net/tutorials/python-programming/sudoku-solver-backtracking/\n",
        "def backtrackingSolver(bo):\n",
        "    sol = bo\n",
        "    find = find_empty(bo)\n",
        "    if not find:\n",
        "        return sol, True\n",
        "    else:\n",
        "        row, col = find\n",
        "\n",
        "    for i in range(1,10):\n",
        "        if valid(bo, i, (row, col)):\n",
        "            sol[row][col] = i\n",
        "            if solve(bo):\n",
        "                return sol, True\n",
        "            sol[row][col] = 0\n",
        "    return sol, False\n",
        "\n",
        "\n",
        "def valid(bo, num, pos):\n",
        "    # Check row\n",
        "    for i in range(len(bo[0])):\n",
        "        if bo[pos[0]][i] == num and pos[1] != i:\n",
        "            return False\n",
        "\n",
        "    # Check column\n",
        "    for i in range(len(bo)):\n",
        "        if bo[i][pos[1]] == num and pos[0] != i:\n",
        "            return False\n",
        "\n",
        "    # Check box\n",
        "    box_x = pos[1] // 3\n",
        "    box_y = pos[0] // 3\n",
        "\n",
        "    for i in range(box_y*3, box_y*3 + 3):\n",
        "        for j in range(box_x * 3, box_x*3 + 3):\n",
        "            if bo[i][j] == num and (i,j) != pos:\n",
        "                return False\n",
        "\n",
        "    return True\n",
        "\n",
        "\n",
        "def find_empty(bo):\n",
        "    for i in range(len(bo)):\n",
        "        for j in range(len(bo[0])):\n",
        "            if bo[i][j] == 0:\n",
        "                return (i, j)  # row, col\n",
        "    return None"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ddun94zTTh9a"
      },
      "source": [
        "## Linear Programming"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4CI4loPOTpic"
      },
      "source": [
        "def linearProgrammingSolver(grid):\n",
        "  number = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\", \"9\"]\n",
        "  vals = number\n",
        "  rows = number\n",
        "  cols = number\n",
        "\n",
        "  subGrids =[]\n",
        "  for i in range(3):\n",
        "      for j in range(3):\n",
        "          subGrids += [[(rows[3*i+k],cols[3*j+l]) for k in range(3) for l in range(3)]]\n",
        "  \n",
        "  #Create the LP problem\n",
        "  prob = LpProblem(\"Sudoku Problem\",LpMinimize)\n",
        "\n",
        "  #Set the decision variables\n",
        "  choices = LpVariable.dicts(\"Choice\",(vals,rows,cols),0,1,LpInteger)\n",
        "\n",
        "  #Add main objective function\n",
        "  prob += 0, \"Arbitrary Objective Function\"\n",
        "\n",
        "  #Add constraints:\n",
        "  for r in rows:\n",
        "      for c in cols:\n",
        "          prob += lpSum([choices[v][r][c] for v in vals]) == 1, \"\"\n",
        "\n",
        "  for v in vals:\n",
        "      for r in rows:\n",
        "          prob += lpSum([choices[v][r][c] for c in cols]) == 1,\"\"\n",
        "          \n",
        "      for c in cols:\n",
        "          prob += lpSum([choices[v][r][c] for r in rows]) == 1,\"\"\n",
        "\n",
        "      for b in subGrids:\n",
        "          prob += lpSum([choices[v][r][c] for (r,c) in b]) == 1,\"\"\n",
        "  \n",
        "  for curR in number:\n",
        "    for curC in number:\n",
        "      v = grid[int(curR)-1][int(curC)-1]\n",
        "      if v != 0:\n",
        "        prob += choices[str(v)][curR][curC] == 1,\"\"\n",
        "\n",
        "  prob.writeLP(\"Sudoku.lp\")\n",
        "  prob.solve()\n",
        "\n",
        "  sol = [[ 0 for i in range(9) ] for j in range(9) ]\n",
        "  for r in rows:\n",
        "      for c in cols:\n",
        "          for v in vals:\n",
        "              if value(choices[v][r][c])==1:     \n",
        "                  sol[int(r)-1][int(c)-1] = v\n",
        "  return sol\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Yh0Z3VhmFfqV",
        "outputId": "5c3ce4d3-b014-45c0-f54b-a2dc891f6e97"
      },
      "source": [
        "easy = [[7,0,0,4,2,0,9,0,1],\n",
        "       [2,0,0,3,1,9,0,5,7],\n",
        "       [0,9,3,7,5,6,8,0,4],\n",
        "       [9,5,8,2,0,0,7,0,0],\n",
        "       [4,0,0,0,0,0,0,0,0],\n",
        "       [0,0,0,0,0,0,2,0,8],\n",
        "       [5,4,6,1,0,7,0,9,0],\n",
        "       [3,7,0,0,9,0,0,8,5],\n",
        "       [8,0,0,5,4,0,0,0,0]]\n",
        "\n",
        "medium = [[0,4,0,0,0,2,0,1,9],\n",
        "       [0,0,0,3,5,1,0,8,6],\n",
        "       [3,1,0,0,9,4,7,0,0],\n",
        "       [0,9,4,0,0,0,0,0,7],\n",
        "       [0,0,0,0,0,0,0,0,0],\n",
        "       [2,0,0,0,0,0,8,9,0],\n",
        "       [0,0,9,5,2,0,0,4,1],\n",
        "       [4,2,0,1,6,9,0,0,0],\n",
        "       [1,6,0,8,0,0,0,7,0]]\n",
        "\n",
        "insanelyHard = [[0,0,5,3,0,0,0,0,0],\n",
        "       [8,0,0,0,0,0,0,2,0],\n",
        "       [0,7,0,0,1,0,5,0,0],\n",
        "       [4,0,0,0,0,5,3,0,0],\n",
        "       [0,1,0,0,7,0,0,0,6],\n",
        "       [0,0,3,2,0,0,0,8,0],\n",
        "       [0,6,0,0,0,0,2,8,0],\n",
        "       [0,0,4,0,0,0,0,3,0],\n",
        "       [0,0,0,0,0,9,7,0,0]]\n",
        "\n",
        "hard = [[0,0,5,3,0,0,0,0,0],\n",
        "       [8,0,0,0,0,0,0,2,0],\n",
        "       [0,7,0,0,1,0,5,0,0],\n",
        "       [4,0,0,0,0,5,3,0,0],\n",
        "       [0,1,0,0,7,0,0,0,6],\n",
        "       [0,0,3,2,0,0,0,8,0],\n",
        "       [0,6,0,5,0,0,0,0,9],\n",
        "       [0,0,4,0,0,0,0,3,0],\n",
        "       [0,0,0,0,0,9,7,0,0]]\n",
        "\n",
        "allLevels = [easy, medium, hard, insanelyHard]\n",
        "\n",
        "for level in allLevels:\n",
        "  print(\"Current: \")\n",
        "  print()\n",
        "  printing(level)\n",
        "  print()\n",
        "\n",
        "  #backtracking\n",
        "  print(\"Backtracking: \")\n",
        "  print()\n",
        "  start_time = time.time()\n",
        "  sol, solved = backtrackingSolver(level)\n",
        "  if solved:\n",
        "    printing(sol)\n",
        "  else:\n",
        "    print(\"no solution was found\")\n",
        "  print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
        "  print()\n",
        "\n",
        "  #linear programmming\n",
        "  print(\"Linear Programming: \")\n",
        "  print()\n",
        "  start_time = time.time()\n",
        "  printing(linearProgrammingSolver(level))\n",
        "  print(\"--- %s seconds ---\" % (time.time() - start_time))\n",
        "  print()\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Current: \n",
            "\n",
            "7 0 0 | 4 2 0 | 9 0 1 \n",
            "2 0 0 | 3 1 9 | 0 5 7 \n",
            "0 9 3 | 7 5 6 | 8 0 4 \n",
            "---------------------\n",
            "9 5 8 | 2 0 0 | 7 0 0 \n",
            "4 0 0 | 0 0 0 | 0 0 0 \n",
            "0 0 0 | 0 0 0 | 2 0 8 \n",
            "---------------------\n",
            "5 4 6 | 1 0 7 | 0 9 0 \n",
            "3 7 0 | 0 9 0 | 0 8 5 \n",
            "8 0 0 | 5 4 0 | 0 0 0 \n",
            "\n",
            "Backtracking: \n",
            "\n",
            "7 6 5 | 4 2 8 | 9 3 1 \n",
            "2 8 4 | 3 1 9 | 6 5 7 \n",
            "1 9 3 | 7 5 6 | 8 2 4 \n",
            "---------------------\n",
            "9 5 8 | 2 6 4 | 7 1 3 \n",
            "4 3 2 | 8 7 1 | 5 6 9 \n",
            "6 1 7 | 9 3 5 | 2 4 8 \n",
            "---------------------\n",
            "5 4 6 | 1 8 7 | 3 9 2 \n",
            "3 7 1 | 6 9 2 | 4 8 5 \n",
            "8 2 9 | 5 4 3 | 1 7 6 \n",
            "--- 0.017908096313476562 seconds ---\n",
            "\n",
            "Linear Programming: \n",
            "\n",
            "7 6 5 | 4 2 8 | 9 3 1 \n",
            "2 8 4 | 3 1 9 | 6 5 7 \n",
            "1 9 3 | 7 5 6 | 8 2 4 \n",
            "---------------------\n",
            "9 5 8 | 2 6 4 | 7 1 3 \n",
            "4 3 2 | 8 7 1 | 5 6 9 \n",
            "6 1 7 | 9 3 5 | 2 4 8 \n",
            "---------------------\n",
            "5 4 6 | 1 8 7 | 3 9 2 \n",
            "3 7 1 | 6 9 2 | 4 8 5 \n",
            "8 2 9 | 5 4 3 | 1 7 6 \n",
            "--- 0.08557295799255371 seconds ---\n",
            "\n",
            "Current: \n",
            "\n",
            "0 4 0 | 0 0 2 | 0 1 9 \n",
            "0 0 0 | 3 5 1 | 0 8 6 \n",
            "3 1 0 | 0 9 4 | 7 0 0 \n",
            "---------------------\n",
            "0 9 4 | 0 0 0 | 0 0 7 \n",
            "0 0 0 | 0 0 0 | 0 0 0 \n",
            "2 0 0 | 0 0 0 | 8 9 0 \n",
            "---------------------\n",
            "0 0 9 | 5 2 0 | 0 4 1 \n",
            "4 2 0 | 1 6 9 | 0 0 0 \n",
            "1 6 0 | 8 0 0 | 0 7 0 \n",
            "\n",
            "Backtracking: \n",
            "\n",
            "5 4 6 | 7 8 2 | 3 1 9 \n",
            "9 7 2 | 3 5 1 | 4 8 6 \n",
            "3 1 8 | 6 9 4 | 7 2 5 \n",
            "---------------------\n",
            "6 9 4 | 2 3 8 | 1 5 7 \n",
            "7 8 3 | 9 1 5 | 2 6 4 \n",
            "2 5 1 | 4 7 6 | 8 9 3 \n",
            "---------------------\n",
            "8 3 9 | 5 2 7 | 6 4 1 \n",
            "4 2 7 | 1 6 9 | 5 3 8 \n",
            "1 6 5 | 8 4 3 | 9 7 2 \n",
            "--- 0.011423110961914062 seconds ---\n",
            "\n",
            "Linear Programming: \n",
            "\n",
            "5 4 6 | 7 8 2 | 3 1 9 \n",
            "9 7 2 | 3 5 1 | 4 8 6 \n",
            "3 1 8 | 6 9 4 | 7 2 5 \n",
            "---------------------\n",
            "6 9 4 | 2 3 8 | 1 5 7 "
          ],
          "name": "stdout"
        },
        {
          "output_type": "stream",
          "text": [
            "/usr/local/lib/python3.7/dist-packages/pulp/pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n",
            "  warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n"
          ],
          "name": "stderr"
        },
        {
          "output_type": "stream",
          "text": [
            "\n",
            "7 8 3 | 9 1 5 | 2 6 4 \n",
            "2 5 1 | 4 7 6 | 8 9 3 \n",
            "---------------------\n",
            "8 3 9 | 5 2 7 | 6 4 1 \n",
            "4 2 7 | 1 6 9 | 5 3 8 \n",
            "1 6 5 | 8 4 3 | 9 7 2 \n",
            "--- 0.09047842025756836 seconds ---\n",
            "\n",
            "Current: \n",
            "\n",
            "0 0 5 | 3 0 0 | 0 0 0 \n",
            "8 0 0 | 0 0 0 | 0 2 0 \n",
            "0 7 0 | 0 1 0 | 5 0 0 \n",
            "---------------------\n",
            "4 0 0 | 0 0 5 | 3 0 0 \n",
            "0 1 0 | 0 7 0 | 0 0 6 \n",
            "0 0 3 | 2 0 0 | 0 8 0 \n",
            "---------------------\n",
            "0 6 0 | 5 0 0 | 0 0 9 \n",
            "0 0 4 | 0 0 0 | 0 3 0 \n",
            "0 0 0 | 0 0 9 | 7 0 0 \n",
            "\n",
            "Backtracking: \n",
            "\n",
            "1 4 5 | 3 2 7 | 6 9 8 \n",
            "8 3 9 | 6 5 4 | 1 2 7 \n",
            "6 7 2 | 9 1 8 | 5 4 3 \n",
            "---------------------\n",
            "4 9 6 | 1 8 5 | 3 7 2 \n",
            "2 1 8 | 4 7 3 | 9 5 6 \n",
            "7 5 3 | 2 9 6 | 4 8 1 \n",
            "---------------------\n",
            "3 6 7 | 5 4 2 | 8 1 9 \n",
            "9 8 4 | 7 6 1 | 2 3 5 \n",
            "5 2 1 | 8 3 9 | 7 6 4 \n",
            "--- 0.21696972846984863 seconds ---\n",
            "\n",
            "Linear Programming: \n",
            "\n",
            "1 4 5 | 3 2 7 | 6 9 8 \n",
            "8 3 9 | 6 5 4 | 1 2 7 \n",
            "6 7 2 | 9 1 8 | 5 4 3 \n",
            "---------------------\n",
            "4 9 6 | 1 8 5 | 3 7 2 \n",
            "2 1 8 | 4 7 3 | 9 5 6 \n",
            "7 5 3 | 2 9 6 | 4 8 1 \n",
            "---------------------\n",
            "3 6 7 | 5 4 2 | 8 1 9 \n",
            "9 8 4 | 7 6 1 | 2 3 5 \n",
            "5 2 1 | 8 3 9 | 7 6 4 \n",
            "--- 0.10110688209533691 seconds ---\n",
            "\n",
            "Current: \n",
            "\n",
            "0 0 5 | 3 0 0 | 0 0 0 \n",
            "8 0 0 | 0 0 0 | 0 2 0 \n",
            "0 7 0 | 0 1 0 | 5 0 0 \n",
            "---------------------\n",
            "4 0 0 | 0 0 5 | 3 0 0 \n",
            "0 1 0 | 0 7 0 | 0 0 6 \n",
            "0 0 3 | 2 0 0 | 0 8 0 \n",
            "---------------------\n",
            "0 6 0 | 0 0 0 | 2 8 0 \n",
            "0 0 4 | 0 0 0 | 0 3 0 \n",
            "0 0 0 | 0 0 9 | 7 0 0 \n",
            "\n",
            "Backtracking: \n",
            "\n",
            "no solution was found\n",
            "--- 3.9080183506011963 seconds ---\n",
            "\n",
            "Linear Programming: \n",
            "\n",
            "1 4 5 | 3 0 0 | 0 7 8 \n",
            "8 3 0 | 0 0 0 | 0 2 0 \n",
            "0 7 0 | 0 1 0 | 5 0 3 \n",
            "---------------------\n",
            "4 0 7 | 0 6 5 | 3 0 2 \n",
            "0 1 0 | 0 7 3 | 0 5 6 \n",
            "6 5 3 | 2 0 0 | 0 0 7 \n",
            "---------------------\n",
            "3 6 0 | 0 0 0 | 2 8 0 \n",
            "7 0 4 | 6 0 0 | 0 3 0 \n",
            "5 2 0 | 0 3 9 | 7 6 4 \n",
            "--- 0.09438109397888184 seconds ---\n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}