Skip to main content

Leetcode 37: Sudoku Solver

 

1. Problem Statement (Simple Explanation):


You are given a 9×9 Sudoku board, partially filled, with:

  • Digits '1'–'9' for filled cells.

  • '.' for empty cells.

You must:

  • Fill the empty cells so that the final board is a valid Sudoku solution:

    1. Each digit 1–9 appears exactly once in each row.

    2. Each digit 1–9 appears exactly once in each column.

    3. Each digit 1–9 appears exactly once in each 3×3 sub-box.

  • The input is guaranteed to have exactly one solution.

  • You must modify the board in-place.


2. Example:


Input board:

[

  ["5","3",".",".","7",".",".",".","."],

  ["6",".",".","1","9","5",".",".","."],

  [".","9","8",".",".",".",".","6","."],

  ["8",".",".",".","6",".",".",".","3"],

  ["4",".",".","8",".","3",".",".","1"],

  ["7",".",".",".","2",".",".",".","6"],

  [".","6",".",".",".",".","2","8","."],

  [".",".",".","4","1","9",".",".","5"],

  [".",".",".",".","8",".",".","7","9"]

]

Output solved board:

[

  ["5","3","4","6","7","8","9","1","2"],

  ["6","7","2","1","9","5","3","4","8"],

  ["1","9","8","3","4","2","5","6","7"],

  ["8","5","9","7","6","1","4","2","3"],

  ["4","2","6","8","5","3","7","9","1"],

  ["7","1","3","9","2","4","8","5","6"],

  ["9","6","1","5","3","7","2","8","4"],

  ["2","8","7","4","1","9","6","3","5"],

  ["3","4","5","2","8","6","1","7","9"]

]


3. Approach – Backtracking with Row/Col/Box Constraints:


This is a classic backtracking search problem:

  1. Choose an empty cell.

  2. Try placing digits '1'–'9' that do not violate Sudoku constraints.

  3. Recursively solve the rest of the board.

  4. If at some point no digit works, backtrack: undo last placement and try next digit.

To make it efficient, we track used digits in:

  • rows[9][9] – rows[r][d] is true if digit d+1 already used in row r.

  • cols[9][9] – cols[c][d] is true if digit d+1 already used in column c.

  • boxes[9][9] – boxes[b][d] is true if digit d+1 already used in box b.

Where:

  • d = digit - '1' gives index 0..8

  • b = (r / 3) * 3 + (c / 3) gives box index 0..8

We initialize these from the given board, then run DFS/backtracking.

Because the problem guarantees exactly one solution, we can stop as soon as the board is filled validly.


4. Detailed Algorithm:


  1. Initialize constraint arrays:

    • For each cell (r, c):

      • If board[r][c] != '.':

        • Compute d = board[r][c] - '1'.

        • Compute boxIndex = (r / 3) * 3 + (c / 3).

        • Mark:

          • rows[r][d] = true

          • cols[c][d] = true

          • boxes[boxIndex][d] = true

  2. Backtracking function: solve(r, c) or better: solve() that scans to find next empty cell.A common pattern:

    • Scan the board to find the next empty cell (r, c):

      • If none is found, puzzle is solved → return true.

    • For digit from '1' to '9':

      • Let d = digit - '1', b = (r / 3) * 3 + (c / 3).

      • If rows[r][d] == false and cols[c][d] == false and boxes[b][d] == false:

        • Place the digit:

          • board[r][c] = digit

          • rows[r][d] = cols[c][d] = boxes[b][d] = true

        • Recurse: if (solve()) return true;

        • Otherwise, backtrack:

          • board[r][c] = '.'

          • rows[r][d] = cols[c][d] = boxes[b][d] = false

    • If none of the digits work, return false.

  3. Call solve() once after initialization.


Pseudo-code:



Complexity:


  • Worst-case, Sudoku solving is exponential in general.

  • But for typical boards and with constraints checking, it’s fast enough.

  • Space: O(1) (fixed size arrays).


5.Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more