ふ.不等式.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_style": "split"
   },
   "source": [
    "<div style='float: right'><img src='pic/inequality.png'/></div>\n",
    "## <div id='inequality' />不等式"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_style": "split",
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from pulp import *\n",
    "from ortoolpy import addvar, addvars, addbinvar, addbinvars\n",
    "data = \"\"\"\\\n",
    ". 1 . 3 .\n",
    "         \n",
    ". 3<. . .\n",
    "         \n",
    ".<. . . 5\n",
    "V   A    \n",
    "2 . . . .\n",
    "    A   A\n",
    ".<.<4<.>.\"\"\".split('\\n')\n",
    "n = (len(data)+1)//2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 問題\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": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "m = LpProblem()\n",
    "v = np.array(addbinvars(n, n, n)) # (1)\n",
    "r = np.array(addvars(n, n)) # (2)\n",
    "for i in range(n):\n",
    "    for j in range(n):\n",
    "        m += lpSum(v[i,j]) == 1 # (3)\n",
    "        m += lpDot(range(n), v[i,j]) + 1 == r[i,j] # (4)\n",
    "        m += lpSum(v[i,:,j]) == 1 # (5)\n",
    "        m += lpSum(v[:,i,j]) == 1 # (5)\n",
    "        c = data[i*2][j*2]\n",
    "        if c.isdigit():\n",
    "            m += v[i,j,int(c)-1] == 1 # (6)\n",
    "for i in range(n - 1):\n",
    "    for j in range(n):\n",
    "        c = data[i*2+1][j*2]\n",
    "        if c == 'A':\n",
    "            m += r[i,j] <= r[i+1,j] - 1 # (7)\n",
    "        elif c == 'V':\n",
    "            m += r[i,j] >= r[i+1,j] + 1 # (7)\n",
    "for i in range(n):\n",
    "    for j in range(n - 1):\n",
    "        c = data[i*2][j*2+1]\n",
    "        if c == '<':\n",
    "            m += r[i,j] <= r[i,j+1] - 1 # (7)\n",
    "        elif c == '>':\n",
    "            m += r[i,j] >= r[i,j+1] + 1 # (7)\n",
    "%time m.solve()\n",
    "np.vectorize(value)(r).astype(int).tolist()"
   ]
  }
 ],
 "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
}