は.橋をかけろ.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/bridge.png'/></div>\n",
    "## <div id='bridge' />橋をかけろ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import product\n",
    "from pulp import *\n",
    "from unionfind import unionfind\n",
    "from ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "data = \"\"\"\\\n",
    ".1.5.3..3\n",
    "....1..2.\n",
    "4..8.2..3\n",
    ".2..2..2.\n",
    "3..2.1..3\n",
    ".6..5..4.\n",
    "3..1.3..1\n",
    ".3..1....\n",
    "3..3.6.4.\"\"\".split()\n",
    "nw, nh = len(data[0]), len(data)\n",
    "r2 = range(2)\n",
    "rhw = list(product(range(nh), range(nw)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\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": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "v = addbinvars(nh, nw, 4) # 0:h1, 1:h2, 2:v1, 3:v2 (1)\n",
    "a = addvars(nh, nw, 2) # 0:h, 1:v (2)\n",
    "def dirs(i, j):\n",
    "    return [a[i + x + y - 1][j + x - y][1 - x ^ y] for y in r2 for x in r2\n",
    "        if 0 <= i + x + y - 1 < nh and 0 <= j + x - y < nw]\n",
    "for i, j in rhw:\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 data[i][j].isdigit():\n",
    "        f = i*nh + j\n",
    "        m += lpSum(dirs(i, j)) == int(data[i][j]) # (4)\n",
    "        for k in range(4):\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 < nh-1 and not data[i+1][j].isdigit():\n",
    "            m += a[i][j][1] == a[i+1][j][1] # (7)\n",
    "        if j < nw-1 and not data[i][j+1].isdigit():\n",
    "            m += a[i][j][0] == a[i][j+1][0] # (7)\n",
    "        if 1 == 0 or 1 == nh-1:\n",
    "            m += a[i][j][1] == 0 # (7)\n",
    "        if j == 0 or j == nw-1:\n",
    "            m += a[i][j][0] == 0 # (7)\n",
    "while True:\n",
    "    %time m.solve()\n",
    "    if m.status == 1:\n",
    "        break\n",
    "    u = unionfind(nh * nw)\n",
    "    e = []\n",
    "    for j in rh:\n",
    "        for i in rw:\n",
    "            if value(a[i][j][0]):\n",
    "                u.unite(i*nh + j, i*nh + j-1)\n",
    "                u.unite(i*nh + j-1, i*nh + j+1)\n",
    "            elif value(a[i][j][1]):\n",
    "                u.unite(i*nh + j, i*nh-nh + j)\n",
    "                u.unite(i*nh-nh + j, i*nh+nh + j)\n",
    "            else:\n",
    "                e.append(lpSum(a[i][j]))\n",
    "    if all([u.issame(f, i*nh + j) for i, j in rhw if data[i][j].isdigit()]):\n",
    "        break\n",
    "    m += lpSum(e) >= 1 # (8)\n",
    "for i in range(nh):\n",
    "    for j in range(nw):\n",
    "        h = int(sum(value(v[i][j][k]) * (3 if k == 2 else 1) for k in range(4)))\n",
    "        print(data[i][j] if data[i][j] != '.' else ' -=|H'[h], end=' ')\n",
    "    print()"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}