Pythonとpulpを用いて、整数最適化問題としてパズルを解きます。

数理最適化によるパズルの解法

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数理最適化によるパズルの解法\n",
    "\n",
    "## Agenda\n",
    "\n",
    "* <a href='#s1'>自己紹介</a>\n",
    "* <a href='#s2'>オペレーションズ・リサーチ(OR)とは</a>\n",
    "* <a href='#s3'>数理最適化とは</a>\n",
    "* <a href='#sudoku'>数独</a>\n",
    "* <a href='#kakkuro'>カックロ</a>\n",
    "* <a href='#nonogram'>ののぐらむ</a>\n",
    "* <a href='#conc'>まとめ</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <div id='s1' />自己紹介\n",
    "* 名前：斉藤努\n",
    "* 会社：構造計画研究所\n",
    "* 仕事：オペレーションズ・リサーチ(主に最適化)を使った、コンサルや開発をしてます\n",
    "\n",
    "## <div id='s2' />オペレーションズ・リサーチ(OR)とは\n",
    "数学を使って様々な問題を解決する学問です。いろいろなテーマがあります。\n",
    "* 数理最適化\n",
    "  * 線形計画問題\n",
    "  * 混合整数計画問題 (←今日の話)\n",
    "* シミュレーション\n",
    "* 待ち行列\n",
    "* PERT\n",
    "* AHP(階層的意思決定モデル)\n",
    "* スケジューリング\n",
    "* ゲーム理論などなど"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ORの心得\n",
    "* プロフェッショナルとしての自覚を持ち、真摯に行動しましょう\n",
    "* 目的をはっきりさせます\n",
    "  * 進む方向を定めます\n",
    "* モデルを作り解きます\n",
    "  * モデルはシンプルにしましょう\n",
    "  * 現実の8割を表せれば十分なこともあります\n",
    "  * モデルを複雑にするより全体を把握できることが大切です\n",
    "* 答えが合っていなかったら戻りましょう\n",
    "  * 前提を見直しましょう\n",
    "  * モデルと結果の関係から得られるものが重要です\n",
    "  * 答えがあっているなら説得しなければいけません\n",
    "* 適用して目的を達成します\n",
    "  * 効果が出ることで意味があります"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <div id='s3' />数理最適化とは\n",
    "* 数理最適化では、問題を __数理モデル__ で表して、それを解きます\n",
    "  * 数理モデルは、非常にシンプルなルールで様々な問題を記述できます\n",
    "  * 解くソフトウェアを __ソルバ__ とよびます\n",
    "* 特定の問題は専用のソルバを使うこともありますが、汎用のソルバを使うことも多いです\n",
    "  * 今回使うソルバは、汎用ソルバでCBCという無料のソルバです\n",
    "  * モデラーがpulpになります\n",
    " \n",
    "### pulpとは\n",
    "* Pythonによる数理最適化モデリングツールです\n",
    "* Gurobi, CBC, GLPKなど複数のソルバが使えます\n",
    "* インストールは、setuptoolsがあれば、「easy_install pulp」です\n",
    "* 「from pulp import *」で利用可能\n",
    "* BSD 3-Clause License\n",
    "\n",
    "## pulpの数理モデル作成\n",
    "* 最初に、__数理モデル(LpProblem)__を作成します\n",
    "* 次に、必要な分だけ、__変数(LpVariable)__を追加します\n",
    "* 次に、__目的関数の式(LpAffineExpression)__を追加します\n",
    "* 最後に、__制約(LpConstraint)__を追加します\n",
    "\n",
    "## pulpの数理モデル(LpProblem)\n",
    "* コンストラクタ LpProblem(self, name='NoName', sense=LpMinimize)\n",
    "  * name：数理モデル名\n",
    "  * sense：最小化(LpMinimize)または最大化(LpMaximize)\n",
    "* solve(solver)\n",
    "  * solverを用いて問題を解く。solver省略時は、cbcを用いる。GLPKの場合、solve(solvers.GLPK())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from pulp import *\n",
    "LpProblem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### pulpの変数(LpVariable)\n",
    "* コンストラクタ LpVariable(self, name, lowBound=None, upBound=None, cat='Continuous', e=None)\n",
    "  * name：変数名\n",
    "  * lowbound：下限\n",
    "  * upbound：上限\n",
    "  * cat：種類\n",
    "    * LpContinuous：連続変数\n",
    "    * LpInteger：整数変数\n",
    "    * LpBinary：バイナリ変数(0または1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "LpVariable?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### pulpの式(LpAffineExpression)\n",
    "  * 変数を使って「x+2*y」のように作成可能\n",
    "  * 式に後から項を追加するのも可能\n",
    "\n",
    "### pulpの制約(LpConstraint)\n",
    "  * 変数を使って「x+y<=1」のように作成可能\n",
    "  * 制約の左辺に後から項を追加するのも可能\n",
    "\n",
    "### pulpのよく使う関数\n",
    "* value()：変数の値を取り出します\n",
    "* lpSum()：項の和を求めます\n",
    "* lpDot()：2つのリストの内積を求めます\n",
    "* 参考：http://mathopt.sakura.ne.jp/pythonpulp.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='background:#ffeedd'>\n",
    "「数独」「カックロ」「ナンバーリンク」「スリザーリンク」「推理パズル」「ましゅ」はニコリの登録商標です\n",
    "<br/>\n",
    "出典 ニコリhttp://www.nikoli.co.jp/ja/\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 利用できるソルバーの一覧表示(Python3のみ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'pulp.solvers.PULP_CBC_CMD'>\n",
      "<class 'pulp.solvers.GUROBI_CMD'>\n"
     ]
    }
   ],
   "source": [
    "from pulp import *\n",
    "def AvailableSolver(cls):\n",
    "    if sys.version_info[0] >= 3:\n",
    "        for c in cls.__subclasses__():\n",
    "            try:\n",
    "                AvailableSolver(c)\n",
    "                if c().available(): print(c)\n",
    "            except NotImplementedError: pass\n",
    "AvailableSolver(LpSolver)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 変数作成用の関数を定義(手間を省くため)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "from pulp import *\n",
    "# 準備\n",
    "#   実数変数作成関数\n",
    "def addvar(s='v', cat=LpContinuous, n=[0]):\n",
    "    n[0] += 1\n",
    "    return LpVariable(s + str(n[0]), lowBound=0, cat=cat)\n",
    "#   バイナリ変数作成関数\n",
    "def addbinvar(s='v'): return addvar(s, cat=LpBinary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/sudoku.png'/></div>\n",
    "## <div id='sudoku' />数独の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/sudoku.txt)\n",
    "### 問題\n",
    "* マスに 1～9 の数字を入れます\n",
    "* 縦、横または3×3に同じ数字は入りません\n",
    "\n",
    "### 定式化\n",
    "\\begin{array}{cl}\n",
    "            変数 & v_{ijk} \\in \\{0, 1\\} ~ \\forall i, j, k ~ ~ ~ マスi,jが数字k+1か (1) \\\\\n",
    "\\mbox{subject to} & \\sum_k{v_{ijk}} = 1 ~ \\forall i, j ~数字は1つ (2) \\\\\n",
    "                 & \\sum_k{v_{ikj}} = 1 ~ \\forall i, j ~ 縦に同じ数字はない (3) \\\\\n",
    "                 & \\sum_k{v_{kij}} = 1 ~ \\forall i, j ~ 横に同じ数字はない (4) \\\\\n",
    "                 & 3\\times3のマスについても同様 (5) \\\\\n",
    "                 & 数字指定 (6) \\\\\n",
    "\\end{array}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 46 ms\n",
      "5 3 6 8 2 7 9 4 1 \n",
      "1 7 2 9 6 4 3 5 8 \n",
      "8 9 4 1 5 3 2 6 7 \n",
      "7 1 5 3 4 9 8 2 6 \n",
      "6 4 3 7 8 2 1 9 5 \n",
      "9 2 8 5 1 6 7 3 4 \n",
      "4 8 1 2 9 5 6 7 3 \n",
      "3 6 9 4 7 1 5 8 2 \n",
      "2 5 7 6 3 8 4 1 9 \n"
     ]
    }
   ],
   "source": [
    "r3, r9 = range(3), range(9)\n",
    "m = LpProblem()\n",
    "v = {(i, j, k):addbinvar() for i in r9 for j in r9 for k in r9} # (1)\n",
    "with open('data/sudoku.txt') as fp:\n",
    "    for i in r9:\n",
    "        s = fp.readline()\n",
    "        for j in r9:\n",
    "            if s[j].isdigit():\n",
    "                m += v[i, j, int(s[j]) - 1] == 1 # (6)\n",
    "for i in r9:\n",
    "    i0, j0 = i // 3, i % 3\n",
    "    for j in r9:\n",
    "        m += lpSum(v[i, j, k] for k in r9) == 1 # (2)\n",
    "        m += lpSum(v[i, k, j] for k in r9) == 1 # (3)\n",
    "        m += lpSum(v[k, i, j] for k in r9) == 1 # (4)\n",
    "        m += lpSum(v[i0 * 3 + i1, j0 * 3 + j1, j] for i1 in r3 for j1 in r3) == 1 # (5)\n",
    "%time m.solve()\n",
    "for i in r9:\n",
    "    for j in r9: print(sum(k * int(value(v[i, j, k]) + 0.5) for k in r9) + 1, end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href='#conc'>まとめ</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/kakkuro.png'/></div>\n",
    "## <div id='kakkuro' />カックロの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/kakkuro.txt)\n",
    "### 問題\n",
    "* マスに 1～9 の数字を入れます\n",
    "* 縦または横に連続する空マスの中に同じ数字は入りません\n",
    "* 連続するマスの合計が示されます\n",
    "\n",
    "### 定式化\n",
    "\\begin{array}{cl}\n",
    "            変数 & v_{ijk} \\in \\{0, 1\\} ~ \\forall i, j, k ~ ~ ~ マスi,jが数字k+1か (1) \\\\\n",
    "                 & r_{ij} \\in Z ~ \\forall i, j ~ ~ ~ ~ ~ マスi,jの数字 (2) \\\\\n",
    "\\mbox{subject to} & \\sum_k{v_{ijk}} = 1 ~ \\forall i, j ~ ~ ~ ~ 数字は1つ (3) \\\\\n",
    "                 & \\sum_k{k \\times v_{ijk}} + 1 = r_{ij} ~ \\forall i, j ~ ~ ~ rをvで表現 (4) \\\\\n",
    "                 & \\sum_{ij}{r_{ij}} = 合計 ~ \\forall i, j ~ ~ ~ ~ ~ マスの合計が同じ (5) \\\\\n",
    "                 & マスの並びで同じ数字は禁止 (6) \\\\\n",
    "\\end{array}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 27 ms\n",
      "* * * * * * \n",
      "* * * 9 8 * \n",
      "* * 3 1 5 2 \n",
      "* 1 2 * 9 7 \n",
      "* 3 4 1 7 * \n",
      "* * 1 2 * * \n"
     ]
    }
   ],
   "source": [
    "with open('data/kakkuro.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2, r9 = range(nw), range(nh), range(2), range(9)\n",
    "    ch = [fp.readline() for i in rh]\n",
    "    hh = fp.readlines()\n",
    "m = LpProblem()\n",
    "v = {(i, j, k):addbinvar() for i in rw for j in rh for k in r9} # (1)\n",
    "r = {(i, j):addvar('r') for i in rw for j in rh} # (2)\n",
    "cnt = -1\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[i][j] != '*':\n",
    "            m += lpSum(v[i, j, k] for k in r9) == 1 # (3)\n",
    "            m += lpSum(k * v[i, j, k] for k in r9) + 1 == r[i, j] # (4)\n",
    "            continue\n",
    "        cnt += 1\n",
    "        nn = [int(t) if t.isdigit() else -1 for t in hh[cnt].rstrip('\\n').split('\\\\')]\n",
    "        for drc in r2: # 縦と横\n",
    "            if nn[drc] < 0: continue\n",
    "            x, y = i, j\n",
    "            l = []\n",
    "            while True:\n",
    "                x, y = x + drc, y + 1 - drc\n",
    "                if x == nw or y == nh or ch[x][y] == '*': break\n",
    "                l.append((x, y))\n",
    "            for h in r9:\n",
    "                m += lpSum(v[x, y, h] for x, y in l) <= 1 # 並びで同じ数は1つ (6)\n",
    "            m += lpSum(r[x, y] for x, y in l) == nn[drc] # 合計が等しい (5)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('*' if ch[j][i] == '*' else '%d' % int(value(r[i, j]) + 0.5), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href='#conc'>まとめ</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/nonogram.png'/></div>\n",
    "## <div id='nonogram' />ののぐらむの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/nonogram.txt)\n",
    "### 問題\n",
    "* 各横行の左、各縦列の上にある数字は、その行(列)の中で連続して黒く塗る白マスの数を表します\n",
    "* 1つの行(列)に対して数字が複数ある場合は、数字の並び順どおりにその数字の数だけ連続して黒く塗ります\n",
    "* 1 つの行(列)に対して数字が複数ある場合は、その数字が表す黒マスの連続の間に1マス以上の白マス(塗らないマス) が入ります\n",
    "\n",
    "### 定式化\n",
    "\\begin{array}{cl}\n",
    "            変数 & v_{ij} \\in \\{0, 1\\} ~ \\forall i, j ~ ~ ~ マスi,jが黒かどうか (1) \\\\\n",
    "                 & r_{k} \\in \\{0, 1\\} ~ \\forall k, 縦または横 ~ ~ ~ ~ ~ 縦または横ごとにk番目の候補を選ぶかどうか (2) \\\\\n",
    "\\mbox{subject to} & \\sum_k{r_k} = 1 ~ \\forall 縦または横 ~ ~ ~ ~ 縦または横ごとに候補の中から1つ (3) \\\\\n",
    "                 & 候補を選んだらマスの色は候補の通り (4) \\\\\n",
    "\\end{array}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 130 ms\n",
      ". . . . * * . . . . \n",
      ". * . . * * . . . . \n",
      ". * . * * * * * . . \n",
      ". * * * * * . * * . \n",
      ". . * . * * . * . . \n",
      ". . . . * * * . . . \n",
      ". . * * * * * * . . \n",
      "* . * * * . * * . * \n",
      "* * * . . . * * * * \n",
      ". * . . . . . . . * \n"
     ]
    }
   ],
   "source": [
    "def baselist(i, j, k): return [0] * i + [1] * j + [0] * k\n",
    "def makelist(n, l):\n",
    "    p = l[-1]\n",
    "    if len(l) == 1:\n",
    "        if n < p: return None\n",
    "        return [baselist(i, p, n - p - i) for i in range(n - p + 1)]\n",
    "    ll = l[:-1]\n",
    "    s = sum(ll) + len(ll) - 1\n",
    "    return [j + baselist(1, p, n - p - s - i - 1) \\\n",
    "        for i in range(n - p - s) for j in makelist(i + s, ll)]\n",
    "def do(m, v, fp, isw, n1, n2):\n",
    "    for i in range(n1):\n",
    "        ss = [int(s) for s in fp.readline().split(',')]\n",
    "        l = makelist(n2, ss)\n",
    "        r = [addbinvar('r') for c in l] # (2)\n",
    "        m += lpSum(r) == 1 # (3)\n",
    "        for j, c in enumerate(l):\n",
    "            for k, b in enumerate(c):\n",
    "                vv = v[i][k] if isw else v[k][i]\n",
    "                m += (1 - 2 * b) * vv <= 1 - b - r[j] # (4)\n",
    "m = LpProblem()\n",
    "with open('data/nonogram.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    v = [[addvar() for i in range(nw)] for j in range(nh)] # (1)\n",
    "    do(m, v, fp, True, nw, nh)\n",
    "    do(m, v, fp, False, nh, nw)\n",
    "%time m.solve()\n",
    "for j in range(nh):\n",
    "    for i in range(nw):\n",
    "        print('.*'[int(value(v[i][j]) + 0.5)], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href='#conc'>まとめ</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/museum.png'/></div>\n",
    "## <div id='museum' />美術館の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/museum.txt)\n",
    "### 問題\n",
    "* 黒マスに入っている数字は、それと隣接する縦横両隣の最大4つの白マスに入る○の数を表します\n",
    "* 照明は，そのマスから上下左右に黒マスか外枠にぶつかるまでの範囲を照らします\n",
    "* 斜めには照らすことはできません\n",
    "* どの照明にも照らされていない白マスがあってはいけません\n",
    "* 照明のあるマスは他の照明で照らされてはいけません\n",
    "\n",
    "### 変数\n",
    "* v:各マスに照明をおくかどうか (1)\n",
    "\n",
    "### 制約\n",
    "* 白マスの並びの中で照明は1つ以下 (2)\n",
    "* 各マスは1つ以上の照明で照らされること (3)\n",
    "* 数字の周りに同じ数の照明 (4)\n",
    "* 数字に照明はおけない (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 17 ms\n",
      "#   +       # \n",
      "  + 4 +     1 \n",
      "    + 2     + \n",
      "+ #     + 1   \n",
      "  +   #       \n",
      "0     + #     \n",
      "#         + 1 \n"
     ]
    }
   ],
   "source": [
    "with open('data/museum.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2 = range(nw), range(nh), range(2)\n",
    "    ch = [fp.readline() for i in range(nh)]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar('v') for j in rh] for i in rw] # (1)\n",
    "e = [[LpAffineExpression() for j in rh] for i in rw]\n",
    "lst = []\n",
    "def addlist(s, i, j, x, y, c): # 白マスの並びを返す\n",
    "    for k in range(len(s)):\n",
    "        if s[k] == '.':\n",
    "            c.append((i + x * k, j + y * k))\n",
    "        else:\n",
    "            if len(c) > 1: lst.append(c)\n",
    "            c = []\n",
    "for j in rh: addlist(ch[j], 0, j, 1, 0, [])\n",
    "for i in rw: addlist([ch[j][i] for j in rh] + ['\\n'], i, 0, 0, 1, [])\n",
    "for l in lst:\n",
    "    m += lpSum(v[x][y] for x, y in l) <= 1 # (2)\n",
    "    for x, y in l: e[x][y] += lpSum(v[p][q] for p, q in l)\n",
    "def dirs(i, j):\n",
    "    return [v[i + x - y][j + x + y - 1] for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[j][i] == '.':\n",
    "            m += e[i][j] >= 1 # (3)\n",
    "        else:\n",
    "            m += v[i][j] == 0 # (5)\n",
    "            if ch[j][i].isdigit():\n",
    "                m += lpSum(dirs(i, j)) == int(ch[j][i]) # (4)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print(ch[j][i] if ch[j][i] != '.' else '+' if value(v[i][j]) > 0.5 else ' ', end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href='#conc'>まとめ</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/numberlink.png'/></div>\n",
    "## <div id='numberlink' />ナンバーリンクの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/numberlink.txt)\n",
    "### 問題\n",
    "* 各マスには2つ以上の線が入ってはいけません\n",
    "* 異なる線同士が交わってはいけません\n",
    "\n",
    "### 変数\n",
    "* vr:どのタイプのラインに含まれるか (1)\n",
    "* vh:水平に出るかどうか (2)\n",
    "* vv:垂直に出るかどうか (3)\n",
    "\n",
    "### 制約\n",
    "* 始点と終点が指定のラインに含まれること (4)\n",
    "* 始点と終点は、1本だけ出ること (5)\n",
    "* 始点終点以外の各マスに接続されるのは、0本か2本 (6) --- __バイナリ変数なしで記述可能！__\n",
    "* 接続したら、両端のタイプは同じになること (7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 35 ms\n",
      "1-1-1 2-2-2-2 \n",
      "|             \n",
      "1 4 3-3-3-3-3 \n",
      "| |           \n",
      "1 4 5-5-5 6-6 \n",
      "| |     |   | \n",
      "1 4-4-4 5 7 6 \n",
      "|       | | | \n",
      "1 5-5-5-5 7 6 \n",
      "|         | | \n",
      "1 7-7-7-7-7 6 \n",
      "  |         | \n",
      "7-7 6-6-6-6-6 "
     ]
    }
   ],
   "source": [
    "with open('data/numberlink.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2 = range(nw), range(nh), range(2)\n",
    "    ch = [fp.readline() for i in range(nh)]\n",
    "m = LpProblem()\n",
    "vr = [[addvar('r') for j in rh] for i in rw] # (1)\n",
    "vh = [[addbinvar('h') for j in rh] for i in range(nw - 1)] # (2)\n",
    "vv = [[addbinvar('h') for j in range(nh - 1)] for i in rw] # (3)\n",
    "def dirs(i, j):\n",
    "    return [vh[i - k][j] for k in r2 if 0 <= i - k < nw - 1] + \\\n",
    "        [vv[i][j - k] for k in r2 if 0 <= j - k < nh - 1]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        s = dirs(i, j)\n",
    "        if ch[j][i].isdigit():\n",
    "            m += vr[i][j] == int(ch[j][i]) # (4)\n",
    "            m += lpSum(s) == 1 # (5)\n",
    "        else:\n",
    "            #m += lpSum(s) == 2 * m.addbinvar() # inefficient (6)\n",
    "            m += lpSum(s) <= 2 # (6)\n",
    "            for k in range(len(s)):\n",
    "                m += lpSum(s) >= 2 * s[k] # (6)\n",
    "        if i < nw - 1:\n",
    "            m += vr[i][j] <= vr[i + 1][j] + 10 * (1 - vh[i][j]) # (7)\n",
    "            m += vr[i + 1][j] <= vr[i][j] + 10 * (1 - vh[i][j]) # (7)\n",
    "        if j < nh - 1:\n",
    "            m += vr[i][j] <= vr[i][j + 1] + 10 * (1 - vv[i][j]) # (7)\n",
    "            m += vr[i][j + 1] <= vr[i][j] + 10 * (1 - vv[i][j]) # (7)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        sys.stdout.write('%d%c' % (value(vr[i][j]), '-' if\n",
    "                        i < nw - 1 and value(vh[i][j]) >= 0.5 else ' '))\n",
    "    if j == nh - 1: break\n",
    "    sys.stdout.write('\\n')\n",
    "    for i in rw:\n",
    "        sys.stdout.write('%c ' % ('|' if value(vv[i][j]) >= 0.5 else ' '))\n",
    "    sys.stdout.write('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/fukumen.png'/></div>\n",
    "## <div id='fukumen' />覆面算の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/fukumen.txt)\n",
    "### 問題\n",
    "* 各記号は0から9までの数字の1に対応します\n",
    "  * 同じ記号には同じ数字が対応します\n",
    "  * 最上位の桁は0になりません\n",
    "\n",
    "### 変数\n",
    "* v:各位置でどの数字を使うか (1)\n",
    "* r:各位置の1桁の数字 (2)\n",
    "* q:nw桁の数字 (3)\n",
    "\n",
    "### 制約\n",
    "* $v_{ij}$内で数字は１つのみ (4)\n",
    "* rをvで表現 (5)\n",
    "* 空白は0、先頭は0でない (6)\n",
    "* 同じ文字は同じ数字、違う文字は違う数字 (7)\n",
    "* qをrで表現 (8)\n",
    "* qの最後以外の合計は、qの最後と等しい (9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 249 ms\n",
      "0 9 5 6 7 \n",
      "0 1 0 8 5 \n",
      "---------\n",
      "1 0 6 5 2 \n"
     ]
    }
   ],
   "source": [
    "with open('data/fukumen.txt') as fp:\n",
    "    lines = fp.readlines()\n",
    "    lines = lines[:-2] + [lines[-1]]\n",
    "    nw, nh = len(lines[0]) - 1, len(lines)\n",
    "    rw, rh, r10 = range(nw), range(nh), range(10)\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar('v') for k in r10] for j in rh] for i in rw] # (1)\n",
    "r = [[addvar('r') for j in rh] for i in rw] # (2)\n",
    "q = [addvar('q') for j in rh] # (3)\n",
    "dic = {}\n",
    "for j in rh:\n",
    "    e = LpAffineExpression()\n",
    "    fst = True\n",
    "    for i in rw:\n",
    "        c = lines[j][i]\n",
    "        e = e * 10 + r[i][j]\n",
    "        m += lpSum(v[i][j]) == 1 # (4)\n",
    "        m += lpDot(r10, v[i][j]) == r[i][j] # (5)\n",
    "        if c == ' ':\n",
    "            m += v[i][j][0] == 1 # (6)\n",
    "        else:\n",
    "            if c in dic:\n",
    "                m += lpDot(r10, v[i][j]) == lpDot(r10, dic[c]) # (7)\n",
    "            else:\n",
    "                dic[c] = v[i][j]\n",
    "            if fst:\n",
    "                fst = False\n",
    "                m += v[i][j][0] == 0 # (6)\n",
    "    m += e == q[j] # (8)\n",
    "for i, t in dic.items():\n",
    "    for j, u in dic.items():\n",
    "        if i < j:\n",
    "            for k in r10:\n",
    "                m += t[k] + u[k] <= 1 # (7)\n",
    "m += lpSum(q[:-1]) == q[-1] # (9)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    if j == nh - 1: print('-' * (nw * 2 - 1))\n",
    "    for i in rw:\n",
    "        print('%d' % value(r[i][j]), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/inequality.png'/></div>\n",
    "## <div id='inequality' />不等式の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/inequality.txt)\n",
    "### 問題\n",
    "* 各白マスには1からnまでの数字が1つだけ入ります\n",
    "* 各横行および各縦列には同じ数字が入りません\n",
    "* 連続する2つのマス目の間に不等号がある場合，それらのマス目に入る数字は不等号の示す大小関係を満たさなければいけません\n",
    "\n",
    "### 変数\n",
    "* v：各位置がどの数字か (1)\n",
    "* r：各位置の数字 (2)\n",
    "\n",
    "### 制約\n",
    "* $v_{ij}$は1つの数字のみ (3)\n",
    "* rをvで表現 (4)\n",
    "* 縦または横に同じ数字が入りません (5)\n",
    "* 数字が指定されていれば、その数字になること (6)\n",
    "* 不等号があれば、その関係を満たすこと (7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15 ms\n",
      "5 1 2 3 4 \n",
      "4 3 5 1 2 \n",
      "3 4 1 2 5 \n",
      "2 5 3 4 1 \n",
      "1 2 4 5 3 \n"
     ]
    }
   ],
   "source": [
    "with open('data/inequality.txt') as fp:\n",
    "    n = int(fp.readline())\n",
    "    rn = range(n)\n",
    "    lines = fp.readlines()\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar('v') for k in rn] for j in rn] for i in rn] # (1)\n",
    "r = [[addvar('r') for j in rn] for i in rn] # (2)\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        m += lpSum(v[i][j]) == 1 # (3)\n",
    "        m += lpDot(rn, v[i][j]) + 1 == r[i][j] # (4)\n",
    "        m += lpSum(v[i][k][j] for k in rn) == 1 # (5)\n",
    "        m += lpSum(v[k][i][j] for k in rn) == 1 # (5)\n",
    "        c = lines[j * 2][i * 2]\n",
    "        if c.isdigit():\n",
    "            m += v[i][j][int(c) - 1] == 1 # (6)\n",
    "for j in range(n - 1):\n",
    "    for i in rn:\n",
    "        c = lines[j * 2 + 1][i * 2]\n",
    "        if c == 'A': m += r[i][j] <= r[i][j + 1] - 1 # (7)\n",
    "        elif c == 'V': m += r[i][j] >= r[i][j + 1] + 1 # (7)\n",
    "for j in rn:\n",
    "    for i in range(n - 1):\n",
    "        c = lines[j * 2][i * 2 + 1]\n",
    "        if c == '<': m += r[i][j] <= r[i + 1][j] - 1 # (7)\n",
    "        elif c == '>': m += r[i][j] >= r[i + 1][j] + 1 # (7)\n",
    "%time m.solve()\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        print('%d' % sum((k + 1) * value(v[i][j][k]) for k in rn), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/building.png'/></div>\n",
    "## <div id='building' />ビルディングパズルの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/building.txt)\n",
    "### 問題\n",
    "* 各数字はそのマスに立てられるビルの高さを表します\n",
    "* 各横行に同じ数字は入りません\n",
    "* 各縦列に同じ数字は入りません\n",
    "* 盤面の外側の数字はその数字の書かれている場所から盤面を眺めたときに同じ横行(または縦列)に見えるビルの数を表します\n",
    "\n",
    "### 変数\n",
    "* v：各位置がどの高さか (1)\n",
    "* r：各位置の高さ (2)\n",
    "* u：各方向別の数字のある各列ごとに  (3)\n",
    "\n",
    "### 制約\n",
    "* $v_{ij}$は、1つの高さのみ (4)\n",
    "* rをvで表現 (5)\n",
    "* 縦または横に同じ高さがないこと (6)\n",
    "* 上下左右から見たときにuの合計が「数字-1」(すなわち、高くなるときにｕ==1とします) (7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 74 ms\n",
      "2 5 1 3 4 \n",
      "5 4 3 2 1 \n",
      "4 3 2 1 5 \n",
      "1 2 5 4 3 \n",
      "3 1 4 5 2 \n"
     ]
    }
   ],
   "source": [
    "with open('data/building.txt') as fp:\n",
    "    n = int(fp.readline())\n",
    "    rn = range(n)\n",
    "    lines = fp.readlines()\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar('v') for k in rn] for j in rn] for i in rn] # (1)\n",
    "r = [[addvar('r') for j in rn] for i in rn] # (2)\n",
    "def add(m, c, p, q, x, y):\n",
    "    if not c.isdigit(): return\n",
    "    k = int(c)\n",
    "    u = [addvar('u') for i in range(n - 1)] # (3)\n",
    "    m += lpSum(u) == k - 1 # (7)\n",
    "    vmx = r[p][q]\n",
    "    for i in rn:\n",
    "        vnx = r[p + x * i + x][q + y * i + y]\n",
    "        m += vmx + n * u[i] >= vnx + 1 # (7)\n",
    "        m += vmx + 1 <= vnx + n - n * u[i] # (7)\n",
    "        if i == n - 2: break\n",
    "        vtm = addvar()\n",
    "        m += vmx <= vtm # (7)\n",
    "        m += vnx <= vtm # (7)\n",
    "        vmx = vtm\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        m += lpSum(v[i][j]) == 1 # (4)\n",
    "        m += lpDot(rn, v[i][j]) + 1 == r[i][j] # (5)\n",
    "        m += lpSum(v[i][k][j] for k in rn) == 1 # (6)\n",
    "        m += lpSum(v[k][i][j] for k in rn) == 1 # (6)\n",
    "    add(m, lines[0][j + 1], j, 0, 0, 1)\n",
    "    add(m, lines[n + 1][j + 1], j, n - 1, 0, -1)\n",
    "    add(m, lines[j + 1][0], 0, j, 1, 0)\n",
    "    add(m, lines[j + 1][n + 1], n - 1, j, -1, 0)\n",
    "%time m.solve()\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        for k in rn:\n",
    "            if value(v[i][j][k]) > 0.5: print(k + 1, end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/wall.png'/></div>\n",
    "## <div id='wall' />ウォールロジックの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/wall.txt)\n",
    "### 問題\n",
    "* 数字が記入されているマスからその数字の数だけ縦と横に線を引きます\n",
    "* 1つのマスには1本の線しか引くことができません\n",
    "* 数字が記入されているマスには線を引くことができません\n",
    "\n",
    "### 変数\n",
    "* v：各位置のどの方向か  (1)\n",
    "* r：各位置の方向別長さ  (2)\n",
    "\n",
    "### 制約\n",
    "* 数字があれば、方向別長さの和に等しく、かつその位置に矢印がないこと  (3)\n",
    "* 数字がなければ矢印は1方向のみ  (4)\n",
    "* 数字がなければ矢印の方向に長さを1足すこと  (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 26 ms\n",
      "4 R R 1 R U \n",
      "D 4 R R 2 U \n",
      "D D 2 R D 2 \n",
      "1 D D 1 D U \n",
      "D 1 R D 1 U \n",
      "L L 3 R D 2 \n"
     ]
    }
   ],
   "source": [
    "with open('data/wall.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    mx = max(nw, nh)\n",
    "    rw, rh, r4 = range(nw), range(nh), range(4)\n",
    "    ch = [fp.readline() for i in range(nh)]\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar('v') for k in r4] for j in rh] for i in rw] # (1)\n",
    "r = [[[addvar('r') for k in r4] for j in rh] for i in rw] # (2)\n",
    "drc = [(-1, 0, 0), (0, -1, 1), (0, 1, 2), (1, 0, 3)]\n",
    "def sumdir(i, j):\n",
    "    return lpSum(r[i + x][j + y][k] for x, y, k in drc if i + x in rw and j + y in rh)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[j][i].isdigit():\n",
    "            m += sumdir(i, j) == int(ch[j][i]) # (3)\n",
    "            for k in r4:\n",
    "                m += r[i][j][k] == 0 # (3)\n",
    "        else:\n",
    "            m += lpSum(v[i][j]) == 1 # (4)\n",
    "            for x, y, k in drc:\n",
    "                m += r[i][j][k] <= mx * v[i][j][k] # (5)\n",
    "                if i + x in rw and j + y in rh:\n",
    "                    m += r[i][j][k] <= v[i][j][k] + r[i + x][j + y][k] # (5)\n",
    "                else: m += r[i][j][k] <= v[i][j][k] # (5)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[j][i].isdigit():\n",
    "            print(ch[j][i], end=' ')\n",
    "        else:\n",
    "            print('LUDR'[sum(k * int(value(v[i][j][k])) for k in r4)], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/ripple.png'/></div>\n",
    "## <div id='ripple' />波及効果の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/ripple.txt)\n",
    "### 問題\n",
    "* 各部屋のマスには1からその部屋のマス数までの数を1つずつ入れます\n",
    "* 同じ数字を同じ横行、または同じ縦列に入れる場合、数字と数字の間にその数字と同じ数以上のマス目がなくてはなりません\n",
    "\n",
    "### 変数\n",
    "* v：各位置がどの数字か (1)\n",
    "* r：各位置の数字 (2)\n",
    "\n",
    "### 制約\n",
    "* 数字があれば、その数字 (3)\n",
    "* 数字は１つのみ (4)\n",
    "* rをvで表現 (5)\n",
    "* nマス以内に2つ以上の数字nはないこと (6)\n",
    "* 各部屋内で同じ数字はないこと (7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 35 ms\n",
      "1 2 1 3 1 2 \n",
      "2 1 3 2 4 5 \n",
      "4 3 2 1 1 4 \n",
      "3 2 1 4 1 3 \n",
      "2 1 4 5 3 2 \n",
      "1 1 2 3 1 1 \n"
     ]
    }
   ],
   "source": [
    "with open('data/ripple.txt') as fp:\n",
    "    nw, nh, nr = [int(s) for s in fp.readline().split(',')]\n",
    "    ch = [fp.readline() for i in range(nh)]\n",
    "    rms = [[eval(s.replace('-', ',')) for s in fp.readline().split(',')] for i in range(nr)]\n",
    "    na = max(len(rm) for rm in rms)\n",
    "    rw, rh, ra = range(nw), range(nh), range(na)\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar('v') for k in ra] for j in rh] for i in rw] # (1)\n",
    "r = [[addvar('r') for j in rh] for i in rw] # (2)\n",
    "def dirs(i, j, k):\n",
    "    for l in range(1, k + 2):\n",
    "        if i + l < nw: yield v[i + l][j][k]\n",
    "        if j + l < nh: yield v[i][j + l][k]\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[j][i].isdigit():\n",
    "            m += r[i][j] == int(ch[j][i]) # (3)\n",
    "        m += lpSum(v[i][j]) == 1 # (4)\n",
    "        m += lpDot(ra, v[i][j]) + 1 == r[i][j] # (5)\n",
    "        for k in range(1, na):\n",
    "            m += lpSum(dirs(i, j, k)) <= 2 * (1 - v[i][j][k]) # (6)\n",
    "for rm in rms:\n",
    "    for k in range(len(rm)):\n",
    "        m += lpSum(v[i][j][k] for j, i in rm) == 1 # (7)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print(int(value(r[i][j]) + 0.5), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/nskeleton.png'/></div>\n",
    "## <div id='nskeleton' />ナンバースケルトンの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/nskeleton.txt)\n",
    "### 問題\n",
    "* 1つの白マスには0から9までの数字が1つだけ入ります\n",
    "* 連続した白マスの数字をつなげると、与えられたナンバーの1つになります\n",
    "* 各ナンバーはそのようにして一度しか出ません。\n",
    "  * 異なる場所にある連続した白マスから同じナンバーは出ません\n",
    "* 与えられたナンバーは全て盤面の中に見つかります\n",
    "* <a href='#skeleton'>参考</a>\n",
    "\n",
    "### 変数\n",
    "* 省略\n",
    "\n",
    "### 制約\n",
    "* 省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 31 ms\n",
      "2 4 9 * 9 \n",
      "4 * 4 4 1 \n",
      "1 * 2 * 9 \n",
      "9 4 * 1 2 \n",
      "* 1 4 9 * \n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "with open('data/nskeleton.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r10 = range(nw), range(nh), range(10)\n",
    "    ch = [fp.readline() for i in range(nh)]\n",
    "    cands = fp.readlines()\n",
    "dic = defaultdict(list)\n",
    "for cand in cands:\n",
    "    k = len(cand.strip())\n",
    "    dic[k].append([int(cand[i]) for i in range(k)])\n",
    "pos = defaultdict(list)\n",
    "def addpos(i, j, x, y):\n",
    "    while True:\n",
    "        while i < nw and j < nh and ch[j][i] != '.':\n",
    "            i, j = i + x, j + y\n",
    "        if i == nw or j == nh: break\n",
    "        k = 1\n",
    "        while i + x * k < nw and j + y * k < nh and ch[j + y * k][i + x * k] == '.': k += 1\n",
    "        if k > 1:\n",
    "            pos[k].append([(i + x * h, j + y * h) for h in range(k)])\n",
    "        i, j = i + x * k, j + y * k\n",
    "for i in rw: addpos(i, 0, 0, 1)\n",
    "for j in rh: addpos(0, j, 1, 0)\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in r10] for j in rh] for i in rw]\n",
    "r = [[addvar() for j in rh] for i in rw]\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        m += lpSum(v[i][j]) == (1 if ch[j][i] == '.' else 0)\n",
    "        m += lpDot(r10, v[i][j]) == r[i][j]\n",
    "for k, cnds in dic.items():\n",
    "    pss = pos[k]\n",
    "    nc = len(cnds)\n",
    "    rc = range(nc)\n",
    "    assert(len(pss) == nc)\n",
    "    a = [[addbinvar() for g in rc] for h in rc]\n",
    "    for h in rc:\n",
    "        m += lpSum(a[h]) == 1\n",
    "        m += lpSum(a[g][h] for g in rc) == 1\n",
    "        ps = pss[h]\n",
    "        for g in range(k):\n",
    "            i, j = ps[g]\n",
    "            for f in rc:\n",
    "                m += r[i][j] <= cnds[f][g] + 9 * (1 - a[h][f])\n",
    "                m += r[i][j] >= cnds[f][g] - 9 * (1 - a[h][f])\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('*' if ch[j][i] == '*' else '%d' % int(value(r[i][j]) + 0.5), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/slither.png'/></div>\n",
    "## <div id='slither' />スリザーリンクの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/slither.txt)\n",
    "### 問題\n",
    "* 点の間を線でつなぎ、一つの輪を作ります\n",
    "* 数字は、周囲の線の数に等しいこと\n",
    "* 一つの点から出る線の数は0か2となること\n",
    "\n",
    "### 考え方\n",
    "* 線は無向ですが、有向として考えます\n",
    "* 数字の3がある角を始点とします（必ず通ります）\n",
    "\n",
    "### 変数\n",
    "* vh：0:to left, 1:to right (1)\n",
    "* vv：0:to down, 1:to up (2)\n",
    "* vz：始点からの距離 (3)\n",
    "\n",
    "### 制約\n",
    "* 数字があれば、矢印の数に等しいこと (4)\n",
    "* 矢印の向きは1つ (5)\n",
    "* 始点以外は、矢印があれば距離が増やします (6)\n",
    "* 始点の距離は0 (7)\n",
    "* 距離は、全点数以下 (8)\n",
    "* 入る矢印数は1以下 (9)\n",
    "* 入る数と出る数は同じになること (10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 870 ms\n",
      " -   - - -   - \n",
      "|3|3|. . .|3|.|\n",
      "   -   -   -   \n",
      "|. . 2|.|. . .|\n",
      "     -       - \n",
      "|. .|. 2|1 .|3 \n",
      " -     -     - \n",
      " 2|3|.|. . 0 2|\n",
      "   -   -       \n",
      " 0 . 0 3|. . .|\n",
      "       -       \n",
      " . . .|. 0 . .|\n",
      "   - -     -   \n",
      " .|3 . . .|3|3|\n",
      "   - - - -   - \n"
     ]
    }
   ],
   "source": [
    "with open('data/slither.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    M = (nw + 1) * (nh + 1) - 1\n",
    "    rw, rh, rw1, rh1, r2 = range(nw), range(nh), range(nw + 1), range(nh + 1), range(2)\n",
    "    ch = [fp.readline() for i in rh]\n",
    "m = LpProblem()\n",
    "vh = [[[addbinvar() for k in r2] for j in rh1] for i in rw] # 0:to left, 1:to right (1)\n",
    "vv = [[[addbinvar() for k in r2] for j in rh] for i in rw1] # 0:to down, 1:to up (2)\n",
    "vz = [[addvar() for j in rh1] for i in rw1] # (3)\n",
    "def dirs(i, j, k):\n",
    "    return [vh[i - l][j][k ^ l] for l in r2 if 0 <= i - l < nw] + \\\n",
    "            [vv[i][j - l][k ^ l] for l in r2 if 0 <= j - l < nh]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        if ch[j][i] != '.':\n",
    "            m += lpSum(vh[i][j + k][l] + vv[i + k][j][l] for l in r2 for k in r2) == int(ch[j][i]) # (4)\n",
    "            if ch[j][i] == '3': fx, fy = i, j\n",
    "m += vz[fx][fy] == 0 # (7)\n",
    "for i in rw:\n",
    "    for j in rh1:\n",
    "        m += lpSum(vh[i][j]) <= 1 # (5)\n",
    "        m += vz[i][j] + 1 <= vz[i + 1][j] + M * (1 - vh[i][j][0]) # (6)\n",
    "        if (i, j) != (fx, fy):\n",
    "            m += vz[i + 1][j] + 1 <= vz[i][j] + M * (1 - vh[i][j][1]) # (6)\n",
    "for i in rw1:\n",
    "    for j in rh:\n",
    "        m += lpSum(vv[i][j]) <= 1 # (5)\n",
    "        m += vz[i][j] + 1 <= vz[i][j + 1] + M * (1 - vv[i][j][0]) # (6)\n",
    "        if (i, j) != (fx, fy):\n",
    "            m += vz[i][j + 1] + 1 <= vz[i][j] + M * (1 - vv[i][j][1]) # (6)\n",
    "    for j in rh1:\n",
    "        m += vz[i][j] <= M # (8)\n",
    "        din = dirs(i, j, 1)\n",
    "        dout = dirs(i, j, 0)\n",
    "        m += lpSum(din) <= 1 # (9)\n",
    "        m += lpSum(din) == lpSum(dout) # (10)\n",
    "%time m.solve()\n",
    "for j in rh1:\n",
    "    sys.stdout.write(' ')\n",
    "    for i in rw:\n",
    "        sys.stdout.write('- ' if (value(vh[i][j][0]) + value(vh[i][j][1])) > 0.5 else '  ')\n",
    "    sys.stdout.write('\\n')\n",
    "    if j == nh: break\n",
    "    for i in rw1:\n",
    "        sys.stdout.write('|' if (value(vv[i][j][0]) + value(vv[i][j][1])) > 0.5 else ' ')\n",
    "        if i < nw: sys.stdout.write(ch[j][i])\n",
    "    sys.stdout.write('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/square.png'/></div>\n",
    "## <div id='square' />四角に切れの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/square.txt)\n",
    "### 問題\n",
    "* 盤面を数字を1つずつ含む長方形に分割します\n",
    "* 数字は1マスの面積を1とした長方形の面積になるようにします\n",
    "\n",
    "### 変数\n",
    "* v：各位置が各部屋かどうか (1)\n",
    "* vl：候補のどれか (2)\n",
    "\n",
    "### 制約\n",
    "* vは1つの部屋のみ (3)\n",
    "* vlは１つの候補のみ (4)\n",
    "* vlの1つを選んだら、その位置のその部屋は1 (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 32 ms\n",
      "1 1 1 2 2 2 \n",
      "3 3 4 4 6 6 \n",
      "3 3 4 4 6 6 \n",
      "3 3 5 5 6 6 \n",
      "7 7 7 8 8 8 \n",
      "7 7 7 8 8 8 \n"
     ]
    }
   ],
   "source": [
    "with open('data/square.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh = range(nw), range(nh)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    tgt = [(i, j, int(ch[j][i])) for j in rh for i in rw if ch[j][i].isdigit()]\n",
    "    nm = len(tgt)\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in range(nm)] for j in rh] for i in rw] # (1)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        m += lpSum(v[i][j]) == 1 # (3)\n",
    "def make(h, pi, pj, na):\n",
    "    lst = []\n",
    "    for i in range(1, na + 1):\n",
    "        j = na // i\n",
    "        if i * j < na: continue\n",
    "        for x in range(i):\n",
    "            if pi - x < 0 or pi - x + i > nw: continue\n",
    "            lx = range(pi - x, pi - x + i)\n",
    "            for y in range(j):\n",
    "                if pj - y < 0 or pj - y + j > nh: continue\n",
    "                ly = range(pj - y, pj - y + j)\n",
    "                lst.append([v[dx][dy][h] for dy in ly for dx in lx])\n",
    "    return lst\n",
    "for h, (i, j, k) in enumerate(tgt):\n",
    "    lst = make(h, i, j, k)\n",
    "    vl = [addbinvar() for ll in lst] # (2)\n",
    "    m += lpSum(vl) == 1 # (4)\n",
    "    for l, ll in enumerate(lst):\n",
    "        for t in ll:\n",
    "            m += vl[l] <= t # (5)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('%d' % sum((k + 1) * value(v[i][j][k]) for k in range(nm)), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/mashu.png'/></div>\n",
    "## <div id='mashu' />ましゅの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/mashu.txt)\n",
    "### 問題\n",
    "* 盤面に線を引き、すべての白丸と黒丸を通る1つの輪を作ります\n",
    "* 線はタテヨコにマスの中央を通り、1マスに1本だけ通過できます\n",
    "* 線をワクの外に出したり、交差や枝分かれさせたりしてはいけません\n",
    "* 白丸を通る線は、白丸のマスで必ず直進し、白丸の両隣のマスの少なくとも片方で直角に曲がります\n",
    "* 黒丸を通る線は、黒丸のマスで必ず直角に曲がりますが、黒丸の隣のマスで曲がってはいけません\n",
    "\n",
    "### 変数\n",
    "* vz：始点からの距離 (1)\n",
    "* vh：水平線を引くかどうか (2)\n",
    "* vv：垂直線を引くかどうか (3)\n",
    "* vhd：0:to left, 1:to right (4)\n",
    "* vvd：0:to down, 1:to up (5)\n",
    "\n",
    "### 制約\n",
    "* vzはM(マス数)以下 (6)\n",
    "* 点に入るのは1以下 (7)\n",
    "* 点に入る数と出る数は等しくなること (8)\n",
    "* ○の条件。●の条件 (9)\n",
    "* vzの更新式。ｖｈ、ｖｖをvhd、vvdで表現 (10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 261 ms\n",
      "+-+-+-+ +-+-+-+ +-+\n",
      "|     | |     | | | \n",
      "+ + + + +-+ +-+ + +\n",
      "|     |   | |   | | \n",
      "+-+-+ + + + + + + +\n",
      "    | |   | |   | | \n",
      "+-+ + +-+-+ + + + +\n",
      "| | |       |   | | \n",
      "+ + + +-+-+ +-+-+ +\n",
      "| | | |   |       | \n",
      "+ + +-+ + + +-+-+ +\n",
      "| |       | |   | | \n",
      "+ +-+-+-+-+ + + + +\n",
      "|           |   | | \n",
      "+ +-+ +-+-+ + + +-+\n",
      "| | | |   | |       \n",
      "+ + + + + + +-+-+-+\n",
      "| | | |   |       | \n",
      "+-+ +-+ + +-+-+-+-+\n"
     ]
    }
   ],
   "source": [
    "with open('data/mashu.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    M = nw * nh - 1\n",
    "    rw, rh, rw1, rh1, r2 = range(nw), range(nh), range(nw - 1), range(nh - 1), range(2)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem()\n",
    "vz = [[addvar() for j in rh] for i in rw] # (1)\n",
    "vh = [[addvar() for j in rh] for i in rw1] # (2)\n",
    "vv = [[addvar() for j in rh1] for i in rw] # (3)\n",
    "vhd = [[[addbinvar() for k in r2] for j in rh] for i in rw1] # 0:to left, 1:to right (4)\n",
    "vvd = [[[addbinvar() for k in r2] for j in rh1] for i in rw] # 0:to down, 1:to up (5)\n",
    "def dirs(i, j, k):\n",
    "    return [vhd[i - l][j][k ^ l] for l in r2 if 0 <= i - l < nw - 1] + \\\n",
    "        [vvd[i][j - l][k ^ l] for l in r2 if 0 <= j - l < nh - 1]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += vz[i][j] <= M # (6)\n",
    "        din = dirs(i, j, 1)\n",
    "        dout = dirs(i, j, 0)\n",
    "        m += lpSum(din) <= 1 # (7)\n",
    "        m += lpSum(din) == lpSum(dout) # (8)\n",
    "        if ch[j][i] == 'o':\n",
    "            fx, fy = i, j\n",
    "            m += lpSum(dirs(i, j, 1)) == 1 # (9)\n",
    "            if 1 <= i < nw - 1:\n",
    "                m += vh[i - 1][j] == vh[i][j] # (9)\n",
    "            if 2 <= i < nw - 2:\n",
    "                m += vh[i - 2][j] + vh[i + 1][j] <= 2 - vh[i][j] # (9)\n",
    "            if 1 <= j < nh - 1:\n",
    "                m += vv[i][j - 1] == vv[i][j] # (9)\n",
    "            if 2 <= j < nh - 2:\n",
    "                m += vv[i][j - 2] + vv[i][j + 1] <= 2 - vv[i][j] # (9)\n",
    "        elif ch[j][i] == '*':\n",
    "            m += lpSum(vh[i - l][j] for l in r2 if 0 <= i - l < nw - 1) == 1 # (9)\n",
    "            if 0 <= i - 2:\n",
    "                m += vh[i - 1][j] <= vh[i - 2][j] # (9)\n",
    "            if i + 1 < nw - 1:\n",
    "                m += vh[i][j] <= vh[i + 1][j] # (9)\n",
    "            if 0 <= j - 2:\n",
    "                m += vv[i][j - 1] <= vv[i][j - 2] # (9)\n",
    "            if j + 1 < nh - 1:\n",
    "                m += vv[i][j] <= vv[i][j + 1] # (9)\n",
    "for i in rw1:\n",
    "    for j in rh:\n",
    "        m += lpSum(vhd[i][j]) == vh[i][j] # (10)\n",
    "        m += vh[i][j] <= 1 # (10)\n",
    "        m += vz[i][j] + 1 <= vz[i + 1][j] + M * (1 - vhd[i][j][0]) # (10)\n",
    "        if (i, j) != (fx, fy):\n",
    "            m += vz[i + 1][j] + 1 <= vz[i][j] + M * (1 - vhd[i][j][1]) # (10)\n",
    "for i in rw:\n",
    "    for j in rh1:\n",
    "        m += lpSum(vvd[i][j]) == vv[i][j] # (10)\n",
    "        m += vv[i][j] <= 1 # (10)\n",
    "        m += vz[i][j] + 1 <= vz[i][j + 1] + M * (1 - vvd[i][j][0]) # (10)\n",
    "        if (i, j) != (fx, fy):\n",
    "            m += vz[i][j + 1] + 1 <= vz[i][j] + M * (1 - vvd[i][j][1]) # (10)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        sys.stdout.write('+')\n",
    "        if i < nw - 1:\n",
    "            sys.stdout.write('-' if value(vh[i][j]) > 0.5 else ' ')\n",
    "    sys.stdout.write('\\n')\n",
    "    if j == nh - 1: break\n",
    "    for i in rw:\n",
    "        sys.stdout.write('| ' if value(vv[i][j]) > 0.5 else '  ')\n",
    "    sys.stdout.write('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/bridge.png'/></div>\n",
    "## <div id='bridge' />橋をかけろの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/bridge.txt)\n",
    "### 問題\n",
    "* 島同士を線(橋)で結び、すべての数字が線でつながっているようにします\n",
    "* 線は他の線と交差したり数字を横切ったりしてはいけません\n",
    "* 線は水平方向か垂直方向に引かれます\n",
    "* どの数の間にも2本までしか線は引けません\n",
    "* 数字はその数字から引かれる線の数を表します\n",
    "\n",
    "### 変数\n",
    "* v：0:h1, 1:h2, 2:v1, 3:v2 (1)\n",
    "* a：0:h, 1:v ∈{0,1,2} (2)\n",
    "\n",
    "### 制約\n",
    "* aをvで表します (3)\n",
    "* 丸内が数字なら、周りの合計に等しくかつvは全て0 (4)\n",
    "* h2==1ならh1==1であること。vも同じ (5)\n",
    "* h1とv1は同時に成り立ちません (6)\n",
    "* 数字以外では線が続き、端では線ははみ出ないこと (7)\n",
    "* 全ての数字がつながること (8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 39 ms\n",
      "  1 - 5 = 3 - - 3 \n",
      "      H 1 - - 2 H \n",
      "4 = = 8 = 2   | 3 \n",
      "H 2   H 2 - - 2 | \n",
      "3 H   2 | 1 - - 3 \n",
      "| 6 = = 5 = = 4 | \n",
      "3 H   1 - 3   H 1 \n",
      "H 3 - - 1 H   H   \n",
      "3 - - 3 = 6 = 4   \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/bridge.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2, r4 = range(nw), range(nh), range(2), range(4)\n",
    "    ch = [fp.readline() for i in rh]\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in r4] for j in rh] for i in rw] # 0:h1, 1:h2, 2:v1, 3:v2 (1)\n",
    "a = [[[addvar() for k in r2] for j in rh] for i in rw] # 0:h, 1:v (2)\n",
    "def dirs(i, j):\n",
    "    return [a[i + x - y][j + x + y - 1][1 - x ^ y] for x in r2 for y in r2 \\\n",
    "        if i + x - y in rw and j + x + y - 1 in rh]\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        m += a[i][j][0] == lpSum(v[i][j][:2]) # (3)\n",
    "        m += a[i][j][1] == lpSum(v[i][j][2:]) # (3)\n",
    "        if ch[j][i].isdigit():\n",
    "            f = i + j * nw\n",
    "            m += lpSum(dirs(i, j)) == int(ch[j][i]) # (4)\n",
    "            for k in r4:\n",
    "                m += v[i][j][k] == 0 # (4)\n",
    "        else:\n",
    "            m += v[i][j][0] >= v[i][j][1] # (5)\n",
    "            m += v[i][j][2] >= v[i][j][3] # (5)\n",
    "            m += lpSum(v[i][j][0:3:2]) <= 1 # (6)\n",
    "            if i < nw - 1 and not ch[j][i + 1].isdigit():\n",
    "                m += a[i][j][0] == a[i + 1][j][0] # (7)\n",
    "            if j < nh - 1 and not ch[j + 1][i].isdigit():\n",
    "                m += a[i][j][1] == a[i][j + 1][1] # (7)\n",
    "            if i == 0 or i == nw - 1:\n",
    "                m += a[i][j][0] == 0 # (7)\n",
    "            if j == 0 or j == nh - 1:\n",
    "                m += a[i][j][1] == 0 # (7)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if m.status == 1: break\n",
    "    u = unionfind(nw * nh)\n",
    "    e = []\n",
    "    for j in rh:\n",
    "        for i in rw:\n",
    "            if value(a[i][j][0]) > 0.5:\n",
    "                u.unite(i + j * nw, i + j * nw - 1)\n",
    "                u.unite(i + j * nw - 1, i + j * nw + 1)\n",
    "            elif value(a[i][j][1]) > 0.5:\n",
    "                u.unite(i + j * nw, i + j * nw - nw)\n",
    "                u.unite(i + j * nw - nw, i + j * nw + nw)\n",
    "            else:\n",
    "                e.append(lpSum(a[i][j]))\n",
    "    if all([u.issame(f, i + j * nw) for i in rw for j in rh if ch[j][i].isdigit()]): break\n",
    "    m += lpSum(e) >= 1 # (8)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        h = int(sum(value(v[i][j][k]) * (3 if k == 2 else 1) for k in r4))\n",
    "        print(ch[j][i] if ch[j][i] != '.' else ' -=|H'[h], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/norinori.png'/></div>\n",
    "## <div id='norinori' />のりのりの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/norinori.txt)\n",
    "### 問題\n",
    "* 盤面のいくつかのマスを黒くぬります\n",
    "* 黒マスは必ずタテかヨコにちょうど２つだけぬります\n",
    "* 太線で区切られた各部分には、黒マスが２つずつ入ります\n",
    "\n",
    "### 変数\n",
    "* v：黒かどうか (1)\n",
    "\n",
    "### 制約\n",
    "* あるマスが白なら、周りは全て白 (2)\n",
    "* あるマスが黒なら、周りは1つだけ黒 (3)\n",
    "* 各部分内の黒は2つ (4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 18 ms\n",
      "* . * . * \n",
      "* . * . * \n",
      ". * . * . \n",
      ". * . * . \n",
      ". . . . . \n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "with open('data/norinori.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2 = range(nw), range(nh), range(2)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rh] for i in rw] # (1)\n",
    "def dirs(i, j):\n",
    "    return [v[i + x - y][j + x + y - 1] for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "dic = defaultdict(list)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        dic[ch[j][i]].append(v[i][j])\n",
    "        m += v[i][j] <= lpSum(dirs(i, j)) # (2)\n",
    "        m += 3 * v[i][j] + lpSum(dirs(i, j)) <= 4 # (3)\n",
    "for l in dic.values():\n",
    "    m += lpSum(l) == 2 # (4)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('.*'[int(value(v[i][j]) + 0.5)], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/block.png'/></div>\n",
    "## <div id='block' />ブロックパズルの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/block.txt)\n",
    "### 問題\n",
    "* 部品と部品の間に線を引いて、盤面を指定されたブロックに分けます\n",
    "* ブロックの中に部品がちょうど1つ入るようにします\n",
    "* それぞれのブロックに入る部品は、どれもタテかヨコにつながっているように\n",
    "\n",
    "### 変数\n",
    "* v：ブロック候補を選ぶかどうか # (1)\n",
    "\n",
    "### 制約\n",
    "* 各マスで選ばれた候補はちょうど1つ # (2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 17 ms\n",
      "1 2 2 2 3 \n",
      "1 1 4 2 3 \n",
      "5 1 4 2 3 \n",
      "5 1 4 4 3 \n",
      "5 5 5 4 3 \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/block.txt') as fp:\n",
    "    nw, nh, ns = [int(s) for s in fp.readline().split(',')]\n",
    "    nb = nw * nh // ns\n",
    "    rw, rh, rb = range(nw), range(nh), range(nb)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "chk = [False] * ns\n",
    "cand = []\n",
    "def makecand(c, ca):\n",
    "    if len(ca) == ns:\n",
    "        if unionfind.isconnectedlist(nw, nh, ca): cand.append(ca)\n",
    "        return\n",
    "    if c == nw * nh: return\n",
    "    i, j = c % nw, c // nw\n",
    "    k = ord(ch[j][i]) - 65\n",
    "    if not chk[k]:\n",
    "        chk[k] = True\n",
    "        makecand(c + 1, ca + [(i, j)])\n",
    "        chk[k] = False\n",
    "    makecand(c + 1, ca)\n",
    "makecand(0, [])\n",
    "nn = len(cand)\n",
    "rn = range(nn)\n",
    "m = LpProblem()\n",
    "v = [addbinvar() for i in rn] # (1)\n",
    "e = [[LpAffineExpression() == 1 for j in rh] for i in rw]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += e[i][j] # (2)\n",
    "for k in rn:\n",
    "    ca = cand[k]\n",
    "    for i, j in ca:\n",
    "        e[i][j].addterm(v[k], 1)\n",
    "%time m.solve()\n",
    "r = [[0] * nw for j in rh]\n",
    "ic = 0\n",
    "for k in rn:\n",
    "    if value(v[k]) < 0.5: continue\n",
    "    ic += 1\n",
    "    ca = cand[k]\n",
    "    for i, j in ca: r[i][j] = ic\n",
    "for j in rh:\n",
    "    for i in rw: print(r[i][j], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/tile.png'/></div>\n",
    "## <div id='tile' />タイルペイントの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/tile.txt)\n",
    "### 問題\n",
    "* 盤面上にある、太線で区切られた部分（タイルと呼ぶ）のいくつかを黒くぬります\n",
    "* 盤面の数字は、その右あるいは下の、外周か次の斜線のマスまでの区切られた一列のうちで、黒くぬられるマスの数を表します\n",
    "* どのタイルも、すべてのマスをぬるかすべてのマスをぬらずにおくかのどちらかとし、タイルの一部のマスだけをぬってはいけません\n",
    "\n",
    "### 変数\n",
    "* v：黒かどうか (1)\n",
    "\n",
    "### 制約\n",
    "* 縦及び横のヒントの数に等しい (2)\n",
    "* タイルは全部塗るか塗らないか（バイナリ変数不要）(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 13 ms\n",
      ". # . . \n",
      "# # . . \n",
      ". # # # \n",
      ". # . # \n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "with open('data/tile.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh = range(nw), range(nh)\n",
    "    hw = [int(s) for s in fp.readline().split(',')]\n",
    "    hh = [int(s) for s in fp.readline().split(',')]\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rh] for i in rw] # (1)\n",
    "for i in rw:\n",
    "    m += lpSum(v[i]) == hw[i] # (2)\n",
    "for j in rh:\n",
    "    m += lpSum(v[i][j] for i in rw) == hh[j] # (2)\n",
    "dic = defaultdict(list)\n",
    "for i in rw:\n",
    "    for j in rw: dic[ch[j][i]].append(v[i][j])\n",
    "for d in dic.values():\n",
    "    for vi, vj in zip(d, d[1:]):\n",
    "        m += vi == vj # (3)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('.#'[int(value(v[i][j]) + 0.5)], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/inshi.png'/></div>\n",
    "## <div id='inshi' />因子の部屋の解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/inshi.txt)\n",
    "### 問題\n",
    "* すべてのマスに１からNまでの数字のどれかを１つずつ入ります（０は使いません）\n",
    "* タテ列、ヨコ列のどれにも、１からNまでの数字が１つずつ入ります\n",
    "* 太線で囲まれた四角形（部屋）の左上のマスに小さく書かれている数は、その部屋の各マスに入る数をすべてかけあわせた値となります\n",
    "\n",
    "### 変数\n",
    "* v：各マスでその数字かどうか (1)\n",
    "* r：マスの数字 (2)\n",
    "\n",
    "### 制約\n",
    "* $v_{ij}$は1つの数字のみ (3)\n",
    "* rをvで表す (4)\n",
    "* 縦および横で同じ数字はない (5)\n",
    "* 積が指定した数字 (6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 27 ms\n",
      "2 3 5 1 4 \n",
      "3 5 4 2 1 \n",
      "5 2 1 4 3 \n",
      "1 4 2 3 5 \n",
      "4 1 3 5 2 \n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from math import log\n",
    "with open('data/inshi.txt') as fp:\n",
    "    nn, nb, nm = [int(s) for s in fp.readline().split(',')]\n",
    "    rn, rb, rm = range(nn), range(nb), range(nm)\n",
    "    ch = [fp.readline() for j in rn]\n",
    "    ns = [log(int(fp.readline())) for l in rb]\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in rm] for j in rn] for i in rn] # (1)\n",
    "r = [[addvar() for j in rn] for i in rn] # (2)\n",
    "dic = defaultdict(list)\n",
    "for i in rn:\n",
    "    for j in rn:\n",
    "        m += lpSum(v[i][j]) == 1 # (3)\n",
    "        m += lpDot(rm, v[i][j]) + 1 == r[i][j] # (4)\n",
    "        dic[ch[j][i]].append((i, j))\n",
    "    for k in rm:\n",
    "        m += lpSum(v[i][j][k] for j in rn) == 1 # (5)\n",
    "for j in rn:\n",
    "    for k in rm:\n",
    "        m += lpSum(v[i][j][k] for i in rn) == 1 # (5)\n",
    "for l in rb:\n",
    "    s = [log(k + 1) * v[i][j][k] for i, j in dic[chr(l + 65)] for k in rm]\n",
    "    m += lpSum(s) >= ns[l] - 0.0001 # (6)\n",
    "    m += lpSum(s) <= ns[l] + 0.0001 # (6)\n",
    "%time m.solve()\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        print(int(value(r[i][j]) + 0.5), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/kurodoko.png'/></div>\n",
    "## <div id='kurodoko' />黒どこの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/kurodoko.txt)\n",
    "### 問題\n",
    "* 盤面のいくつかのマスを黒くぬります\n",
    "* 盤面の数字は、その数字から上下左右４方向にまっすぐ進み、次の黒マスか外周にたどりつくまでの、その数字を含めてのマス数の合計を表します\n",
    "* 数字が入っているマスを黒くぬってはいけません\n",
    "* 黒マスをタテヨコに連続させたり、黒マスで盤面を分断したりしてはいけません\n",
    "\n",
    "### 変数\n",
    "* vb：0: white, 1: black (1)\n",
    "* vd：0: left, 1: up. 2: right, 3:down (2)\n",
    "\n",
    "### 制約\n",
    "* 各マスが黒ならvdは全方向とも0 (3)\n",
    "* 各マスが白ならvdは方向先のvdより1大きいこと (4)\n",
    "* 端のvdは、白なら1、黒なら0 (5)\n",
    "* 黒は連続しないこと (6)\n",
    "* 数字ならマスは白 (7)\n",
    "* 数字なら$vd_{ij}$の和は数字＋３に等しいこと (8)\n",
    "* 黒マスが分断しないこと (9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 40 ms\n",
      ". 3 # . . . . \n",
      ". . . . # 2 # \n",
      ". # 5 . . # 2 \n",
      ". . . d . . . \n",
      "8 . # . 5 . # \n",
      ". 7 . . # . . \n",
      ". . . . . 9 # \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/kurodoko.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r4 = range(nw), range(nh), range(4)\n",
    "    ch = [fp.readline() for i in rh]\n",
    "m = LpProblem()\n",
    "vb = [[addbinvar() for j in rh] for i in rw] # 0: white, 1: black (1)\n",
    "vd = [[[addvar() for k in r4] for j in rh] for i in rw] # 0: left, 1: up. 2: right, 3:down (2)\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        for k in r4:\n",
    "            mx = nw if k % 2 == 0 else nh\n",
    "            m += vd[i][j][k] <= (1 - vb[i][j]) * mx # (3)\n",
    "            ik, jk = i + [-1, 0, 1, 0][k], j + [0, -1, 0, 1][k]\n",
    "            if 0 <= ik < nw and 0 <= jk < nh:\n",
    "                m += vd[i][j][k] >= vd[ik][jk][k] + 1 - mx * vb[i][j] # (4)\n",
    "                m += vd[i][j][k] <= vd[ik][jk][k] + 1 + mx * vb[i][j] # (4)\n",
    "            else:\n",
    "                m += vd[i][j][k] == 1 - vb[i][j] # (5)\n",
    "        if i > 0: m += vb[i - 1][j] + vb[i][j] <= 1 # (6)\n",
    "        if j > 0: m += vb[i][j - 1] + vb[i][j] <= 1 # (6)\n",
    "        if ch[j][i] != '.':\n",
    "            m += vb[i][j] == 0 # (7)\n",
    "            n = int(ch[j][i]) if ch[j][i].isdigit() else ord(ch[j][i]) - 87\n",
    "            m += lpSum(vd[i][j]) == n + 3 # (8)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(vb[i][j]) < 0.5 for j in rh] for i in rw]): break\n",
    "    s = [vb[i][j] for i in rw for j in rh if value(vb[i][j]) > 0.5]\n",
    "    m += lpSum(s) <= len(s) - 1 # (9)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print(ch[j][i] if ch[j][i] != '.' else '#' if value(vb[i][j]) > 0.5 else '.', end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/suiri.png'/></div>\n",
    "## <div id='suiri' />推理パズルの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/suiri.txt)\n",
    "### 問題\n",
    "* 3つの組を入力し、各組間の対応を求めます\n",
    "* 入力ファイルの意味\n",
    "  * ヒント数\n",
    "  * 組1のリスト\n",
    "  * 組2のリスト\n",
    "  * 組3のリスト\n",
    "  * 以降ヒント\n",
    "    * 明は白いのを買った\n",
    "    * 明は糸じゃない\n",
    "    * 青い紙を買った人がいる\n",
    "    * 勇は紙じゃない\n",
    "    * 正は靴を買った\n",
    "    * 正は赤じゃない\n",
    "\n",
    "### 変数\n",
    "* v12 (1)\n",
    "* v23 (2)\n",
    "* v31 (3)\n",
    "\n",
    "### 制約\n",
    "* 縦横で丸は1つ (4)\n",
    "* AかつB、BかつCなら、CかつA (5)\n",
    "* ヒントを満たすこと (6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 22 ms\n",
      "akira umbrella white\n",
      "isamu string red\n",
      "tadashi shoes black\n",
      "hiroshi paper blue\n"
     ]
    }
   ],
   "source": [
    "with open('data/suiri.txt') as fp:\n",
    "    nh = int(fp.readline())\n",
    "    rh, r3, r4 = range(nh), range(3), range(4)\n",
    "    it = [fp.readline().rstrip('\\n').split(',') for i in r3]\n",
    "    hh = [fp.readline().rstrip('\\n').split(',') for h in rh]\n",
    "dic = [{} for i in r3]\n",
    "for i in r3:\n",
    "    for j in r4:\n",
    "        dic[i][it[i][j]] = j\n",
    "m = LpProblem()\n",
    "v12 = [[addbinvar() for j in r4] for i in r4] # (1)\n",
    "v23 = [[addbinvar() for j in r4] for i in r4] # (2)\n",
    "v31 = [[addbinvar() for j in r4] for i in r4] # (3)\n",
    "for i in r4:\n",
    "    m += lpSum(v12[i]) == 1 # (4)\n",
    "    m += lpSum(v12[j][i] for j in r4) == 1 # (4)\n",
    "    m += lpSum(v23[i]) == 1 # (4)\n",
    "    m += lpSum(v23[j][i] for j in r4) == 1 # (4)\n",
    "    m += lpSum(v31[i]) == 1 # (4)\n",
    "    m += lpSum(v31[j][i] for j in r4) == 1 # (4)\n",
    "    for j in r4:\n",
    "        for k in r4:\n",
    "            m += v12[i][j] + v23[j][k] - v31[k][i] <= 1 # (5)\n",
    "            m += v23[i][j] + v31[j][k] - v12[k][i] <= 1 # (5)\n",
    "            m += v31[i][j] + v12[j][k] - v23[k][i] <= 1 # (5)\n",
    "for h in rh:\n",
    "    c0, c1, c2, c3 = [int(eval(hh[h][0]))] + [dic[i].get(hh[h][i + 1], -1) for i in r3]\n",
    "    if c1 >= 0 and c2 >= 0: m += v12[c1][c2] == c0 # (6)\n",
    "    if c2 >= 0 and c3 >= 0: m += v23[c2][c3] == c0 # (6)\n",
    "    if c3 >= 0 and c1 >= 0: m += v31[c3][c1] == c0 # (6)\n",
    "%time m.solve()\n",
    "for i in r4:\n",
    "    print(it[0][i], end=' ')\n",
    "    j = [j for j in r4 if value(v12[i][j]) > 0.5][0]\n",
    "    print(it[1][j], end=' ')\n",
    "    k = [k for k in r4 if value(v23[j][k]) > 0.5][0]\n",
    "    print(it[2][k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/hitori.png'/></div>\n",
    "## <div id='hitori' />ひとりにしてくれの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/hitori.txt)\n",
    "### 問題\n",
    "* 盤面に並んでいる数字のうちいくつかを黒くぬり、タテでもヨコでも同じ列に同じ数字が複数個入らないようにします\n",
    "* 黒マスをタテヨコに連続したり、黒マスで盤面を分断してはいけません\n",
    "\n",
    "### 変数\n",
    "* v：0:number, 1:black (1)\n",
    "\n",
    "### 制約\n",
    "* 黒以外の数字は縦横に重複しないこと (2)\n",
    "* 黒は連続しないこと (3)\n",
    "* 黒で分断しないこと (4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 20 ms\n",
      "Wall time: 18 ms\n",
      "Wall time: 19 ms\n",
      "Wall time: 11 ms\n",
      "Wall time: 15.6 ms\n",
      "Wall time: 21 ms\n",
      "Wall time: 21 ms\n",
      "Wall time: 22 ms\n",
      "Wall time: 19 ms\n",
      "Wall time: 15.6 ms\n",
      "Wall time: 33.6 ms\n",
      "Wall time: 16 ms\n",
      "Wall time: 31.2 ms\n",
      "Wall time: 20 ms\n",
      "Wall time: 24 ms\n",
      "Wall time: 20 ms\n",
      "Wall time: 2 ms\n",
      "Wall time: 31.2 ms\n",
      "Wall time: 15.6 ms\n",
      "Wall time: 30.6 ms\n",
      "Wall time: 21 ms\n",
      "Wall time: 15.6 ms\n",
      "1 8 # 2 6 7 5 3 \n",
      "3 # 1 # 8 # 2 # \n",
      "8 3 2 4 7 6 # 1 \n",
      "# 7 5 8 3 # 1 4 \n",
      "5 4 # 6 # 1 8 2 \n",
      "7 1 4 # 2 5 3 # \n",
      "2 # 8 3 4 # 7 5 \n",
      "# 2 3 1 # 4 6 # \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/hitori.txt') as fp:\n",
    "    nn = int(fp.readline())\n",
    "    rn = range(nn)\n",
    "    ch = [fp.readline() for j in rn]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rn] for i in rn] # 0:number, 1:black (1)\n",
    "for i in rn:\n",
    "    for j in rn:\n",
    "        if i > 0: m += v[i - 1][j] + v[i][j] <= 1 # (2)\n",
    "        if j > 0: m += v[i][j - 1] + v[i][j] <= 1 # (2)\n",
    "        s = [v[i][k] for k in rn if int(ch[k][i]) == j + 1]\n",
    "        if len(s) > 1: m += lpSum(s) >= len(s) - 1 # (3)\n",
    "        s = [v[k][i] for k in rn if int(ch[i][k]) == j + 1]\n",
    "        if len(s) > 1: m += lpSum(s) >= len(s) - 1 # (3)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(v[i][j]) < 0.5 for i in rn] for j in rn]): break\n",
    "    s = [v[i][j] for i in rn for j in rn if value(v[i][j]) > 0.5]\n",
    "    m += lpSum(s) <= len(s) - 1 # (34)\n",
    "for j in rn:\n",
    "    for i in rn:\n",
    "        print('#' if value(v[i][j]) > 0.5 else ch[j][i], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/heyawake.png'/></div>\n",
    "## <div id='heyawake' />へやわけの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/heyawake.txt)\n",
    "### 問題\n",
    "* 盤面のいくつかのマスを黒くぬります\n",
    "* 太線で区切られた四角（部屋）に入っている数字は、その部屋に入る黒マスの数を表します\n",
    "* 数字の入っていない部屋は、いくつ黒マスが入るか不明です\n",
    "* 白マスを、タテまたはヨコにまっすぐに３つ以上の部屋にわたって続けさせてはいけません\n",
    "* 黒マスをタテヨコに連続させたり、黒マスで盤面を分断したりしてはいけません\n",
    "\n",
    "### 変数\n",
    "* v：0:white, 1:black (1)\n",
    "\n",
    "### 制約\n",
    "* 3つの部屋で白をまっすぐ連続してはいけません (2)\n",
    "* 数字は部屋内の黒の数となること (3)\n",
    "* 黒は連続しないこと (4)\n",
    "* 黒で分断しないこと (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 21 ms\n",
      "Wall time: 31.2 ms\n",
      "Wall time: 15.6 ms\n",
      "Wall time: 15.6 ms\n",
      "# A B # C C D # D # \n",
      "A # B C C # E E E F \n",
      "G G # G H H # I # F \n",
      "G G G # H H I # I F \n",
      "# K L L # H # I # F \n",
      "J K # L M # M N N N \n",
      "J # L L # M M # N # \n",
      "# Q Q R R R # S T T \n",
      "P Q Q # U # S S # V \n",
      "# Q Q U # U S # V V \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "from collections import defaultdict\n",
    "with open('data/heyawake.txt') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rn, r2 = range(nw), range(nh), range(nn), range(2)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    hh = [fp.readline().split(',') for h in rn]\n",
    "dic = {}\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        it = dic.get(ch[j][i], [i, j, i, j])\n",
    "        dic[ch[j][i]] = [min(it[0], i), min(it[1], j), max(it[0], i), max(it[1], j)]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rh] for i in rw] # 0:white, 1:black (1)\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        if i > 0: m += v[i - 1][j] + v[i][j] <= 1 # (4)\n",
    "        if j > 0: m += v[i][j - 1] + v[i][j] <= 1 # (4)\n",
    "for c, s in hh:\n",
    "    mni, mnj, mxi, mxj = dic[c]\n",
    "    ni, nj = mxi - mni + 1, mxj - mnj + 1\n",
    "    m += lpSum(v[i + mni][j + mnj] for i in range(ni) for j in range(nj)) == int(s) # (3)\n",
    "for mni, mnj, mxi, mxj in dic.values():\n",
    "    ni, nj = mxi - mni + 1, mxj - mnj + 1\n",
    "    if mnj > 0 and mxj < nh - 1:\n",
    "        for i in range(ni):\n",
    "            m += lpSum(v[i + mni][j] for j in range(mnj - 1, mxj + 2)) >= 1 # (2)\n",
    "    if mni > 0 and mxi < nw - 1:\n",
    "        for j in range(nj):\n",
    "            m += lpSum(v[i][j + mnj] for i in range(mni - 1, mxi + 2)) >= 1 # (2)\n",
    "def dirs(i, j):\n",
    "    return [i + x - y + nw * (j + x + y - 1) for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    t = [[value(v[i][j]) < 0.5 for j in rh] for i in rw]\n",
    "    u = unionfind(nw * nh)\n",
    "    if unionfind.isconnected(t, u): break\n",
    "    dc = defaultdict(list)\n",
    "    for i in rw:\n",
    "        for j in rh:\n",
    "            if t[i][j]: continue\n",
    "            ll = list(set(u.find(k) for k in dirs(i, j)))\n",
    "            if len(ll) >= 2:\n",
    "                for l in ll: dc[l].append(v[i][j])\n",
    "    for s in dc.values():\n",
    "        m += lpSum(s) <= len(s) - 1 # (5)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('#' if value(v[i][j]) > 0.5 else ch[j][i], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/paint.png'/></div>\n",
    "## <div id='paint' />ペイントエリアの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/paint.txt)\n",
    "### 問題\n",
    "* 盤面上にある、太線で区切られた部分（タイル）のいくつかを黒くぬります\n",
    "* 盤面の数字は、その数字の入っているマスにタテヨコに隣り合うマスのうち、黒マスになるマスの数を表します\n",
    "* 数字のマスが黒マスになることもあります\n",
    "* どのタイルも、すべてのマスをぬるかすべてのマスをぬらずにおくかのどちらとし、タイルの一部のマスだけをぬってはいけません\n",
    "* すべての黒マスはつながること\n",
    "* 黒白マスとも、２×２以上はだめ\n",
    "\n",
    "### 変数\n",
    "* v：0:white, 1:black (1)\n",
    "\n",
    "### 制約\n",
    "* 2×2の黒がないこと (2)\n",
    "* タイル内は同じこと (3)\n",
    "* 数字は周りの黒の数と等しいこと (4)\n",
    "* 全ての黒がつながること (5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15.6 ms\n",
      "Wall time: 18.6 ms\n",
      "# # # # C \n",
      "D # F # C \n",
      "D # F H H \n",
      "D # # # H \n",
      "K K L # H \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "from collections import defaultdict\n",
    "with open('data/paint.txt') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rn, r2 = range(nw), range(nh), range(nn), range(2)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    hh = [[int(s) for s in fp.readline().split(',')] for h in rn]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rh] for i in rw] # 0:white, 1:black (1)\n",
    "dic = defaultdict(list)\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        dic[ch[j][i]].append(v[i][j])\n",
    "        if i > 0 and j > 0:\n",
    "            m += lpSum(v[i - x][j - y] for x in r2 for y in r2) <= 3 # (2)\n",
    "for ss in dic.values():\n",
    "    for s, t in zip(ss, ss[1:]): m += s == t # (3)\n",
    "def dirs(i, j):\n",
    "    return [v[i + x - y][j + x + y - 1] for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "for i, j, k in hh:\n",
    "    m += lpSum(dirs(i, j)) == k # (4)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(v[i][j]) > 0.5 for i in rw] for j in rh]): break\n",
    "    m += lpSum([v[i][j] for i in rw for j in rh if value(v[i][j]) < 0.5]) >= 1 # (5)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('#' if value(v[i][j]) > 0.5 else ch[j][i], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/suukoro.png'/></div>\n",
    "## <div id='suukoro' />数コロの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/suukoro.txt)\n",
    "### 問題\n",
    "* 全てのマスを１から４の数字か空白にします\n",
    "* 数字は、そのマスの隣接マスに数字が入るマスの数になります\n",
    "* 同じ数字を連続してはいけません\n",
    "* すべての数字を連結すること\n",
    "\n",
    "### 変数\n",
    "* v：0:white, 1-4:number (1)\n",
    "* r：数字 (2)\n",
    "\n",
    "### 制約\n",
    "* 数字があればその数字 (3)\n",
    "* 数字は1つ (4)\n",
    "* rをvで表現 (5)\n",
    "* 数字は周りの数字の数に等しいこと (6)\n",
    "* 同じ数字は連続しないこと (7)\n",
    "* 全ての数字がつながること (8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 38.6 ms\n",
      "1 . 1 2 . . 1 \n",
      "3 1 . 3 2 3 2 \n",
      "2 . . 2 . 2 . \n",
      "3 2 3 4 2 4 1 \n",
      "2 . 2 3 . 2 . \n",
      "3 1 . 1 . 3 1 \n",
      "1 . . . 1 2 . \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/suukoro.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2, r5 = range(nw), range(nh), range(2), range(5)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in r5] for j in rh] for i in rw]  # 0:white, 1-4:number (1)\n",
    "r = [[addvar() for j in rh] for i in rw] # (2)\n",
    "def dirs(i, j):\n",
    "    return [1 - v[i + x - y][j + x + y - 1][0] for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        if ch[j][i].isdigit():\n",
    "            m += v[i][j][int(ch[j][i])] == 1 # (3)\n",
    "        m += lpSum(v[i][j]) == 1 # (4)\n",
    "        m += lpDot(r5, v[i][j]) == r[i][j] # (5)\n",
    "        m += lpSum(dirs(i, j)) >= r[i][j] # (6)\n",
    "        m += lpSum(dirs(i, j)) <= r[i][j] + 4 * v[i][j][0] # (6)\n",
    "        for k in range(1, 5):\n",
    "            if i < nw - 1:\n",
    "                m += v[i][j][k] + v[i + 1][j][k] <= 1 # (7)\n",
    "            if j < nh - 1:\n",
    "                m += v[i][j][k] + v[i][j + 1][k] <= 1 # (7)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(v[i][j][0]) < 0.5 for i in rw] for j in rh]): break\n",
    "    s = [v[i][j][0] for i in rw for j in rh if value(v[i][j][0]) > 0.5]\n",
    "    m += lpSum(s) <= len(s) - 1 # (8)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('.1234'[int(value(r[i][j]))], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/pipelink.png'/></div>\n",
    "## <div id='pipelink' />パイプリンクの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/pipelink.txt)\n",
    "### 問題\n",
    "* すべてのマスに線をひき１つのリンクにします\n",
    "* 線は交差してもよいが、枝分かれはしません\n",
    "* 最初に線が引いてあるマスは形を変えてはいけません\n",
    "\n",
    "### 変数\n",
    "* vh (1)\n",
    "* vv (2)\n",
    "* vr：表示用 (3)\n",
    "\n",
    "### 制約\n",
    "* 指定した形はそのままとすること (4)\n",
    "* 全マスに線を引くこと (5)\n",
    "* 交差はいいが、枝分かれしないこと (6)\n",
    "* １つのリンクにすること (7)\n",
    "* 外にはみ出ないこと (8)\n",
    "* vrをvhとvvで表現 (9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15.6 ms\n",
      "┌ ─ ┐ ┌ ┐ \n",
      "│ ┌ ┼ ┘ │ \n",
      "└ ┘ └ ┐ │ \n",
      "┌ ─ ─ ┘ │ \n",
      "└ ─ ─ ─ ┘ \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/pipelink.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rw1, rh1, r2, r4 = range(nw), range(nh), range(nw + 1), range(nh + 1), range(2), range(4)\n",
    "    ch = [fp.readline() for j in range(2 * nh - 1)]\n",
    "m = LpProblem()\n",
    "vh = [[addbinvar() for j in rh] for i in rw1] # (1)\n",
    "vv = [[addbinvar() for j in rh1] for i in rw] # (2)\n",
    "vr = [[addvar() for j in rh] for i in rw] # (3)\n",
    "for j in rh:\n",
    "    m += vh[0][j] == 0 # (8)\n",
    "    m += vh[nw][j] == 0 # (8)\n",
    "for i in rw:\n",
    "    m += vv[i][0] == 0 # (8)\n",
    "    m += vv[i][nh] == 0 # (8)\n",
    "    for j in rh:\n",
    "        if i > 0 and ch[2 * j][2 * i - 1] == '-': m += vh[i][j] == 1 # (4)\n",
    "        if j > 0 and ch[2 * j - 1][2 * i] == '|': m += vv[i][j] == 1 # (4)\n",
    "        l = [vv[i][j], vh[i][j], vv[i][j + 1], vh[i + 1][j]]\n",
    "        m += lpSum(l) >= 2 # (5)\n",
    "        for k in r4: m += lpDot([-1 if p == k else 1 for p in r4], l) <= 2 # (6)\n",
    "        m += lpDot([2**k for k in r4], l) == vr[i][j] # (9)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if m.status != 1: break\n",
    "    b = [[value(vr[i][j]) > 14.5 for j in rh] for i in rw]\n",
    "    u = unionfind(nw * nh)\n",
    "    for i in rw:\n",
    "        for j in rh:\n",
    "            if b[i][j]:\n",
    "                u.unite(i - 1 + j * nw, i + 1 + j * nw)\n",
    "                u.unite(i + j * nw - nw, i + j * nw + nw)\n",
    "            else:\n",
    "                if value(vh[i][j]) > 0.5 and (i == 0 or not b[i - 1][j]):\n",
    "                    u.unite(i + j * nw, i - 1 + j * nw)\n",
    "                if value(vv[i][j]) > 0.5 and (j == 0 or not b[i][j - 1]):\n",
    "                    u.unite(i + j * nw, i + j * nw - nw)\n",
    "    if all([b[i][j] or u.issame(0, i + j * nw) for i in rw for j in rh]): break\n",
    "    for gr in u.groups():\n",
    "        if len(gr) == 1: continue\n",
    "        l = []\n",
    "        for k in gr:\n",
    "            i, j = k % nw, k // nw\n",
    "            l.extend(vh[i + p][j] for p in r2 if value(vh[i + p][j]) > 0.5)\n",
    "            l.extend(vv[i][j + p] for p in r2 if value(vv[i][j + p]) > 0.5)\n",
    "        m += lpSum(l) <= len(l) - 2 # (7)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print(u'012┘4│┐78└─1┌34┼'[int(value(vr[i][j]))], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/kuriku.png'/></div>\n",
    "## <div id='kuriku' />クリークの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/kuriku.txt)\n",
    "### 問題\n",
    "* いくつかのマスを黒くぬります\n",
    "* 数字は、数字が隣接するマス中の黒マスの数を表します\n",
    "* すべての白マスは連結すること\n",
    "\n",
    "### 変数\n",
    "* v：0:white, 1:black (1)\n",
    "\n",
    "### 制約\n",
    "* 数字と黒マス数が等しいこと (2)\n",
    "* 全白マスが連結すること (3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15.6 ms\n",
      "Wall time: 0 ns\n",
      "Wall time: 26.6 ms\n",
      "Wall time: 10 ms\n",
      ". . . . # \n",
      ". # # # # \n",
      ". # . # # \n",
      ". # . . . \n",
      ". . . # # \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/kuriku.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rw1, rh1, r2 = range(nw), range(nh), range(nw + 1), range(nh + 1), range(2)\n",
    "    ch = [fp.readline() for j in rh1]\n",
    "m = LpProblem()\n",
    "v = [[addbinvar() for j in rh] for i in rw] # 0:white, 1:black (1)\n",
    "for i in rw1:\n",
    "    for j in rh1:\n",
    "        if ch[j][i].isdigit():\n",
    "            m += lpSum(v[i - x][j - y] for x in r2 if 0 <= i - x < nw \\\n",
    "                for y in r2 if 0 <= j - y < nh) == int(ch[j][i]) # (2)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(v[i][j]) is None or value(v[i][j]) < 0.5 for i in rw] for j in rh]): break\n",
    "    s = [v[i][j] for i in rw for j in rh if value(v[i][j]) and value(v[i][j]) > 0.5]\n",
    "    m += lpSum(s) <= len(s) - 1 # (3)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print( '.' if value(v[i][j]) is None or value(v[i][j]) < 0.5 else '#', end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/eisbahn.png'/></div>\n",
    "## <div id='eisbahn' />アイスバーンの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/eisbahn.txt)\n",
    "### 問題\n",
    "* INから入りOUTにいく１本の線をひきます\n",
    "* 灰色のマスをアイスバーンとし、必ず通ります\n",
    "* アイスバーンで曲がってはいけません\n",
    "* アイスバーンのみ交差可です\n",
    "* 矢印は必ず通ること\n",
    "\n",
    "### 変数\n",
    "* vh：0:L, 1:R (1)\n",
    "* vv：0:U, 1:D (2)\n",
    "* vhs (3)\n",
    "* vvs (4)\n",
    "\n",
    "### 制約\n",
    "* vhsをvhで、vvsをvvで表現 (5)\n",
    "* 矢印は必ず通ること (6)\n",
    "* 各マスで入る数と出る数が同じこと (7)\n",
    "* アイスバーンなら横は同じ、縦も同じこと（曲がらない） (8)\n",
    "* アイスバーンなら線は2以上 (9)\n",
    "* アイスバーンでないなら線は2以下 (10)\n",
    "* 線は1つ (11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15.6 ms\n",
      "Wall time: 15.6 ms\n",
      "Wall time: 31.2 ms\n",
      " . . . . .\n",
      "R . L*L*L .\n",
      " D D . . U\n",
      ". . . R R .\n",
      " D D U . .\n",
      ".*. R*R R .\n",
      " D . U . D\n",
      ". . . L . .\n",
      " D . . U D\n",
      ". R*R*R . R\n",
      " . . . . .\n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/eisbahn.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rw1, rh1, r2, r12 = range(nw), range(nh), range(nw + 1), range(nh + 1), range(2), range(1, 3)\n",
    "    ch = [fp.readline() for j in range(2 * nh + 1)]\n",
    "m = LpProblem()\n",
    "vh = [[[addbinvar() for k in r2] for j in rh] for i in rw1] # 0:L, 1:R (1)\n",
    "vv = [[[addbinvar() for k in r2] for j in rh1] for i in rw] # 0:U, 1:D (2)\n",
    "vhs = [[addvar() for j in rh] for i in rw1] # (3)\n",
    "vvs = [[addvar() for j in rh1] for i in rw] # (4)\n",
    "for j in rh1:\n",
    "    for i in rw:\n",
    "        c = ch[j * 2][i * 2 + 1]\n",
    "        m += lpDot(r12, vv[i][j]) == vvs[i][j] # (5)\n",
    "        m += vvs[i][j] <= (0 if c == '.' and j % nh == 0 else 2) # (6)\n",
    "        if c == 'U': m += vv[i][j][1] + 1 <= vv[i][j][0] # (6)\n",
    "        elif c == 'D': m += vv[i][j][0] + 1 <= vv[i][j][1] # (6)\n",
    "    if j == nh: break\n",
    "    for i in rw1:\n",
    "        c = ch[j * 2 + 1][i * 2]\n",
    "        m += lpDot(r12, vh[i][j]) == vhs[i][j] # (5)\n",
    "        m += vhs[i][j] <= (0 if c == '.' and i % nw == 0 else 2) # (6)\n",
    "        if c == 'L': m += vh[i][j][1] + 1 <= vh[i][j][0] # (6)\n",
    "        elif c == 'R': m += vh[i][j][0] + 1 <= vh[i][j][1] # (6)\n",
    "    for i in rw:\n",
    "        e1 = lpSum(vv[i][j + k][1 - k] + vh[i + k][j][1 - k] for k in r2)\n",
    "        e2 = lpSum(vv[i][j + k][k] + vh[i + k][j][k] for k in r2)\n",
    "        m += e1 == e2 # (7)\n",
    "        if ch[j * 2 + 1][i * 2 + 1] == '*':\n",
    "            m += vhs[i][j] == vhs[i + 1][j] # (8)\n",
    "            m += vvs[i][j] == vvs[i][j + 1] # (8)\n",
    "            m += e1 + e2 >= 2 # (9)\n",
    "        else: m += e1 + e2 <= 2 # (10)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if m.status != 1: break\n",
    "    b = [[all([value(vhs[i + k][j]) > 0.5 and value(vvs[i][j + k]) > 0.5 for k in r2]) for j in rh] for i in rw]\n",
    "    e = [[all([value(vhs[i + k][j]) < 0.5 and value(vvs[i][j + k]) < 0.5 for k in r2]) for j in rh] for i in rw]\n",
    "    u = unionfind(nw * nh)\n",
    "    p = -1\n",
    "    for i in rw:\n",
    "        for j in rh:\n",
    "            if not e[i][j]: p = i + j * nw\n",
    "            if b[i][j]:\n",
    "                u.unite(i - 1 + j * nw, i + 1 + j * nw)\n",
    "                u.unite(i + j * nw - nw, i + j * nw + nw)\n",
    "            else:\n",
    "                if i > 0 and value(vhs[i][j]) > 0.5 and not b[i - 1][j]:\n",
    "                    u.unite(i + j * nw, i - 1 + j * nw)\n",
    "                if j > 0 and value(vvs[i][j]) > 0.5 and not b[i][j - 1]:\n",
    "                    u.unite(i + j * nw, i + j * nw - nw)\n",
    "    if all([b[i][j] or e[i][j] or u.issame(p, i + j * nw) for i in rw for j in rh]): break\n",
    "    for gr in u.groups():\n",
    "        if len(gr) == 1: continue\n",
    "        s = []\n",
    "        for g in gr:\n",
    "            i, j = g % nw, g // nw\n",
    "            for k in r2:\n",
    "                for l in r2:\n",
    "                    if value(vh[i + k][j][l]) > 0.5: s.append(vh[i + k][j][l])\n",
    "                    if value(vv[i][j + k][l]) > 0.5: s.append(vv[i][j + k][l])\n",
    "        m += lpSum(s) <= len(s) - 2 # (11)\n",
    "for j in rh1:\n",
    "    for i in rw:\n",
    "        sys.stdout.write(' %c' % '.UD'[int(value(vvs[i][j]))])\n",
    "    sys.stdout.write('\\n')\n",
    "    if j == nh: break\n",
    "    for i in rw1:\n",
    "        sys.stdout.write('%c%c' % ('.LR'[int(value(vhs[i][j]))],\n",
    "            '\\n' if i == nw else ch[j * 2 + 1][i * 2 + 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/sumline.png'/></div>\n",
    "## <div id='sumline' />サムラインの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/sumline.txt)\n",
    "### 問題\n",
    "* 1から9の数字をいれます\n",
    "* タテヨコ各列のカギは、その列に入る数の合計です\n",
    "* タテもヨコも、同じ数字は１つまでです\n",
    "\n",
    "### 変数\n",
    "* v (1)\n",
    "* r (2)\n",
    "\n",
    "### 制約\n",
    "* $v_{ij}$は1つ (3)\n",
    "* rをvで表現 (4)\n",
    "* 縦も横も同じ数字は1つまで (5)\n",
    "* ヒントを満たすこと (6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 46.6 ms\n",
      "1 6 7 8 * 9 \n",
      "7 * 8 3 5 4 \n",
      "4 5 9 * 6 * \n",
      "* 9 * 7 1 2 \n",
      "9 1 3 4 * 5 \n",
      "2 * 5 6 9 8 \n"
     ]
    }
   ],
   "source": [
    "with open('data/sumline.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r9 = range(nw), range(nh), range(9)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    hh = [int(fp.readline()) for j in rh]\n",
    "    hv = [int(fp.readline()) for i in rw]\n",
    "m = LpProblem()\n",
    "v = [[[addbinvar() for k in r9] for j in rh] for i in rw]\n",
    "r = [[addvar() for j in rh] for i in rw]\n",
    "def addsum(i, j, x, y):\n",
    "    e, f = LpAffineExpression(), LpAffineExpression()\n",
    "    while i < nw and j < nh:\n",
    "        if ch[j][i] == '.':\n",
    "            f = f * 10 + r[i][j]\n",
    "        else:\n",
    "            e += f\n",
    "            f = LpAffineExpression()\n",
    "        i, j = i + x, j + y\n",
    "    return e + f\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += lpSum(v[i][j]) == 1\n",
    "        m += lpDot(r9, v[i][j]) + 1 == r[i][j]\n",
    "    for k in r9:\n",
    "        m += lpSum(v[i][j][k] for j in rh) <= 1\n",
    "    m += addsum(i, 0, 0, 1) == hv[i]\n",
    "for j in rh:\n",
    "    for k in r9:\n",
    "        m += lpSum(v[i][j][k] for i in rw) <= 1\n",
    "    m += addsum(0, j, 1, 0) == hh[j]\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('*' if ch[j][i] == '*' else '%d' % int(value(r[i][j]) + 0.5), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/countryroad.png'/></div>\n",
    "## <div id='countryroad' />カントリーロードの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/countryroad.txt)\n",
    "### 問題\n",
    "* いくつかのマスに線を引き、１つの輪を作ります\n",
    "* 線は、交差や枝分かれしてはいけません\n",
    "* 太線で区切られたところ（国と呼ぶ）すべてを１回ずつだけ通ります\n",
    "* 数字は、その数字がある国を線が通るマス数を表します\n",
    "* 数字のない国には、何マスでもよいです\n",
    "* 線が通らないマスが、太線（国境）をはさんでタテヨコに隣接してはいけません\n",
    "\n",
    "### 変数\n",
    "* vh：0:L, 1:R (1)\n",
    "* vv：0:U, 1:D (2)\n",
    "* vhs (3)\n",
    "* vvs (4)\n",
    "* vr：表示用 (5)\n",
    "\n",
    "### 制約\n",
    "* vh,vv,vhs,vvsの関係 (6)\n",
    "* 入る数と出る数が同じであること (7)\n",
    "* 1つの輪 (8)\n",
    "* その他は略 (9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 62.4 ms\n",
      "┌┐┼┼┌─┐\n",
      "│└─┐│┼│\n",
      "└┐┼│└┐│\n",
      "┼│┼└┐││\n",
      "┼│┌┐└┘│\n",
      "┌┘│└─┐│\n",
      "└─┘┼┼└┘\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from unionfind import *\n",
    "with open('data/countryroad.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rw1, rh1, r2, r4 = range(nw), range(nh), range(nw + 1), range(nh + 1), range(2), range(4)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    hh = fp.readlines()\n",
    "m = LpProblem()\n",
    "vh = [[[addbinvar() for k in r2] for j in rh] for i in rw1] # 0:L, 1:R (1)\n",
    "vv = [[[addbinvar() for k in r2] for j in rh1] for i in rw] # 0:U, 1:D (2)\n",
    "vhs = [[addvar() for j in rh] for i in rw1] # (3)\n",
    "vvs = [[addvar() for j in rh1] for i in rw] # (4)\n",
    "vr = [[addvar() for j in rh] for i in rw] # (5)\n",
    "dic1, dic2 = defaultdict(list), defaultdict(list)\n",
    "for i in rw:\n",
    "    m += vvs[i][0] == 0 # (9)\n",
    "    m += vvs[i][nh] == 0 # (9)\n",
    "for j in rh1:\n",
    "    for i in rw:\n",
    "        m += lpSum(vv[i][j]) == vvs[i][j] # (6)\n",
    "        m += vvs[i][j] <= 1 # (9)\n",
    "    if j == nh: break\n",
    "    m += vhs[0][j] == 0 # (9)\n",
    "    m += vhs[nw][j] == 0 # (9)\n",
    "    for i in rw1:\n",
    "        m += lpSum(vh[i][j]) == vhs[i][j] # (6)\n",
    "        m += vhs[i][j] <= 1 # (9)\n",
    "    for i in rw:\n",
    "        m += lpDot([-1, 1, 1, -1], [vh[i + k][j][l] for k in r2 for l in r2]) \\\n",
    "          == lpDot([1, -1, -1, 1], [vv[i][j + k][l] for k in r2 for l in r2]) # (7)\n",
    "        l = [vvs[i][j], vhs[i][j], vvs[i][j + 1], vhs[i + 1][j]]\n",
    "        dic1[ch[j][i]].extend(l)\n",
    "        m += lpDot([2**k for k in r4], l) == vr[i][j] # (9)\n",
    "        m += lpSum(l) <= 2\n",
    "        if i < nw - 1 and ch[j][i] != ch[j][i + 1]:\n",
    "            m += vr[i][j] + vr[i + 1][j] >= 1 # (9)\n",
    "            dic2[ch[j][i]].append(vh[i + 1][j][0])\n",
    "            dic2[ch[j][i + 1]].append(vh[i + 1][j][1])\n",
    "        if j < nh - 1 and ch[j][i] != ch[j + 1][i]:\n",
    "            m += vr[i][j] + vr[i][j + 1] >= 1 # (9)\n",
    "            dic2[ch[j][i]].append(vv[i][j + 1][0])\n",
    "            dic2[ch[j + 1][i]].append(vv[i][j + 1][1])\n",
    "for s in hh:\n",
    "    ss = s.split(',')\n",
    "    if len(ss) < 2: break\n",
    "    m += lpSum(dic1[ss[0]]) == 2 * int(ss[1]) # (9)\n",
    "for s in dic2.values():\n",
    "    m += lpSum(s) == 1 # (9)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if m.status != 1: break\n",
    "    u = unionfind(nw * nh)\n",
    "    p = -1\n",
    "    for i in rw:\n",
    "        for j in rh:\n",
    "            if value(vhs[i + 1][j]) > 0.5:\n",
    "                p = i + j * nw\n",
    "                u.unite(i + j * nw, i + 1 + j * nw)\n",
    "            if value(vvs[i][j + 1]) > 0.5:\n",
    "                u.unite(i + j * nw, i + j * nw + nw)\n",
    "    if all([u.find(i + j * nw) == i + j * nw or u.issame(p, i + j * nw) for i in rw for j in rh]): break\n",
    "    for gr in u.groups():\n",
    "        if len(gr) == 1: continue\n",
    "        s = []\n",
    "        for g in gr:\n",
    "            i, j = g % nw, g // nw\n",
    "            for k in r2:\n",
    "                if value(vhs[i + k][j]) > 0.5: s.append(vhs[i + k][j])\n",
    "                if value(vvs[i][j + k]) > 0.5: s.append(vvs[i][j + k])\n",
    "        m += lpSum(s) <= len(s) - 2 # (8)\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        sys.stdout.write(u'┼12┘4│┐78└─1┌34┼'[int(value(vr[i][j]))])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/kanaore.png'/></div>\n",
    "## <div id='kanaore' />カナオレの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/kanaore.txt)\n",
    "### 問題\n",
    "* 全マスに１文字ずつ入れ、リストの言葉全部を盤面に作ります\n",
    "* どの言葉も、１文字目は言葉の前に書かれている数字のマスに入り、２文字目は矢印の方向に１つ進んだマスに入ります\n",
    "* ３文字目以降は、タテヨコにつながって入ります\n",
    "* １つの文字を複数の言葉が共通して使うこともあります\n",
    "* １つの文字を１つの言葉が複数回使うことはありません\n",
    "\n",
    "### 変数\n",
    "* v：各マスの文字のID (1)\n",
    "* 各単語ごとに候補(lst)を作り\n",
    "  * vt：どの候補を選ぶか (2)\n",
    "\n",
    "### 制約\n",
    "* 候補から選ぶこと (3)\n",
    "* 候補を選んだら、その場所は、その文字とすること (4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 31.2 ms\n",
      "ナ オ レ マ ロ \n",
      "カ ン ケ ツ ク \n",
      "ラ イ イ ミ ノ \n",
      "ム ケ ス オ フ \n",
      "サ ナ ン ル イ \n"
     ]
    }
   ],
   "source": [
    "import codecs\n",
    "with codecs.open('data/kanaore.txt', 'r', 'utf-8') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().strip(u'\\ufeff').split(',')]\n",
    "    rw, rh, rn, r4 = range(nw), range(nh), range(nn), range(4)\n",
    "    wds = [fp.readline().strip().split(',') for i in rn]\n",
    "def makecand(lst, x, y, d, l, p, u):\n",
    "    xx, yy = x + [-1, 0, 1, 0][d], y + [0, -1, 0, 1][d]\n",
    "    if 0 <= xx < nw and 0 <= yy < nh and (xx, yy) not in u:\n",
    "        if p == l - 1:\n",
    "            lst.append(u + [(xx, yy)])\n",
    "            return\n",
    "        for k in r4: makecand(lst, xx, yy, k, l, p + 1, u + [(xx, yy)])\n",
    "m = LpProblem()\n",
    "v = [[addvar() for j in rh] for i in rw] # (1)\n",
    "dic, dic2 = {}, {}\n",
    "for wd in wds:\n",
    "    for c in wd[3]:\n",
    "        if not c in dic:\n",
    "            t = len(dic)\n",
    "            dic[c], dic2[t] = t, c\n",
    "    lst = []\n",
    "    x, y = int(wd[0]), int(wd[1])\n",
    "    makecand(lst, x, y, u'←↑→↓'.index(wd[2]), len(wd[3]), 1, [(x, y)])\n",
    "    vt = [addbinvar() for cand in lst] # (2)\n",
    "    m += lpSum(vt) == 1 # (3)\n",
    "    for i, cand in enumerate(lst):\n",
    "        for j, (x, y) in enumerate(cand):\n",
    "            c = dic[wd[3][j]]\n",
    "            m += v[x][y] <= c + nw * nh * (1 - vt[i]) # (4)\n",
    "            m += v[x][y] >= c - nw * nh * (1 - vt[i]) # (4)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print(dic2[int(value(v[i][j]))], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/fillmat.png'/></div>\n",
    "## <div id='fillmat' />フィルマットの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/fillmat.txt)\n",
    "### 問題\n",
    "* 点線の上にタテヨコに線を引いて、盤面をいくつかの畳（幅１マスで長さ１～４マスの四角形）に区切ります\n",
    "* 数字は、その数字を含む畳の面積を、１マスを１として表します\n",
    "* 数字の入らない畳を作ってもよいが、２つ以上の数字を含む畳を作ってはいけません\n",
    "* 同じ面積の畳をタテヨコに隣り合わせてはいけません\n",
    "* 畳の境界線が十字に交差してはいけません\n",
    "\n",
    "### 変数\n",
    "* 数字ごとの候補 (1)\n",
    "\n",
    "### 制約\n",
    "* 1つの候補を選ぶ (2)\n",
    "* 4つの角を接する組合せの合計が≦3 (3)\n",
    "* 同じ面積の候補同士で隣り合うものの合計≦1 (4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 31.2 ms\n",
      "A A A A I \n",
      "B B G H I \n",
      "C C C H I \n",
      "D E E E E \n",
      "D F F F J \n"
     ]
    }
   ],
   "source": [
    "with open('data/fillmat.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r4, r19 = range(nw), range(nh), range(4), range(1, 9)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem()\n",
    "vls = [] # list of (var, pos_list)\n",
    "cs = [[LpAffineExpression() for j in rh] for i in rw] # cons of pos\n",
    "dic = {} # key:(x_start, y_start, x_len, y_len), value:(var, pos_list)\n",
    "def chk(v, ky):\n",
    "    if ky in dic: m.add(v + dic[ky][0] <= 1) # (4)\n",
    "def cand(i, j, n, dx, dy):\n",
    "    p, q = [], []\n",
    "    for k in range(n):\n",
    "        x, y = i + k * dx, j + k * dy\n",
    "        p.append((x, y))\n",
    "        if ch[y][x].isdigit(): q.append(int(ch[y][x]))\n",
    "    if len(q) >= 2 or (len(q) == 1 and q[0] != n): return\n",
    "    v = addbinvar() # (1)\n",
    "    for k in range(max(1, n * dy)):\n",
    "        chk(v, (i - 1, j + k - n + 1, 0, n))\n",
    "        chk(v, (i - n, j + k, n, 0))\n",
    "    for k in range(max(1, n * dx)):\n",
    "        chk(v, (i + k, j - n, 0, n))\n",
    "        chk(v, (i + k - n + 1, j - 1, n, 0))\n",
    "    vls.append((v, p))\n",
    "    dic[(i, j, dx * n, dy * n)] = vls[-1]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        for k in r4:\n",
    "            if i + k < nw: cand(i, j, k + 1, 1, 0)\n",
    "            if k > 0 and j + k < nh: cand(i, j, k + 1, 0, 1)\n",
    "for i, vl in enumerate(vls):\n",
    "    for x, y in vl[1]: cs[x][y] += vl[0]\n",
    "def chk2(ky1, ky2, ky3, ky4):\n",
    "    if ky1 in dic and ky2 in dic and ky3 in dic and ky4 in dic:\n",
    "        m.add(dic[ky1][0] + dic[ky2][0] + dic[ky3][0] + dic[ky4][0] <= 3) # (3)\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += cs[i][j] == 1 # (2)\n",
    "        if i == 0 or j == 0: continue\n",
    "        for k1 in r19:\n",
    "            x1, y1, z1, w1 = (i - k1, j - 1, k1, 0) if k1 < 5 else (i - 1, j - k1 + 4, 0, k1 - 4)\n",
    "            if x1 < 0 or y1 < 0: continue\n",
    "            for k2 in r19:\n",
    "                x2, y2, z2, w2 = (i, j - 1, k2, 0) if k2 < 5 else (i - 1, j - k2 + 4, 0, k2 - 4)\n",
    "                if x2 + z2 > nw or y2 < 0: continue\n",
    "                for k3 in r19:\n",
    "                    x3, y3, z3, w3 = (i, j, k3, 0) if k3 < 5 else (i, j, 0, k3 - 4)\n",
    "                    if x3 + z3 > nw or y3 + w3 > nh: continue\n",
    "                    for k4 in r19:\n",
    "                        x4, y4, z4, w4 = (i - k4, j, k4, 0) if k4 < 5 else (i - 1, j, 0, k4 - 4)\n",
    "                        if x4 < 0 or y4 + w4 > nh: continue\n",
    "                        chk2((x1, y1, z1, w1), (x2, y2, z2, w2), (x3, y3, z3, w3), (x4, y4, z4, w4))\n",
    "%time m.solve()\n",
    "i, ss = 65, [[0 for i in rw] for j in rh]\n",
    "for vl in vls:\n",
    "    if value(vl[0]) > 0.5:\n",
    "        for x, y in vl[1]: ss[y][x] = chr(i)\n",
    "        i += 1\n",
    "for s in ss:\n",
    "    for c in s: print(c, end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/shakashaka.png'/></div>\n",
    "## <div id='shakashaka' />シャカシャカの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/shakashaka.txt)\n",
    "### 問題\n",
    "* 盤面のいくつかの白マスを三角形に黒くぬりつぶします\n",
    "* マスのぬり方は4通りのいずれかです\n",
    "* 盤面の数字は、その数字の入っているマスにタテヨコに隣り合うマスのうち、三角形にぬるマスの数を表します\n",
    "* ぬられずに残った部分は、すべて長方形となります\n",
    "\n",
    "### 変数\n",
    "* va (1)\n",
    "\n",
    "### 制約\n",
    "* $va_{ij}$は１つのみ (2)\n",
    "* 数字か■なら$va_{ij5}$==1 (3)\n",
    "* 数字なら周りの斜めの合計と同じ (4)\n",
    "* 画面端で可能な形の指定 (5)\n",
    "* 右や下との境で合わない物通しの禁止 (6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 46.8 ms\n",
      " 2┛┗ 2■┛┗ 3┛┗\n",
      "┛　┏┛┗┓┏┛　┏\n",
      "┓┏┛　┏■■┓┏ 3\n",
      "■ *┓┏■ 0■■┛┗\n",
      "┛┗ 3┛┗■┛┗┓┏\n",
      "┓┏■┓┏ 3┓┏ 3■\n",
      " 2■ 0■■┛┗┛┗■\n",
      "┛┗■┛┗┓┏┓┏ 1\n",
      "┓　┗┓　┗■ 1■■\n",
      " 2┓┏ 3┓┏■ 0■■\n"
     ]
    }
   ],
   "source": [
    "with open('data/shakashaka.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2, r6 = range(nw), range(nh), range(2), range(6)\n",
    "    ch = [fp.readline() for i in rh]\n",
    "m = LpProblem()\n",
    "va = [[[addbinvar() for k in r6] for j in rh] for i in rw] # (1)\n",
    "def dirs(i, j):\n",
    "    return [va[i + x - y][j + x + y - 1] for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        v = va[i][j]\n",
    "        m += lpSum(v) == 1 # (2)\n",
    "        if ch[j][i] != '.':\n",
    "            m += v[5] == 1 # (3)\n",
    "            if ch[j][i].isdigit():\n",
    "                m += lpSum(v[1:5] for v in dirs(i, j)) == int(ch[j][i]) # (4)\n",
    "        if i == 0: m += v[0] + lpSum(v[2:4]) == 0 # (5)\n",
    "        if j == 0: m += v[0] + lpSum(v[3:5]) == 0 # (5)\n",
    "        if i == nw - 1: m += v[0] + lpSum(v[1:5:3]) == 0 # (5)\n",
    "        if j == nw - 1: m += v[0] + lpSum(v[1:3]) == 0 # (5)\n",
    "        if i > 0:\n",
    "            m += lpSum([va[i - 1][j][0]] + va[i - 1][j][1:5:3] + [v[1]] + v[4:6]) <= 1 # (6)\n",
    "            m += lpSum(va[i - 1][j][2:4] + [va[i - 1][j][5]] + [v[0]] + v[2:4]) <= 1 # (6)\n",
    "        if j > 0:\n",
    "            m += lpSum(va[i][j - 1][:3] + v[1:3] + [v[5]]) <= 1 # (6)\n",
    "            m += lpSum(va[i][j - 1][3:6] + [v[0]] + v[3:5]) <= 1 # (6)\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if ch[j][i] != '.': sys.stdout.write(' %c' % ch[j][i])\n",
    "        else: sys.stdout.write(u'　┛┗┏┓■'[int(value(lpDot(r6, va[i][j])))])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/yajirin.png'/></div>\n",
    "## <div id='yajirin' />ヤジリンの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/yajirin.txt)\n",
    "### 問題\n",
    "* 線を引いて全体で１つの輪を作り、線が通らないマスは黒くぬります\n",
    "* 数字は、矢印の方向に入る黒マスの数を表します\n",
    "* 数字のマスに線を引いたり、黒マスにしたりしてはいけません\n",
    "* 線は、マスの中央を通るようにタテヨコに引き、線を交差させたり、枝分かれさせたりしてはいけません\n",
    "* 黒マスをタテヨコに連続させてはいけません\n",
    "\n",
    "### 変数\n",
    "* 略\n",
    "\n",
    "### 制約\n",
    "* 略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 1.15 s\n",
      "┌──┐╂┌──┐2D\n",
      "└─┐└─┘╂1L│╂\n",
      "╂1L└┐╂┌─┐└┐\n",
      "┌──┘2U└┐└┐│\n",
      "│╂1L┌┐┌┘1L││\n",
      "│0L┌┘││0L┌┘│\n",
      "└┐└┐└┘┌┘┌┘\n",
      "0D│1D│3R╂│╂│╂\n",
      "┌┘╂└─┐└┐└┐\n",
      "└────┘╂└─┘\n"
     ]
    }
   ],
   "source": [
    "with open('data/yajirin.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    M, rw, rh, rw1, rh1, r2, r4 = nw * nh, range(nw), range(nh), range(nw + 1), range(nh + 1), range(2), range(4)\n",
    "    hh = [s.strip().split(',') for s in fp.readlines()]\n",
    "m = LpProblem()\n",
    "vh = [[[addbinvar() for k in r2] for j in rh] for i in rw1] # 0:L, 1:R\n",
    "vv = [[[addbinvar() for k in r2] for j in rh1] for i in rw] # 0:U, 1:D\n",
    "vhs = [[addvar() for j in rh] for i in rw1]\n",
    "vvs = [[addvar() for j in rh1] for i in rw]\n",
    "vr = [[addvar() for j in rh] for i in rw]\n",
    "vb = [[addbinvar() for j in rh] for i in rw]\n",
    "vd = [[addvar() for j in rh] for i in rw]\n",
    "dic = {}\n",
    "for h in hh:\n",
    "    x, y, n, d = int(h[0]), int(h[1]), int(h[2]), 'LURD'.index(h[3])\n",
    "    dx, dy = [-1, 0, 1, 0][d], [0, -1, 0, 1][d]\n",
    "    m += vr[x][y] == 0\n",
    "    m += vb[x][y] == 0\n",
    "    m += lpSum(vb[x + dx * i][y + dy * i] for i in range(1, max(nw, nh)) \\\n",
    "        if 0 <= x + dx * i < nw and 0 <= y + dy * i < nh) == n\n",
    "    dic[(x, y)] = '%d%c' % (n, h[3])\n",
    "    if n == 0: px, py = x + dx, y + dy\n",
    "for i in rw:\n",
    "    m += vvs[i][0] == 0\n",
    "    m += vvs[i][nh] == 0\n",
    "for j in rh1:\n",
    "    for i in rw:\n",
    "        m += lpSum(vv[i][j]) == vvs[i][j]\n",
    "        m += vvs[i][j] <= 1\n",
    "    if j == nh: break\n",
    "    m += vhs[0][j] == 0\n",
    "    m += vhs[nw][j] == 0\n",
    "    for i in rw1:\n",
    "        m += lpSum(vh[i][j]) == vhs[i][j]\n",
    "        m += vhs[i][j] <= 1\n",
    "    for i in rw:\n",
    "        m += lpDot([-1, 1, 1, -1], [vh[i + k][j][l] for k in r2 for l in r2]) \\\n",
    "          == lpDot([1, -1, -1, 1], [vv[i][j + k][l] for k in r2 for l in r2])\n",
    "        l = [vvs[i][j], vhs[i][j], vvs[i][j + 1], vhs[i + 1][j]]\n",
    "        m += lpDot([2**k for k in r4], l) == vr[i][j]\n",
    "        m += lpSum(l) <= 2\n",
    "        if (i, j) not in dic:\n",
    "            m += vr[i][j] + vb[i][j] >= 1\n",
    "            m += vr[i][j] <= 12 * (1 - vb[i][j])\n",
    "        m += vd[i][j] <= M\n",
    "        if i > 0:\n",
    "            m += vb[i - 1][j] + vb[i][j] <= 1\n",
    "            if (i - 1, j) != (px, py):\n",
    "                m += vd[i - 1][j] + M * (1 - vh[i][j][0]) >= vd[i][j] + 1\n",
    "            if (i, j) != (px, py):\n",
    "                m += vd[i][j] + M * (1 - vh[i][j][1]) >= vd[i - 1][j] + 1\n",
    "        if j > 0:\n",
    "            m += vb[i][j - 1] + vb[i][j] <= 1\n",
    "            if (i, j - 1) != (px, py):\n",
    "                m += vd[i][j - 1] + M * (1 - vv[i][j][0]) >= vd[i][j] + 1\n",
    "            if (i, j) != (px, py):\n",
    "                m += vd[i][j] + M * (1 - vv[i][j][1]) >= vd[i][j - 1] + 1\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        if (i, j) in dic: sys.stdout.write(dic[(i, j)])\n",
    "        elif value(vb[i][j]) > 0.5: sys.stdout.write(u'╂')\n",
    "        else: sys.stdout.write(u'　12┘4│┐78└─1┌34┼'[int(value(vr[i][j]))])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/nurikabe.png'/></div>\n",
    "## <div id='nurikabe' />ぬりかべの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/nurikabe.txt)\n",
    "### 問題\n",
    "* 盤面のいくつかのマスを黒くぬります\n",
    "* 数字は、黒マスによって分断されたシマのマスの数を表します\n",
    "* すべてのシマに数字がちょうど１つずつ入ります\n",
    "* 数字が入っているマスを黒くぬってはいけません\n",
    "* すべての黒マスはタテヨコにひとつながりになります\n",
    "* 黒マスを２×２以上のカタマリにしてはいけません\n",
    "\n",
    "### 考え方\n",
    "* 高速に解くために黒マスの数を最大化します\n",
    "\n",
    "### 変数\n",
    "* vb：0:white, 1:black (1)\n",
    "* 島ごとに可能な候補を作ります\n",
    "  * vt (2)\n",
    "\n",
    "### 制約\n",
    "* 黒マスを２×２以上のカタマリ禁止 (3)\n",
    "* 候補から1つ選びます (4)\n",
    "* 候補を選んだらそのマスは白マスで周りは黒マス (5)\n",
    "* 黒マスが連結していること (6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 21 ms\n",
      "# 3 . . # 1 # \n",
      "# # # # # # # \n",
      "2 . # 1 # . . \n",
      "# # # # # # . \n",
      "# 1 # . 2 # . \n",
      "# # 2 # # # . \n",
      "1 # . # 1 # 6 \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "with open('data/nurikabe.txt') as fp:\n",
    "    nw, nh = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, r2 = range(nw), range(nh), range(2)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "m = LpProblem('', LpMaximize)\n",
    "vb = [[addbinvar() for j in rh] for i in rw] # 0:white, 1:black (1)\n",
    "m += lpSum(v for vv in vb for v in vv) # onj func\n",
    "def dirs(i, j):\n",
    "    return [(i + x - y, j + x + y - 1) for x in r2 for y in r2 \\\n",
    "        if 0 <= i + x - y < nw and 0 <= j + x + y - 1 < nh]\n",
    "def make(lst, i, j, n, w):\n",
    "    if len(w) == n:\n",
    "        lst.append(w)\n",
    "        return\n",
    "    for a, b in dirs(i, j):\n",
    "        if (a, b) not in w and all([(c, d) == w[0] or ch[d][c] == '.' for c, d in dirs(a, b)]):\n",
    "            make(lst, a, b, n, w + [(a, b)])\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        if i < nw - 1 and j < nh - 1:\n",
    "            m += lpSum(vb[i + k][j + l] for k in r2 for l in r2) <= 3 # (3)\n",
    "        if ch[j][i] == '.': continue\n",
    "        lst = []\n",
    "        make(lst, i, j, int(ch[j][i]), [(i, j)])\n",
    "        lst = [u[0] for u in itertools.groupby(lst)]\n",
    "        vt = [addbinvar() for w in lst] # (2)\n",
    "        m += lpSum(vt) == 1 # (4)\n",
    "        for k, w in enumerate(lst):\n",
    "            bd = [(c, d) for a, b in w for c, d in dirs(a, b) if (c, d) not in w]\n",
    "            bd = list(set(bd))\n",
    "            m += lpSum(vb[x][y] for x, y in w) + len(bd) - lpSum(vb[x][y] for x, y in bd) <= \\\n",
    "                (len(w) + len(bd)) * (1 - vt[k]) # (5)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if unionfind.isconnected([[value(vb[i][j]) > 0.5 for j in rh] for i in rw]): break\n",
    "    m += lpSum(vb[i][j] for i in rw for j in rh if value(vb[i][j]) < 0.5) >= 1 # (6)\n",
    "for j in rh:\n",
    "    for i in rw: print(ch[j][i] if ch[j][i] != '.' else '.' if value(vb[i][j]) < 0.5 else '#', end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/hotaru.png'/></div>\n",
    "## <div id='hotaru' />ホタルビームの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/hotaru.txt)\n",
    "### 問題\n",
    "* 全ての白丸の黒点から点線上に線をのばして白丸の黒点でないところにつなげます\n",
    "* どの線も白丸以外のところで、途切れたり交差したり枝分かれしたりしてはいけません\n",
    "* 線で全体がひとつながりにならなければいけません\n",
    "* 数字は、その白丸の黒点から出る線が白丸につながるまでに曲がる回数を表します\n",
    "\n",
    "### 変数\n",
    "* 省略\n",
    "\n",
    "### 制約\n",
    "* 省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 15.6 ms\n",
      "Wall time: 31.2 ms\n",
      "0 -   -   - 2     - 3\n",
      "            |   |    \n",
      "      -   -       -  \n",
      "    |               |\n",
      "  - ? -   -       - 4\n",
      "|   |       |   |    \n",
      "      -   - 1     -  \n",
      "|                   |\n",
      "1 -   -   - 0 -      \n",
      "                |   |\n",
      "                ? -  \n"
     ]
    }
   ],
   "source": [
    "from unionfind import *\n",
    "L = 9 # limit length from '?'\n",
    "with open('data/hotaru.txt') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().split(',')]\n",
    "    rw, rh, rw1, rh1, rn, r4 = range(nw), range(nh), range(nw - 1), range(nh - 1), range(nn), range(4)\n",
    "    hh = [fp.readline().strip().split(',') for k in rn] # x, y, turn, dir\n",
    "bh = [[(-1, 0) for j in rh] for i in rw] # (id, dir) of hint\n",
    "for k, h in enumerate(hh):\n",
    "    hh[k] = hc = [int(h[0]), int(h[1]), -2 if h[2] == '?' else int(h[2]), 'LTRB'.index(h[3])]\n",
    "    bh[hc[0]][hc[1]] = (k, hc[3])\n",
    "m = LpProblem()\n",
    "cc = [[[LpAffineExpression() for j in rh] for i in rw], # check node overlap \\\n",
    "      [[LpAffineExpression() for j in rh] for i in rw1], # check h_line overlap \\\n",
    "      [[LpAffineExpression() for j in rh1] for i in rw]] # check v_line overlap\n",
    "vas = []\n",
    "def make(cands, x, y, n, d, p0, q0):\n",
    "    dx, dy = [-1, 0, 1, 0][d], [0, -1, 0, 1][d]\n",
    "    nx, ny = x + dx, y + dy\n",
    "    if n == -1 or (nx, ny) in p0 or not (0 <= nx < nw and 0 <= ny < nh) or len(p0) > L: return\n",
    "    p, q = p0 + [(nx, ny)], q0 + [(0, nx, ny), (1, nx, ny), (0, x, y), (1, x, y)][d:d + 1]\n",
    "    if bh[nx][ny][0] >= 0:\n",
    "        if n <= 0 and d != (bh[nx][ny][1] + 2) % 4:\n",
    "            cands.append((p, q))\n",
    "        return\n",
    "    for k in r4: make(cands, nx, ny, n if d == k else n - 1, k, p, q)\n",
    "for h in hh:\n",
    "    cands = []\n",
    "    make(cands, h[0], h[1], h[2], h[3], [(h[0], h[1])], [])\n",
    "    vv = [addbinvar() for cand in cands]\n",
    "    m += lpSum(vv) == 1\n",
    "    for i in range(len(cands)):\n",
    "        vas.append((vv[i], cands[i]))\n",
    "        for j, (w, x, y) in enumerate(cands[i][1]):\n",
    "                cc[0][cands[i][0][j][0]][cands[i][0][j][1]] += vv[i]\n",
    "                cc[w + 1][x][y] += vv[i]\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += cc[0][i][j] <= 1\n",
    "        if i < nw - 1: m += cc[1][i][j] <= 1\n",
    "        if j < nh - 1: m += cc[2][i][j] <= 1\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    u = unionfind(nn)\n",
    "    l = []\n",
    "    for va, cand in vas:\n",
    "        if value(va) > 0.5:\n",
    "            l.append(va)\n",
    "            (x1, y1), (x2, y2) = cand[0][0], cand[0][-1]\n",
    "            u.unite(bh[x1][y1][0], bh[x2][y2][0])\n",
    "    if all([u.issame(0, k) for k in rn]): break\n",
    "    m += lpSum(l) <= len(l) - 1\n",
    "bd = [[' '] * (2 * nw - 1) for j in range(2 * nh - 1)]\n",
    "for h in hh: bd[h[1] * 2][h[0] * 2] = '?' if h[2] < 0 else str(h[2])\n",
    "for va, cand in vas:\n",
    "    if value(va) > 0.5:\n",
    "        for w, x, y in cand[1]: bd[2 * y + w][2 * x + 1 - w] = '-|'[w]\n",
    "for b in bd: print(' '.join(b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/stainedglass.png'/></div>\n",
    "## <div id='stainedglass' />ステンドグラスの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/stainedglass.txt)\n",
    "### 問題\n",
    "* 線で区切られた部分（ピース）のいくつかを黒くぬります\n",
    "* 小さな丸は、その丸が接している周囲のピースのうち、黒ピースと白ピースのどちらの数が多いかを表します\n",
    "* 黒丸なら黒ピースの方が多く、白丸なら白ピースの方が多く、灰色の丸は、同数となります\n",
    "\n",
    "### 変数\n",
    "* v：パネルごとに黒く塗るかどうか (1)\n",
    "\n",
    "### 制約\n",
    "* 白丸、黒丸、灰色丸ごとに設定 (2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 0 ns\n",
      "1 4 5 6 8 \n"
     ]
    }
   ],
   "source": [
    "with open('data/stainedglass.txt') as fp:\n",
    "    nn, np = [int(s) for s in fp.readline().split(',')]\n",
    "    rn, rp, r2 = range(nn), range(np), range(2)\n",
    "    hh = [fp.readline().split(',') for i in rn]\n",
    "m = LpProblem()\n",
    "v = [addbinvar() for j in rp] # (1)\n",
    "for i in rn:\n",
    "    l = [v[int(s)] for s in hh[i][1:]]\n",
    "    if hh[i][0] == 'W':\n",
    "        m += lpSum(l) <= (len(l) - 1) // 2 # (2)\n",
    "    elif hh[i][0] == 'B':\n",
    "        m += lpSum(l) >= (len(l) + 2) // 2 # (2)\n",
    "    else:\n",
    "        m += lpSum(l) == len(l) // 2 # (2)\n",
    "%time m.solve()\n",
    "for j in rp:\n",
    "    if value(v[j]) > 0.5: print(j, end=' ')\n",
    "print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/satogaeri.png'/></div>\n",
    "## <div id='satogaeri' />さとがえりの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/satogaeri.txt)\n",
    "### 問題\n",
    "* ○をタテヨコいずれかにまっすぐ移動し、すべての○が、太線で区切られたところ（国）１つにつき１つずつ入るようにします\n",
    "* ○の中の数字は、移動するマス数を表します\n",
    "* 数字のない○は何マス移動するか不明（移動しないこともあります）\n",
    "* ○が移動した跡や、他の○のあるところには○を移動できません\n",
    "\n",
    "### 変数\n",
    "* 省略\n",
    "\n",
    "### 制約\n",
    "* 省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 17.6 ms\n",
      "a|aaa*--*-\n",
      " a*--*bff**\n",
      " ghehij|*f|\n",
      " -*hh-**jf|\n",
      " *i*--klj*m\n",
      " |**--rr*|*\n",
      " ---**ru|*|\n",
      " *too|ru*||\n",
      " |--*xyw|||\n",
      " |*--**-|||\n",
      " "
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "with open('data/satogaeri.txt') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().split(',')]\n",
    "    mx, rw, rh, rn, r2 = max(nw, nh) + 1, range(nw), range(nh), range(nn), range(2)\n",
    "    ch = [[c for c in fp.readline()] for j in rh]\n",
    "    hh = [list(map(int, fp.readline().split(','))) for k in rn]\n",
    "dic = defaultdict(list)\n",
    "for i in rw:\n",
    "    for j in rh: dic[ch[j][i]].append((i, j))\n",
    "for x, y, n in hh: ch[y][x] = '*'\n",
    "def chk(xy): return 0 <= xy[0] < nw and 0 <= xy[1] < nh and ch[xy[1]][xy[0]] != '*'\n",
    "m = LpProblem()\n",
    "vls = []\n",
    "vo = [[[] for j in rh] for i in rw]\n",
    "cc = [[LpAffineExpression() for j in rh] for i in rw]\n",
    "for x, y, n in hh:\n",
    "    cands = []\n",
    "    if n == 0: cands.append([(x, y)])\n",
    "    for p in r2:\n",
    "        for q in r2:\n",
    "            dx, dy = p - q, p + q - 1\n",
    "            l = list(itertools.takewhile(chk, [(x + dx * k, y + dy * k) \\\n",
    "                for k in range(1, 1 + n if n >= 0 else mx)]))\n",
    "            if len(l) > 0 and (n < 0 or len(l) == n):\n",
    "                for k in range(0 if n < 0 else len(l) - 1, len(l)):\n",
    "                    cands.append([(x, y)] + l[:k + 1])\n",
    "    v = [addbinvar() for cand in cands]\n",
    "    m += lpSum(v) == 1\n",
    "    for k, cand in enumerate(cands):\n",
    "        vls.append((v[k], cand))\n",
    "        for i, j in cand: cc[i][j] += v[k]\n",
    "        vo[cand[-1][0]][cand[-1][1]].append(v[k])\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        m += cc[i][j] <= 1\n",
    "for c, lst in dic.items():\n",
    "    m += lpSum(lpSum(vo[i][j]) for i, j in lst) == 1\n",
    "%time m.solve()\n",
    "for vl, cand in vls:\n",
    "    if value(vl) > 0.5:\n",
    "        d = 1 if cand[0][0] == cand[-1][0] else 0\n",
    "        for i, j in cand[:-1]: ch[j][i] = '-|'[d]\n",
    "        ch[cand[-1][1]][cand[-1][0]] = '*'\n",
    "for s in ch: print(''.join(s), end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style='float: right'><img src='https://dl.dropboxusercontent.com/u/35689878/pic/skeleton.png'/></div>\n",
    "## <div id='skeleton' />スケルトンの解き方\n",
    "[データ](https://dl.dropboxusercontent.com/u/35689878/data/skeleton.txt)\n",
    "### 問題\n",
    "* リストの言葉を全て、盤面にちょうど１つ入れます\n",
    "* <a href='#nskeleton'>参考</a>\n",
    "\n",
    "### 変数\n",
    "* 省略\n",
    "\n",
    "### 制約\n",
    "* 省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wall time: 28.6 ms\n",
      "   チ    サ ツ キ    \n",
      "   ュ    ク    キ    \n",
      "ガ ー ベ ラ    ョ    \n",
      "   リ          ウ メ \n",
      "   ツ バ キ          \n",
      "   プ    ク チ ナ シ \n"
     ]
    }
   ],
   "source": [
    "import codecs\n",
    "with codecs.open('data/skeleton.txt', 'r', 'utf-8') as fp:\n",
    "    nw, nh, nn = [int(s) for s in fp.readline().strip(u'\\ufeff').split(',')]\n",
    "    rw, rh, rn, r4 = range(nw), range(nh), range(nn), range(4)\n",
    "    ch = [fp.readline() for j in rh]\n",
    "    wds = [fp.readline().strip() for i in rn]\n",
    "m = LpProblem()\n",
    "vo = [[addvar() for j in rh] for i in rw]\n",
    "dic, dic2, dic3 = {}, {}, {}\n",
    "for wd in wds:\n",
    "    for c in wd:\n",
    "        if c not in dic: dic[c], dic2[len(dic2)] = len(dic2), c\n",
    "    l = dic3.setdefault(len(wd), ([], []))\n",
    "    l[0].append(wd)\n",
    "M = len(dic) + 1\n",
    "def chk(xy): return 0 <= xy[0] < nw and 0 <= xy[1] < nh and ch[xy[1]][xy[0]] != '.'\n",
    "for i in rw:\n",
    "    for j in rh:\n",
    "        if i == 0 or ch[j][i - 1] == '.':\n",
    "            sp = list(itertools.takewhile(chk, [(i + k, j) for k in rw]))\n",
    "            if len(sp) > 1: dic3[len(sp)][1].append(sp)\n",
    "        if j == 0 or ch[j - 1][i] == '.':\n",
    "            sp = list(itertools.takewhile(chk, [(i, j + k) for k in rw]))\n",
    "            if len(sp) > 1: dic3[len(sp)][1].append(sp)\n",
    "for nl, (wl, pl) in dic3.items():\n",
    "    nc = len(wl)\n",
    "    vb = [[addbinvar() for j in range(nc)] for i in range(nc)]\n",
    "    for i in range(nc):\n",
    "        m += lpSum(vb[i]) == 1\n",
    "        m += lpSum(vb[k][i] for k in range(nc)) == 1\n",
    "        for j in range(nc):\n",
    "            wd = wl[j]\n",
    "            for k in range(nl):\n",
    "                (x, y), a = pl[i][k], dic[wd[k]]\n",
    "                m += vo[x][y] <= a + M * (1 - vb[i][j])\n",
    "                m += vo[x][y] >= a - M * (1 - vb[i][j])\n",
    "%time m.solve()\n",
    "for j in rh:\n",
    "    for i in rw:\n",
    "        print('  ' if ch[j][i] == '.' else dic2[int(value(vo[i][j]))], end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <div id='list' />数理最適化で解ける様々なパズル\n",
    "\n",
    "<a href='#kakkuro'>カックロ</a>|<a href='#nonogram'>ののぐらむ</a>|<a href='#museum'>美術館</a>|<a href='#numberlink'>ナンバーリンク</a>|<a href='#fukumen'>覆面算</a>\n",
    "-|-|-|-|-\n",
    "<a href='#inequality'>不等式</a>|<a href='#building'>ビルディングパズル</a>|<a href='#wall'>ウォールロジック</a>|<a href='#ripple'>波及効果</a>|<a href='#nskeleton'>ナンバースケルトン</a>\n",
    "<a href='#slither'>スリザーリンク</a>|<a href='#square'>四角に切れ</a>|<a href='#mashu'>ましゅ</a>|<a href='#bridge'>橋をかけろ</a>|<a href='#norinori'>のりのり</a>\n",
    "<a href='#block'>ブロックパズル</a>|<a href='#tile'>タイルペイント</a>|<a href='#inshi'>因子の部屋</a>|<a href='#kurodoko'>黒どこ</a>|<a href='#suiri'>推理パズル</a>\n",
    "<a href='#hitori'>ひとりにしてくれ</a>|<a href='#heyawake'>へやわけ</a>|<a href='#paint'>ペイントエリア</a>|<a href='#suukoro'>数コロ</a>|<a href='#pipelink'>パイプリンク</a>\n",
    "<a href='#kuriku'>クリーク</a>|<a href='#eisbahn'>アイスバーン</a>|<a href='#sumline'>サムライン</a>|<a href='#countryroad'>カントリーロード</a>|<a href='#kanaore'>カナオレ</a>\n",
    "<a href='#fillmat'>フィルマット</a>|<a href='#shakashaka'>シャカシャカ</a>|<a href='#yajirin'>ヤジリン</a>|<a href='#nurikabe'>ぬりかべ</a>|<a href='#hotaru'>ホタルビーム</a>\n",
    "<a href='#stainedglass'>ステンドグラス</a>|<a href='#satogaeri'>さとがえり</a>|<a href='#skeleton'>スケルトン</a>|<a href='#sudoku'>数独</a>|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <div id='conc' />まとめ\n",
    "\n",
    "* 数理モデルをPython上で作成し、解くことができます\n",
    "* Pythonによる数理モデルは簡潔でわかりやすく、様々な問題を記述できます\n",
    "* 汎用ソルバでも、多くの問題を扱えますが、規模が大きい問題では、専用のソルバを用い、近似解法を用いた方がよいこともあります\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}

http://nbviewer.ipython.org/gist/Tsutomu-KKE/1b526ed7ef2ab111c829