Interactive Programming Education Platform

Logic Practice

A C++ Crossword Puzzle Solver is a software application created to autonomously populate a provided crossword grid with a predetermined set of words.

Problem Statement:

A crossword puzzle consists of:

✅ A grid of cells (usually square or rectangular), some of which may be blacked out.
✅ A word list that contains the words to be placed in the grid.
✅ Rules to ensure that words fit into the grid horizontally or vertically without conflict.

The objective is to fit all terms from the list into the grid while ensuring that:

✅ The words adhere to the grid's specifications, such as cell sizes and intersections.
✅ There are no clashes between letters where words intersect.

Example:

Example


#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Check if a word can be placed horizontally at the given position
bool canPlaceHorizontally(vector<vector<char>>& grid, const string& word, int row, int col) {
    if (col + word.size() > grid[0].size()) return false;
    for (int i = 0; i < word.size(); ++i) {
        if (grid[row][col + i] != '-' && grid[row][col + i] != word[i]) return false;
    }
    return true;
}
// Check if a word can be placed vertically at the given position
bool canPlaceVertically(vector<vector<char>>& grid, const string& word, int row, int col) {
    if (row + word.size() > grid.size()) return false;
    for (int i = 0; i < word.size(); ++i) {
        if (grid[row + i][col] != '-' && grid[row + i][col] != word[i]) return false;
    }
    return true;
}
// Place a word horizontally in the grid
void placeHorizontally(vector<vector<char>>& grid, const string& word, int row, int col, vector<bool>& marker) {
    for (int i = 0; i < word.size(); ++i) {
        if (grid[row][col + i] == '-') {
            grid[row][col + i] = word[i];
            marker[i] = true; // Mark cells modified
        }
    }
}
// Place a word vertically in the grid
void placeVertically(vector<vector<char>>& grid, const string& word, int row, int col, vector<bool>& marker) {
    for (int i = 0; i < word.size(); ++i) {
        if (grid[row + i][col] == '-') {
            grid[row + i][col] = word[i];
            marker[i] = true; // Mark cells modified
        }
    }
}
// Remove a word placed horizontally
void removeHorizontally(vector<vector<char>>& grid, const string& word, int row, int col, const vector<bool>& marker) {
    for (int i = 0; i < word.size(); ++i) {
        if (marker[i]) {
            grid[row][col + i] = '-';
        }
    }
}
// Remove a word placed vertically
void removeVertically(vector<vector<char>>& grid, const string& word, int row, int col, const vector<bool>& marker) {
    for (int i = 0; i < word.size(); ++i) {
        if (marker[i]) {
            grid[row + i][col] = '-';
        }
    }
}
// Backtracking function to solve the crossword
bool solveCrossword(vector<vector<char>>& grid, vector<string>& words, int index) {
    if (index == words.size()) return true; // All words placed
    string word = words[index];
    for (int row = 0; row < grid.size(); ++row) {
        for (int col = 0; col < grid[0].size(); ++col) {
            // Try placing the word horizontally
            if (canPlaceHorizontally(grid, word, row, col)) {
                vector<bool> marker(word.size(), false);
                placeHorizontally(grid, word, row, col, marker);
                if (solveCrossword(grid, words, index + 1)) return true;
                removeHorizontally(grid, word, row, col, marker);
            }
            // Try placing the word vertically
            if (canPlaceVertically(grid, word, row, col)) {
                vector<bool> marker(word.size(), false);
                placeVertically(grid, word, row, col, marker);
                if (solveCrossword(grid, words, index + 1)) return true;
                removeVertically(grid, word, row, col, marker);
            }
        }
    }
    return false; // No solution found
}
// Utility function to print the crossword grid
void printGrid(const vector<vector<char>>& grid) {
    for (const auto& row : grid) {
        for (char cell : row) {
            cout << cell << ' ';
        }
        cout << endl;
    }
}
int main() {
    // Define the crossword grid
    vector<vector<char>> grid = {
        {'-', '-', '-', '#', '-', '-'},
        {'-', '-', '-', '-', '-', '-'},
        {'-', '#', '-', '-', '#', '-'},
        {'-', '-', '-', '-', '-', '-'},
        {'-', '-', '-', '#', '-', '-'}
    };
    // Define the list of words
    vector<string> words = {"apple", "pear", "grape", "peach"};
    cout << "Initial Grid:\n";
    printGrid(grid);
    // Solve the crossword
    if (solveCrossword(grid, words, 0)) {
        cout << "\nSolved Grid:\n";
        printGrid(grid);
    } else {
        cout << "\nNo solution exists.\n";
    }
    return 0;
}

