DAY 25: Solve N Knights, Sudoku & Word Search Using Recursion in Java | My DSA Journey – Recursion

---

🚀 Introduction

Welcome to Day 25 of my DSA Journey!
Over the past few weeks, I’ve been diving deep into one of the most fundamental and powerful concepts in Data Structures & Algorithms — Recursion.

In the last 3 days, I solved three classic backtracking problems:
N Knights, Sudoku Solver, and Word Search — each one helped me understand recursion with real, constraint-driven problem-solving.

I’m documenting my journey publicly to stay consistent and to help others who are just beginning their own DSA path from scratch.

📅 Here’s What I Covered Over the Last 3 Days:

Day 22

• N Knights Problem

Day 23

• Sudoku Solver

Day 24

• Word Search

Let’s break down each of these topics below 👇

---

Q 1. N Knights Problem:

The N Knights Problem is a classic backtracking challenge where we aim to place N knights on an N x N chessboard such that no two knights attack each other. This problem tests our understanding of recursion, safe-position checking, and backtracking strategies.

Given an N x N chessboard, place exactly N knights such that no two knights threaten each other. Knights must be placed one at a time in valid positions. We need to:

• Count the total number of ways to arrange them safely.
• Optionally print all such valid board configurations.

How Does a Knight Move?

A knight in chess moves in an "L" shape — either:

• Two squares in one direction and one square perpendicular,
• Or one square in one direction and two squares perpendicular.

From a given cell (r, c), a knight can potentially move to these 8 positions:

Upward:

• (r - 2, c - 1)
• (r - 2, c + 1)
• (r - 1, c - 2)
• (r - 1, c + 2)

Downward:

• (r + 1, c - 2)
• (r + 1, c + 2)
• (r + 2, c - 1)
• (r + 2, c + 1)

In our implementation, we only check positions in upward direction, since we fill the board row by row from top to bottom. This optimization avoids checking all 8 directions.

Example:

Let’s take N = 4. We want to place 4 knights on a 4×4 board so that no two knights can attack each other.

Output:
K O O K
O O O O
K O O O
O O O K

In this configuration:

• K represents a knight.
• O represents an empty cell.

This is a valid placement because no two knights attack each other.

Approach:

We use recursive backtracking to try all possible placements:

1. Start from (0,0) and move through the board cell by cell.
2. At each cell:
   • Try placing a knight if it's safe.
   • Recur to the next column (or next row if at the end of a row).
3. Use backtracking:
   • Remove the knight and try the next possibility.
4. When N knights are successfully placed, count and display the configuration.

We stop and count only when all knights are placed.

How Do We Check If a Position Is Safe?

Before placing a knight at board[row][col], we must ensure it cannot be attacked by any of the knights already placed on the board.

Since we place knights row-by-row from top to bottom and left to right, we only need to check those knight attack positions that lie above or to the left of the current cell. This makes the search more efficient.

A knight moves in an "L" shape: 2 steps in one direction and 1 step in a perpendicular direction.

For the current cell (row, col), we check the 4 possible L-shaped positions from which a knight could attack this cell (and where knights may already have been placed):

1. Two Rows Up, One Column Left

• Check if a knight exists at (row - 2, col - 1) Direction movement:

  (row - 2, col - 1)
  

2. Two Rows Up, One Column Right

• Check if a knight exists at (row - 2, col + 1) Direction movement:

  (row - 2, col + 1)
  

3. One Row Up, Two Columns Left

• Check if a knight exists at (row - 1, col - 2) Direction movement:

  (row - 1, col - 2)
  

4. One Row Up, Two Columns Right

• Check if a knight exists at (row - 1, col + 2) Direction movement:

  (row - 1, col + 2)
  

If none of these positions already contain a knight, it’s safe to place a knight at board[row][col].

This works because we’re filling the board from top-left to bottom-right, so we never need to check future (lower or right) positions — only those that have already been filled.

Code:

public class NKnights {
    public static void main(String[] args) {
        int n = 4;
        boolean[][] board = new boolean[n][n];

        int ways = knights(board, 0, 0, 4);
        System.out.println(ways);
    }

    static int knights(boolean[][] board, int row, int col, int knights) {
        if (knights == 0) {
            display(board);
            System.out.println();
            return 1;
        }

        if (row == board.length) {
            return 0;
        }

        if (col == board.length) {
            return knights(board, row + 1, 0, knights);
        }

        int count = 0;

        if (isSafe(board, row, col)) {
            board[row][col] = true;
            count += knights(board, row, col + 1, knights - 1);
            board[row][col] = false;
        }

        count += knights(board, row, col + 1, knights);

        return count;
    }

