sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from collections import defaultdict, namedtuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://arxiv.org/pdf/cs/0011047.pdf\n",
    "# https://medium.com/optima-blog/solving-sudoku-fast-702912c13307"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [[0, 0, 1, 0, 1, 1, 0],\n",
    "     [1, 0, 0, 1, 0, 0, 1],\n",
    "     [0, 1, 1, 0, 0, 1, 0],\n",
    "     [1, 0, 0, 1, 0, 0, 0],\n",
    "     [0, 1, 0, 0, 0, 0, 1],\n",
    "     [0, 0, 0, 1, 1, 0, 1]]\n",
    "A = np.array(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sudoku = np.array([[0, 0, 0, 0, 0, 4, 0, 9, 0],\n",
    "#                    [8, 0, 2, 9, 7, 0, 0, 0, 0],\n",
    "#                    [9, 0, 1, 2, 0, 0, 3, 0, 0],\n",
    "#                    [0, 0, 0, 0, 4, 9, 1, 5, 7],\n",
    "#                    [0, 1, 3, 0, 5, 0, 9, 2, 0],\n",
    "#                    [5, 7, 9, 1, 2, 0, 0, 0, 0],\n",
    "#                    [0, 0, 7, 0, 0, 2, 6, 0, 3],\n",
    "#                    [0, 0, 0, 0, 3, 8, 2, 0, 5],\n",
    "#                    [0, 2, 0, 5, 0, 0, 0, 0, 0]])\n",
    "# sudoku = np.array([[7, 3, 5, 6, 1, 4, 8, 9, 2],\n",
    "#                    [8, 4, 2, 9, 7, 3, 5, 6, 1],\n",
    "#                    [9, 6, 1, 2, 8, 5, 3, 7, 4],\n",
    "#                    [2, 8, 6, 3, 4, 9, 1, 5, 7],\n",
    "#                    [4, 1, 3, 8, 5, 7, 9, 2, 6],\n",
    "#                    [5, 7, 9, 1, 2, 6, 4, 3, 8],\n",
    "#                    [1, 5, 7, 4, 9, 2, 6, 8, 3],\n",
    "#                    [6, 9, 4, 7, 3, 8, 2, 1, 5],\n",
    "#                    [3, 2, 8, 5, 6, 1, 7, 4, 9]])\n",
    "# sudoku = [[0, 6, 0, 3, 0, 0, 8, 0, 4],\n",
    "#           [5, 3, 7, 0, 9, 0, 0, 0, 0],\n",
    "#           [0, 4, 0, 0, 0, 6, 3, 0, 7],\n",
    "#           [0, 9, 0, 0, 5, 1, 2, 3, 8],\n",
    "#           [0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "#           [7, 1, 3, 6, 2, 0, 0, 4, 0],\n",
    "#           [3, 0, 6, 4, 0, 0, 0, 1, 0],\n",
    "#           [0, 0, 0, 0, 6, 0, 5, 2, 3],\n",
    "#           [1, 0, 2, 0, 0, 9, 0, 8, 0]]\n",
    "# sudoku = np.array(sudoku)\n",
    "\n",
    "# sudoku = [[0, 0, 0, 0, 0, 0, 0, 1, 2],\n",
    "#           [0, 0, 0, 0, 0, 0, 0, 0, 3],\n",
    "#           [0, 0, 2, 3, 0, 0, 4, 0, 0],\n",
    "#           [0, 0, 1, 8, 0, 0, 0, 0, 5],\n",
    "#           [0, 6, 0, 0, 7, 0, 8, 0, 0],\n",
    "#           [0, 0, 0, 0, 0, 9, 0, 0, 0],\n",
    "#           [0, 0, 8, 5, 0, 0, 0, 0, 0],\n",
    "#           [9, 0, 0, 0, 4, 0, 5, 0, 0],\n",
    "#           [4, 7, 0, 0, 0, 6, 0, 0, 0]]\n",
    "# sudoku = np.array(sudoku)\n",
    "\n",
    "# World hardest sudoku.\n",
    "sudoku = [[8, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "          [0, 0, 3, 6, 0, 0, 0, 0, 0],\n",
    "          [0, 7, 0, 0, 9, 0, 2, 0, 0],\n",
    "          [0, 5, 0, 0, 0, 7, 0, 0, 0],\n",
    "          [0, 0, 0, 0, 4, 5, 7, 0, 0],\n",
    "          [0, 0, 0, 1, 0, 0, 0, 3, 0],\n",
    "          [0, 0, 1, 0, 0, 0, 0, 6, 8],\n",
    "          [0, 0, 8, 5, 0, 0, 0, 1, 0],\n",
    "          [0, 9, 0, 0, 0, 0, 4, 0, 0]]\n",
    "sudoku = np.array(sudoku)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %%writefile dlx.py\n",
    "# Data object, x.\n",
    "class X:\n",
    "    def __init__(self, column=None, row=None):\n",
    "        self.up = self.down = self.right = self.left = self\n",
    "        \n",
    "        # Points to the column object at the head of the relevant column.\n",
    "        self.column = column\n",
    "        self.row = row\n",
    "\n",
    "    def __str__(self):\n",
    "        return f'{self.column.name}:{self.row}'\n",
    "\n",
    "# Column object, y.\n",
    "class Y(X):\n",
    "    def __init__(self, row=None, name='', size=0):\n",
    "        self.size = size # The number of 1s in the column.\n",
    "        self.name = name # Symbolic identifier for printing the answers.\n",
    "        \n",
    "        X.__init__(self, self, row)\n",
    "\n",
    "class DLX:\n",
    "    @staticmethod\n",
    "    def solve(A):\n",
    "        torodial = DLX.init_toroidal(A)\n",
    "        return DLX.search(torodial)\n",
    "\n",
    "    @staticmethod\n",
    "    def init_column_labels(A):\n",
    "        rows, cols = A.shape\n",
    "        \n",
    "        # Use a human-readable label.\n",
    "        labels = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')\n",
    "\n",
    "        # In case we have a lot of columns...\n",
    "        if cols >= len(labels):\n",
    "            labels = list(map(str, range(cols)))\n",
    "\n",
    "        return labels\n",
    "    \n",
    "    @staticmethod\n",
    "    def init_column_header(A):\n",
    "        _, cols = A.shape\n",
    "        labels = DLX.init_column_labels(A)\n",
    "            \n",
    "        # The root header links all the column headers.\n",
    "        root = Y(name='root', \n",
    "                 size=float('inf'))\n",
    "        \n",
    "        # The column headers is a circular linkedlist.\n",
    "        curr = root\n",
    "        for col in range(cols):\n",
    "            curr.right = Y(name=labels[col])\n",
    "            curr.right.left = curr\n",
    "            curr = curr.right\n",
    "\n",
    "        # Linking the rightmost column label to the root\n",
    "        # to make it circular.\n",
    "        curr.right = root\n",
    "        curr.right.left = curr\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    @staticmethod\n",
    "    def header_pointer(root):\n",
    "        # Simple pointer to help us find the column at constant time.\n",
    "        header = {}\n",
    "        curr = root.right\n",
    "        while curr != root:\n",
    "            header[curr.name] = curr\n",
    "            curr = curr.right\n",
    "        return header\n",
    "    \n",
    "    @staticmethod\n",
    "    def smallest_column_object(root):\n",
    "        '''\n",
    "        Attempt to select the column object with the smallest size.\n",
    "        '''\n",
    "        curr = root.column.right\n",
    "        c = root\n",
    "        while curr != root:\n",
    "            if curr.size < c.size:\n",
    "                c = curr\n",
    "            curr = curr.right\n",
    "        return c\n",
    "\n",
    "    @staticmethod\n",
    "    def init_toroidal(A):\n",
    "        labels = DLX.init_column_labels(A)\n",
    "        root = DLX.init_column_header(A)\n",
    "        header = DLX.header_pointer(root)\n",
    "        \n",
    "        for i, row in enumerate(A):\n",
    "            prev = None\n",
    "            left = None\n",
    "            for j, col in enumerate(row):\n",
    "                if col != 1: continue\n",
    "\n",
    "                head = header[labels[j]]\n",
    "                head.size += 1\n",
    "\n",
    "                curr = head.up\n",
    "                curr.down = X(column=head,\n",
    "                              row=i)\n",
    "                curr.down.up = curr\n",
    "\n",
    "                curr = curr.down\n",
    "                curr.down = curr.column\n",
    "                curr.down.up = curr\n",
    "\n",
    "                if prev is None:\n",
    "                    prev = curr\n",
    "                    prev.right = curr\n",
    "                    prev.right.left = prev\n",
    "                    left = curr\n",
    "                else:\n",
    "                    prev.right = curr\n",
    "                    prev.right.left = prev\n",
    "                    prev = curr\n",
    "\n",
    "            # Happens when the column does not have any 1s.\n",
    "            if prev is not None:\n",
    "                prev.right = left\n",
    "                prev.right.left = prev\n",
    "        return root\n",
    "    \n",
    "    @staticmethod\n",
    "    def cover(col):\n",
    "        col = col.column\n",
    "        col.right.left = col.left\n",
    "        col.left.right = col.right\n",
    "        i = col.down\n",
    "        while i != col:\n",
    "            j = i.right\n",
    "            while j != i:\n",
    "                j.up.down = j.down\n",
    "                j.down.up = j.up\n",
    "                j.column.size -= 1    \n",
    "                j = j.right\n",
    "            i = i.down\n",
    "    \n",
    "    @staticmethod\n",
    "    def uncover(col):\n",
    "        col = col.column\n",
    "        i = col.up\n",
    "        while i != col:\n",
    "            j = i.left\n",
    "            while j != i:\n",
    "                j.column.size += 1\n",
    "                j.up.down = j\n",
    "                j.down.up = j\n",
    "                j = j.left\n",
    "            i = i.up\n",
    "        col.right.left = col\n",
    "        col.left.right = col\n",
    "    \n",
    "    @staticmethod\n",
    "    def search(root, k=0, solution=None):\n",
    "        if solution is None:\n",
    "            solution = []\n",
    "        if root.right == root:\n",
    "            return solution[:]\n",
    "\n",
    "        col = DLX.smallest_column_object(root)\n",
    "        DLX.cover(col)\n",
    "\n",
    "        r = col.down\n",
    "        while r != col:\n",
    "            o_k = r\n",
    "            solution.append(o_k.row)\n",
    "\n",
    "            j = r.right\n",
    "            while j != r:\n",
    "                DLX.cover(j)\n",
    "                j = j.right\n",
    "\n",
    "            result = DLX.search(root, k+1, solution)\n",
    "            if result: return result\n",
    "            solution.remove(o_k.row)\n",
    "\n",
    "            r = o_k\n",
    "            col = r.column\n",
    "\n",
    "            j = r.left\n",
    "            while j != r:\n",
    "                DLX.uncover(j)\n",
    "                j = j.left\n",
    "            r = r.down\n",
    "        DLX.uncover(col)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 0, 4]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = DLX.solve(A)\n",
    "result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 1, 1, 1, 1, 1, 1])"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A[result, :].sum(axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %%writefile sudoku.py\n",
    "\n",
    "import numpy as np\n",
    "from collections import defaultdict, namedtuple\n",
    "from dlx import DLX\n",
    "\n",
    "Metadata = namedtuple('Metadata', 'row col val')\n",
    "\n",
    "class SudokuSolver:\n",
    "    @staticmethod\n",
    "    def constraint_index(row, col, val):\n",
    "        '''\n",
    "        Returns the index of the unique constraint in a 9x9 row.\n",
    "        For all four constraints below, we will construct a 4x9x9\n",
    "        row and mark the index.\n",
    "        '''\n",
    "        r = row // 3 * 3 # Gives the current grid row.\n",
    "        c = col // 3     # Gives the current grid col.\n",
    "        grid = r + c     # The grid number from top to bottom, left to right.\n",
    "        # Grid:\n",
    "        # 012\n",
    "        # 345\n",
    "        # 678\n",
    "        return (row * 9 + col,         # Each cell can only have one number.\n",
    "                row * 9 + val - 1,     # For each row, a number can only appear once.\n",
    "                col * 9 + val - 1,     # For each column, a number can only appear once.\n",
    "                grid * 9 + val - 1)    # For each region, a number can only appear once.\n",
    "\n",
    "    @staticmethod\n",
    "    def parse(sudoku):\n",
    "        '''\n",
    "        Build the constraint matrix for all the existing values in the sudoku board,\n",
    "        as well as the ones that we have not seen yet. Dancing links will try\n",
    "        to find all the possible combinations.\n",
    "        '''\n",
    "\n",
    "        # The actual size of the result is 9 * 9 * 9 for every combination of numbers in each row, col and grid.\n",
    "        # If we have a partial solution (filled numbers in the sudoku), we can eliminate most of them.\n",
    "        result, metadata = [], []\n",
    "        for row in range(0, 9):\n",
    "            for col in range(0, 9):\n",
    "                val = sudoku[row, col]\n",
    "                if val == 0:\n",
    "                    # The cell is empty. We need to fill it with all the values that are not inside yet.\n",
    "                    # To do so, find the values that are not in the current row yet.\n",
    "                    # ! Numbers must be in range 1-9, not index 0.\n",
    "                    values = [i for i in range(1, 10) \n",
    "                              if i not in sudoku[row]]\n",
    "                else:\n",
    "                    values = [val]\n",
    "                for val in values:\n",
    "                    cell_c, row_c, col_c, grid_c = SudokuSolver.constraint_index(row, col, val)\n",
    "                    mat = np.zeros(4*9*9) # Each constraints have 81 indices.\n",
    "                    mat[cell_c + 0 * 81] = 1\n",
    "                    mat[row_c + 1 * 81] = 1\n",
    "                    mat[col_c + 2 * 81] = 1\n",
    "                    mat[grid_c + 3 * 81] = 1\n",
    "                    result.append(mat)\n",
    "                    metadata.append(Metadata(row=row, col=col, val=val))\n",
    "        return np.array(result), metadata\n",
    "    \n",
    "    def __call__(self, sudoku):\n",
    "        board, metadata = SudokuSolver.parse(sudoku)\n",
    "        result = DLX.solve(board)\n",
    "        if result is None:\n",
    "            return None\n",
    "\n",
    "        # Draw back the solution.\n",
    "        solution = np.zeros((9, 9))\n",
    "        for row in result:\n",
    "            cell = metadata[row]\n",
    "            solution[cell.row, cell.col] = cell.val\n",
    "        return solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8., 1., 2., 7., 5., 3., 6., 4., 9.],\n",
       "       [9., 4., 3., 6., 8., 2., 1., 7., 5.],\n",
       "       [6., 7., 5., 4., 9., 1., 2., 8., 3.],\n",
       "       [1., 5., 4., 2., 3., 7., 8., 9., 6.],\n",
       "       [3., 6., 9., 8., 4., 5., 7., 2., 1.],\n",
       "       [2., 8., 7., 1., 6., 9., 5., 3., 4.],\n",
       "       [5., 2., 1., 9., 7., 4., 3., 6., 8.],\n",
       "       [4., 3., 8., 5., 2., 6., 9., 1., 7.],\n",
       "       [7., 9., 6., 3., 1., 8., 4., 5., 2.]])"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solver = SudokuSolver()\n",
    "solver(sudoku)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}