{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "af348fbafae4",
   "metadata": {},
   "source": [
    "# Valid Sudoku\n",
    "\n",
    "| Field      | Value                                   |\n",
    "|------------|-----------------------------------------|\n",
    "| Source     | [link](https://leetcode.com/problems/valid-sudoku/)  |\n",
    "| Difficulty | Medium                    |\n",
    "| Topics     | `array`, `hash set`, `matrix`                     |\n",
    "| Date       | 2026-10-13                              |\n",
    "| Status     | Solved                                  |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43c87c7aa88a",
   "metadata": {},
   "source": [
    "## 1. Problem\n",
    "\n",
    "> You are given a 9 x 9 Sudoku board `board`. A Sudoku board is valid if the following rules are\n",
    "> followed:\n",
    "> - Each row must contain the digits 1-9 without duplicates.\n",
    "> - Each column must contain the digits 1-9 without duplicates.\n",
    "> - Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.\n",
    ">\n",
    "> Return `true` if the Sudoku board is valid, otherwise return `false`.\n",
    ">\n",
    "> **Note:** A board does not need to be full or be solvable to be valid.\n",
    "\n",
    "**Example 1**\n",
    "```\n",
    "Input: board =\n",
    "[[\"1\",\"2\",\".\",\".\",\"3\",\".\",\".\",\".\",\".\"],\n",
    " [\"4\",\".\",\".\",\"5\",\".\",\".\",\".\",\".\",\".\"],\n",
    " [\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\".\",\"3\"],\n",
    " [\"5\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"4\"],\n",
    " [\".\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"5\"],\n",
    " [\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    " [\".\",\".\",\".\",\".\",\".\",\".\",\"2\",\".\",\".\"],\n",
    " [\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"8\"],\n",
    " [\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "Output: true\n",
    "```\n",
    "\n",
    "**Example 2**\n",
    "```\n",
    "Input: board =\n",
    "[[\"1\",\"2\",\".\",\".\",\"3\",\".\",\".\",\".\",\".\"],\n",
    " [\"4\",\".\",\".\",\"5\",\".\",\".\",\".\",\".\",\".\"],\n",
    " [\".\",\"9\",\"1\",\".\",\".\",\".\",\".\",\".\",\"3\"],\n",
    " [\"5\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"4\"],\n",
    " [\".\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"5\"],\n",
    " [\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    " [\".\",\".\",\".\",\".\",\".\",\".\",\"2\",\".\",\".\"],\n",
    " [\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"8\"],\n",
    " [\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "Output: false\n",
    "Explanation: There are two 1's in the top-left 3x3 sub-box.\n",
    "```\n",
    "\n",
    "**Constraints**\n",
    "- `board.length == 9`\n",
    "- `board[i].length == 9`\n",
    "- `board[i][j]` is a digit `1-9` or `'.'`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ee544dafaaf4",
   "metadata": {},
   "source": [
    "## 2. Thinking\n",
    "\n",
    "- **Brute force idea:** collect the 27 groups (9 rows, 9 columns, 9 boxes) separately and check\n",
    "  each one for duplicates. That's already $O(81)$, i.e. $O(1)$ for a fixed board (or $O(n^2)$ for\n",
    "  an $n \\times n$ board), so it's not *slow*. What's wrong with it is that it reads the board three\n",
    "  times and the box loop is easy to get wrong.\n",
    "- **Key insight:** every cell `(r, c)` belongs to exactly **one row, one column and one box**,\n",
    "  and the box can be computed directly:\n",
    "  $$\\text{box} = (r \\,/\\!/\\, 3) \\cdot 3 + (c \\,/\\!/\\, 3) \\quad\\text{or the pair}\\quad (r \\,/\\!/\\, 3,\\ c \\,/\\!/\\, 3)$$\n",
    "  So one pass over the 81 cells is enough. Keep a \"seen\" set for each row, each column and each\n",
    "  box. If a digit is already in any of the three, the board is invalid.\n",
    "- **Edge cases to remember:**\n",
    "  - Empty board (all `'.'`) is **valid**.\n",
    "  - Don't check solvability. Only check for duplicates.\n",
    "  - A box duplicate can sit in different rows *and* different columns (Example 2: `(0,0)` and\n",
    "    `(2,2)`), so row and column checks alone don't catch it.\n",
    "  - Check **all 9 boxes**, not just the diagonal ones (my second attempt checked only\n",
    "    `(0,0)`, `(3,3)`, `(6,6)`)."
   ]
  },
  {
   "cell_type": "code",
   "id": "4160e46b43e9",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Setup: run this cell first. Lets you run pytest tests inside the notebook.\n",
    "try:\n",
    "    import ipytest\n",
    "except ImportError:  # Colab and other fresh kernels don't ship ipytest\n",
    "    %pip install -q ipytest\n",
    "    import ipytest\n",
    "import pytest\n",
    "\n",
    "ipytest.autoconfig()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9827882cc1bc",
   "metadata": {},
   "source": [
    "## 3. Solution\n",
    "\n",
    "### Approach A — my version (three passes, join + `len(set)`)\n",
    "\n",
    "**Complexity:** Time $O(81)$ (= $O(n^2)$ for an $n \\times n$ board) · Space $O(9)$ per group.\n",
    "Correct, and the Big-O is the same as the best answer. It's \"not ideal\" because:\n",
    "1. **Three separate passes** over the board (rows, columns, boxes), with three copies of the\n",
    "   same \"join → strip dots → compare `len` to `len(set)`\" logic.\n",
    "2. **No early exit inside a group:** it builds the whole row/column/box string and the whole set\n",
    "   before checking, instead of stopping at the first repeated digit.\n",
    "3. **The box loop is the fragile part:** four nested loops with two offset variables (`i`, `l`).\n",
    "   This is where both of my bugs were.\n",
    "4. The string `\"\".join(...).replace(\".\", \"\")` trick works only because every cell is a single\n",
    "   character.\n",
    "\n",
    "The code is unchanged except for the signature and comments."
   ]
  },
  {
   "cell_type": "code",
   "id": "6ed9644cb724",
   "metadata": {},
   "source": [
    "def is_valid_sudoku_mine(board: list[list[str]]) -> bool:\n",
    "    for row in board:                                       # pass 1: rows\n",
    "        nums = \"\".join(row).replace(\".\", \"\")\n",
    "        if len(nums) != len(set(nums)):                     # builds the whole set, no early exit\n",
    "            return False\n",
    "    for col in range(9):                                    # pass 2: columns\n",
    "        nums = []\n",
    "        for row in range(9):\n",
    "            nums.append(board[row][col])\n",
    "        nums_str = \"\".join(nums).replace(\".\", \"\")\n",
    "        if len(nums_str) != len(set(nums_str)):\n",
    "            return False\n",
    "    for i in range(0, 9, 3):                                # pass 3: boxes, 4 nested loops\n",
    "        for l in range(0, 9, 3):\n",
    "            nums = []\n",
    "\n",
    "            for j in range(i, i + 3):\n",
    "                for k in range(l, l + 3):\n",
    "                    nums.append(board[j][k])\n",
    "            nums_str = \"\".join(nums).replace(\".\", \"\")\n",
    "            if len(nums_str) != len(set(nums_str)):\n",
    "                return False\n",
    "\n",
    "    return True"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "21d53a717aee",
   "metadata": {},
   "source": [
    "### Approach B — one pass, a set per row / column / box ✅ best practice (interview answer)\n",
    "\n",
    "**Complexity:** Time $O(81)$ · Space $O(81)$ (27 sets, at most 9 digits each).\n",
    "Walk every cell once. Skip `'.'`. Compute `box = (r // 3) * 3 + c // 3`. If the digit is\n",
    "already in `rows[r]`, `cols[c]` or `boxes[box]`, return `False`. Otherwise add it to all three.\n",
    "It stops at the first duplicate, has a single loop, and the box formula replaces the four\n",
    "nested loops."
   ]
  },
  {
   "cell_type": "code",
   "id": "b31ac9efe07d",
   "metadata": {},
   "source": [
    "def is_valid_sudoku(board: list[list[str]]) -> bool:\n",
    "    rows = [set() for _ in range(9)]\n",
    "    cols = [set() for _ in range(9)]\n",
    "    boxes = [set() for _ in range(9)]\n",
    "    for r in range(9):\n",
    "        for c in range(9):\n",
    "            d = board[r][c]\n",
    "            if d == \".\":\n",
    "                continue\n",
    "            b = (r // 3) * 3 + c // 3\n",
    "            if d in rows[r] or d in cols[c] or d in boxes[b]:\n",
    "                return False\n",
    "            rows[r].add(d)\n",
    "            cols[c].add(d)\n",
    "            boxes[b].add(d)\n",
    "    return True"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "e2b416640d09",
   "metadata": {},
   "source": [
    "### Approach C — one set of tagged tuples (Pythonic)\n",
    "\n",
    "**Complexity:** Time $O(81)$ · Space $O(81)$.\n",
    "Same idea, but all 27 groups share **one** set. Each digit is recorded three times as a tagged\n",
    "tuple: `(r, d)` for its row, `(d, c)` for its column (digit first, so it can't collide with a\n",
    "row entry), and `(r // 3, c // 3, d)` for its box (length 3, so it can't collide with either).\n",
    "Short and neat. In an interview, explain the tagging or use explicit tags like `(\"row\", r, d)`."
   ]
  },
  {
   "cell_type": "code",
   "id": "ab8f18cfe7b4",
   "metadata": {},
   "source": [
    "def is_valid_sudoku_tuples(board: list[list[str]]) -> bool:\n",
    "    seen = set()\n",
    "    for r in range(9):\n",
    "        for c in range(9):\n",
    "            d = board[r][c]\n",
    "            if d == \".\":\n",
    "                continue\n",
    "            keys = ((r, d), (d, c), (r // 3, c // 3, d))\n",
    "            if any(k in seen for k in keys):\n",
    "                return False\n",
    "            seen.update(keys)\n",
    "    return True"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "45f9ae4e0e15",
   "metadata": {},
   "source": [
    "### Approach D — bitmasks\n",
    "\n",
    "**Complexity:** Time $O(81)$ · Space $O(27)$ ints.\n",
    "Replace each set with a 9-bit integer: bit `d` is set once digit `d` has been seen. Checking\n",
    "and adding are one `&` and one `|`. This is the standard trick in C++/Java (and the base of\n",
    "Sudoku *solvers*, #37). In Python it isn't faster, because of the `int(d)` and shift on every cell."
   ]
  },
  {
   "cell_type": "code",
   "id": "90356138cc97",
   "metadata": {},
   "source": [
    "def is_valid_sudoku_bitmask(board: list[list[str]]) -> bool:\n",
    "    rows = [0] * 9\n",
    "    cols = [0] * 9\n",
    "    boxes = [0] * 9\n",
    "    for r in range(9):\n",
    "        for c in range(9):\n",
    "            d = board[r][c]\n",
    "            if d == \".\":\n",
    "                continue\n",
    "            bit = 1 << int(d)\n",
    "            b = (r // 3) * 3 + c // 3\n",
    "            if (rows[r] | cols[c] | boxes[b]) & bit:\n",
    "                return False\n",
    "            rows[r] |= bit\n",
    "            cols[c] |= bit\n",
    "            boxes[b] |= bit\n",
    "    return True"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "e6c0214da78b",
   "metadata": {},
   "source": [
    "## 4. Tests\n",
    "\n",
    "Every approach runs against every case. Boards are built from a dict of `(r, c) → digit` so each\n",
    "case shows exactly which cells matter. None of the approaches mutate `board`."
   ]
  },
  {
   "cell_type": "code",
   "id": "fbddffc2b767",
   "metadata": {},
   "source": [
    "%%ipytest -q\n",
    "\n",
    "APPROACHES = [\n",
    "    is_valid_sudoku_mine,\n",
    "    is_valid_sudoku,\n",
    "    is_valid_sudoku_tuples,\n",
    "    is_valid_sudoku_bitmask,\n",
    "]\n",
    "\n",
    "def make_board(cells: dict[tuple[int, int], str]) -> list[list[str]]:\n",
    "    board = [[\".\"] * 9 for _ in range(9)]\n",
    "    for (r, c), d in cells.items():\n",
    "        board[r][c] = d\n",
    "    return board\n",
    "\n",
    "EXAMPLE_1 = [\n",
    "    [\"1\",\"2\",\".\",\".\",\"3\",\".\",\".\",\".\",\".\"],\n",
    "    [\"4\",\".\",\".\",\"5\",\".\",\".\",\".\",\".\",\".\"],\n",
    "    [\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\".\",\"3\"],\n",
    "    [\"5\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"4\"],\n",
    "    [\".\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"5\"],\n",
    "    [\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],\n",
    "    [\".\",\".\",\".\",\".\",\".\",\".\",\"2\",\".\",\".\"],\n",
    "    [\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"8\"],\n",
    "    [\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"],\n",
    "]\n",
    "EXAMPLE_2 = [row[:] for row in EXAMPLE_1]\n",
    "EXAMPLE_2[2][2] = \"1\"\n",
    "\n",
    "SOLVED = [list(row) for row in [\n",
    "    \"534678912\", \"672195348\", \"198342567\",\n",
    "    \"859761423\", \"426853791\", \"713924856\",\n",
    "    \"961537284\", \"287419635\", \"345286179\",\n",
    "]]\n",
    "SOLVED_BAD = [row[:] for row in SOLVED]\n",
    "SOLVED_BAD[8][8], SOLVED_BAD[8][7] = SOLVED_BAD[8][7], SOLVED_BAD[8][8]  # swap breaks 2 columns\n",
    "\n",
    "CASES = [\n",
    "    (EXAMPLE_1, True),\n",
    "    (EXAMPLE_2, False),                                     # two 1s in top-left box\n",
    "    (make_board({}), True),                                 # empty board is valid\n",
    "    (make_board({(4, 0): \"5\", (4, 8): \"5\"}), False),        # row duplicate only\n",
    "    (make_board({(0, 4): \"7\", (8, 4): \"7\"}), False),        # column duplicate only\n",
    "    (make_board({(1, 3): \"3\", (2, 5): \"3\"}), False),        # top-middle box: off-diagonal box\n",
    "    (make_board({(6, 0): \"3\", (8, 2): \"3\"}), False),        # bottom-left box\n",
    "    (make_board({(7, 7): \"9\", (8, 6): \"9\"}), False),        # bottom-right box (last box)\n",
    "    (make_board({(0, 0): \"1\", (0, 3): \"2\", (3, 0): \"2\"}), True),  # same digit, different groups\n",
    "    (SOLVED, True),                                         # full valid board: no early exit\n",
    "    (SOLVED_BAD, False),                                    # full board, duplicate in columns\n",
    "]\n",
    "\n",
    "@pytest.mark.parametrize(\"fn\", APPROACHES)\n",
    "@pytest.mark.parametrize(\"board, expected\", CASES)\n",
    "def test_is_valid_sudoku(fn, board, expected):\n",
    "    assert fn(board) is expected"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "f6b44dc85a13",
   "metadata": {},
   "source": [
    "## 5. Scratch / Experiments\n",
    "\n",
    "The board is always $9 \\times 9$, so Big-O is $O(1)$ for all of them and only constant factors\n",
    "matter. Worst case = a **full valid board** (no early exit, every cell is a digit). Also an\n",
    "**empty board** (all `'.'`), where the one-pass versions do almost nothing per cell.\n",
    "\n",
    "Typical results (µs):\n",
    "\n",
    "| Approach | full valid | empty |\n",
    "|---|---|---|\n",
    "| A mine (3 passes, join + set) | ~14 | ~12 |\n",
    "| B set per group ✅ | ~15.5 | ~4 |\n",
    "| C tagged tuples | ~34 | ~2.7 |\n",
    "| D bitmask | ~17 | ~2.6 |\n",
    "\n",
    "Big-O and timing disagree here, and it's worth knowing why:\n",
    "- **A keeps up on a full board** (and is slightly ahead) because most of its work is `\"\".join`,\n",
    "  `str.replace` and `set(str)`. Those are **C-level** loops over 9 characters, while B/C/D run\n",
    "  Python bytecode for every one of the 81 cells (index, compare, 3 lookups, 3 adds).\n",
    "- **On an empty / sparse board the one-pass versions are 3–4× faster**: they just skip `'.'`,\n",
    "  while A still builds 27 strings and sets no matter what.\n",
    "- **C is slowest on a full board:** it builds 3 tuples per cell and hashes them, plus a\n",
    "  generator in `any`. On an empty board it wins because it allocates only one set instead of 27.\n",
    "- **D isn't faster than B in Python:** `int(d)` and `1 << ...` cost about as much as a set lookup.\n",
    "  Bitmasks pay off in C++/Java, not CPython.\n",
    "\n",
    "So A isn't \"slow\". It's verbose and fragile. B is the one to remember because it's a single,\n",
    "general pass that's easy to get right, early-exits, and scales to \"check any grid constraint\"."
   ]
  },
  {
   "cell_type": "code",
   "id": "e8dc2538d5c5",
   "metadata": {},
   "source": [
    "FULL = [row[:] for row in SOLVED]\n",
    "EMPTY = make_board({})\n",
    "\n",
    "for label, board in [(\"full valid\", FULL), (\"empty\", EMPTY)]:\n",
    "    print(f\"--- {label}\")\n",
    "    for fn in APPROACHES:\n",
    "        print(f\"{fn.__name__:28s}\", end=\" \")\n",
    "        %timeit fn(board)"
   ],
   "execution_count": null,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "id": "7981b667732a",
   "metadata": {},
   "source": [
    "## 6. Takeaways\n",
    "\n",
    "- **Pattern:** \"no duplicates within each **group**\" → a **seen set per group**, filled in a\n",
    "  single pass. For grids, map each cell straight to its groups: row `r`, column `c`, box\n",
    "  `(r // 3) * 3 + c // 3` (in general, block `(r // h, c // w)`). Computing the group index\n",
    "  from the cell is simpler than looping over each group separately.\n",
    "- **Mistakes I made:**\n",
    "  - `len(nums) != set(nums)`: compared an `int` to a `set`, which is always unequal, so it\n",
    "    returned `False` on the first row. Compare `len` to `len(set(...))`.\n",
    "  - `nums_str` vs `num_str`: a typo that becomes a `NameError`.\n",
    "  - Box loop v1 used **one** index for both the row start and the column start, so it only\n",
    "    checked the 3 diagonal boxes. Box loop v2 never offset `j`/`k`, so it checked the top-left\n",
    "    box 3 times. **Lesson:** the 9 boxes need **two independent** starting coordinates, or no\n",
    "    box loop at all if you use `r // 3, c // 3`.\n",
    "  - Tested only on the given examples, which both put the problem in the top-left box. Add a\n",
    "    case for an off-diagonal box.\n",
    "- **Related problems:** Sudoku Solver (#37, same row/column/box sets plus backtracking;\n",
    "  bitmasks are standard there), Contains Duplicate (#217, the single-group version of this),\n",
    "  Set Matrix Zeroes (#73, per-row / per-column marking), N-Queens (#51, the same \"which groups\n",
    "  does this cell belong to\" trick with diagonals `r - c` and `r + c`), Valid Anagram (#242,\n",
    "  comparing counts instead of seen sets)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}