MagicSquare.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/OptimizationExpert/Pyomo/blob/main/MagicSquare.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VvJL0bOSIm84"
      },
      "source": [
        "Developed by Alireza Soroudi\n",
        "alireza.soroudi@gmail.com\n",
        "\n",
        "Linkedin News letter : https://www.linkedin.com/newsletters/optimization-in-open-source-6874020019009859585/\n",
        "\n",
        "Git hub: https://github.com/OptimizationExpert/Pyomo\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "w_3yuwV8XtMF",
        "outputId": "a07681c8-72cc-4df1-8d1b-efc25e35bd5a"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting ortools\n",
            "  Downloading ortools-9.9.3963-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (24.8 MB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m24.8/24.8 MB\u001b[0m \u001b[31m32.5 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting absl-py>=2.0.0 (from ortools)\n",
            "  Downloading absl_py-2.1.0-py3-none-any.whl (133 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m133.7/133.7 kB\u001b[0m \u001b[31m14.9 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hRequirement already satisfied: numpy>=1.13.3 in /usr/local/lib/python3.10/dist-packages (from ortools) (1.25.2)\n",
            "Requirement already satisfied: pandas>=2.0.0 in /usr/local/lib/python3.10/dist-packages (from ortools) (2.0.3)\n",
            "Collecting protobuf>=4.25.3 (from ortools)\n",
            "  Downloading protobuf-5.26.1-cp37-abi3-manylinux2014_x86_64.whl (302 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m302.8/302.8 kB\u001b[0m \u001b[31m23.1 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hCollecting immutabledict>=3.0.0 (from ortools)\n",
            "  Downloading immutabledict-4.2.0-py3-none-any.whl (4.7 kB)\n",
            "Requirement already satisfied: python-dateutil>=2.8.2 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2.8.2)\n",
            "Requirement already satisfied: pytz>=2020.1 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2023.4)\n",
            "Requirement already satisfied: tzdata>=2022.1 in /usr/local/lib/python3.10/dist-packages (from pandas>=2.0.0->ortools) (2024.1)\n",
            "Requirement already satisfied: six>=1.5 in /usr/local/lib/python3.10/dist-packages (from python-dateutil>=2.8.2->pandas>=2.0.0->ortools) (1.16.0)\n",
            "Installing collected packages: protobuf, immutabledict, absl-py, ortools\n",
            "  Attempting uninstall: protobuf\n",
            "    Found existing installation: protobuf 3.20.3\n",
            "    Uninstalling protobuf-3.20.3:\n",
            "      Successfully uninstalled protobuf-3.20.3\n",
            "  Attempting uninstall: absl-py\n",
            "    Found existing installation: absl-py 1.4.0\n",
            "    Uninstalling absl-py-1.4.0:\n",
            "      Successfully uninstalled absl-py-1.4.0\n",
            "\u001b[31mERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.\n",
            "google-ai-generativelanguage 0.6.2 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-api-core 2.11.1 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0.dev0,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-aiplatform 1.48.0 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-bigquery-connection 1.12.1 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-bigquery-storage 2.24.0 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-datastore 2.15.2 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-firestore 2.11.1 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-functions 1.13.3 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-iam 2.15.0 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-language 2.13.3 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-resource-manager 1.12.3 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "google-cloud-translate 3.11.3 requires protobuf!=3.20.0,!=3.20.1,!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "googleapis-common-protos 1.63.0 requires protobuf!=3.20.0,!=3.20.1,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0.dev0,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "grpc-google-iam-v1 0.13.0 requires protobuf!=3.20.0,!=3.20.1,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.19.5, but you have protobuf 5.26.1 which is incompatible.\n",
            "proto-plus 1.23.0 requires protobuf<5.0.0dev,>=3.19.0, but you have protobuf 5.26.1 which is incompatible.\n",
            "tensorflow 2.15.0 requires protobuf!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.20.3, but you have protobuf 5.26.1 which is incompatible.\n",
            "tensorflow-metadata 1.15.0 requires protobuf<4.21,>=3.20.3; python_version < \"3.11\", but you have protobuf 5.26.1 which is incompatible.\u001b[0m\u001b[31m\n",
            "\u001b[0mSuccessfully installed absl-py-2.1.0 immutabledict-4.2.0 ortools-9.9.3963 protobuf-5.26.1\n"
          ]
        }
      ],
      "source": [
        "!pip install ortools\n",
        "from ortools.sat.python import cp_model # CP-SAT solver\n",
        "import numpy as np\n",
        "from random import randint\n",
        "import random\n",
        "from math import ceil\n",
        "import pandas as pd\n",
        "import matplotlib.pyplot as plt # Data visualization\n",
        "from matplotlib.patches import Rectangle"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "A magic square is a fascinating mathematical puzzle where numbers are arranged in a grid in such a way that the sum of the numbers in each row, column, and diagonal is the same. It's like a numerical crossword, where every row and column holds a unique combination of numbers, and the challenge lies in arranging the digits so that they magically add up to a constant sum. Magic squares come in various sizes and complexities, from simple 3x3 grids to larger, intricate puzzles. Solving a magic square requires both logic and creativity, making it a delightful and engaging mathematical challenge for enthusiasts of all ages. M = n(n*n+1)/2"
      ],
      "metadata": {
        "id": "sQnYWNChTQPc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
        "    \"\"\"Print intermediate solutions.\"\"\"\n",
        "    def __init__(self, variables):\n",
        "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
        "        self.__variables = variables\n",
        "        self.__solution_count = 0\n",
        "    def on_solution_callback(self):\n",
        "        self.__solution_count += 1\n",
        "        N = int(np.sqrt(len(self.__variables)))\n",
        "        for r in range(1,1+N):\n",
        "            print([self.Value(self.__variables[i,j]) for (i,j) in self.__variables if i==r])\n",
        "        print('-------------------------')\n",
        "    def solution_count(self):\n",
        "        return self.__solution_count\n",
        "\n",
        "def SearchForAllSolutionsSampleSat(n):\n",
        "    \"\"\"Showcases calling the solver to search for all solutions.\"\"\"\n",
        "    # Creates the model.\n",
        "    model = cp_model.CpModel()\n",
        "\n",
        "    # Creates the variables.\n",
        "    M = int(n*(n*n+1)/2)\n",
        "    rows = range(1,n+1)\n",
        "    cols = range(1,n+1)\n",
        "    x = {(i,j):model.NewIntVar(1, n**2, f\"x_{i}_{j}\") for i in rows for j in cols}\n",
        "\n",
        "    # Create the constraints.\n",
        "    model.AddAllDifferent([x[i,j] for (i,j) in x])\n",
        "\n",
        "    for r in rows:\n",
        "        expressions = [x[r,c] for c in cols]\n",
        "        model.Add(sum(expressions) == M )\n",
        "        model.AddAllDifferent(expressions)\n",
        "\n",
        "\n",
        "    for c in cols:\n",
        "        expressions = [x[r,c] for r in rows]\n",
        "        model.Add(sum(expressions) == M )\n",
        "        model.AddAllDifferent(expressions)\n",
        "\n",
        "    expressions_d = [x[r,c] for r in rows for c in cols if r==c]\n",
        "    model.Add(sum(expressions_d) == M )\n",
        "\n",
        "    expressions_ad = [x[r,c] for r in rows for c in cols if r==n-c+1]\n",
        "    model.Add(sum(expressions_ad) == M )\n",
        "\n",
        "\n",
        "    # Create a solver and solve.\n",
        "    solver = cp_model.CpSolver()\n",
        "    solution_printer = VarArraySolutionPrinter(x)\n",
        "    # Enumerate all solutions.\n",
        "    solver.parameters.enumerate_all_solutions = True\n",
        "    # Solve.\n",
        "\n",
        "    status = solver.Solve(model, solution_printer)\n",
        "    #status = solver.Solve(model)\n",
        "\n",
        "    print(f\"Status = {solver.StatusName(status)}\")\n",
        "    print(f\"Number of solutions found: {solution_printer.solution_count()}\")\n",
        "\n",
        "\n",
        "SearchForAllSolutionsSampleSat(3)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "t9cLSkLUSAXR",
        "outputId": "24e789ed-f5cb-41d1-f066-1690e04199dd"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[2, 9, 4]\n",
            "[7, 5, 3]\n",
            "[6, 1, 8]\n",
            "-------------------------\n",
            "[4, 9, 2]\n",
            "[3, 5, 7]\n",
            "[8, 1, 6]\n",
            "-------------------------\n",
            "[6, 7, 2]\n",
            "[1, 5, 9]\n",
            "[8, 3, 4]\n",
            "-------------------------\n",
            "[2, 7, 6]\n",
            "[9, 5, 1]\n",
            "[4, 3, 8]\n",
            "-------------------------\n",
            "[4, 3, 8]\n",
            "[9, 5, 1]\n",
            "[2, 7, 6]\n",
            "-------------------------\n",
            "[8, 3, 4]\n",
            "[1, 5, 9]\n",
            "[6, 7, 2]\n",
            "-------------------------\n",
            "[8, 1, 6]\n",
            "[3, 5, 7]\n",
            "[4, 9, 2]\n",
            "-------------------------\n",
            "[6, 1, 8]\n",
            "[7, 5, 3]\n",
            "[2, 9, 4]\n",
            "-------------------------\n",
            "Status = OPTIMAL\n",
            "Number of solutions found: 8\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yJdhHr-DIlur"
      },
      "source": []
    }
  ],
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}