day 23 - sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sudoku(matrix, n=0):\n",
    "    if n >= 81:\n",
    "        return matrix\n",
    "    if matrix.A1[n]:\n",
    "        return sudoku(matrix, n + 1)\n",
    "\n",
    "    i, j, k, l = n // 9, n % 9, n // 27 * 3, (n % 9) // 3 * 3\n",
    "\n",
    "    # get viable values\n",
    "    x = set(range(1, 10)) - (\n",
    "        set(matrix[i].A1) |\n",
    "        set(matrix.T[j].A1) |\n",
    "        set(matrix[k:k + 3, l:l + 3].A1)\n",
    "    )\n",
    "\n",
    "    # backtracking\n",
    "    for value in x:\n",
    "        matrix[i, j] = value\n",
    "        if sudoku(matrix, n + 1) is not None:\n",
    "            return matrix\n",
    "    else:\n",
    "        matrix[i, j] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[8, 2, 4, 1, 3, 9, 5, 7, 6],\n",
       "        [6, 9, 1, 5, 2, 7, 8, 3, 4],\n",
       "        [5, 7, 3, 6, 4, 8, 2, 1, 9],\n",
       "        [4, 6, 5, 3, 8, 1, 7, 9, 2],\n",
       "        [9, 1, 7, 2, 6, 5, 3, 4, 8],\n",
       "        [2, 3, 8, 9, 7, 4, 1, 6, 5],\n",
       "        [3, 8, 2, 7, 9, 6, 4, 5, 1],\n",
       "        [1, 4, 6, 8, 5, 3, 9, 2, 7],\n",
       "        [7, 5, 9, 4, 1, 2, 6, 8, 3]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku(np.matrix(\"\"\"\n",
    "    8 0 0 1 0 9 0 7 0;\n",
    "    0 9 0 0 0 0 8 0 0;\n",
    "    5 0 3 0 4 0 0 0 0;\n",
    "    0 0 0 0 0 0 7 9 0;\n",
    "    0 0 7 2 6 5 3 0 0;\n",
    "    0 3 8 0 0 0 0 0 0;\n",
    "    0 0 0 0 9 0 4 0 1;\n",
    "    0 0 6 0 0 0 0 2 0;\n",
    "    0 5 0 4 0 2 0 0 3\n",
    "\"\"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[1, 2, 3, 4, 5, 8, 9, 6, 7],\n",
       "        [4, 5, 8, 6, 7, 9, 1, 2, 3],\n",
       "        [9, 6, 7, 1, 2, 3, 8, 4, 5],\n",
       "        [2, 1, 9, 8, 3, 4, 5, 7, 6],\n",
       "        [3, 8, 4, 5, 6, 7, 2, 1, 9],\n",
       "        [5, 7, 6, 9, 1, 2, 3, 8, 4],\n",
       "        [8, 9, 1, 3, 4, 6, 7, 5, 2],\n",
       "        [6, 3, 2, 7, 8, 5, 4, 9, 1],\n",
       "        [7, 4, 5, 2, 9, 1, 6, 3, 8]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sudoku(np.matrix(np.zeros((9, 9), dtype=int)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}