lunchbox_sudoku_solver.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solver for Qodec's lunchbox sudoku problem\n",
    "\n",
    "https://logic-masters.de/Raetselportal/Raetsel/zeigen.php?id=000451"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Define the Sudoku board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "model = cp_model.CpModel()\n",
    "def create_row_vars(y):\n",
    "    return [model.NewIntVar(1, 9, 'x:{},y:{}'.format(x,y)) for x in range(9)] \n",
    "nodes = [create_row_vars(y) for y in range(9)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Add the normal sudoku constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in range(9):\n",
    "    model.AddAllDifferent(nodes[x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "for y in range(9):\n",
    "    model.AddAllDifferent([nodes[x][y] for x in range(9)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x_offset in range(0, 9, 3):\n",
    "    for y_offset in range(0, 9, 3):\n",
    "        square = []\n",
    "        for x in range(3):\n",
    "            for y in range(3):\n",
    "                square.append(nodes[x_offset+x][y_offset+y])\n",
    "        model.AddAllDifferent(square)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining sandwich constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vertical_sandwich(x, top, bottom, model, nodes):\n",
    "    b = model.NewBoolVar('vsandwich{},{}:{}_b'.format(y,top,bottom))\n",
    "    model.Add(sum(nodes[x][top+1:bottom]) == nodes[x][top]*10+ nodes[x][bottom])\\\n",
    "                    .OnlyEnforceIf(b)    \n",
    "    model.Add(sum(nodes[x][top+1:bottom]) == nodes[x][top]   + 10*nodes[x][bottom])\\\n",
    "                    .OnlyEnforceIf(b.Not())    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def horizontal_sandwich(y, left, right, model, nodes):\n",
    "    b = model.NewBoolVar('hsandwich{},{}:{}_b'.format(x,left,right))\n",
    "    model.Add(sum([nodes[x][y] for x in range(left+1,right)]) == nodes[left][y]*10+ nodes[right][y])\\\n",
    "                    .OnlyEnforceIf(b)\n",
    "    model.Add(sum([nodes[x][y] for x in range(left+1,right)]) == nodes[left][y]   + 10*nodes[right][y])\\\n",
    "                    .OnlyEnforceIf(b.Not())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defining the puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<ortools.sat.python.cp_model.Constraint at 0x7f1088211580>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.Add(nodes[0][7]==6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "horizontal_sandwich(1,3,7,model,nodes)\n",
    "horizontal_sandwich(3,0,5,model,nodes)\n",
    "horizontal_sandwich(4,0,5,model,nodes)\n",
    "horizontal_sandwich(5,0,5,model,nodes)\n",
    "horizontal_sandwich(8,4,7,model,nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "vertical_sandwich(2,1,8, model, nodes)\n",
    "vertical_sandwich(3,0,7, model, nodes)\n",
    "vertical_sandwich(3,2,5, model, nodes)\n",
    "vertical_sandwich(6,3,6, model, nodes)\n",
    "vertical_sandwich(7,0,7, model, nodes)\n",
    "vertical_sandwich(8,1,8, model, nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solver = cp_model.CpSolver()\n",
    "solver.Solve(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_solution(solver, nodes):\n",
    "    for y in range(9):\n",
    "        if(y%3==0):\n",
    "            print(\"\")            \n",
    "        for x in range(9):\n",
    "            if(x%3 == 0):\n",
    "                print(\" \", end='')\n",
    "            print(solver.Value(nodes[x][y]), end='')            \n",
    "        print(\"\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " 315 264 897\n",
      " 769 583 412\n",
      " 824 197 563\n",
      "\n",
      " 953 471 286\n",
      " 248 956 371\n",
      " 176 328 945\n",
      "\n",
      " 587 642 139\n",
      " 691 835 724\n",
      " 432 719 658\n"
     ]
    }
   ],
   "source": [
    "print_solution(solver,nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CpSolverResponse:\n",
      "status: OPTIMAL\n",
      "objective: 0\n",
      "best_bound: 0\n",
      "booleans: 194\n",
      "conflicts: 98387\n",
      "branches: 149082\n",
      "propagations: 1901674\n",
      "integer_propagations: 4958003\n",
      "walltime: 6.56338\n",
      "usertime: 6.56338\n",
      "deterministic_time: 1.71989\n",
      "primal_integral: 0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(solver.ResponseStats())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}