    static boolean isSafe(boolean[][] board, int row, int col) {
        if (valid(board, row - 2, col - 1) && board[row - 2][col - 1]) return false;
        if (valid(board, row - 2, col + 1) && board[row - 2][col + 1]) return false;
        if (valid(board, row - 1, col - 2) && board[row - 1][col - 2]) return false;
        if (valid(board, row - 1, col + 2) && board[row - 1][col + 2]) return false;

        return true;
    }

    private static boolean valid(boolean[][] board, int row, int col) {
        return row >= 0 && row < board.length && col >= 0 && col < board.length;
    }

    static void display(boolean[][] board) {
        for (boolean[] row : board) {
            for (boolean element : row) {
                System.out.print(element ? "K " : "O ");
            }
            System.out.println();
        }
    }
}

Key Takeaways:

• The N Knights problem is a classic example of backtracking with additional geometric constraints due to the knight’s unique movement.
• The isSafe() function checks only the 4 critical positions from which a knight can attack the current cell — making the solution efficient.
• We backtrack using board[row][col] = false after exploring a possibility, ensuring all valid configurations are tried.
• The base case knights == 0 indicates a valid arrangement of knights — we display the board and count it.
• Time complexity is still exponential, but smart pruning using isSafe() helps eliminate invalid paths early.
• Unlike N Queens, knight placements don’t depend on just rows or columns — their "L" shaped attacks require careful offset-based safety checks.

---

Q 2. Sudoku Solver:

The Sudoku Solver is a classic problem that showcases how powerful backtracking can be when dealing with constraint-based puzzles. The goal is to fill a 9×9 Sudoku board so that every row, column, and 3×3 box contains digits from 1 to 9 without repetition.

Given a partially filled 9×9 Sudoku board. Empty cells are represented by the character '.'.

Our task is to fill the board such that:

• Every digit 1-9 appears exactly once in each row.
• Every digit 1-9 appears exactly once in each column.
• Every digit 1-9 appears exactly once in each of the nine 3×3 sub-boxes.

Example:

Input:
[
['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:
[
['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']
]

Approach:

We solve this using backtracking, trying every possible digit from '1' to '9' in empty cells. For each choice:

1. If the number is valid in that row, column, and box → place it.
2. Move to the next empty cell.
3. If at any point we hit a dead-end (no valid number), we backtrack and undo the last choice.

This continues recursively until the entire board is validly filled.

Algorithm Steps:

1. Traverse the board row by row and column by column.
2. When we find an empty cell (i.e., '.'):
   • Try placing each digit '1' to '9'.
   • For each digit, use isValid() to check if it can be legally placed.
   • If valid:
     • Place it.
     • Recur to solve the rest of the board.
     • If recursion succeeds → return true.
     • Otherwise → backtrack and try the next digit.
3. If no valid digit can be placed in the current cell → return false.
4. If all cells are filled → return true (base case).

How Do We Check If a Placement is Valid?

To place num at position board[row][col], we must ensure the following three conditions:

1. It's not already in the current row

We iterate through all columns in the same row to ensure the number doesn't already exist.

for (int i = 0; i < 9; i++) {
    if (board[row][i] == num) return false;
}

2. It's not already in the current column

We iterate through all rows in the same column to check for duplicates.

for (int i = 0; i < 9; i++) {
    if (board[i][col] == num) return false;
}

3. It's not already in the corresponding 3×3 box

We calculate the top-left corner of the 3×3 box using:

int r = (3 * (row / 3)) + (i / 3);
int c = (3 * (col / 3)) + (i % 3);

Then iterate through all 9 cells of the box using a single loop:

for (int i = 0; i < 9; i++) {
    int r = (3 * (row / 3)) + (i / 3);
    int c = (3 * (col / 3)) + (i % 3);
    if (board[r][c] == num) return false;
}

If all three checks pass, then it is safe to place num at board[row][col].

Code:

public static boolean solve(char[][] board) {
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board.length; col++) {
            if (board[row][col] == '.') {
                for (char ch = '1'; ch <= '9'; ch++) {
                    if (isValid(board, row, col, ch)) {
                        board[row][col] = ch;
                        if (solve(board)) {
                            return true;
                        } else {
                            board[row][col] = '.'; // backtrack
                        }
                    }
                }
                return false; // if no valid number fits here
            }
        }
    }
    return true; // board completely filled
}

static boolean isValid(char[][] board, int row, int col, char num) {
    for (int i = 0; i < board.length; i++) {
        // Check Row
        if (board[row][i] == num) return false;

        // Check Column
        if (board[i][col] == num) return false;

        // Check 3x3 Box
        int r = (3 * (row / 3)) + (i / 3);
        int c = (3 * (col / 3)) + (i % 3);
        if (board[r][c] == num) return false;
    }
    return true;
}

Key Takeaways:

