sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_board(board):\n",
    "    for r in range(board.shape[0]):\n",
    "        row = board[r]\n",
    "        line = ''\n",
    "        for c in range(board.shape[1]):\n",
    "            column = board[r, c]\n",
    "            if c != 0 and c % 3 == 0:\n",
    "                line += '| '\n",
    "            if column == 0:\n",
    "                line += '. '\n",
    "            else:\n",
    "                line += f'{int(column)} '\n",
    "        print(line)\n",
    "        if r != 8 and (r + 1) % 3 == 0:\n",
    "            print('- ' * (board.shape[1] + (board.shape[1] // 3 - 1)))\n",
    "\n",
    "def get_square(x, y, board):\n",
    "    x_square = x // 3\n",
    "    y_square = y // 3\n",
    "    return board[3 * y_square:3 * (y_square + 1), 3 * x_square:3 * (x_square + 1)]\n",
    "\n",
    "def get_line(x, y, board):\n",
    "    return board[y,]\n",
    "\n",
    "def get_column(x, y, board):\n",
    "    return board[:,x]\n",
    "\n",
    "def value_in_board(value, x, y, board):\n",
    "    if value in get_line(x, y, board).flat:\n",
    "        return True\n",
    "    if value in get_column(x, y, board).flat:\n",
    "        return True\n",
    "    if value in get_square(x, y, board).flat:\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "def remaining_generator(board, start_x, start_y):\n",
    "    size_y, size_x = board.shape\n",
    "    left_y = size_y - start_y\n",
    "    left_x = size_x - start_x\n",
    "    for y, x in np.ndindex(left_y, size_x):\n",
    "        if y == 0:\n",
    "            if x >= left_x:\n",
    "                continue\n",
    "            if board[y + start_y, x + start_x] != 0:\n",
    "                continue\n",
    "            yield x + start_x, y + start_y\n",
    "        elif board[y + start_y, x] != 0:\n",
    "            continue\n",
    "        else:\n",
    "            yield x, y + start_y\n",
    "\n",
    "def possible_values(x, y, board, restriction):\n",
    "    values = np.arange(max(board.shape)) + 1\n",
    "    np.random.shuffle(values)\n",
    "    for value in values:\n",
    "        if restriction and (x, y) == restriction[0] and value == restriction[1]:\n",
    "            continue\n",
    "        if not value_in_board(value, x, y, board):\n",
    "            yield value\n",
    "\n",
    "def solve(board, start_x=0, start_y=0, print_solutions=True, find_multiple=True, restriction=None):\n",
    "    for x, y in remaining_generator(board, start_x, start_y):\n",
    "        for value in possible_values(x, y, board, restriction):\n",
    "            board[y, x] = value\n",
    "            solution = solve(board, x, y, print_solutions, find_multiple, restriction)\n",
    "            if solution is not False:\n",
    "                return solution\n",
    "            board[y, x] = 0\n",
    "        return False\n",
    "    if print_solutions:\n",
    "        print_board(board)\n",
    "    if find_multiple:\n",
    "        return False\n",
    "    return np.copy(board)\n",
    "\n",
    "def create_board(remove_n=20):\n",
    "    indexes = list(np.ndindex(9, 9))\n",
    "    np.random.shuffle(indexes)\n",
    "    solved_board = solve(np.zeros([9, 9]), find_multiple=False, print_solutions=False)\n",
    "    for x, y in indexes:\n",
    "        to_remove = solved_board[y, x]\n",
    "        solved_board[y, x] = 0\n",
    "        restriction = ((x, y), to_remove)\n",
    "        solved_board_copy = np.copy(solved_board)\n",
    "        solution = solve(solved_board_copy, print_solutions=False, find_multiple=False, restriction=restriction)\n",
    "        if solution is not False:\n",
    "            solved_board[y, x] = to_remove\n",
    "        else:\n",
    "            remove_n -= 1\n",
    "            if remove_n <= 0:\n",
    "                break\n",
    "    return solved_board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 5.54 s, sys: 128 ms, total: 5.67 s\n",
      "Wall time: 5.6 s\n",
      "9 5 . | 8 7 . | . 6 . \n",
      ". . 3 | 4 . 1 | . . 9 \n",
      "4 . . | . . . | 8 2 . \n",
      "- - - - - - - - - - - \n",
      ". . . | . . . | 3 . . \n",
      "1 . . | . . . | . 7 4 \n",
      ". . 6 | . . . | . 8 . \n",
      "- - - - - - - - - - - \n",
      ". 3 . | 9 . . | . . 6 \n",
      ". 2 1 | 5 . . | . . . \n",
      ". . . | 2 . . | . . 8 \n"
     ]
    }
   ],
   "source": [
    "%time created = create_board(55)\n",
    "print_board(created)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9 5 2 | 8 7 3 | 4 6 1 \n",
      "8 6 3 | 4 2 1 | 7 5 9 \n",
      "4 1 7 | 6 5 9 | 8 2 3 \n",
      "- - - - - - - - - - - \n",
      "2 7 4 | 1 6 8 | 3 9 5 \n",
      "1 8 5 | 3 9 2 | 6 7 4 \n",
      "3 9 6 | 7 4 5 | 1 8 2 \n",
      "- - - - - - - - - - - \n",
      "5 3 8 | 9 1 7 | 2 4 6 \n",
      "6 2 1 | 5 8 4 | 9 3 7 \n",
      "7 4 9 | 2 3 6 | 5 1 8 \n",
      "CPU times: user 565 ms, sys: 21.6 ms, total: 586 ms\n",
      "Wall time: 571 ms\n"
     ]
    }
   ],
   "source": [
    "%time _ = solve(created, find_multiple=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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
}