sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "46a18e5e-d3e2-4f62-ac5f-238a5b980b31",
   "metadata": {},
   "source": [
    "# Sudoku"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e7fa684c-9318-424e-b147-d33039858cd8",
   "metadata": {},
   "source": [
    "## define setup and I/O functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7e0715f5-a5a8-46c8-8ac0-ae669a344065",
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialize_domains():\n",
    "    domains = []  # domain for each cell\n",
    "    dom_sizes = []  # size of the domain for each cell\n",
    "    for i in range(9):\n",
    "        domains.append([])\n",
    "        dom_sizes.append([])\n",
    "        for j in range(9):\n",
    "            domains[i].append([])\n",
    "            dom_sizes[i].append(9)\n",
    "            for k in range(9):\n",
    "                domains[i][j].append(True)\n",
    "    return domains, dom_sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d4262e3b-af3e-4d67-9ea3-37e59badf931",
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_data(filename):\n",
    "    with open(filename) as f:\n",
    "        data = f.readlines()\n",
    "\n",
    "    board = []\n",
    "    domains, dom_sizes = initialize_domains()\n",
    "\n",
    "    for i, line in enumerate(data):\n",
    "        line = line.strip()  # remove newline character\n",
    "        line = line.split(\"|\")[1:-1]\n",
    "        row = []\n",
    "        for j, cell in enumerate(line):\n",
    "            if cell == \"\" or cell == \" \":  # accounts for both input formats\n",
    "                row.append(0)  # 0 represents an empty cell\n",
    "            else:\n",
    "                cell = int(cell)\n",
    "                row.append(cell)\n",
    "                domains, dom_sizes, consistent = consistency_check(domains, dom_sizes, i, j, cell)\n",
    "                if not consistent:\n",
    "                    raise ValueError(\"invalid input board\")\n",
    "        board.append(row)\n",
    "    \n",
    "    return board, domains, dom_sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "02ff59b5-d592-44da-a30c-003e54fb7a02",
   "metadata": {},
   "outputs": [],
   "source": [
    "def board_str(board):\n",
    "    string = ''\n",
    "    for row in board:\n",
    "        for cell in row:\n",
    "            string += '|'\n",
    "            string += str(cell)\n",
    "        string += '|\\n'\n",
    "    string = string[:-1]\n",
    "    return string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e28e6bb9-9d49-490d-ab13-a93870079366",
   "metadata": {},
   "outputs": [],
   "source": [
    "def write_data(filename, board):\n",
    "    with open(filename, 'w') as f:\n",
    "        f.write(board_str(board))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3cd3e3c4-eeef-42c2-82d0-c381c9834ab5",
   "metadata": {},
   "source": [
    "## define solver functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b81877f1-1fb1-4278-91f8-545f908ee481",
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7c795877-4930-4b50-8eec-fad7ccf57349",
   "metadata": {},
   "outputs": [],
   "source": [
    "def consistency_check(domains, dom_sizes, i, j, k):\n",
    "    domains = copy.deepcopy(domains)\n",
    "    dom_sizes = copy.deepcopy(dom_sizes)\n",
    "    \n",
    "    # update domain for cell (i,j)\n",
    "    domains[i][j] = [False] * 9\n",
    "    domains[i][j][k-1] = True\n",
    "    dom_sizes[i][j] = 1\n",
    "    \n",
    "    # update domains for cells in same column\n",
    "    for x in range(9):\n",
    "        y = j\n",
    "        if x != i:\n",
    "            if domains[x][y][k-1]:\n",
    "                dom_sizes[x][y] -= 1\n",
    "                if dom_sizes[x][y] == 0:\n",
    "                    return None, None, False\n",
    "            domains[x][y][k-1] = False\n",
    "    \n",
    "    # update domains for cells in same row\n",
    "    for y in range(9):\n",
    "        x = i\n",
    "        if y != j:\n",
    "            if domains[x][y][k-1]:\n",
    "                dom_sizes[x][y] -= 1\n",
    "                if dom_sizes[x][y] == 0:\n",
    "                    return None, None, False\n",
    "            domains[x][y][k-1] = False\n",
    "            \n",
    "    # update domains for cells in same subgrid\n",
    "    r = i // 3\n",
    "    c = j // 3\n",
    "    for x in range(3*r, 3*(r+1)):\n",
    "        for y in range(3*c, 3*(c+1)):\n",
    "            if x != i and y != j:\n",
    "                if domains[x][y][k-1]:\n",
    "                    dom_sizes[x][y] -= 1\n",
    "                    if dom_sizes[x][y] == 0:\n",
    "                        return None, None, False\n",
    "                domains[x][y][k-1] = False\n",
    "    \n",
    "    return domains, dom_sizes, True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "22d08b6e-f60d-4f8a-9be4-54303990ee61",
   "metadata": {},
   "outputs": [],
   "source": [
    "def backtrack(cell_id, board, domains, dom_sizes):\n",
    "    if cell_id >= 81:\n",
    "        # Sudoku puzzle is completed\n",
    "        return True, board, domains, dom_sizes\n",
    "    \n",
    "    i = cell_id // 9\n",
    "    j = cell_id % 9\n",
    "    \n",
    "    board = copy.deepcopy(board)\n",
    "    domains = copy.deepcopy(domains)\n",
    "    dom_sizes = copy.deepcopy(dom_sizes)\n",
    "    \n",
    "    for k, val in enumerate(domains[i][j]):\n",
    "        if val:\n",
    "            # try a new value in cell (i,j)\n",
    "            board[i][j] = k+1\n",
    "            new_domains, new_dom_sizes, consistent = consistency_check(domains, dom_sizes, i, j, k+1)\n",
    "            \n",
    "            if consistent:\n",
    "                # move on to next cell\n",
    "                res, new_board, new_domains, new_dom_sizes = backtrack(cell_id + 1, board, new_domains, new_dom_sizes)\n",
    "                if res:\n",
    "                    # Sudoku puzzle is completed\n",
    "                    return True, new_board, new_domains, new_dom_sizes\n",
    "    \n",
    "    # no values worked for cell (i,j); going back to previous cell\n",
    "    return False, board, domains, dom_sizes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "52b15bfa-1768-4854-af7e-c4460d60511e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(board, domains, dom_sizes):\n",
    "    res, board, domains, dom_sizes = backtrack(0, board, domains, dom_sizes)\n",
    "    if res:\n",
    "        print(\"Here is a solution to this Sudoku puzzle:\\n\")\n",
    "        print(board_str(board))\n",
    "        return True, board\n",
    "    else:\n",
    "        print(\"There is no solution to this Sudoku puzzle.\")\n",
    "        return False, None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c40658e1-06a5-4248-b652-afbbab1a17cb",
   "metadata": {},
   "source": [
    "## run solver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2b0d21a3-8e8d-435c-bfef-7b292ee9b1b2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "|8|0|0|9|3|0|0|0|2|\n",
      "|0|0|9|0|0|0|0|4|0|\n",
      "|7|0|2|1|0|0|9|6|0|\n",
      "|2|0|0|0|0|0|0|9|0|\n",
      "|0|6|0|0|0|0|0|7|0|\n",
      "|0|7|0|0|0|6|0|0|5|\n",
      "|0|2|7|0|0|8|4|0|6|\n",
      "|0|3|0|0|0|0|5|0|0|\n",
      "|5|0|0|0|6|2|0|0|8|\n"
     ]
    }
   ],
   "source": [
    "file_in = \"input_boards/mixed_format_board.txt\"\n",
    "board, domains, dom_sizes = read_data(file_in)\n",
    "print(board_str(board))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "283438e6-04ec-46a1-a08c-ac671e46ef3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import perf_counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "74862d79-4918-421b-bce3-c86a593b2ddd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Here is a solution to this Sudoku puzzle:\n",
      "\n",
      "|8|4|6|9|3|7|1|5|2|\n",
      "|3|1|9|6|2|5|8|4|7|\n",
      "|7|5|2|1|8|4|9|6|3|\n",
      "|2|8|5|7|1|3|6|9|4|\n",
      "|4|6|3|8|5|9|2|7|1|\n",
      "|9|7|1|2|4|6|3|8|5|\n",
      "|1|2|7|5|9|8|4|3|6|\n",
      "|6|3|8|4|7|1|5|2|9|\n",
      "|5|9|4|3|6|2|7|1|8|\n",
      "\n",
      "time elapsed (s): 0.8980649000000085\n"
     ]
    }
   ],
   "source": [
    "start = perf_counter()\n",
    "solved, res = solve(board, domains, dom_sizes)\n",
    "end = perf_counter()\n",
    "\n",
    "print(f\"\\ntime elapsed (s): {end - start}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "3dc0c983-caf7-4ceb-a5ef-bcf9dbbb72b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "written to file output_boards/output_board.txt\n"
     ]
    }
   ],
   "source": [
    "if solved:\n",
    "    file_out = \"output_boards/output_board.txt\"\n",
    "    write_data(file_out, res)\n",
    "    print(f\"written to file {file_out}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dcfb61e0-777e-40f8-9cf8-98c82c14e70e",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:cs411]",
   "language": "python",
   "name": "conda-env-cs411-py"
  },
  "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.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}