Output:

Output


Initial Grid:
- - - # - - 
- - - - - - 
- # - - # - 
- - - - - - 
- - - # - - 
Solved Grid:
a - p # - - 
p p e a c h 
p # a - # - 
l g r a p e 
e - - # - -

Explanation:

Problem Representation

The program operates on a grid and a list of words:

✅ The grid is a two-dimensional matrix where:
✅ '-' represents an empty cell that can hold a letter.
✅ '#' represents a blocked cell that cannot hold a letter.
✅ The list of words contains all the words to be placed into the grid. Each word must fit into a sequence of '-' cells either horizontally or vertically.

Solving Strategy

The program uses backtracking, a recursive technique where:

✅ Words are placed one by one into available slots in the grid.
✅ If a word fits, the program proceeds to the next word.
✅ If a conflict arises (e.g., a word cannot fit), the program undoes the placement of the previous word and tries a different arrangement.

Core Components

a. Word Placement Check

Before inserting a word, the software verifies that it is suitable for the designated position:

✅ In a horizontal orientation: The word's length must align with the row limits, and each character should correspond to the letters already present in the grid or vacant spaces ('-').
✅ In a vertical orientation: The word's length must align with the column limits, and each character should match the existing letters in the grid or empty cells.

This step guarantees that inserting the word does not break any crossword regulations, like conflicting letters in overlapping words.

b. Word Placement

If the word successfully meets the placement criteria:

✅ The word is integrated into the grid by substituting the '-' cells with the letters of the word.
✅ A marker is employed to monitor the cells that underwent modifications during the placement. This marker plays a crucial role in the backtracking procedure by enabling the software to reverse only the alterations made while positioning the current word.

c. Backtracking

Backtracking ensures that if a word cannot be placed in any slot, the program can revert to a previous state and try an alternative arrangement. The steps are below:

✅ Remove the word using the marker, restoring the grid to its previous state.
✅ Try placing the word in the next available slot.
✅ If all slots for the current word are exhausted, the program backtracks to the previous word.

This methodical investigation guarantees the testing of every conceivable word positioning.

Iterative Procedure

The solver works recursively:

✅ It starts with the first word in the list and tries to place it in all valid slots in the grid.
✅ If successful, it moves to the next word.
✅ If a conflict arises while placing a later word, it backtracks and adjusts the placement of the earlier word.
✅ The recursion terminates successfully when all words are placed, or it concludes failure if no arrangement is possible.

Handling Horizontal and Vertical Placement

The software manages the positioning of words in two different orientations:

Horizontal Positioning:

✅ The software locates a row and verifies if the term can be accommodated within the horizontal spaces provided.
✅ This guarantees that the term aligns with the current characters or vacant squares.
✅ The software locates a specific column and verifies if the term can be accommodated in the vertical spaces provided.
✅ Comparable validations guarantee alignment with current characters or vacant cells.

For every orientation, the software tries positioning elements and reverts if needed.

Helper Functions

Several helper functions support the solver:

Validation Functions:

These functions verify whether a term is compatible with a designated space, ensuring no clashes occur.

Placement Functions:

✅ These functions are responsible for adding a word to the grid and keeping track of any modifications made.

Removal Methods:

✅ These functions reverse the positioning of words by utilizing the marker to bring back the grid to its original state.

Special Scenarios

The solver is robust enough to handle various scenarios:

✅ Blocked Cells ('#'): Words cannot overlap or pass through blocked cells, so placement checks account for them.
✅ Intersecting Words: When two words share a cell, their letters must match.
✅ Grid Bounds: Words cannot exceed the grid's boundaries.

Output

The software displays:

✅ The completed puzzle grid, in case a solution is discovered, reveals all words positioned following the guidelines of the crossword.
✅ An alert message is shown in case there is no way to arrange the words to fit the grid.

Complexity analysis:

Time Complexity

Word Placement

For every individual word, the solver systematically tests all potential locations within the grid to ascertain if the word is a feasible fit. This process includes:

