{"nbformat_minor": 0, "worksheets": [{"cells": [{"source": ["Sudoku using POCS and Sparsity\n", "==============================\n", "\n*Important:* Please read the [installation page](http://gpeyre.github.io/numerical-tours/installation_matlab/) for details about how to install the toolboxes.\n", "$\\newcommand{\\dotp}[2]{\\langle #1, #2 \\rangle}$\n", "$\\newcommand{\\enscond}[2]{\\lbrace #1, #2 \\rbrace}$\n", "$\\newcommand{\\pd}[2]{ \\frac{ \\partial #1}{\\partial #2} }$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\umax}[1]{\\underset{#1}{\\max}\\;}$\n", "$\\newcommand{\\umin}[1]{\\underset{#1}{\\min}\\;}$\n", "$\\newcommand{\\uargmin}[1]{\\underset{#1}{argmin}\\;}$\n", "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n", "$\\newcommand{\\abs}[1]{\\left|#1\\right|}$\n", "$\\newcommand{\\choice}[1]{ \\left\\{  \\begin{array}{l} #1 \\end{array} \\right. }$\n", "$\\newcommand{\\pa}[1]{\\left(#1\\right)}$\n", "$\\newcommand{\\diag}[1]{{diag}\\left( #1 \\right)}$\n", "$\\newcommand{\\qandq}{\\quad\\text{and}\\quad}$\n", "$\\newcommand{\\qwhereq}{\\quad\\text{where}\\quad}$\n", "$\\newcommand{\\qifq}{ \\quad \\text{if} \\quad }$\n", "$\\newcommand{\\qarrq}{ \\quad \\Longrightarrow \\quad }$\n", "$\\newcommand{\\ZZ}{\\mathbb{Z}}$\n", "$\\newcommand{\\CC}{\\mathbb{C}}$\n", "$\\newcommand{\\RR}{\\mathbb{R}}$\n", "$\\newcommand{\\EE}{\\mathbb{E}}$\n", "$\\newcommand{\\Zz}{\\mathcal{Z}}$\n", "$\\newcommand{\\Ww}{\\mathcal{W}}$\n", "$\\newcommand{\\Vv}{\\mathcal{V}}$\n", "$\\newcommand{\\Nn}{\\mathcal{N}}$\n", "$\\newcommand{\\NN}{\\mathcal{N}}$\n", "$\\newcommand{\\Hh}{\\mathcal{H}}$\n", "$\\newcommand{\\Bb}{\\mathcal{B}}$\n", "$\\newcommand{\\Ee}{\\mathcal{E}}$\n", "$\\newcommand{\\Cc}{\\mathcal{C}}$\n", "$\\newcommand{\\Gg}{\\mathcal{G}}$\n", "$\\newcommand{\\Ss}{\\mathcal{S}}$\n", "$\\newcommand{\\Pp}{\\mathcal{P}}$\n", "$\\newcommand{\\Ff}{\\mathcal{F}}$\n", "$\\newcommand{\\Xx}{\\mathcal{X}}$\n", "$\\newcommand{\\Mm}{\\mathcal{M}}$\n", "$\\newcommand{\\Ii}{\\mathcal{I}}$\n", "$\\newcommand{\\Dd}{\\mathcal{D}}$\n", "$\\newcommand{\\Ll}{\\mathcal{L}}$\n", "$\\newcommand{\\Tt}{\\mathcal{T}}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\al}{\\alpha}$\n", "$\\newcommand{\\la}{\\lambda}$\n", "$\\newcommand{\\ga}{\\gamma}$\n", "$\\newcommand{\\Ga}{\\Gamma}$\n", "$\\newcommand{\\La}{\\Lambda}$\n", "$\\newcommand{\\si}{\\sigma}$\n", "$\\newcommand{\\Si}{\\Sigma}$\n", "$\\newcommand{\\be}{\\beta}$\n", "$\\newcommand{\\de}{\\delta}$\n", "$\\newcommand{\\De}{\\Delta}$\n", "$\\newcommand{\\phi}{\\varphi}$\n", "$\\newcommand{\\th}{\\theta}$\n", "$\\newcommand{\\om}{\\omega}$\n", "$\\newcommand{\\Om}{\\Omega}$\n"], "metadata": {}, "cell_type": "markdown"}, {"source": ["This numerical tour explores the use of numerical schemes to solve the\n", "Sudoku game.\n", "\n", "\n", "This tour was written by <http://lcav.epfl.ch/~lu/ Yue M. Lu> and\n", "<http://www.ceremade.dauphine.fr/~peyre/ Gabriel Peyr >.\n", "\n", "\n", "The idea of encoding the Sudoku rule using a higer dimensional lifting,\n", "linear constraints and binary constraint is explained in:\n", "\n", "\n", "Andrew C. Bartlett, Amy N. Langville,\n", "_An Integer Programming Model for the Sudoku Problem,_\n", "The Journal of Online Mathematics and Its Applications, Volume 8. May 2008.\n", "\n", "\n", "The idea of removing the binary constraint and using sparsity constraint\n", "is exposed in:\n", "\n", "\n", "P. Babu, K. Pelckmans, P. Stoica, and J. Li,\n", "_Linear Systems, Sparse Solutions, and Sudoku_,\n", "IEEE Signal Processing Letters, vol. 17, no. 1, pp. 40-42, 2010.\n", "\n", "\n", "This tour elaborarates on these two ideas. In particular it explains\n", "why $L^1$ minimization is equivalent to a POCS (projection on convex sets)\n", "method to find a feasible point inside a convex polytope."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 2, "cell_type": "code", "language": "python", "metadata": {}, "input": ["addpath('toolbox_signal')\n", "addpath('toolbox_general')\n", "addpath('solutions/sparsity_7_sudoku')"]}, {"source": ["Game Encoding and Decoding\n", "--------------------------\n", "The basic idea is to use a higher dimensional space of size |(n,n,n)| to represent\n", "a Sudoku matrix of size |(n,n)|. In this space, the arrays are\n", "constrained\n", "to have binary entries.\n", "\n", "\n", "Size of the Sudoku. This number must be a square."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 3, "cell_type": "code", "language": "python", "metadata": {}, "input": ["n = 9;"]}, {"source": ["Create a random integer matrix with entries in 1...9."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 4, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x = floor(rand(n)*n)+1;"]}, {"source": ["Comparison matrix used for encoding to binary format."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 5, "cell_type": "code", "language": "python", "metadata": {}, "input": ["U = repmat( reshape(1:n, [1 1 n]), n,n );"]}, {"source": ["Encoding in binary format."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 6, "cell_type": "code", "language": "python", "metadata": {}, "input": ["encode = @(x)double( repmat(x, [1 1 n])==U );\n", "X = encode(x);"]}, {"source": ["The resulting matrix has binary entries and\n", "has size |(n,n,n)|. One has |x(i,j)=k| if |X(i,j,k)=1| and |X(i,j,l)=0|\n", "for |l~=k|.\n", "\n", "\n", "Decoding from binary format. One use a |min| to be able to recover even\n", "if the matrix |X| is not binary (because of computation errors)."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 7, "cell_type": "code", "language": "python", "metadata": {}, "input": ["[tmp,x1] = min( abs(X-1), [], 3 );"]}, {"source": ["Show that decoding is ok."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 8, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 0: ' num2str(norm(x-x1,'fro')) '.']);"]}, {"source": ["Encoding Constraints\n", "--------------------\n", "For |X| to be a valid encoded matrix, it should be binary and satifies\n", "that each |X(i,j,:)| contains only a single |1|, which can be represented\n", "using a linear contraint |Aenc*X(:)=1|.\n", "\n", "\n", "Now we construct one encoding constraint."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 9, "cell_type": "code", "language": "python", "metadata": {}, "input": ["i = 4; j = 4;\n", "Z = zeros(n,n,n);\n", "Z(i,j,:) = 1;"]}, {"source": ["Add this constraint to the encoding constraint matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 10, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Aenc = [];\n", "Aenc(end+1,:) = Z(:)';"]}, {"source": ["Show that constraint is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 1: 1.\n"], "output_type": "display_data"}], "prompt_number": 11, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 1: ' num2str(Aenc*X(:)) '.']);"]}, {"source": ["__Exercise 1__\n", "\n", "Build the encoding matrix |Aenc|. Display it."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAKDElEQVR4nO3c0U4z\nRxZGURjN+78yc/FH0ciIUDFgf5te6y65OjrVZpcbkte3t7cXAKj5z7MHAIB7CBgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAk\nCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAk\nCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQNJ/nz3Aj3t9ff3/f3x7\ne7v5Nws2pxq0uajNqQZZ1KGRRb29vT17hE9c7hvY+8di4ZAWHtZPWdRH3l+SnjXJP1iYavP4bmwu\namGqQZcL2Huffqg8On9Y1KHNRW1ONWhzUZtTPZ2Afc79+pD79aHN+7XjO7S5qMSPqW8nYP9a4vF9\n7yIP9Kc2F7U51SCLOnSRRQnYczz+6dns7qc2F7U51SCLOmRR97liwBauHomnZ3NRm1MNsqhDm4ta\nmGrfFQN2kS/XX7e5qM2pBlnUoc1FbU615ooB+5RH59DmojanGmRRhzYXtTnVgwnYPbwYObS5qMTf\nay1MtXl8NzYXtTnV7yNgv5YL2qHNRW1ONWhzUZtT/T4CtmLzz5B8zF5WFxW9X28uanMqPiVgLy8b\nP6Y3H2hv2w5tHt+NzUVtTjVoYVFrBOzlxff9Y5uL2pxq0OaiNqcaZFHvCdgRF7RD7td3s6iPeA1w\naPP4fpSA/R6bF7TNqQZZ1KHNRW1O9esJ2NNs/t54c6pBFnVoc1GbU/FvXTRgC7ehzQd6c6obju/Q\n5qI2pxq0sKhxFw1Y9Pv+5lSPFz2+x9tc1OZUgyzqUxcN2Kc2H53NqQZZ1KHNRW1ONciiBOxOm68g\n/L3Woc3ju7G5qM2pBlnUAwjYb7Z5QducatDmojanGmRRDyBgQzb/MmpzqkGbi9qcapBFFQnYXxZu\nQ17X3M2iPuKt8qHN47uxsKgpAvaXze/7m1MNii7Krf+P6PE9nkXdELBTvh7dzaI+4uvRoc3ju7G5\nqIWpfo6A3c9t6JBFHdpc1OZUgzYXtTnVd7lQwLyuOWRRhzYXtTnVoM1FbU4160IB87rmUOKB3lzU\n5lSDLOojiR9TOy4UsBuJx/c9D/Qfm4vanGqQRR2yqH923YBFeaAPbS5qc6pB0UV5AfhgAvadFj5U\niQd6c1GbUw2yqI8kXgBuTnUfAftO0Wvj420uanOqQRZ1aHNRm1Pd59IB833/0OaiNqcaZFGHNhe1\nOdWISwcscU4Lt6HNRXldc2jz+G5sLmpzKv526YAl/Kbv+z9q83Pu+A5tLmpzKv4mYF+y8Phu/uC+\nsbCo9xamcnyHNhe1OdWNheP7IQL2JS5ohzYXtTnVoOiiNqd6vOjxnbhWwPw69NDmojanGrS5qM2p\nBlnUuWsFLHFOC7chv82+m0V9xB/dHNo8vk3XCljC5vf9zakGWdShzUVtTsVHBKxn8zO2OdUgizq0\nuajNqS5LwL7ZwuPrBeDdLOrQ5qI2pxq0sKhvIWDfbPOCtjnVIIs6tLmozakG/ZpFCdijVa6NC1MN\nqizq6VNtfhGpHN/TbR7fewL2fJu3oc2pBm0uanOqQRaVJmABm5+xzakGbS5qc6pBFrVMwL5q4fHd\nfDGSeAthUR/xn20d2jy+GwuL+gkC9lWbF7TNqQZFF+V/1vBH9Pge77cu6jU6NwAX5xsYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkDS/wAZqjaI\ncWvurwAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 12, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo1()"]}, {"collapsed": false, "outputs": [], "prompt_number": 13, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Show that constraint |Aenc*X(:)=1| is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 14, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 0: ' num2str(norm(Aenc*X(:)-1)) '.']);"]}, {"source": ["Sudoku Rules Constraints\n", "------------------------\n", "In a Sudoku valid matrix |x|, each column, row and sub-square of |x| should\n", "contains all the values in 0...n. This can be encoded on the high dimensional |X| using linear\n", "constraints |Arow*X=1|, |Acol*X=1| and |Ablock*X=1|.\n", "\n", "\n", "A valid Sudoku matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["\n", "x =\n", "\n", "     8     1     9     6     7     4     3     2     5\n", "     5     6     3     2     8     1     9     4     7\n", "     7     4     2     5     9     3     6     8     1\n", "     6     3     8     9     4     5     1     7     2\n", "     9     7     1     3     2     8     4     5     6\n", "     2     5     4     1     6     7     8     9     3\n", "     1     8     5     7     3     9     2     6     4\n", "     3     9     6     4     5     2     7     1     8\n", "     4     2     7     8     1     6     5     3     9\n", "\n"], "output_type": "display_data"}], "prompt_number": 15, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x = [8 1 9 6 7 4 3 2 5; \n", "     5 6 3 2 8 1 9 4 7; \n", "     7 4 2 5 9 3 6 8 1; \n", "     6 3 8 9 4 5 1 7 2; \n", "     9 7 1 3 2 8 4 5 6; \n", "     2 5 4 1 6 7 8 9 3;\n", "     1 8 5 7 3 9 2 6 4;\n", "     3 9 6 4 5 2 7 1 8; \n", "     4 2 7 8 1 6 5 3 9]"]}, {"source": ["Encode it in binary format."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 16, "cell_type": "code", "language": "python", "metadata": {}, "input": ["X = encode(x);"]}, {"source": ["Select the index of the entries of a row."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 17, "cell_type": "code", "language": "python", "metadata": {}, "input": ["i=3; k=5;\n", "Z = zeros(n,n,n);\n", "Z(i,:,k) = 1;"]}, {"source": ["Fill the first entries of the row matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 18, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Arow = [];\n", "Arow(end+1,:) = Z(:)';"]}, {"source": ["Show that constraint is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 1: 1.\n"], "output_type": "display_data"}], "prompt_number": 19, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 1: ' num2str(Arow*X(:)) '.']);"]}, {"source": ["__Exercise 2__\n", "\n", "Build the full row matrix |Arow|. Display it."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAIX0lEQVR4nO3b24ob\nORRAUXvI//9yzcOEMCS4q+NL1dmqtR4b0RiieEvKyX3bthsA1Pxz9gcAgGcIGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA0o+zP8DH3e/3sz/Cvm3b\nvv6cBywA+L9t287+CDvcwEbYTcsBC3Y364QFAL8IGD9NiGjijvhnZX/7yQELgNvtdl/+L0biOxFe\nNOEV2jP1YubXwQ0MVjDhfpyo14SX8PlhqLhiwGxQuKwJIU+UPuGKAZuwQSdEVGWBtCsGbIIJEU0c\nAydMTCg9zGSIA9ZkaoMXza+DGxisacIlfsJL+PxvYZ4mYMCnTIho4o74xP/8k/abgM1hv8Jl/VlZ\naf8OAZtiwn41MQGEGOKANzAxwXrm18ENDN5g5gV64AJ4IwGDRUyIaOKOaGJiGRcNmP0Kl2ViYhkX\nDdiE/fpEAk1MAPxiiIMeExNwgPl1uOgNjLQJF+iECbd8+BwBg2U90enffvL6AhMTfI6AAR9kYuJp\nSr9LwM70+muMHQyrUvpdAnamv32N2f0Nn1ggosBMAsaOCRFNMDEBBxMweI/ExMQpz9TwIQIG63g9\ngd/5nX+7IMFTedGFAjbhKGoHw0yeyosuFLAJR1ETEwDvcqGAJUyIaIKJCUDASJowMTHThEu80nMM\nAYOlTLjEeyrnGAIGHG1CRGc64KF7pfYL2MkmHEVD+xXWdsBD90rtF7CTTTiKnvLgY2ICeJGAse8T\njTQxcdgCWJWAwfMm3I9NTHBZAgaLmxDRmUxM1F0rYBOOovYrDGFiou5aAZtwFDUxAfAW1wpYgomJ\nRybcj5Ue5hAwMibcj5X+0YLdWz68nYDBak4J+e4t/+0TE58YqaDlvvyfaOLIDPCfbdu+/tY6bMH8\nOlz9BmZiAhhlwkt45dx/9YCZmHhkwkCE0gNfuHrAeGTCKU/pHy0wMQE3AYMXmZh4RFb5tMA/070o\ncYoHTjFnYuLrz3mK+XVYP2AALMkTIgBJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZA0r83UVooSa356wAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 20, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo2()"]}, {"collapsed": false, "outputs": [], "prompt_number": 21, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Show that constraint |Arow*X(:)=1| is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 22, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 0: ' num2str(norm(Arow*X(:)-1)) '.']);"]}, {"source": ["__Exercise 3__\n", "\n", "Build the full column matrix |Acol|. Display it."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAHsElEQVR4nO3bwW7b\nMBQAwTjo//+ye2hRtEkPdODIb8mZm2+E8agVBel2v9/fAKDm/dULAICvEDAAkgQMgCQBAyBJwABI\nEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJ\nwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQB\nAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQM\ngCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAA\nkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABI\nEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJ\nwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQB\nAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQM\ngCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAA\nkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABI\nEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJ\nwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgKQfr17At7vdbq9ewn/c7/e/\nf85cJHCyD5epgfYP2EwDi/V5WAcuEuAPAeM3uVqk9DCEgMFjZuZKVjmQgMEO5GqR0u/kuIAZXziZ\n/b6T4wI2c3xlFeBRxwVsJrlapPTAHwJGiVyt860h2xMw2NPAYjlA81wCBlxErhYp/SIBG8rzHziW\n/b5IwIYaOMHuCoFRBIxVcrVI6eEaAgZPNjNXssp+BAyOIFeLlD5EwD4yvnAy+z1EwD6aOb6yCvCB\ngDXI1SKlh3MIGFuRq3W+NaROwOBQA4vlAM1DBAyYQq4WKf0vAlbl+Q8cy37/RcCqBk6wu0LgSgLG\n08jVIqWHpxAwuNrMXMkqOQIGvL3J1TKln0PAHmZ84WT2+xwC9rCZ4yurwGkEbBNytUjpYRsCxlnk\nap1vDRlOwID/G1gsB2j+JmBAhlwtOqT0ArYtz3/gWIfsdwHb1sAJPuSuELiGgHEduVqk9LBCwGCc\nmbmSVaYRMGCJXC1S+ssI2LfwAgUcy36/jIB9i4ET7K4Q2IyAnUKuFik9VAgY/EOu1nlUzmsJGPBF\nA4vlAH0UAQP2IVeL9ii9gF1hj1kBtrHHJUjArrDHrFxA6YF1AsYgcrXOCxQgYJA0sFgO0FxMwIDn\nkKtFSv8st89/JQDM9/7qBQDAVwgYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEk/AVHwoEspQNTnAAAAAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 23, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo3()"]}, {"collapsed": false, "outputs": [], "prompt_number": 24, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Show that constraint |Acol*X(:)=1| is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 25, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 0: ' num2str(norm(Acol*X(:)-1)) '.']);"]}, {"source": ["Now we proceed to block constraints.\n", "\n", "\n", "Size of a block."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 26, "cell_type": "code", "language": "python", "metadata": {}, "input": ["p = sqrt(n);"]}, {"source": ["The upper left square should contain\n", "all numbers in |{1,...,n}|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 27, "cell_type": "code", "language": "python", "metadata": {}, "input": ["k = 1;\n", "Z = zeros(n,n,n);\n", "Z(1:p,1:p,k) = 1;"]}, {"source": ["Add it as the first row of the block constraint matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 28, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Ablock = [];\n", "Ablock(end+1,:) = Z(:)';"]}, {"source": ["Show that constraint is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 1: 1.\n"], "output_type": "display_data"}], "prompt_number": 29, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 1: ' num2str(Ablock*X(:)) '.']);"]}, {"source": ["__Exercise 4__\n", "\n", "Create the full block matrix. Display it."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAH0UlEQVR4nO3bOZIi\nQRAAQRjb/3+5V1hldgbjPjKq3UUMoYQ2gkyo47ZtBwCo+fr0AQDgHgIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAk\nCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAk\nCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIG\nQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZD059MHeLnj8fjpI5ywbdv3g23b\ndvj/qD/eAPBm/z6XJjvOP+KDZOBKJyP6/ZXfbwAWNr8OAga3UXp2Yn4dBAxWcHELLavcan4dBAzY\nEQP09ebXQcB+8nwDHARsgjVKY0EEvNn8OggYSzFAw7PMr4OAwU65jMh58+sgYMAUBuhR5tdBwABi\n3lP6+XUQsGVZEAGPmF8HAeN9LIggZH4dBAzGuVj6gwGa15tfBwEDruIy4t7Mr4OAATzTMqvy+XXY\nS8AuPkCVRwrgPebXYS8BG2iZr2nAkubXQcAIcCUA3m9+HQQM1mFVzhPNr4OAAS/kSkDX/DoIGMAI\n0wbo+XUQsJJpzzewsPl1EDAe5R8WsKT5dRAweBMDNC3z6yBgsF8uI3LG/DoIGMBl16zKD2t94Myv\ng4A9jQURsJL5dRCwlVkQAXebXwcBg8PBAA2/zK+DgAE3UPr9mF8HAQPyXEZ8hfl1EDCAvbhpgJ5f\nBwH7MP+zAGaaXwcB4wS/cwDz6yBgcL+Lv7UoPV3z6yBgsBoDNE8xvw4CBuyU0p83vw4Cdo4FEbBb\n8+sgYD2+NgJvML8OAsayDNDwiPl1EDDYO5cROWl+HQQMmMiq/OPm10HAAMJetyqfXwcBezJfG4E1\nzK+DgPEZSg/Dza+DgMFo/mHBp8yvg4ABNzNA78H8OggYwKukLyPOr8P6AQNgSV+fPgAA3EPAAEgS\nMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnA\nAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyA\nJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACS\nBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgS\nMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnA\nAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyA\nJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACS\nBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgS\nMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnA\nAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEj6C67W5LkE\nkFfoAAAAAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 30, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo4()"]}, {"collapsed": false, "outputs": [], "prompt_number": 31, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Show that constraint |Ablock*X(:)=1| is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 32, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['Should be 0: ' num2str(norm(Ablock*X(:)-1)) '.']);"]}, {"source": ["Inpainting Constraint\n", "---------------------\n", "A Sudoku game asks to fill the missing entries of a partial\n", "Sudoku matrix |x1| to obtain a full Sudoku matrix |x|.\n", "\n", "\n", "The fact that for each available entry |(i,j)| on must have\n", "|x(i,j)=x1(i,j)| can be encoded using a linear constraint.\n", "\n", "\n", "Load a Sudoku with missing entries, that are represented as 0.\n", "This is an easy grid."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 33, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x1 = [0 1 0 0 0 0 3 0 0; \n", "     0 0 3 0 8 0 0 4 0; \n", "     7 0 2 0 0 3 0 0 1; \n", "     0 3 0 9 4 0 1 0 0; \n", "     9 0 0 0 0 0 0 0 6; \n", "     0 0 4 0 6 7 0 9 0;\n", "     1 0 0 7 0 0 2 0 4;\n", "     0 9 0 0 5 0 7 0 0; \n", "     0 0 7 0 0 0 0 3 0];"]}, {"source": ["Retrieve the indexes of the available entries."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 34, "cell_type": "code", "language": "python", "metadata": {}, "input": ["[I,J] = ind2sub( [n n], find(x1(:)~=0) );\n", "v = x1(x1(:)~=0);"]}, {"source": ["Create a vector corresponding to the constraint that |x1(I(i),J(i))==v(i)|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 35, "cell_type": "code", "language": "python", "metadata": {}, "input": ["i = 1;\n", "Z = zeros(n,n,n);\n", "Z(I(i), J(i), v(i)) = 1;"]}, {"source": ["Fill the first entries of the row matrix."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 36, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Ainp = [];\n", "Ainp(end+1,:) = Z(:)';"]}, {"source": ["__Exercise 5__\n", "\n", "Build the full inpainting matrix |Ainp|. Display it."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAGvklEQVR4nO3ZQVbE\nIBBAwcHn/a+Mexej8cXAT6pO0Ct+A2PO+QKAmo/VAwDAXwgYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkDS5+oB/t0YY/UIAD1zztUj/MANDICk\nxwVs/50CgN94XMC8KALcw+MCBsA9CBgASQIGkORHX8AAjtmkHH70BQzgGOXYhIABkCRgQM8mj3is\nJWBcx6HDWTzi8RKwJ9gnGw4d4EQCdn+ycdQ+yQfeEDD4TvIhQcAuYqkHOJeAXcRSD3Cu4WYAQJEb\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZA0hdDQyRbIyuWEgAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 37, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo5()"]}, {"collapsed": false, "outputs": [], "prompt_number": 38, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Show that constraint |Ainp*X1(:)=1| is satisfied."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 0.\n"], "output_type": "display_data"}], "prompt_number": 39, "cell_type": "code", "language": "python", "metadata": {}, "input": ["X1 = encode(x1);\n", "disp(['Should be 0: ' num2str(norm(Ainp*X1(:)-1)) '.']);"]}, {"source": ["Solving the Sudoku by Binary Integer Programming\n", "------------------------------------------------\n", "The whole set of constraints can be written |A*X(:)=1|, where the matrix\n", "|A| is defined as a concatenation of all the constraint matrices."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 40, "cell_type": "code", "language": "python", "metadata": {}, "input": ["A = [Aenc; Arow; Acol; Ablock; Ainp];"]}, {"source": ["Pre-compute the pseudo-inverse of A."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 41, "cell_type": "code", "language": "python", "metadata": {}, "input": ["pA = pinv(A);"]}, {"source": ["If the Sudoku game has an unique solution |x|, then the corresponding\n", "lifted vector |X| is the only solution to |A*X(:)=1| under the constraint that |X| is binary.\n", "\n", "\n", "This is the idea proposed in:\n", "\n", "\n", "Andrew C. Bartlett, Amy N. Langville,\n", "_An Integer Programming Model for the Sudoku Problem,_\n", "The Journal of Online Mathematics and Its Applications, Volume 8. May 2008.\n", "\n", "\n", "Unfortunately, solving a linear system under binary constraints is\n", "difficult, in fact solving a general integer program is known to be NP-hard.\n", "It means that such a method is very slow to solve Sudoku for large\n", "|n|.\n", "\n", "\n", "One can use branch-and-bounbs methods to solve the binary integer\n", "program, but this might be slow. One can use for instance the\n", "command |bintprog| of Matlab (optimization toolbox), with\n", "an arbitrary objective function (since one wants to solve a feasability\n", "problem,\n", "no objective is needed)."], "metadata": {}, "cell_type": "markdown"}, {"source": ["__Exercise 6__\n", "\n", "Implement the Soduku solver using an interger linear programming\n", "algorithm."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 42, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo6()"]}, {"collapsed": false, "outputs": [], "prompt_number": 43, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Removing the Binary Constraint\n", "------------------------------\n", "If one removes the binary constraint, one simply wants to\n", "compute a solution to\n", "the linear system |A*X(:)=1|. But unfortunately it has an infinite number of\n", "solutions (and the set of solutions is not bounded).\n", "\n", "\n", "It is thus unlikely that chosing a solution at random will work, but\n", "let's try it by projecting\n", "any vector on the constraint |A*X(:)=1|.\n", "\n", "\n", "First define the orthogonal projector on the constraint |{X \\ A*X(:)=1}|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 44, "cell_type": "code", "language": "python", "metadata": {}, "input": ["projector = @(u)reshape( u(:) - pA*(A*u(:)-1), [n n n]);"]}, {"source": ["We project an arbitrary vector (that does not satisfy the constraint) onto the\n", "constraint |A*X(:)=1|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 45, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xproj = projector( zeros(n,n,n) );"]}, {"source": ["Check that |Xproj| projects onto itself because it satisfies the constraints."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Should be 0: 4.1665e-14.\n"], "output_type": "display_data"}], "prompt_number": 46, "cell_type": "code", "language": "python", "metadata": {}, "input": ["d = projector(Xproj)-Xproj;\n", "disp(['Should be 0: ' num2str(norm(d(:), 'fro')) '.']);"]}, {"source": ["Plot the histogrtam of the entries of |Xproj|. As you can see, they are not\n", "binary, meaning that the binary constraint is violated."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAKFklEQVR4nO3dQXLa\nSABAUXrKB/ZRfOOeBRWVBoMDzjjwW+8tUmCzUFtEn26EGHPOEwDU/PPsDQCA7xAwAJIEDIAkAQMg\nScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAk\nAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDICkt2dvwGPGGHPO7fb5\nxvknF3cvHgPAQ/bH0teUCdjVFO3TtQ/b/u9+sQ8ufruSxNDGGKfTx90Pf7+1W1ey8NBOS49u4aGd\nIq/+M0uIc86L58rCTx0AfiszA7vl/CLoixcLidcRAE+XO1qGA3axcnjL5yXEH9wmgKzcCQSZJcSr\nvrGKuPDC48JDOy09uoWHdlp6dAsPraI6Azu/OtifeXj1LEQAVhUL2Banz5XSLYBDaS8hAnBYAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZA0tuzN+AxY4w553b7fOP8k4u7AKwtE7CtT9vdi5Lt72oYwPIyS4hzTlkCYJOZgX3b\nxdRNBQGuujhavr71A6ZYAPfYHy0TMcssIQLAXnUGNud0FiLAkcUCto/TRah0C+BQLCECkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJse8D48KjX/vt\nW9OAZQjYAj7ufuT7D24FwN9lCRGAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIMml\npI7l0Wsn3s9VFoG/TMCO5qELJ7rKIvC6LCECkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkPT27A34I2OM0+k0\n59xub3cBWFs4YGOMfbq2bm0/B2BhlhABSArPwE67ude2fnjrMRuTM4CrvjiQvqZqwPbrhF//0RUL\n4B77o2UiZpYQAUiqzsD2y4bOQgQ4oGrATp9CpVsAh2IJEYAkAQMgScAASBIwAJIEDIAkAQMgScAA\nSBIwAJIEDIAkAQMgScAASBIwAJIEDICk8NXoeSmJr78DViJg/F8+7nvY+89uBXAYlhABSBIwAJIE\nDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIw\nAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAA\nSHp79gZwaYzx7E0ACBCw1/Rx9yPff3ArAF6YJUQAksIzsG2pbc75+S4Aa6sG7Jyrfbq2bo0xNAxg\nee0lxDGGXAEcU3UGdvrvlOuLh138Vu0ArsqdAh0O2J0UC+Ae+6NlImbtJUQADqs6A5tzOgsR4Miq\nATt9CpVuARyKJUQAkgQMgCQBAyAp/B4YR/DQubzeB4VDETBenAvzA9dZQgQgScAASBIwAJIEDIAk\nAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIE\nDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIw\nAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASHp79gYcwhjj2ZsAsBoB+2s+7n7k+w9uBcAqLCEC\nkJQP2LY6N3557vYA8He0lxD39Zpzfr4NwKrCMzChAjiy9gzsHheLipoHcFXuLZhqwM5/6P2/tygW\nwD32R8tEzKpLiPOXk0QBHFJ1BnZhzrm9XtAzgCPIB2zLlW4BHEp1CRGAgxMwAJIEDIAkAQMgScAA\nSBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMg\nScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJLenr0BVWOMZ28CwAPWO2oJ2J/4\nuPuR7z+4FQD3WuqoZQkRgCQBAyBJwABIEjAAkgQMgCQBAyBJwABI8jkw1vHQ5zTnnD+3JcBfIGCs\nZKkPaQJfs4QIQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQFL4ShzbdYPO1wS6uAvA2sIB\nO/03XVu3xhgaBrC88BKiSgEcWXsGdvo13/riMuQXv5I9gDWEA3axcniLYgEsKbyEeBIngAOrzsDO\n06/9mYfOQgQ4lGrAPldKtwAOpb2ECMBhCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgA\nSQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZD09uwN\neCFjjGdvAgD3ErALH3c/8v0HtwKA37GECECSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCS\ngAGQ5FJSHNRDl76cc/7clgDfI2AcluteQpslRACSBAyAJAEDIEnAAEha/yQO37MMsKT1A+ZkM4Al\nWUIEIEnAAEgSMACSBAyAJAEDIEnA4MnW/qTHwqNbeGgVRziNHv6US9fDC1oqYNtRxhGE/5tPE8LL\nWSdgY4ytW/vbACxpnQP91YBZpAb4ntevwzozsKtefwcA8D3OQgQgScAASFrnPbCTsxABjmSpgAFw\nHIufxPHFnGyx6dpxhrPASL8eQv1DILdGt/aOO/+qO7SrXv+puHLAfvvJsO1U+xffSb+12Gfg1t5x\nX4+u/sGPW6PbH9/X23H7z+0Uh/ZZ5Xl43JM41nieHdDCO26Zw98tY4zlx7iGOWdiN608A7uH/05R\ndlzOSosEny25hPj6lgrYQ9NeT7ioVXfceVzbv+sNcFWLLeC3LBWwR99O8FSLWnLHOQjCoxb/r/L5\nrKHz0eGibQv8ERY4xWtv7R13MbpbZwRE3RrdAk/R3z4tu0O76vWfiq++fQBw1XHPQgQgTcAASBIw\nAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAA\nSBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMg\nScAASPoXUmBqvigpS1YAAAAASUVORK5CYII=\n", "output_type": "display_data"}], "prompt_number": 47, "cell_type": "code", "language": "python", "metadata": {}, "input": ["clf;\n", "hist(Xproj(:), 30);\n", "axis('tight');"]}, {"source": ["It is thus not a\n", "solution to the Sudoku problem.\n", "We emphasize this by counting\n", "the number of violated constraints after decoding / re-encoding."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Number of violated constraints: 119.\n"], "output_type": "display_data"}], "prompt_number": 48, "cell_type": "code", "language": "python", "metadata": {}, "input": ["[tmp,xproj] = min( abs(Xproj-1), [], 3 );\n", "Xproj1 = encode(xproj); \n", "disp(['Number of violated constraints: ' num2str(sum(A*Xproj1(:)~=1)) '.']);"]}, {"source": ["Solving the Sudoku by Projection on Convex Sets\n", "-----------------------------------------------\n", "A way to improve the quality of the result is to find a vector that\n", "satisfies both |A*X(:)=1| and |0<=X<=1|. Note that this last constraint\n", "can be modified to |X>=0| because of the fact that the entries of |X(i,j,:)|\n", "must sum to 1 because of |A*X(:)|.\n", "\n", "\n", "A way to find a point inside this polytope\n", "|P = {X \\ A*X(:)=1 and X>=0}| is to start from a random initial guess."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 49, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xproj = zeros(n,n,n);"]}, {"source": ["And iteratively project on each constraint. This corresponds to the POCS\n", "algorithm to find a feasible point into the (non empty) intersection of\n", "convex sets."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 50, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xproj = max( projector(Xproj),0 );"]}, {"source": ["__Exercise 7__\n", "\n", "Perform iterative projections (POCS) on the two constraints |A*Xproj(:)=1| and\n", "|Xproj>=0|. Display the decay of the error |norm(A*Xproj(:)-1)| in logarithmic scale."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAORElEQVR4nO3d0Xbb\nOLZFUeKO/P8v4z6orWJEipYUisAG5nyokbJdLbYSe/kcInKptS4AkOb/Wl8AAHxCwACIJGAARBIw\nACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgk\nYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACL9aX0BZyql3H5Ra217JQB82zgB\nK6Xcu7X+NQBDskIEINI4E9iuUpZlKa2vAiBP/3uswQO29PF70MlKs4fL6OEaXEZv1+AyeruGZXWk\noGdWiABEGmcCq7U6hQgwj3ECtugWwEy6WLZ+TynL0P//AL6ik1txx9wDAyCSgAEQScAAiCRgAEQS\nMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACI\nJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkf60voC3lVJuv6i1PnvX\n7nsBGElYwEop9zKtf32nWwCTGG2FWEpZz2EAjCpsAvvVbQJ7GNS2HwDAg7jv/rsO2Lvt2f0AxQJ4\nxfqrZUTMug7YW+3ZvSUGwKi6DthWrXV7CvGWrt13ATCqsIAte3G6v0W3AOYx2ilEACYhYABEEjAA\nIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRg\nAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDINKAASul\ntL4EAL7uT+sLOJN0AcxjqAms1lprbX0VAFxhqAls18NYpnAAu+KWWKkBez1LigXwivVXy4iYpQZM\nlgAmN9Q9sD0R30YA8LYBA2Y4A5jBgAEDYAYCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBI\nAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgA\nkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIv1pfQEfKqXUWrdvvP96/d5Sls3HApAtL2DrSm1t\nq1brcvhfABApb4VYa91W6q6Uclw4AMaQN4Edu7VtvWAspSxLvVftIH4AM4v77r/rgD08m7+2Z/cD\naq2l6BbAL/4+OhAQs64D9lZ1do91ADCqrgP2olu6arUnBJhIasDWibr/WrcA5pF3ChEAFgEDIJSA\nARBploAlnAgF4A1TBMzZDoDxTBEwAMYjYABEEjAAIgkYAJEEDIBIEwXMSXqAkcwSMCfpAQYzS8AA\nGIyAARBJwACINFfAnOMAGMZEAXOOA2AkEwUMgJEIGACRpguY22AAY5grYG6DAQxjroABMIwZA2aL\nCDCA6QJmiwgwhukCBsAYJg2YLSJAuhkDZosIMIAZA3ZjCAOINmnAbkOYhgHkmjRgi0UiQLh5A3Zj\nCAMI9af1BZyp/OSovjZe1SpgAKlGm8BqrbXW8nKXNAwg1FABe3Hw2tIwgDhDrRBvSinrkj1MY9vI\n3YawUhzrAKb2+u6qE6kB283S7Y0PiXplLLNIBDj41r9PqQF7lqWPt4jLYggDSJIasK3b9wvvHkS8\nuy8SF39FDCDBOAH7l9nr539hWRb3wwAyDHUK8RReZQogwjgT2InWDTOKAfTJBPbUeqMIQG8E7Eit\nNooAnRKw3xnFADokYC9Zj2IyBtADAXuDjAH0Q8DeJmMAPRCwD8kYQFsC9k9kDKAVATuBjAFcT8BO\nI2MAV/JSUie7v/SUV6IC+CoB+5aHl/BQMoBzWSF+l70iwJcI2BVkDOB0AnYdGQM4kYBdTcYATiFg\nbcgYwD8SsJZkDOBjAtaejAF8QMB6IWMAbxGwvsgYwIsErEcyBvArAeuXjAEcELDeyRjALi/mm+Hh\nRe4Xrw4MTM8EFsZABnAjYJFkDEDAgskYMDP3wOJtG+b2GDCDvICVn6/TdfN1uqzGkO17x7Y+5XF7\nGiZ7AoDp5AVs+YlTKWVbqdm6tfUwkE3/fADDygvYcaJuQ9j6Y8rfd4cmKZyMAe8qaffS8wJ2szt+\nLXvD2STF2uX2GPC6g2/9+9R1wHaHp+2M9fABPHB7DBhS1wF7FqTdtz+bybizVwRG0nXAtm7j18NB\nxFu6aq0HBxS5kzFgDGEBO94c6tbr3B4D0oUFjHO5PQbk8lJSLItXpQICCRj/kTEgiBUij/zsMSCC\nCYynDGRAzwSMX8gY0CcrRF7i2D3QGwHjDY7dA/2wQuQT9opAcwLG52QMaMgKkX/l9hjQhIBxDrfH\ngItZIXIye0XgGgLGV8gY8G1WiHyR22PA9wgYX+f2GPANVohcx14ROJGAcTUZA05hhUgbfmgL8I9M\nYDRmIAM+I2B0QcaAd1kh0hHH7oHXCRjdceweeIUVIv2yVwQOCBi9kzFglxUiGdweAx4IGEncHgPu\nrBCJZK8ICBjBZAxmZoVIPK9KBXMygTEOAxlMZagJrPx80aq+A5/YQ8P8WYBRDRWw5SddpRQNm5xj\n9zC8oQK2G63y9y5J2Kbi2D28rqRt3ocK2LL3G6BYLPaK8IL1V8uImKUG7NlcdV8hNrgmuidjMJLU\ngG3nKve9eJHbYzCG1IBt1VqdQuR1bo9BunECtugWH7FXhFBDBQw+Zq8IcQQM/mOvCEG8lBTs8KpU\n0D8Bg6dkDHpmhQi/cHsM+iRg8BK3x6A3VojwHntF6ISAwSdkDJqzQoTP+WHQ0JAJDE5gIIPrCRic\nRsbgSlaIcDLH7uEaAgZf4dg9fJsVInyXvSJ8iYDBFWQMTmeFCNdx7B5OZAKDBgxk8O8EDJqRMfgX\nVojQmGP38BkBgy44dg/vskKEvtgrwosEDHokY/ArK0Tol2P3cMAEBgEMZLAlYBBDxmDNChHCOHYP\nNwIGkRy7BytEyGavyLQEDEYgY0zIChHG4fYYU8kLWPn51KybT82y+s5z+16YhNtjTCIvYMtPnEop\n20rpFtw9DGQ+ORhMXsCOE3UbwmQM7uwVGVVewJa/V4UPtsPZwwdrG3OyV+RXB19a+9R1wJ61516p\nh4/fjZNiwZq9Is+sv1pGxKzrgO0e03gWpIN3AQ9kjAF0HbCtWuv2FOItXbvvAg64PUa0sIAte3F6\nWC0Cb3F7jFBeiQP4Hy/nQRYBA/4iY6TIWyECF/DDoOmfCQw4YiCjWwIG/E7G6JAVIvAqx+7pioAB\n73Hsnk5YIQIfslekLQED/omM0YoVInACx+65ngkMOJOBjMsIGHA+GeMCVojAtzh2z1cJGPBdjt3z\nJVaIwEXsFTmXgAGXkjHOYoUINODYPf/OBAa0ZCDjYwIGtCdjfMAKEeiFY/e8RcCAvjh2z4usEIFO\n2StyTMCArskYz1ghAgHcHmNLwIAYbo+xZoUI5LFXZDGBAbnsFScnYEA2e8VpWSECg7BXnI2AAUOR\nsXlYIQIDcntsBgNOYMU3XcCyLD/TmIFsVKMFTL2ALRkb0lABK6VUawLgCRkbzPj3wB5mMoWDyflh\n0M/EbbBSR5ZtlnZDZSYDjsnYrogvnqkT2PaZvb8l4nkHOvGwVPTFI0hqwABO5Nh9ogEDZvwCPuNV\nqbIMdQoR4BTOK0YQMIB9Mta5AVeIACdy7L5bJjCAlxjIeiNgAG+QsX5YIQK8zbH7HggYwIccu2/L\nChHgX9krNiFgAOeQsYtZIQKcybH7y5jAAL7CQPZtAgbwRTL2PVaIAF/n2P03CBjARRy7P5cVIsDV\n7BVPIWAAbcjYP7JCBGjJ7bGPCRhAe26PfcAKEaAj9oqvM4EBdMde8RUCBtApe8VjVogAvbNX3CVg\nABlk7IEVIkASt8fuBAwgj9tjixUiQLSZ94oCBhBvzoxZIQIMYrYfBm0CAxjNJAOZgAGMafiMWSEC\njGzgY/epASul1M1vQll9j7F9L8C0hjx2H7lCLM+H4frjyuv51cEFX6mHy+jhGhaX0dk1LC7jwmsY\naa+YF7Dd2Wv93h7+CAL0bIyMpa4Qn7m1bR25h571NpwBtLI9dr8sSTXrOmDb9tzecv/nQ41246RY\nAMfu09iy1Nu/RqyyjtZxPdvW62Hquo9iDS4OINj/vpD2H4euJ7AX3XJ1n8+W1dQVmmcAfpU6gQEw\nubxTiACwCBgAoQQMgEgjHOLo0PY4ycPbt++6wPHfAb/4oRs+Fc9+dxo+bqtno9VTcfDQPkfWb7n/\nutWf1esf+i0Cdr7dA/13Tf40NPzrBMev+3XllWwf+vqvVgeP2+rZaPVUHDx0w4Q0edyDh27+OdI5\nK8SrNXmxq4avD3nw0K1e96ttKp5p9Qfj4kd85aGbPBVdzV7rd7XKasTL8pnArtbwG97etH0qenvc\nVs9Gt2OHz5Gly/m4KyawS/X8R+FiDZ+K27eWTe6vHNerid6m84Y79vU/e3joPufjrgjYdfqfxy/T\n/KnoaovYcEfU5HEPHrrVJa1/DNP1t0V3H7rD350OdT0e5no4YbV9bcaulldXPnTzp6LVN7m7j9vP\ns9H8FGLzp+J+VT5H2j70WwQMgEhWiABEEjAAIgkYAJEEDIBIAgZAJAED4C8pfxVMwAD4T0q9FgED\n4K7zFz98IGAA/McEBkC/7pUqP27/2vDFnT/gx6kATGQ9YD376bspDTOBAQzo2U+HyZqxjgkYAJEE\nDGBAtdasI4UfEDCAAd3qFXSk8AMOcQCM5sXZa124xFlt8AETgFFZIQIQScAAiCRgAEQSMAAiCRgA\nkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARDp/wGkzaT4Z2PN\noQAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 51, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo7()"]}, {"collapsed": false, "outputs": [], "prompt_number": 52, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Display the histogram of the recovered values."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAJz0lEQVR4nO3d0W7i\nVhRAUbvKB/dT+se3D1Yt12ESZhSwt73WQwQOEqcwYeObSzqPMSYAqPnr6AEA4E8IGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA0sfRA7zWPM9HjwCQ\nNMY4eoRvXDxg0zRN0z9P3/LvFz1h8zyf4Z/CGcY4wwzGONsMxjjbDFPk3b8lRACSBAyAJAEDIEnA\n3uEMK9rTOcY4wwyTMU42w2SMk81QIWAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJH0cPcCz5nleLqz/u9Ldkc83AODCGgFb4rSGaoyx\nfP383fUGB00KwJs0ArbYhQqAO8sEzAkWwEutv4ipyAQMgJfanhskYmYXIgBJjTOwZdfGevnhEbsQ\nAW6lEbDpUZZ2R3QL4FYsIQKQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkC\nBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkfRw/wrHme18tjjO2Rh1cBuLZMwKb/l2me5/Xqkq7tVQ0DuLxS\nwHahAuAHbRe6EkoBW5cKNQzgx+1WuQ6c5EmZTRyiBcBWI2CJ9wIAvFNjCXGMsdtk+PmIXYgAt9II\n2PQoS7sjugVwK40lRADYETAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJ\nwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQB\nAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQM\ngCQBAyBJwABIEjAAkj6OHuD3zPM8xlgvLxeWI7urAFxbKWBroqZHJdte1TCAy8ssIcoSAFulMzAA\nXme7ypXQCNjysK5fnYoB/LjtS2siZo2A+f0WADuNgH02xrALEeDOYgHbxmkXKt0CuJXMLkQA2BIw\nAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAA\nSBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMg\nScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJI+jh7g\nWfM8LxfGGA+PfL4BABeWCdi0CdUYY/m6HF/Stb2qYQCXl1lC1CQAtkpnYOsiIQA/LvcaWwrY7ndd\nAPyg7UJX4pW2sYSYeCgBeKfGGdiya2O9/PCIXYgAt9II2PQoS7sjugVwK40lRADYETAAkgQMgCQB\nAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQM\ngCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAA\nkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgKSPowd41jzP\ny4UxxsMjn28AwIVlAjZtQjXGWL4ux5d0ba9qGMDlZZYQNQmArdIZ2OTsCuBl1l/EVGQCtlsnBOBn\nbV9gEzHLLCFO6gXARuMMbHkvsN1nuOzjWK9OdiEC3EwjYA+btDuoWwC3UlpCBICVgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ9HH0AL9nnucxxnp5\nubAc2V0F4NoyAVv7tF7dlWx7VcMALi+zhDjGkCUAVpkzMABearfQdX4CBsA0/X8DQSJmmSVEANiq\nnoGNMexCBLizWMC2cdqFSrcAbsUSIgBJAgZAkoABkCRgACQJGABJsV2IAPyZxGeTf4uAAdzHP0/f\n8u8XTvFDLCECkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ2DvM83z0CNN0jjHOMMNkjJPNMBnj\nZDNUCBgASR9HD/CT1ncuY4xjJwHg1a4TsHme125tLwNwSdd5oX8YMKvJAH/m/HW4zhnYQ+d/AgD4\nMzZxAJAkYAAkXed3YJNdiAB3cqmAAXAfV97EceAJ2dd3/Z5d/l/M8M5H5lf39eZnp/KMPPzue8Y4\nwzOy2zZ81EOx/e59fkY+O//nkS4bsAM/FvbFXb9tW/+3//nrxwxe+sh8PcZ7Zvh2jPc8KU8+I0eN\nsX2xPvAZeecPy7f/Ko79GTn2g62VDyDZxPFWY4wzvKMxw+o87zHneT78VWOZ4QwPyEnGuK2TvFJ9\n67JnYHzr8NeIw1+vT+VtZz9fD3DsDKfytiXEZ8bgIQG7o5P8ZB7+11KWu16/HviAHP5cnMrhBT3D\n36UbY6w/pxr2K5YQb+rwF4gD7301/jMd+oCc5NHgVJZwemfztSuvFZxnF+LnrRyHbG1a7vfYjV6f\n/0zlIXveTvWMPPzW28Y42zPyzjMez8i3g508EGefDwAesoQIQJKAAZAkYAAkCRgASQIGQJKAAZAk\nYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKA\nAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZD0L7nNCHvnrJ9B\nAAAAAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 53, "cell_type": "code", "language": "python", "metadata": {}, "input": ["clf;\n", "hist(Xproj(:), 30);\n", "axis('tight');"]}, {"source": ["As you can see, the resulting vector is (nearly, up to convergence errors of the POCS)\n", "a binary one, meaning that it is\n", "actually the (unique) solution to the Sudoku problem.\n", "\n", "\n", "We check this by counting the number of violated constraints\n", "after decoding and re-encoding."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Number of violated constraints: 0.\n"], "output_type": "display_data"}], "prompt_number": 54, "cell_type": "code", "language": "python", "metadata": {}, "input": ["[tmp,xproj] = min( abs(Xproj-1), [], 3 );\n", "Xproj1 = encode(xproj); \n", "disp(['Number of violated constraints: ' num2str(sum(A*Xproj1(:)~=1)) '.']);"]}, {"source": ["__Exercise 8__\n", "\n", "Prove (numerically) that for this grid, the polytope of constraints\n", "|P={X \\ A*X(:)=1 and X>=0}| is actually reduced to a singleton, which is\n", "the solution of the Sudoku problem."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 55, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo8()"]}, {"collapsed": false, "outputs": [], "prompt_number": 56, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Unfortunately, this is not always the case.\n", "For more difficult grids, |P| might not be reduced to a singleton.\n", "\n", "\n", "This is a difficult grid."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 57, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x1 = [0 0 3 0 0 9 0 8 1;\n", "     0 0 0 2 0 0 0 6 0;\n", "     5 0 0 0 1 0 7 0 0;\n", "     8 9 0 0 0 0 0 0 0;\n", "     0 0 5 6 0 1 2 0 0;\n", "     0 0 0 0 0 0 0 3 7;\n", "     0 0 9 0 2 0 0 0 8;\n", "     0 7 0 0 0 4 0 0 0;\n", "     2 5 0 8 0 0 6 0 0];"]}, {"source": ["__Exercise 9__\n", "\n", "Try the iterative projection on convexs set (POCS) method on this grid\n", "(remember that you need to re-define |A| and |pA|).\n", "What is your conclusion ?\n", "ill the constraint matrix\n", "OCS\n", "heck wether this is a valid solution."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Number of violated constraints: 20.\n"], "output_type": "display_data"}, {"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAM2UlEQVR4nO3d4XLi\nNhiGUauT+79l9Qcb1ouNgQQsvdI50+mkgRm7hPDkEwJKrXUBgDT/tT4BAPgJAQMgkoABEEnAAIgk\nYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQ\nScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIj01foE3qmUcvmi1tr2TAD4tHECVkq5\ndmv9NQBDsoQIQKRxJrBdpSzLUlqfBUCe/texBg/Y0sfPoJMlzR5Oo4dzcBq9nYPT6O0cltWWgp5Z\nQgQg0jgTWK3VLkSAeYwTsEW3AGbSxWLr55SyDP3/B/ARnTwVd8xzYABEEjAAIgkYAJEEDIBIAgZA\nJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQM\ngEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJ\nGACRBAyASAIGQCQBAyCSgAEQScAAiPTV+gReVkq5fFFrvXfR7qUAjCQsYKWUa5nWX1/pFsAkwgL2\n0GUIW2dsPZYtCgdwx82jZf9GC9ilT+vhTLEAnnHwp3+fug7Yq8OTVgHMo+uAvRSk3afEABhV1wHb\nqrVudyFe0rV7EQCjCgvYshcnT3cBTMgLmQGIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAA\niCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKA\nARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAk\nAQMgkoABEGnAgJVSWp8CAB/31foE3km6AOYx1ARWa621tj4LAM4w1AS262YsUziAXXGLWKkBez5L\nigXwjPWjZUTMUgMmSwCTG+o5MADmMWDADGcAMxgwYADMQMAAiCRgAEQSMAAijR+whBczAPCy4QMm\nXwBjGj5gAIxJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQM\ngEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARBJwACIJGAARBIwACIJ\nGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAET6an0CP1RKqbVuv3n9enspACPJC9i6Ulu6BTCJvIBd\nEnUvY5fv32TMZAbw0PF40KG8gB275m0dKtECeGj9UBkRs64DdnMLPuyQUAHMo+uAvRSk3W0dAIyq\n64A96ZKuWut1YlMygOGlBmz3KS7dApiHFzIDEEnAAIgkYABEEjAAIgkYAJEEDIBI4wes1iXhLVEA\neM34AQNgSAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMgkoABEGmWgHk/X4DB\nTBGwWlufAQDvNkXAABiPgAEQScAAiCRgAEQSMAAiCRgAkWYJWK1eCgYwlFkCBsBgBAyASAIGQCQB\nAyDSXAGzjwNgGBMFzFv6AoxkooABMBIBAyCSgAEQabqA2ccBMIa5AmYfB8Aw5goYAMP4an0C71S+\n1werUQtgdKNNYLXWWmvxTBfA6IYK2DODl89VARjDUEuIF6WUdclupjGriwC74tauUgO2m6XLN28S\npVgAzzj4079PqQG7l6Unc1WKLfUA2VIDtnX5e+GZjYieBgMYwDgBs1QIMJWhdiECMI95A2YVESDa\npAGz3AiQbtKAAZBu6oBZRQTINW/ArCICRJs3YABEmz1gVhEBQk0dMKuIALmmDhgAuQTMKiJApNkD\nZhURINTsAQMglIAti1VEgEACZhURIJKAARBJwP6wigiQRcCWxSoiQCABAyCSgP1lFREgiID9YRUR\nIIuAARBJwP6q1SoiQAwBAyCSgN0yhAFEELB/2MoBkELAdhjCAPonYLcMYQARBGyfIQygcwK24zKE\naRhAzwRsn4YBdE7A7tIwgJ4J2BENA+iWgD2gYQB9ErDHNAygQwL2FA0D6I2APUvDALoiYC/QMIB+\nCNhrNAygEwL2smvDZAygIQH7iVqNYgCNfbU+gZeV72jUzfvGl1VPtpe+Xa1/5jBvYA9wvryALd9x\nKqVsK3VCt/49nIYBtJEXsONEXYaw9XXKv8t8by+chgFjKGlPiuQF7GJ3/Fr2hjNriQDPOPjTv09d\nB2x3eNrOWDdXaOLasMVnOgOcouuA3QvS7vfvzWSnWW+v1zCAT+s6YFuX8etmI+IlXbXWgw2Kp7Gc\nCHCOsIAdrxy2ncCuNAzgBF7I/BFe5gzwaWETWJB1w4xiAG9nAvssoxjAhwjYx2kYwCcI2Bk0DODt\nBOwkPoQF4L0E7Dw+hAXgjQTsbBoG8BYC1oDlRIDfE7A2LCcC/JKAtaRhAD8mYI1ZTgT4GQFrz3Ii\nwA8IWC80DOAlAtYRy4kAzxOwvlhOBHiSgPXIKAbwkIB1yigGcMwHWnbNp2IC3GMCC2BFEWBLwDKs\nVxRlDGARsCwyBnDlObA824Z5egyYkIClukbrWjIZA6ZiCTGedUVgTiawQVhXBGYjYEOxrgjMQ8DG\nZCADhidgIzOQAQMTsCmsS3bzHYBQAjYXS4vAMARsRpYWgQEI2NQMZEAuAcNABkQSMP4ykAFBBIxb\n24FsUTKgPwLGXZYWgZ4JGI9ZWgQ6JGA8y0AGdEXAeJn39QB6MFTAyvcDavWAegpLi0BDQwVs+U5X\nKUXDTmPXItDEUAETrbaUDDjTUAFbVquI974jcidQMki0ffzsXGrA7mXpuoS4vYjz7ZZsETPo0vrR\nMiJmqQHbZsnzXj1b/2TEDHiL1IBt1VrtQoxwELNFz4CnjROwRbcC3fzEDGfA84YKGOkMZ8DzBIxO\nGc6AYwJGBsMZcEPAyHM8nG2vAAxJwIhnsRHmJGCMxmIjTELAGJnhDAYmYEzEcAYjETAmZScIpBMw\nWBaLjRBIwGCHxUbon4DBA4Yz6JOAwWu2PTu4FPgcAYNfsdgIrQgYvI3FRjiTgMGnGM7gowQMzuBl\nZ/B2AgYNPOzZ9jrADQGD9ratMqLBQwIGPTKiwUMCBgGMaLAlYBDJrhAQMBiBJUcmJGAwIEuOzEDA\nYApGNMYjYDAjIxoDEDBgWewKIZCAATssOdI/AQMes+RIhwQM+AkjGs0JGPAGRjTOJ2DARxjR+DQB\nA85gROPtBAxow4jGLwkY0AUjGq8SMKBTRjSOCRiQwYjGDQEDUhnRJidgwCCMaLMRMGBYu0l7eB1S\nCBgwEW+6P5K8gJXvu1vd3NHK6p64vRTghhEtWl7Alu84lVK2ldIt4DdsDAmSF7DjRF2GMBkD3sLG\nkJ7lBWz5d6nwxnY4u7mytgG/MfCIdvDQ2qeuA3avPddK3Vx/N06KBXzOSCPa+tEyImZdB2x3m8a9\nIB1cBHCagUe03nQdsK1a63YX4iVduxcBtDXSiNabsIAte3G6WVoE6JkR7V3yAgYwEiPajwkYQF+M\naE8SMICuGdHu+a/1CUyhkw2pPZxGD+ewOI3OzmFxGi+eQ63//LN8J239zwxMYADZnhnRdq+WTsAA\nRjPJqqOAAYxvyI0hg797RQ8r2gAJti+xbXIaLxg8YACMyi5EACIJGACRBAyASAIGQCTb6D/i3ge7\nrHdFnr99puFHpm0P3fCmaPWxOwfHbXVrNPwEIr8jDw/dw+/I+Yd+iYC93/qOuL1TNrk3NHw5wcGh\nG/5iXD/U++RzODhuq1uj1U1xcOiGCWly3INDN/8d6ZwlxLOVUs7/Pbl84OfJB3146CY3xdI6Ffe0\numOcfMRnDt3kpuhq9lpf1CqrDQ/9PBPY2Rr+wdubtjdFb8dtdWt0O3b4HVm6nI+7YgI7Vc93hZM1\nvCkuf1o2eX7luF5N9DadN1xjX/+7h0P3OR93RcDO0/88fprmN0VXq4gN14iaHPfg0K1OqX5bTr9v\n3Dt0hz+dDnU9Hua62WF1/bu74aavpelqwPoWaHtTtPojd/e4/dwazXchNr8prmfld6TtoV8iYABE\nsoQIQCQBAyCSgAEQScAAiCRgAEQSMAD+kfJSMAED4K+Uei0CBsBV529+eEPAAPjLBAZAv66VKt8u\n/9nwzZ1/wMepAExkPWDd+/TdlIaZwAAGdO/TYbJmrGMCBkAkAQMYUK01a0vhDwgYwIAu9QraUvgD\nNnEAjObJ2WtduMRZbfABE4BRWUIEIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQ\nScAAiCRgAEQSMAAiCRgAkQQMgEgCBkAkAQMg0v/UpxQCczdINgAAAABJRU5ErkJggg==\n", "output_type": "display_data"}], "prompt_number": 58, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo9()"]}, {"collapsed": false, "outputs": [], "prompt_number": 59, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Decoding Using L1 Sparsity\n", "--------------------------\n", "The true solution has exactly |n^2| non zero entries, while a\n", "feasible point within the convex polytope |P| is usually not as sparse.\n", "\n", "\n", "Compute the sparsity of a projected vector."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Sparsity: 729 (optimal: 81).\n"], "output_type": "display_data"}], "prompt_number": 60, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xproj = projector( zeros(n,n,n) );\n", "disp(['Sparsity: ' num2str(sum(Xproj(:)~=0)) ' (optimal: ' num2str(n*n) ').']);"]}, {"source": ["One can prove that any solution to |A*X(:)=1| has more\n", "than |n^2| non zeros, and that the true Sudoku solution is the unique\n", "solution to |A*X(:)=1| with |n^2| entries.\n", "\n", "\n", "One can thus (in principle) solve the Sudoku by finding the solution to\n", "|A*X(:)=1| with minimal L0 norm.\n", "\n", "\n", "Unfortunately, solving this problem is known to be in some sense NP-hard.\n", "\n", "\n", "A classical method to approximate the solution to the minimum L0 norm\n", "problem it to replace it by a minimum L1 norm solution, which can be\n", "computed with polynomial time algorithms.\n", "\n", "\n", "\n", "This idea is put forward in:\n", "\n", "\n", "P. Babu, K. Pelckmans, P. Stoica, and J. Li,\n", "_Linear Systems, Sparse Solutions, and Sudoku_,\n", "IEEE Signal Processing Letters, vol. 17, no. 1, pp. 40-42, 2010.\n", "\n", "\n", "\n", "The L1 norm of the Sudoku solution is |n^2|.\n", "The L1 norm of a projected vector is usually larger."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["L1 norm: 102.7585 (optimal: 81).\n"], "output_type": "display_data"}], "prompt_number": 61, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['L1 norm: ' num2str(norm(Xproj(:),1)) ' (optimal: ' num2str(n*n) ').']);"]}, {"source": ["Unfortunately, all the vectors in the (bouned) polytope |A*X(:)=1| and |X>=0|\n", "has the same L1 norm, equal to |81|.\n", "\n", "\n", "This shows that the L1 minimization has the same properties as the POCS\n", "algorithm. They work if and only if the polytope is reduced to a single\n", "point.\n", "\n", "\n", "\n", "Nevertheless, one can compute the solution with minimum L1 norm which corresponds\n", "to the Basis pursuit\n", "problem. This problem is equivalent to a linear program, and can be\n", "solved using standard interior points method (other algorithms, such as\n", "Douglas-Rachford could be used as well).\n", "\n", "\n", "Define a shortcut for the resolution of basis pursuit."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 62, "cell_type": "code", "language": "python", "metadata": {}, "input": ["solvel1 = @(A)reshape(perform_solve_bp(A, ones(size(A,1),1), n^3, 30, 0, 1e-10), [n n n]);"]}, {"source": ["Solve the L1 minimization."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 63, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xbp = solvel1(A);"]}, {"source": ["Compute the L1 norm of the solution, to check that it is indeed equal to the minimal possible L1 norm |n^2|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["L1 norm: 81 (optimal: 81).\n"], "output_type": "display_data"}], "prompt_number": 64, "cell_type": "code", "language": "python", "metadata": {}, "input": ["disp(['L1 norm: ' num2str(norm(Xbp(:),1)) ' (optimal: ' num2str(n*n) ').']);"]}, {"source": ["Unfortunately, on this difficult problem, similarely to POCS, the L1\n", "method does not works."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Number of violated constraints: 16.\n"], "output_type": "display_data"}], "prompt_number": 65, "cell_type": "code", "language": "python", "metadata": {}, "input": ["[tmp,xbp] = min( abs(Xbp-1), [], 3 );\n", "Xbp1 = encode(xbp); \n", "disp(['Number of violated constraints: ' num2str(sum(A*Xbp1(:)~=1)) '.']);"]}, {"source": ["Decoding Using more Aggressive Sparsity\n", "---------------------------------------\n", "Since the L1 norm does not perform better than POCS, it is tempting to\n", "use a more agressive sparsity measure, like |L^alpha| norm for |alpha<1|.\n", "\n", "\n", "This leads to non-convex problems, and one can compute a (not necessarily\n", "globally optimal) local minimum.\n", "\n", "\n", "An algorithm to find a local minimum of the energy is the reweighted L1\n", "minimization, described in:\n", "\n", "\n", "E. J. Cand s, M. Wakin and S. Boyd,\n", "_Enhancing sparsity by reweighted l1 minimization_,\n", "J. Fourier Anal. Appl., 14 877-905.\n", "\n", "\n", "This idea is introduced in the paper:\n", "\n", "\n", "P. Babu, K. Pelckmans, P. Stoica, and J. Li,\n", "_Linear Systems, Sparse Solutions, and Sudoku_,\n", "IEEE Signal Processing Letters, vol. 17, no. 1, pp. 40-42, 2010.\n", "\n", "\n", "At each iteration of the algorithm, one minimizes\n", "\n", "\n", "\n", "$$min \\sum 1/u_k  |x_k|$$  subject to  $$A x=1$$\n", "\n", "\n", "\n", "The weights are then updated as\n", "\n", "\n", "\n", "$$u_k=|x_k|^{1-\\alpha} + \\epsilon$$\n", "\n", "\n", "\n", "The weighted L1 minimization can be recasted as a traditional L1 minimization\n", "using a change of variables.\n", "\n", "\n", "\n", "$$min |y|_1$$ subject to $$A diag(u) y=1$$ and $$x_k = y_k u_k$$\n", "\n", "\n", "\n", "Set the target |alpha|, that should be in |0<=alpha<=1|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 66, "cell_type": "code", "language": "python", "metadata": {}, "input": ["alpha = 0;"]}, {"source": ["Set the regularisation parameter |epsilon|, that avoids a division by\n", "zero."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 67, "cell_type": "code", "language": "python", "metadata": {}, "input": ["epsilon = 0.1;"]}, {"source": ["Initial set of weights."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 68, "cell_type": "code", "language": "python", "metadata": {}, "input": ["u = ones(n,n,n);"]}, {"source": ["Solve the weighted L1 minimization."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 69, "cell_type": "code", "language": "python", "metadata": {}, "input": ["Xrw = solvel1( A*diag(u(:)) ) .* u;"]}, {"source": ["Update the weights."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 70, "cell_type": "code", "language": "python", "metadata": {}, "input": ["u = (abs(Xrw).^(1-alpha)+epsilon);"]}, {"source": ["__Exercise 10__\n", "\n", "Compute the solution using the reweighted L1 minimization.\n", "Track the evolution of the number of invalidated constraints as the\n", "algorithm iterates."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "text": ["Number of violated constraints: 0.\n"], "output_type": "display_data"}], "prompt_number": 71, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo10()"]}, {"collapsed": false, "outputs": [], "prompt_number": 72, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["Display the histogram."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAKAUlEQVR4nO3c0W6r\nxgJAUbjKB/dT+sfTB3QRJW7iE8WGDWs9RIZY8tQ03p7x+MxjjAkAav539AAA4CcEDIAkAQMgScAA\nSBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMg\nScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASPo4egBPmed5ezjG2J58eAjAtTUCtm3S\nEqp5nteTy5ntoYYBXF5sCVGcAFg0ZmA/tlt7BOBJ558tlAL2s+nXGa7BSSaOZxjGGcZgGGcbg2Gc\nbQxT5N1/bAkRABaZGdjuXckYwy5EgDvLBOxzlnZndAvgVk6x2Po6J1lNBmhJvHj6DAyAJAEDIEnA\nAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAEDIEnAAEgSMACSBAyAJAED\nIEnAAEgSMACSPo4ewMvN8/z8nccYrxsJAL/o+gGbpr+fvudfLxwFAL/KEiIASQIGQJKAAZAkYAAk\nCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZAkYAAkCRgASQIGQJKAAZD0\ncfQAnjXP83JjjPHwzOc7AHBhjYAtcVpDNcZYfn7+7XqHg0YKwJs0ArbYhQqAO8sEzAQL4KXWD2Iq\nMgED4KW2c4NEzOxCBCCpMQNbdm2stx+esQsR4FYaAZseZWl3RrcAbsUSIgBJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRg\nACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoAB\nkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkPRx9ACeNc/zenuMsT3z8BCAa8sEbPp3meZ5\nXg+XdG0PNQzg8kpLiPM8b+dhANxZbwZmggXwCrkZQiZgogXwUruPaQ4cyZMaS4iJpxKAd2rMwMYY\nu02Gn8/YhQhwK42ATY+ytDujWwC30lhCBIAdAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAk\nAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIE\nDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIwAJIEDIAkAQMgScAASBIw\nAJIEDIAkAQMg6ePoAfyZeZ7HGOvt5cZyZncIwLWVArYmanpUsu2hhgFcXmYJUZYA2CrNwAB4ne0q\nV0IjYMvTuv40FQP4dduX1kTMGgHz+RYAO42AfTbGsAsR4M5iAdvGaRcq3QK4lcwuRADYEjAAkgQM\ngCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAA\nkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABI\nEjAAkgQMgCQBAyBJwABIEjAAkgQMgCQBAyBJwABIEjAAkj6OHsCz5nlebowxHp75fAcALiwTsGkT\nqjHG8nM5v6Rre6hhAJeXWULUJAC2SjOwdZEQgF+Xe40tBWz3WRcAv2i70JV4pW0sISaeSgDeqTED\nW3ZtrLcfnrELEeBWGgGbHmVpd0a3AG6lsYQIADsCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkY\nAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQ9HH0AJ41z/NyY4zx8MznOwBwYZmATZtQjTGWn8v5JV3bQw0DuLzMEqIm\nAbBVmoFNZlcAL7N+EFORCdhunRCA37V9gU3ELLOEOKkXABuNGdjyXmC7z3DZx7EeTnYhAtxMI2AP\nm7Q7qVsAt1JaQgSAlYABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZA\nkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkPRx9AD+\nzDzPY4z19nJjObM7BODaMgFb+7Qe7kq2PdQwgMvLLCGOMWQJgFVmBgbAS+0Wus5PwACYpn9vIEjE\nLLOECABb1RnYGMMuRIA7iwVsG6ddqHQL4FYsIQKQJGAAJAkYAEkCBkCSgAGQFNuFCMDPJL6b/EcE\nDOA+/n76nn+9cBS/xBIiAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAA\nJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgAGQ\nJGAAJAkYAEkCBkCSgAGQJGAAJAkYAEkCBkCSgL3DPM9HD2GazjGMM4xhMoyTjWEyjJONoULAAEj6\nOHoAv2l95zLGOHYkALzadQI2z/Pare1tAC7pOi/0DwNmNRngZ85fh+vMwB46/wUA4Gds4gAgScAA\nSLrOZ2CTXYgAd3KpgAFwH1fexHHghOzrh37PLv8vxvDOZ+a/HuvNV6dyRR7+9j3DOMMV2W0bPuqp\n2P72Pn8jn53/+0iXDdiBXwv74qHftq3/2//89WsGL31mvh7Ge8bw7TDec1GevCJHDWP7Yn3gFXnn\nH8u3/1cc+zdy7BdbK19AsonjrcYYZ3hHYwyr87zHnOf58FeNZQxneEJOMozbOskr1bcuOwPjW4e/\nRhz+en0qb5v9fD2AY8dwKm9bQnxmGDwkYHd0kr/Mw/+1lOWh158HPiGHX4tTObygZ/h36cYY69+p\nhv0XS4g3dfgLxIGPvhr/Nx36hJzk2eBUlnB6Z/O1K68VnGcX4uetHIdsbVoe99iNXp//mcpD9ryd\n6oo8/NXbhnG2K/LOGY8r8u3ATh6Is48PAB6yhAhAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJ\nAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJ\nGABJAgZAkoABkCRgACQJGABJAgZAkoABkCRgACQJGABJAgZAkoABkPQPAZImmArXUQoAAAAASUVO\nRK5CYII=\n", "output_type": "display_data"}], "prompt_number": 73, "cell_type": "code", "language": "python", "metadata": {}, "input": ["hist(Xrw(:), 30);"]}, {"source": ["While reweighting L1 works for reasonnably complicated Sudoku, it might\n", "fail on very difficult one.\n", "\n", "\n", "This is the _Al Escargot_ puzzle, believed to be the hardest Sudoku\n", "available."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 74, "cell_type": "code", "language": "python", "metadata": {}, "input": ["x1 = [1 0 0 0 0 7 0 9 0;\n", "      0 3 0 0 2 0 0 0 8;\n", "      0 0 9 6 0 0 5 0 0; \n", "      0 0 5 3 0 0 9 0 0; \n", "      0 1 0 0 8 0 0 0 2;\n", "      6 0 0 0 0 4 0 0 0; \n", "      3 0 0 0 0 0 0 1 0; \n", "      0 4 0 0 0 0 0 0 7;\n", "      0 0 7 0 0 0 3 0 0];"]}, {"source": ["__Exercise 11__\n", "\n", "Try reweighted L1 on this puzzle.\n", "ill matrix.\n", "olve"], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [{"metadata": {}, "png": "iVBORw0KGgoAAAANSUhEUgAAAkAAAAGwCAIAAADOgk3lAAAACXBIWXMAAAsSAAALEgHS3X78AAAA\nIXRFWHRTb2Z0d2FyZQBBcnRpZmV4IEdob3N0c2NyaXB0IDguNTRTRzzSAAAOeUlEQVR4nO3d3Xab\nuhqGUdij93/L2gduWBT/YQeQXmnOgzXSNDGYLvuJPrAzl1ImAEjzv9o7AADfEDAAIgkYAJEEDIBI\nAgZAJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMFo3z/PD\njz/93qP24Te3fPuuzfe+uKm3WznqDu6/tWdfc+yewB5/au8AvDfPcynl7dfcPiilXPBk+nZ/Tvre\n6qJ3ns4IGAFuTVo/dS5/XH9+85nNcmf5ss1nbn/cPC/f5/DhDmxKud7E5m/ffu/07yJmvd2Ht//g\nMD25a3u+cXM3l2Nyv/WHd+3hylLqOJuA0bmHUdmk7r5e99/17Ol487S+/uIX2dhs4n5Xp3/7cb+V\n+1u+//zmXmxuanPHN7f89i5sbuftgYLDCRgZjh0MXnPC5sAzdp/e1J7DdR/IY7erZJxNwBjO23na\nIZ6tk774+i92+Ist3vfm07uw5zbhQAJGjM2qYv9T6vLt074lwtfLiBfzvRebuN/VZ5+/vwuvd/v1\nvXi2D5vTdc/uwsP9vOYKGrjxIxIAkbwODIBIAgZAJAEDIFL2RRyb1/TcPumsHsAIggO2ecMFF+8C\nDMUIEYBIwSuw6dE77jz8AgA+1f4oKzVg+98joIV/g0ammi3sRgv7YDda2we70do+TCE//RshAhAp\ndQX26bvmANCZ1IBNd6HSLYChNDFsPU8j02SALBFPns6BARBJwACIJGAARBIwACIJGACRBAyASAIG\nQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQMgEg9B2yep2kqCb8XG4CPdRuwdbfmeZIxgM50GzAA\n+tZnwKy3ALrXZ8AA6F6fASul9h4AcLI+A3ZP0gA6023ASrlF6+/ZMGfFADrTbcAA6Fv/ATM8BOhS\n/wFbmCIC9GSggAHQkyECZooI0J8hArYwRQToxlgBA6AbowRsmSJahAH0YZSAAdAZAQMg0kABM0UE\n6MlAAQOgJ2MFzAvCALoxVsAWpogA6QYNGADphguYKSJAH4YL2MIUESDauAEDINqIAfOCMIAOjBgw\nADogYABEGjRgpogA6QYNGADpxg2YF4QBRBs3YAtTRIBEAgZApKEDZooIkGvogC1MEQHi/Km9A1+a\n/21OKWX5TLGwAhhAasDWlZrneZ7n5TPrj3fcjuUXQKT4EeJHuXp5O7+/DQCuk7oC2+9+2FhrTwBa\nNqf9IJ8dsD3Lrx1f8Hf5Nc+uSwTGtTk1U3FPdoofIQIwpuAV2Hr59curEF3KARAnOGCbUB11KYcp\nIkAEI0QAIgnYXxZeAFkEbMvJMIAIAgZAJAH7jykiQBABe8AUEaB9AgZAJAH7xzJFtAgDaJyAARBJ\nwACIJGBbpogAEQQMgEgC9oAXhAG0T8BeMUUEaJaAARBJwB4zRQRonIC9YYoI0CYBAyCSgD3lBWEA\nLRMwACIJGACRBOwVU0SAZgkYAJEE7A0vCANok4DtZYoI0BQBAyCSgL1nigjQIAH7gCkiQDsEDIBI\nAraLF4QBtEbAAIgkYABEErC9TBEBmiJgAEQSsA94QRhAOwTsG6aIANUJGACRBOwzpogAjRCwL5ki\nAtQlYABEErCPmSICtEDAvmeKCFCRgAEQScC+4W2lAKoTMAAiCdiXXMoBUJeA/ZYpIkAVAgZAJAH7\nnikiQEUCdgBTRIDrCRgAkf7U3oHvzT8Ln1LK/R+vUYrlF0AdqQG75WqdrqVb8zxf2bCfjTolBnCp\n1IDdLOman6+DNn91fdsAIrx4Im1TcMDWS649X3babvydIlqEAdHWz5YRMXMRBwCRBAyASKkjxPV5\nr4pXIf5s0RQR4GqpAZvuQuXqDIChGCEeQz0BLiZgB0u4cgegBwIGQCQBO4wpIsCVBOx4pogAFxAw\nACIJ2JGWKaJFGMDZBAyASAIGQCQBO5gpIsA1BAyASAJ2PC8IA7iAgJ3IFBHgPAIGQCQBO4UpIsDZ\nBOxcpogAJxEwACIJ2Fm8IAzgVAIGQCQBAyCSgJ3IFBHgPAIGQCQBO5cXhAGcRMAuYooIcCwBAyCS\ngJ3OFBHgDAJ2HVNEgAMJGACRBOwKpogAhxOwS5kiAhxFwACIJGAX8bZSAMcSMAAiCdh1XMoBcCAB\nq8AUEeD3BAyASAJ2KVNEgKMIWB2miAC/JGAARBKwq5kiAhxCwKoxRQT4DQEDIJKAVeBtpQB+T8AA\niCRgAEQSsDpMEQF+ScAAiCRg1XhBGMBvCFh9pogAXxAwACL9qb0D35tXK5dSyvLHkjObK8XyC+BL\nwQGbVq2a5/nhxynm2SkxgM9kjxDneZ4tYQCG1MMK7HXDNn/b2uJsmSJahAF1xa0HggO2M0WtFQug\nTetny4iYpY4QIw4uAOdJXYHdX3aYeBXijSkiwBdSAzbdhSquWwD8RuoIsTPiC/ApAWuLU3sAOwkY\nAJEErBWmiAAfEbDmmCIC7CFgAEQSsIYsU0SLMIC3BAyASAIGQCQBa4spIsBOAgZAJAFrjheEAewh\nYO0yRQR4QcAAiCRgLTJFBHhLwJpmigjwjIABEEnAGmWKCPCagLXOFBHgIQEDIJKAtcvbSgG8IGAA\nRBKwprmUA+AZActgigiwIWAARBKw1pkiAjwkYDFMEQHWBAyASAIWwBQR4J6AJTFFBFgIGACRBCyD\nt5UC2BAwACIJGACRBCyGKSLAmoABEEnAknhBGMBCwCKZIgIIGACRBCyMKSLAjYClMkUEBidgAEQS\nsDxeEAYwCRgAoQQMgEgCFskUEUDAAIgkYKm8IAwYnIDFM0UExiRgAEQSsGCmiMDI4gM2/0zQ5h91\n96eKIe80MLo/tXfgV9b1Kj/rkfXHAPQqeAUmVJMXhAEDy16B7bEZKmoewENxp2BSA3Y70Ov/PqNY\nAHusny0jYpY6Qiw/puETZYoIjCl1BbZRSll+Xhi8ZwCDiA/YkquRu1WK5RcwnNQRIg/JGDAOAQMg\nkoB1YuABKjAoAeuNKSIwCAEDIJKA9cMUERiKgHXIFBEYgYABEEnAuuJtpYBxCBgAkQSsNy7lAAYh\nYN0yRQT6JmAARBKwDpkiAiMQsJ6ZIgIdEzAAIglYn0wRge4JWOdMEYFeCRgAkQSsW95WCuibgAEQ\nScAAiCRgPTNFBDomYABEErDOeUEY0CsBG4UpItAZAQMgkoD1b30ph3UY0A0B698mWhoG9EHARqRh\nQAcEDIBIAgZAJAEblCkikE7A+vfstcwaBkT7U3sHuMKmYUu65tlbdQCprMBGtI6WF4cBoQRsUM/W\nZAApBGxcpWyXYgBBBGx0GgaEEjCcEgMiCRjTZJwIBBIw/qNhQBAB4x8aBqQQMLacEgMiCBgPOCUG\ntE/AeErDgJYJGK8YJwLNEjDe8KZTQJsEjPecEgMaJGDspWFAUwSMDzglBrQj+Bdazj9Pn6WU+z9y\nklL+6ZZfiQnUEhyw6d90Ld2a51nDTnU7un6tM1BX8AhRpepySgyoK3sFNu944tx8jewdaD1OvH3g\n6EKuPc+oTckO2Obs14uv4STGidCN9bNlRMxSR4gRB3ccxonA9VJXYKUUVyE2ZTNO9I8AnC01YNNd\nqHSrOqfEgCuljhBpkzedAi4jYBxPw4ALCBin8KZTwNkEjLP4PSzAqQSMEzklBpxHwDidhgFnEDCu\n4JQYcDgB4yLGicCxBIxLaRhwFAHjahoGHELAqMApMeD3BIw6nBIDfknAqEnDgK8JGJVpGPAdAaM+\np8SALwgYTXBKDPiUgNEQDQP2EzDaYpwI7CRgNMfvYQH2EDBa5JQY8JaA0S4NA14QMJrmlBjwjIDR\nOuNE4CEBI4OGARsCRgwNA9YEjCROiQELASOMU2LAjYARScMAASOVhsHgBIxgTonByASMbE6JwbAE\njB5oGAxIwOiEcSKMRsDoh9/DAkMRMLrilBiMQ8DokIbBCASMPjklBt0TMLplnAh9EzA697BhYgbv\nlPdfUtuf2jsApyvlQbpuH5SAB+lZNhUf+VBMjsZK0GPECowhPHsQWootRj4UI9/3jftD0fLBsQJj\nFOt12FrLj8+LORQLhyKCFRgAkazAGF3LI/7zPFxhjHkoJkdjJWvpaQXGQO6fksZ8kpoGvuM7DXt8\nsh4jAsZY1o/Glh+ZF1i/Tm7zmrnROBRrQY8RI0SG0/hj8mKOxsKhWJQyzfNcmj8iVmAARBIwACIJ\n2BXmNq7saWE3WtiHyW40tg+T3WhsH1IIGACRgi/iWH5OuZ1p3PwRgL4FB2z6N11LtyIungHgl3p4\nrn8RMNNkgO+0X4fsFdj0k6tnoWr/HwCA7wQHbLPwAmAo2VchqhfAsFLPgW1mhuspYug9AuAjqQED\nYHDB58B2qnhV/f2m1wvHK/eq4vL02aZrHYoXu1RxuxWPxuQxUnW7Lzbdwi41vsLpOWAVr6F/sela\n/0Msr5m7fgeebbriY6PW0Xix3YoJqbLdF5uu+xhpatNVdml9fVzjL6vNvojjtVJKxUfCs03P83z9\nU0aDj8yp0qGYWn1+rHI0mlp7rf+qyv8Ytbb7YtPVd6nlek19r8DaVPHnmtaereoeiou3+Ha7ET/w\nXqPB9XGtTdc9FFU2/ZGeV2ANqtiPWv8jPtt03UdFrdX5s+1WnBSt/9vCpttcH1fZdMvlaISAXafu\n+1o19fhs8LxLxe3W2qXyY7r8f49nm27wX6fWpr0N3h5NLw8P0cLcbP3B7a9qXV5VfdN1D8Vmr6pf\n2dXC0Zg8Rn72pMp27zdd/VDU3fRH+g8YAF0yQgQgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZA\nJAEDIJKAARBJwACIJGAARBIwACIJGACRBAyASAIGQCQBAyCSgAEQScAAiCRgAEQSMAAiCRgAkQQM\ngEgCBkAkAQMgkoABEEnAAIgkYABEEjAAIgkYAJEEDIBIAgZAJAEDIJKAARDp/8NDhgC2uIvwAAAA\nAElFTkSuQmCC\n", "output_type": "display_data"}], "prompt_number": 75, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo11()"]}, {"collapsed": false, "outputs": [], "prompt_number": 76, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["__Exercise 12__\n", "\n", "Try other sparsity-enforcing minimization methods, such as Orthogonal\n", "Matching Pursuit (OMP), or iterative hard thresholding."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 77, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo12()"]}, {"collapsed": false, "outputs": [], "prompt_number": 78, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["__Exercise 13__\n", "\n", "Try the different methods of this tour on a large number of Sudokus."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 79, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo13()"]}, {"collapsed": false, "outputs": [], "prompt_number": 80, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}, {"source": ["__Exercise 14__\n", "\n", "Try the different methods of this tour on larger Sudokus, for |n=4,5,6|."], "metadata": {}, "cell_type": "markdown"}, {"collapsed": false, "outputs": [], "prompt_number": 81, "cell_type": "code", "language": "python", "metadata": {}, "input": ["exo14()"]}, {"collapsed": false, "outputs": [], "prompt_number": 82, "cell_type": "code", "language": "python", "metadata": {}, "input": ["%% Insert your code here."]}], "metadata": {}}], "nbformat": 3, "metadata": {"kernelspec": {"name": "matlab_kernel", "language": "matlab", "display_name": "Matlab"}, "language_info": {"mimetype": "text/x-matlab", "name": "matlab", "file_extension": ".m", "help_links": [{"url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md", "text": "MetaKernel Magics"}]}}}