• This is a classic constraint satisfaction problem solved using recursive backtracking.
• The isValid() function is the heart of the logic, ensuring row, column, and 3×3 box rules are satisfied.
• Backtracking undoes the last decision using board[row][col] = '.' if it leads to a dead-end.
• The solution explores all possibilities but prunes invalid paths early, making it efficient for most real Sudoku boards.
• Sudoku solving is an excellent way to practice:
  • Recursive problem solving
  • 2D array manipulation
  • Clean logic structuring

---

Q 3. Word Search:

The Word Search problem is a popular backtracking challenge often asked in interviews. It tests our ability to navigate a 2D grid recursively while keeping track of visited cells and matching a target word character by character.

Given a 2D grid of characters and a word. We need to determine if the word exists in the grid. The word must be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same cell cannot be used more than once.

Example:

Input:
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED"

Output: true

Explanation:

The word "ABCCED" can be formed by the following path:

• A → B → C → C → E → D

Each character is adjacent (up, down, left, or right), and no cell is reused.

Approach:

We use backtracking to explore every possible path in the grid:

1. Traverse each cell of the board.
2. If a cell matches the first character of the word:
   • Start a recursive search using the isWordConstructed function from that cell.
3. From the current cell, move in all four directions:
   • Up
   • Down
   • Left
   • Right
4. Mark the cell as visited by replacing its character with a temporary marker (like '#').
5. Recurse for the next character in the word.
6. If the full word is matched → return true.
7. Backtrack by restoring the cell’s original character if the path doesn't lead to a solution.

How isWordConstructed() Works?

This recursive function tries to match the word starting from a specific cell on the board.

private static boolean isWordConstructed(char[][] board, int row, int col, String word, int index)

Base Case:

If all characters in the word are matched, return true. The word exists in the grid.

if (index == word.length()) return true;

Invalid Conditions:

if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != word.charAt(index))
    return false;

Return false if:

• The cell is out of bounds
• OR the current character in the board does not match the current character of the word

Recursive Exploration:

char ch = board[row][col];
board[row][col] = '#';  // mark as visited

We temporarily mark the current cell as visited by replacing its value.

Now we try all 4 directions:

boolean right = isWordConstructed(board, row, col + 1, word, index + 1);
boolean down  = isWordConstructed(board, row + 1, col, word, index + 1);
boolean left  = isWordConstructed(board, row, col - 1, word, index + 1);
boolean up    = isWordConstructed(board, row - 1, col, word, index + 1);

Backtracking:

board[row][col] = ch;  // restore original character

Restore the original value after exploring all directions — this is backtracking.

The function returns true if any one of the recursive calls successfully constructs the word.

Code:

public class WordSearch {
    public static void main(String[] args) {
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";

        boolean ans = exist(board, word);
        System.out.println(ans);
    }

    static boolean exist(char[][] board, String word) {
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (board[row][col] == word.charAt(0)) {
                    if (isWordConstructed(board, row, col, word, 0)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private static boolean isWordConstructed(char[][] board, int row, int col, String word, int index) {
        if (index == word.length()) {
            return true;
        }

        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != word.charAt(index)) {
            return false;
        }

        char ch = board[row][col];
        board[row][col] = '#'; // mark as visited

        boolean right = isWordConstructed(board, row, col + 1, word, index + 1);
        boolean down  = isWordConstructed(board, row + 1, col, word, index + 1);
        boolean left  = isWordConstructed(board, row, col - 1, word, index + 1);
        boolean up    = isWordConstructed(board, row - 1, col, word, index + 1);

        board[row][col] = ch; // backtrack

        return right || down || left || up;
    }
}

Key Takeaways:

• The Word Search problem is a classic example of using DFS with backtracking in a 2D matrix.
• The recursive function explores all four directions (up, down, left, right) to find the next matching character.
• Visited cells are temporarily marked (e.g. with '#') to avoid revisiting and are restored after recursion — this is the essence of backtracking.
• Time complexity in the worst case is:
  O(N × M × 4^L), where:
  • N × M is the size of the board
  • L is the length of the word
• Efficient pruning (via bounds checks and character mismatches) helps avoid unnecessary recursive calls, improving practical performance.

---

4. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

5. Conclusion:

In this blog of my dsa journey, we explored three classic backtracking problems — N Knights Problem, Sudoku Solver, and Word Search. Each of these challenges highlights the power of recursion and constraint-based decision making.

• The N Knights Problem taught us how to place pieces safely with limited movement rules.
• The Sudoku Solver reinforced how constraint satisfaction problems can be handled efficiently with recursion and pruning.
• The Word Search problem showed how to explore a 2D grid using depth-first search and careful backtracking.

All three problems use a similar pattern: explore → validate → recurse → backtrack. Practicing these helps build a strong foundation in backtracking, recursion, and 2D array manipulation — essential skills for tackling more advanced problems in competitive programming and technical interviews.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.