✅ Examining each row and column thoroughly.
✅ Confirming suitability for both horizontal and vertical orientations.

If the grid is of size m×n and contains k words, the maximum number of locations to examine for a single word is roughly m×n. Each location necessitates comparing the length, l, of the word with the cells in the grid.

Cost per word insertion: O(m×n×l).

Backtracking

In the worst case, the solver explores all possible arrangements of the k words. For each word:

✅ There are O(m×n) placement options.
✅ The program tries each option recursively, leading to a branching factor of O(m×n).
✅ Thus, the worst-case time complexity is: O((m×n) k×l)

Space Complexity

Grid Storage

The grid is illustrated as a 2D array with dimensions m×n. The storage needed for the grid is O(m×n).

Vocabulary List

The collection of k terms is maintained in an array or vector, necessitating storage that scales with the combined length of all words: O(k×l)

Marker Array

The marker array keeps a record of the grid cells that were altered for every word placement. Its size is proportional to the length of the word: O(l)

Total Space Complexity

Combining all elements results in a space complexity of O(m×n+k×l+k+l)

For extensive grids, the grid storage complexity of O(m×n) is the predominant factor.

Advantages of a Crossword Puzzle

Automation and Efficiency

✅ The solver automates the tedious task of manually filling crossword grids, saving time and effort.
✅ It explores all possible solutions systematically, ensuring that no valid configuration is overlooked.

Flexibility

✅ Can handle grids of different sizes and structures, including complex puzzles with blocked cells or predefined letters.
✅ Works with word lists of varying lengths, accommodating a wide range of puzzle requirements.

Scalability

✅ The program can be extended to support larger grids or additional rules with minimal changes.
✅ Modular design allows for easy adjustments to handle more complex crossword features.

Backtracking Accuracy

✅ Backtracking ensures that every possible arrangement of words is explored, providing reliable results for solvable puzzles.
✅ Invalid configurations are pruned early, reducing computational waste.

Reusability

✅ Components such as grid validation and word placement can be reused in other programs, like crossword generators or word-based games.

Disadvantages of a Crossword Puzzle

Exponential Time Complexity

✅ The backtracking algorithm has exponential complexity, making it inefficient for large grids or long word lists.
✅ Solving complex puzzles with numerous constraints may require significant computational time.

Memory Usage

✅ Larger grids and longer word lists consume more memory, especially when dealing with recursion stacks and grid states.
✅ For huge puzzles, this can lead to performance bottlenecks or even memory exhaustion.

Limited Practical Use

✅ Most crossword puzzles are solved manually for entertainment, limiting the real-world application of an automated solver.
✅ It may not handle human-centric nuances, such as aesthetic preferences in puzzle design.

Difficulty in debugging

✅ Recursive backtracking can be challenging to debug due to the deep call stack and dynamic nature of state changes.
✅ Errors in validation or backtracking logic may lead to incorrect solutions or infinite recursion.

Dependence on Input Quality

✅ The solver relies on a well-formed grid and a valid word list. Incorrect input (e.g., incompatible word lengths) can cause the program to fail or produce meaningless results.
✅ It cannot generate meaningful solutions for poorly designed puzzles with unsolvable constraints.

Properties of a Crossword Puzzle

Backtracking-Based Problem Solving

✅ Recursive Exploration: The solver uses backtracking to explore all possible placements of words in the grid.
✅ Branch Pruning: As soon as an invalid placement is detected, the solver backtracks, saving computational effort by avoiding unnecessary checks.

Flexible Grid Handling

✅ Dynamic Grid Dimensions: The program can handle grids of varying sizes, ensuring versatility for different crossword puzzles.
✅ Blocked Cells Support: It respects blocked cells ('#'), ensuring words do not overlap or pass through them.

Validity Checks

✅ Horizontal and Vertical Validation: Ensures that words fit the grid boundaries and do not conflict with existing letters.
✅ Letter Matching: Supports intersecting words by checking that shared cells contain matching letters.
✅ Boundary Management: Prevents words from exceeding the grid dimensions.

Efficient Undo Mechanism

✅ Marker-Based Tracking: Tracks modified grid cells during word placement, enabling efficient removal when backtracking.
✅ Selective Restoration: Ensures only relevant changes are undone, preserving the integrity of the grid for other words.

Crossword Puzzle Solver In C++