Skip to content

This repository provides a tree-based framework for solving the Knight's Tour problem using various tree search algorithms, including BFS, DFS, DFS-H1B, and DFS-H2, along with their heuristics. The Knight's Tour problem is a classic combinatorial puzzle in which a knight on a chessboard must visit every square exactly once.

License

Notifications You must be signed in to change notification settings

Pirate-960/Knight-Tour-Problem-Tree-Search-Framework

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation


Knight-Tour-Problem-Tree-Search-Framework

This repository presents an advanced and extensible framework for solving the Knight's Tour Problem, a classic combinatorial puzzle. The framework leverages tree-based search algorithms enhanced with heuristic strategies to tackle the computational challenges associated with this problem.

Problem Overview

The Knight's Tour Problem is a chessboard puzzle where a knight must visit every square exactly once. The problem scales in complexity as the board size ((N)) increases, with the search space expanding exponentially. For example, while a 5x5 board has 304 possible solutions, the number explodes to over (10^{35}) for an 8x8 board. The computational complexity of this problem makes it a rich subject for studying graph traversal, optimization, and search strategies.

The Knight's Tour problem has historical significance, first appearing in Arabic manuscripts in 840 AD. It later caught the attention of European mathematicians, including Euler, and continues to be a fascinating testbed for modern algorithmic techniques.

Problem Variants

Several classifications and extensions exist for the Knight's Tour Problem:

  • Open Tour: The tour does not need to return to the starting square.
  • Closed or Reentrant Tour: The knight returns to the starting square, forming a cycle.
  • Symmetric Tour: Aesthetic tours that exhibit symmetry properties.
  • Any Solution: For large boards, finding just one complete tour is often the primary goal due to the sheer size of the solution space.

Features

1. Search Algorithms Implemented

This framework incorporates a variety of search algorithms, providing insights into different problem-solving approaches:

  • Breadth-First Search (BFS):
    Explores all possible moves level by level. BFS guarantees finding the shortest solution but becomes infeasible for large boards due to high memory usage.

  • Depth-First Search (DFS):
    Explores one path deeply before backtracking. While DFS can find solutions efficiently on smaller boards, it often suffers from dead ends and redundant searches on larger boards.

  • DFS with Warnsdorff's Heuristic (DFS-H1B):
    Implements Warnsdorff's rule to prioritize squares with fewer onward moves, reducing the likelihood of dead ends.

  • DFS with Enhanced Heuristic (DFS-H2):
    Extends Warnsdorff’s method by resolving tie cases using proximity to corners, significantly improving success rates on large boards.

2. Heuristics for Optimization

The repository includes two advanced heuristics to optimize search performance:

  • Warnsdorff’s Rule (H1B):

    • Prefers squares with fewer onward moves, indirectly avoiding dead ends and inaccessible squares.
    • Efficient for moderate board sizes but fails in specific configurations or very large boards ((N > 300)).
  • Enhanced Heuristic (H2):

    • Builds on H1B by prioritizing squares closer to the corners in tie cases.
    • Provides complete tours on large boards in (O(N^2)) time without backtracking.
    • Successfully addresses cases where H1B fails, making it robust for practical applications.

The heuristic functions demonstrate how intelligent decision-making can dramatically reduce the search space, transforming intractable problems into solvable ones.

3. Tree Framework

At the core of the implementation lies a tree-based representation of the problem:

  • Nodes represent the knight's current position.
  • Edges correspond to valid knight moves.
  • The search tree is dynamically constructed to explore possible tours.
  • The framework supports modular integration of new algorithms or heuristics.

This structure facilitates a systematic exploration of solutions and enables efficient pruning of non-viable paths.

4. Historical and Mathematical Context

  • Early Records: The first recorded Knight’s Tours were found in Arabic manuscripts around 840 AD.
  • Mathematical Exploration: Euler analyzed the problem in the 18th century, paving the way for studies in graph theory and combinatorial optimization.
  • Modern Algorithms: Advances in computational power have enabled exhaustive enumeration and heuristic-driven exploration for larger boards.

5. Comparative Analysis of Algorithms

The repository includes tools to compare the performance of various search strategies:

  • Execution Time: Benchmarks show the efficiency of heuristic-guided methods compared to brute force.
  • Solution Quality: H2 consistently outperforms H1B on challenging boards, ensuring fewer dead ends and faster convergence.
  • Scalability: The framework demonstrates the limitations of uninformed search and highlights the scalability of heuristic methods for large boards.

6. Applications and Implications

Beyond its recreational appeal, the Knight’s Tour Problem has applications in:

  • Robotics: Path planning for mobile robots navigating constrained spaces.
  • Algorithm Design: Benchmarking new search and optimization techniques.
  • Educational Tools: Teaching graph traversal, heuristics, and combinatorial problem-solving.

Contributing

We welcome contributions to enhance and expand this framework. Possible areas of contribution include:

  • Adding new search algorithms or heuristics.
  • Improving the visualization of tours and search processes.
  • Extending the framework to support non-standard chessboards or additional constraints.
  • Conducting detailed performance analyses and publishing results.

Contribution Guidelines

  1. Fork the repository.
  2. Create a new branch for your changes.
  3. Submit a pull request with a clear description of your modifications.

License

This project is licensed under the MIT License. See the LICENSE file for details.

Acknowledgments

Special thanks to:

  • Researchers like Luis Paris for pioneering heuristic strategies for the Knight's Tour Problem.
  • Historical mathematicians, such as Euler, for their foundational work in graph theory and combinatorial puzzles.
  • The open-source community for their contributions and support in developing computational frameworks.

About

This repository provides a tree-based framework for solving the Knight's Tour problem using various tree search algorithms, including BFS, DFS, DFS-H1B, and DFS-H2, along with their heuristics. The Knight's Tour problem is a classic combinatorial puzzle in which a knight on a chessboard must visit every square exactly once.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published