{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an ipython (jupyter) worksheet with code from the lecture notes for the course\n",
    "**Permutation Puzzles: A Mathematical Perspective**, by Jamie Mulholland\n",
    "\n",
    "Coures webpage: http://www.sfu.ca/~jtmulhol/math302 <br />\n",
    "Course notes booklet: http://www.sfu.ca/~jtmulhol/math302/notes/302notes.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 24: Lights Out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.2 Matrix Model\n",
    "\n",
    "## 24.2.2 Solving Linear Systems in SageMath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example of using SageMath to solve the linear system:\n",
    "$$\n",
    "\\begin{bmatrix}\n",
    "1 & 0 & 2\\\\\n",
    "3 & 2 & 5\n",
    "\\end{bmatrix}\n",
    "\\boldsymbol{x} = \n",
    "\\left[\\begin{array}{c}\n",
    "3\\\\\n",
    "0 \\\\\n",
    "\\end{array}\n",
    "\\right]\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, -9/2, 0)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M=matrix(QQ,[[1,0,2],[3,2,5]])\n",
    "b=vector(QQ,[3,0])\n",
    "M.solve_right(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lights Out Matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition of the matrix for Lights Out\n",
    "# input = integer n (where lights out board is nxn)\n",
    "# output = lights out matrix A which is nxn\n",
    "def lights_out(n):\n",
    "    A = identity_matrix(GF(2),n*n)     # initialize A with ones along diagonal\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            m = n*i+j               \n",
    "            if i > 0 : A[(m,m-n)] = 1   # I block below diagonal\n",
    "            if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal\n",
    "            if j > 0 : A[(m,m-1)] = 1   # C block below diagonal\n",
    "            if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1 1 0 1 0 0 0 0 0]\n",
       "[1 1 1 0 1 0 0 0 0]\n",
       "[0 1 1 0 0 1 0 0 0]\n",
       "[1 0 0 1 1 0 1 0 0]\n",
       "[0 1 0 1 1 1 0 1 0]\n",
       "[0 0 1 0 1 1 0 0 1]\n",
       "[0 0 0 1 0 0 1 1 0]\n",
       "[0 0 0 0 1 0 1 1 1]\n",
       "[0 0 0 0 0 1 0 1 1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lights_out(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The lights out matrix for a 5x5 boaard would be a 25x25 matrix. SageMath won't print this out by default."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25 x 25 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lights_out(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 24.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "starting configuration: \n",
      "[1 1 0 0 1]\n",
      "[1 1 1 0 0]\n",
      "[1 0 0 0 1]\n",
      "[0 0 1 1 1]\n",
      "[1 0 0 1 1]\n",
      "solution: \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0 0 1 0 0]\n",
       "[1 0 1 1 1]\n",
       "[0 1 0 1 0]\n",
       "[1 1 1 0 1]\n",
       "[0 0 1 0 0]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#current game configuration (i.e. buttons that are lit) \n",
    "b=vector(GF(2),[1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1]);\n",
    "print \"starting configuration: \"\n",
    "print matrix(GF(2),5,5,b.list())\n",
    "\n",
    "#solving the game\n",
    "x=lights_out(5).solve_right(b);\n",
    "\n",
    "#now put the solution x in a nice matrix form so we can see what buttons to press\n",
    "button_press_matrix = matrix(GF(2),5,5,x.list())    # convert vector to a list then a matrix\n",
    "print \"solution: \"\n",
    "button_press_matrix "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lights Out Solver Function (basic version)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition of the solution function for Lights Out\n",
    "# input = integer n (where lights out baord is nxn), and b is the configuration vector\n",
    "# output = a matrix x indicating which buttons to press for a solution\n",
    "def lights_out_solver(n,b):\n",
    "    x=lights_out(n).solve_right(b);\n",
    "    button_press_matrix = matrix(GF(2),n,n,x.list())\n",
    "    return button_press_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0 0 1 0 0]\n",
       "[1 0 1 1 1]\n",
       "[0 1 0 1 0]\n",
       "[1 1 1 0 1]\n",
       "[0 0 1 0 0]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=vector(GF(2), [1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1])\n",
    "lights_out_solver(5,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.2.3 Solvable Configuration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A lit button configuration $\\boldsymbol{b}$ is solvable if the corresponding linear system $A\\boldsymbol{x}= \\boldsymbol{b}$ has a solution. \n",
    "From linear algebra we know\n",
    "\n",
    "$$A\\boldsymbol{x}= \\boldsymbol{b} \\text{ is solvable for every } \\boldsymbol{b} \\quad \\iff  \\quad \\text{$A$ is invertible} \\quad \\iff \\quad  \\det(A)\\ne 0.$$\n",
    "\n",
    "The lights out matrix (for $5\\times 5$ game) has determinant $0$.  Therefore, there do exist unsolvable configurations $\\boldsymbol{b}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lights_out(5).determinant()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example of an unsolvable configuration and how SageMath will let you know with a traceback error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "matrix equation has no solutions",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-19-491bae57dc08>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mvector\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mGF\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mlights_out_solver\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m5\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-15-2e660d04caea>\u001b[0m in \u001b[0;36mlights_out_solver\u001b[1;34m(n, b)\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;31m# output = a matrix x indicating which buttons to press for a solution\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mlights_out_solver\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m     \u001b[0mx\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mlights_out\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msolve_right\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m;\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      6\u001b[0m     \u001b[0mbutton_press_matrix\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mmatrix\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mGF\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      7\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mbutton_press_matrix\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m/opt/sage/src/sage/matrix/matrix2.pyx\u001b[0m in \u001b[0;36msage.matrix.matrix2.Matrix.solve_right (/opt/sage/src/build/cythonized/sage/matrix/matrix2.c:7149)\u001b[1;34m()\u001b[0m\n\u001b[0;32m    401\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    402\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mrank\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnrows\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 403\u001b[1;33m             \u001b[0mX\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_solve_right_general\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mC\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mcheck\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mcheck\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    404\u001b[0m         \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    405\u001b[0m             \u001b[0mX\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_solve_right_nonsingular_square\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mC\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mcheck_rank\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mFalse\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m/opt/sage/src/sage/matrix/matrix2.pyx\u001b[0m in \u001b[0;36msage.matrix.matrix2.Matrix._solve_right_general (/opt/sage/src/build/cythonized/sage/matrix/matrix2.c:8296)\u001b[1;34m()\u001b[0m\n\u001b[0;32m    519\u001b[0m             \u001b[1;31m# Have to check that we actually solved the equation.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    520\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0mX\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[0mB\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 521\u001b[1;33m                 \u001b[1;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m\"matrix equation has no solutions\"\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    522\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0mX\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    523\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mValueError\u001b[0m: matrix equation has no solutions"
     ]
    }
   ],
   "source": [
    "b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])\n",
    "lights_out_solver(5,b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Could use try and except for error proofing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current state has no solution.\n"
     ]
    }
   ],
   "source": [
    "b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])\n",
    "try:\n",
    "    lights_out_solver(5,b)\n",
    "except:\n",
    "    print \"Current state has no solution.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The set of solvable configurations is the column space of the lights out matrix $A$, $\\text{col}(A)=\\text{span}(\\boldsymbol{t}_{1,1}, \\boldsymbol{t}_{1,2},\\ldots,\\boldsymbol{t}_{5,5})$, and the dimension of $\\text{col}(A)$ is called the rank of $A$, denoted $\\text{rank}(A)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lights_out(5).rank()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore only $23$ buttons are required to solve any configuration, and if each one can either be pressed or not, then there are $2^{23}$ solvable configurations, out of a possible $2^{25}$ configurations.  Therefore the probability that a random configuration is solvable is 1/4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quite Patterns (Null Space of Lights Out Matrix)\n",
    "\n",
    "There exist sequences of button presses that will leave the lights unchanged.  These are known as **quiet patterns**. Such a sequence **x** is a solution to the homogeneous equation $A\\boldsymbol{x}= \\boldsymbol{0}$.  That is, **x** is in the null space of $A$, denoted by $\\text{nul}(A)$.  Since $A$ has rank 23 then it has nullity 2 and so $\\text{nul}(A)$ contains 4 vectors:\n",
    "\n",
    "\\begin{align*}\n",
    "\\text{nul}(A)& = \\text{span}(\\boldsymbol{d}_1,\\boldsymbol{d}_2) = \\{ r_1\\boldsymbol{d}_1+r_2\\boldsymbol{d}_2 \\ |\\ r_1, r_2 \\in \\mathbb{F}_2\\}\\\\\n",
    " &=\\{ \\boldsymbol{0},  \\boldsymbol{d}_1,  \\boldsymbol{d}_2, \\boldsymbol{d}_1+ \\boldsymbol{d}_2 \\}.\n",
    " \\end{align*}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vector space of degree 25 and dimension 2 over Finite Field of size 2\n",
       "Basis matrix:\n",
       "[1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 1 0 1 0 1]\n",
       "[0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lights_out(5).right_kernel()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $\\boldsymbol{s_1}$ and $\\boldsymbol{s_2}$ are both solutions of a configuration $\\boldsymbol{b}$ then $A\\boldsymbol{s_1}=A\\boldsymbol{s_2}=b$ so $\\boldsymbol{s_1}-\\boldsymbol{s_2}$ is in the null space of A.\n",
    "\n",
    "Therefore, all solutions for $\\boldsymbol{b}$ are $\\boldsymbol{s_1}+\\text{nul}(A)$:\n",
    "\n",
    "$$\\{ \\boldsymbol{s_1},  \\boldsymbol{s_1}+\\boldsymbol{d}_1,  \\boldsymbol{s_1}+\\boldsymbol{d}_2, \\boldsymbol{s_1}+\\boldsymbol{d}_1+ \\boldsymbol{d}_2 \\}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## 24.2.4 Optimal Solution to Lights Out"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we define a function which counts the number of 1's in a vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Function:  number_of_presses\n",
    "# input = a vector x of dimension 25 with 0,1 entries\n",
    "# output = the number of times 1 appears as an entry\n",
    "def number_of_presses(x):\n",
    "    counter=0;               # initialize counter, which is our variable to count 1's\n",
    "    for i in range(0,25):    # recall python indexes lists from 0, not 1\n",
    "        if x[i]==1: counter=counter+1  # check if the ith entry is 1, increment counter\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])\n",
    "number_of_presses(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Could also do it by converting the vector from GF(2) to $\\mathbb{Q}$ then summing entries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b=vector(GF(2),[1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0, 0,0,0,0,0])\n",
    "bQ = vector(QQ,b.list())   # change field to rationals\n",
    "sum(bQ)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we'll find all 4 solutions to Example 24.1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0) 12\n",
      "(1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1) 8\n",
      "(0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0) 8\n",
      "(1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1) 20\n"
     ]
    }
   ],
   "source": [
    "b=vector(GF(2), [1,1,0,0,1, 1,1,1,0,0, 1,0,0,0,1, 0,0,1,1,1, 1,0,0,1,1])\n",
    "x=lights_out(5).solve_right(b)   # one solution\n",
    "nulsp = lights_out(5).right_kernel()\n",
    "for d in nulsp:\n",
    "    print x+d, number_of_presses(x+d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An optimal solution is (1, 0, 0, 0, 1,   0, 0, 0, 1, 0,   0, 1, 0, 1, 0,   0, 1, 0, 0, 0,  1, 0, 0, 0, 1), which contains 8 presses."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.3 Summary of Lights Out (5x5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1 0 1 0 1]\n",
       "[1 0 1 0 1]\n",
       "[0 0 0 0 0]\n",
       "[0 0 0 0 0]\n",
       "[0 0 0 0 0]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Definition of the matrix for Lights Out\n",
    "# input = integer n (where lights out board is nxn)\n",
    "# output = lights out matrix A which is n^2 x n^2\n",
    "def lights_out(n):\n",
    "    A = identity_matrix(GF(2),n*n)     # initialize A with ones along diagonal\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            m = n*i+j               \n",
    "            if i > 0 : A[(m,m-n)] = 1   # I block below diagonal\n",
    "            if i < n-1 : A[(m,m+n)] = 1 # I block above diagonal\n",
    "            if j > 0 : A[(m,m-1)] = 1   # C block below diagonal\n",
    "            if j < n-1 : A[(m,m+1)] = 1 # C block above diagonal\n",
    "    return A\n",
    "\n",
    "\n",
    "# Function:  number_of_presses\n",
    "# input = a vector x of dimension 25 with 0,1 entries\n",
    "# output = the number of times 1 appears as an entry\n",
    "def number_of_presses(x):\n",
    "    counter=0;\n",
    "    for i in range(0,25):\n",
    "        if x[i]==1: counter=counter+1\n",
    "    return counter\n",
    "\n",
    "# Function:  optimal_solution\n",
    "# input = a strategy vector x\n",
    "# output = an equivalent strategy vector which uses the minimum number of button presses\n",
    "def optimal_solution(x):\n",
    "    op_button_presses=x\n",
    "    n=number_of_presses(x)\n",
    "    nul=lights_out(5).right_kernel()\n",
    "    for d in nul:\n",
    "        if number_of_presses(x+d)<n:\n",
    "            op_button_presses=x+d     # update variable\n",
    "            n=number_of_presses(x+d)  # update variable\n",
    "    return op_button_presses\n",
    "\n",
    "# Function:  lights_out_solver\n",
    "# input = b the configuration vector of lights on 5-by-5 game\n",
    "# output = a matrix which solve the puzzle using the least number of button presses\n",
    "def lights_out_solver(b):\n",
    "    x=lights_out(5).solve_right(b);  # one solution\n",
    "    x=optimal_solution(x)     # exchanges x for an optimal solution\n",
    "    button_press_matrix = matrix(GF(2),5,5,x.list())\n",
    "    return button_press_matrix\n",
    "\n",
    "# Example\n",
    "b=vector(GF(2),[0,0,0,0,0, 0,0,0,0,0, 1,0,1,0,1, 0,0,0,0,0, 0,0,0,0,0]);\n",
    "lights_out_solver(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 24.4 Eigenvalues and Eigenvectors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I25=MatrixSpace(GF(2),25,25).identity_matrix()   # 25x25 identity matrix\n",
    "A=lights_out(5);\n",
    "(A-I25).nullity()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 7.3",
   "language": "",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}