Sudoku Checker

05_17_the_sudoku_checker_problem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 05_17 the_sudoku_checker_problem\n",
    "\n",
    "Check whether a 9 x 9 2D array representing a partially completed sudoku is valid.  Specifically, check that now row, column, or 3 x 3 subarray contains duplicates.  A 0-value in the 2D array indicates that entry is blank.  Every other entry is in [1, 9].\n",
    "\n",
    "*Hint*:  Directly test the constraints.  Use an array to encode sets.\n",
    "\n",
    "### Remarks:  Seems like fun."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Valid\n",
      "False on 8, v: [4, 4, 1, 6, 5, 9]\n",
      "Invalid\n",
      "Valid\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "from collections import defaultdict\n",
    "\n",
    "def get_sets(arr):\n",
    "    # rows = {i: e for i, e in enumerate(arr)}\n",
    "    rows = defaultdict(list)\n",
    "    cols = defaultdict(list)\n",
    "    subs = defaultdict(list)\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        row = arr[i]\n",
    "        x = i // 3\n",
    "        for j in range(len(row)):\n",
    "            y = j // 3\n",
    "            cell = arr[i][j]\n",
    "            rows[i].append(cell)\n",
    "            cols[j].append(cell)\n",
    "            subs[x * 3 + y].append(cell)\n",
    "    return rows, cols, subs\n",
    "\n",
    "def check_set(my_set):\n",
    "    for k, v in my_set.items():\n",
    "        v = [i for i in v if i != 0]\n",
    "        if len(v) != len(set(v)):\n",
    "            print(\"False on {}, v: {}\".format(k, v))\n",
    "            return False \n",
    "    return True\n",
    "        \n",
    "def solution(arr):\n",
    "    rows, cols, subs = get_sets(arr)\n",
    "    if all(map(check_set, [rows, cols, subs])):\n",
    "        print(\"Valid\")\n",
    "    else:\n",
    "        print(\"Invalid\")\n",
    "    \n",
    "    # return check_set(rows) & check_set(cols) & check_set(subs)\n",
    "    # check_set(rows)\n",
    "    # print(check_set(cols))\n",
    "    \n",
    "\n",
    "    \n",
    "    \n",
    "\n",
    "    \n",
    "#test = [ [random.randint(0, 1) for i in range(9)] for j in range(9) ]\n",
    "\n",
    "test = [ # valid partial assignment from Figure 5.2 (a)\n",
    "    [5, 3, 0, 0, 7, 0, 0, 0, 0],\n",
    "    [6, 0, 0, 1, 9, 5, 0, 0, 0],\n",
    "    [0, 9, 8, 0, 0, 0, 0, 6, 0],\n",
    "    [8, 0, 0, 0, 6, 0, 0, 0, 3],\n",
    "    [4, 0, 0, 8, 0, 3, 0, 0, 1],\n",
    "    [7, 0, 0, 0, 2, 0, 0, 0, 6],\n",
    "    [0, 6, 0, 0, 0, 0, 2, 8, 0],\n",
    "    [0, 0, 0, 4, 1, 9, 0, 0, 5],\n",
    "    [0, 0, 0, 0, 8, 0, 0, 7, 9]\n",
    "]\n",
    "\n",
    "solution(test)\n",
    "test = [ # invalid suduoku\n",
    "    [5, 3, 0, 0, 7, 0, 0, 0, 0],\n",
    "    [6, 0, 0, 1, 9, 5, 0, 0, 0],\n",
    "    [0, 9, 8, 0, 0, 0, 0, 6, 4],\n",
    "    [8, 0, 0, 0, 6, 0, 0, 0, 4],\n",
    "    [4, 0, 0, 8, 0, 3, 0, 0, 1],\n",
    "    [7, 0, 0, 0, 2, 0, 0, 0, 6],\n",
    "    [0, 6, 0, 0, 0, 0, 2, 8, 0],\n",
    "    [0, 0, 0, 4, 1, 9, 0, 0, 5],\n",
    "    [0, 0, 0, 0, 8, 0, 0, 7, 9]\n",
    "]\n",
    "solution(test)\n",
    "\n",
    "test = [ # solution from book Figure 5.2 (b)\n",
    "    [5, 3, 4, 6, 7, 8, 9, 1, 2],\n",
    "    [6, 7, 2, 1, 9, 5, 3, 4, 8],\n",
    "    [1, 9, 8, 3, 4, 2, 5, 6, 7],\n",
    "    [8, 5, 9, 7, 6, 1, 4, 2, 3],\n",
    "    [4, 2, 6, 8, 5, 3, 7, 9, 1],\n",
    "    [7, 1, 3, 9, 2, 4, 8, 5, 6],\n",
    "    [9, 6, 1, 5, 3, 7, 2, 8, 4],\n",
    "    [2, 8, 7, 4, 1, 9, 6, 3, 5],\n",
    "    [3, 4, 5, 2, 8, 6, 1, 7, 9]\n",
    "]\n",
    "\n",
    "solution(test)"
   ]
  },
  {
   "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.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}