msjidandClaude Haiku 4.5
698ffacd11
- Add clear project description and features - Improve installation and usage instructions - Add output format documentation - Include project structure - Add algorithm details section - Fix grammar and formatting - Add GraphViz visualization instructions Co-Authored-By: Claude Haiku 4.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01PgzMA4na39RHxCyPHGSPKs
82 lines
2.0 KiB
Markdown
82 lines
2.0 KiB
Markdown
# Knight's Shortest Path Solver
|
|
|
|
A Python-based algorithm that finds all shortest paths for a knight on an empty chessboard.
|
|
|
|
## Problem Description
|
|
|
|
Given two positions on a standard 8x8 chessboard, this program computes:
|
|
|
|
- **All minimum-length move sequences** to get a knight from the starting position to the destination
|
|
- **A graph visualization** (in GraphViz/DOT format) showing all shortest paths
|
|
|
|
## Features
|
|
|
|
- Finds all optimal solutions (not just one)
|
|
- Generates GraphViz DOT files for visualization
|
|
- Containerized execution for consistency
|
|
- Configurable output naming
|
|
|
|
## Prerequisites
|
|
|
|
- Docker (for containerized execution)
|
|
- Python 3.7+ (for running directly)
|
|
- GraphViz (optional, for rendering DOT files)
|
|
|
|
## Installation & Usage
|
|
|
|
### Using Docker (Recommended)
|
|
|
|
Build and run the algorithm:
|
|
|
|
```bash
|
|
./run.sh build <dest_x> <dest_y> <output_name>
|
|
```
|
|
|
|
Example:
|
|
```bash
|
|
./run.sh build 4 5 knight_paths
|
|
```
|
|
|
|
Or use an existing image:
|
|
|
|
```bash
|
|
./run.sh run <dest_x> <dest_y> <output_name>
|
|
```
|
|
|
|
### Parameters
|
|
|
|
- `<dest_x>`: X-coordinate of destination (0-7)
|
|
- `<dest_y>`: Y-coordinate of destination (0-7)
|
|
- `<output_name>`: Base name for output files (no extension)
|
|
|
|
### Output
|
|
|
|
The program generates:
|
|
- `<output_name>.txt`: All shortest paths in text format
|
|
- `<output_name>.dot`: GraphViz file for visualization
|
|
|
|
To visualize the graph:
|
|
|
|
```bash
|
|
dot -Tpng <output_name>.dot -o <output_name>.png
|
|
```
|
|
|
|
## Project Structure
|
|
|
|
```
|
|
├── README.md
|
|
├── run.sh # Build and execution script
|
|
├── Dockerfile # Container configuration
|
|
├── src/
|
|
│ └── knight_solver.py # Main algorithm
|
|
└── requirements.txt # Python dependencies
|
|
```
|
|
|
|
## Algorithm Details
|
|
|
|
The solver uses BFS (Breadth-First Search) to explore all possible knight moves, ensuring all minimum-length paths are found. It then constructs a directed graph of these paths and outputs the results in both human-readable and GraphViz formats.
|
|
|
|
## License
|
|
|
|
See LICENSE file for details.
|