Backtracking Visualization Project

This project is an interactive visualization tool for backtracking algorithms, demonstrating two classic problems: Rat in a Maze and N-Queens. It provides both a web-based interface (built with HTML, CSS, and JavaScript) and a console-based version (implemented in C++). The tool helps users understand the backtracking process through step-by-step animations, explanations, and real-time visualizations, making it ideal for learning Data Structures and Algorithms (DSA).

The web version offers a modern, user-friendly UI with customizable options, while the C++ version provides a simple console-based simulation for quick testing without a browser.

---

Features

Core Features

• Interactive Backtracking Visualization: Step-by-step animation of the backtracking process for both problems, showing trial-and-error paths, placements, and backtracks.
• Two Classic Problems:
  • Rat in a Maze: Find all possible paths for a rat to navigate from the top-left to the bottom-right of a maze, avoiding walls and without revisiting cells. Supports custom or randomly generated mazes.
  • N-Queens: Place N queens on an N×N chessboard such that no two queens attack each other (no shared row, column, or diagonal).
• Modes of Operation:
  • Automatic Mode: Runs the visualization with adjustable speed (100ms to 2000ms delay per step).
  • Manual Mode: User-controlled stepping through the algorithm via a "Next Step" button.
• Explanations and Tutorials:
  • In-app modal tutorial for new users.
  • Real-time step explanations (e.g., "Trying to place queen at row X, col Y" or "Moving to (r,c) with path: DLR").
  • DSA concept overview, including time and space complexities (e.g., O(4^(n^2)) for Rat in Maze, O(N!) for N-Queens).
• Input Customization:
  • For Rat in Maze: Enter maze size (n ≥ 2), generate random mazes, or set custom mazes (0 for walls, 1 for open paths). Clear maze removes the current grid and associated buttons.
  • For N-Queens: Enter board size (n ≥ 4).
• Output Display:
  • Lists all found paths/solutions.
  • Visual grid/board with color-coded cells (e.g., paths in green, walls in red for web; symbols like '#' for walls, 'R' for rat in console).
• Responsive Design (Web Version): Adapts to mobile and desktop screens with adjustable cell sizes.
• Error Handling: Validates inputs (e.g., maze size, blocked start/end) and shows alerts for invalid cases.
• Console Version (C++) Specifics:
  • Menu-driven interface for selecting problems.
  • Console-based visualization using symbols (e.g., 'R' for rat, 'Q' for queens, '#' for walls).
  • Backtracking with delays for step-by-step viewing.
  • Platform-independent clear screen and delay functions.

Technical Highlights

• Web Version: Built with JavaScript (ES modules), Tailwind CSS for styling, and custom CSS for neon-themed UI.
• C++ Version: Uses standard libraries like <iostream>, <vector>, and <chrono> for delays; supports Windows and Unix-like systems.
• Backtracking Implementation: Recursive functions with safe checks, marking visited cells, and backtracking to explore all possibilities.
• Visualization Techniques:
  • Web: DOM manipulation for grid updates, CSS transitions for smooth animations (e.g., rat movement, queen opacity).
  • Console: Repeated screen clearing and printing with delays.

---

Project Structure

• backtracking-visualization/
• ├── index.html # Main HTML file for web version
• ├── style.css # Custom CSS styles
• ├── src/
• │ ├── main.js # Entry point for web logic
• │ ├── nQueens.js # N-Queens solver and visualizer
• │ ├── ratInMaze.js # Rat in Maze solver and visualizer
• │ └── utils.js # Utility functions (delays, explanations)
• └── cpp_version/
• └── main.cpp # Console-based C++ implementation

---

Usage

Web Version

1. Open index.html in a browser.
2. Select a problem (Rat in a Maze or N-Queens).
3. Choose visualization mode (Auto / Manual) and speed.
4. For Rat in a Maze:
   • Enter size.
   • Generate random or custom maze.
   • Click Run.
   • Use Clear Maze to remove the current grid and its buttons.
5. For N-Queens:
   • Enter N.
   • Click Start.
6. Watch the animation and view results.

C++ Version

1. Run the executable.
2. Select option from menu:
   • 1 for Rat in a Maze
   • 2 for N-Queens
   • 3 to Exit
3. Follow prompts to input maze/board size and data.
4. Observe console updates with delays.

---

Future Enhancements

To expand the project's scope and educational value, the following features are planned:

Additional Problems

• Sudoku Solver: Visualize number placements and conflict resolution on a 9×9 grid.
• Knight's Tour: Show a knight's path covering all squares on a chessboard exactly once.
• Graph Coloring: Assign colors to graph vertices with no adjacent conflicts.

Visualization & Insights

• Time Complexity Visualization: Add real-time graphs or counters showing recursion depth, nodes explored, and estimated time complexity (e.g., branching factor visualization).
• Space Complexity Insights: Display recursion stack usage or memory footprints during execution.

Advanced Modes

• Pause/resume functionality.
• Path replay.
• Export solutions as images/videos.

Performance & Optimization

• Multi-Threading (C++): Optimize larger problems with parallel exploration (if feasible for backtracking).
• Benchmarking: Compare execution times across problems and input sizes.

Cross-Platform & AI

• Mobile App Version: Port to React Native for cross-platform mobile access.
• AI Integration: Use machine learning to suggest optimal starting points or predict solution counts.

---

💡 Contributions to these or other ideas are welcome!