Knight's Tour (Multithreaded Solver)

This project implements a multi-threaded solution to the classic Knight's Tour problem.
The goal is to determine whether a knight can visit every square on an M × N chessboard exactly once.

This implementation uses a parallelized backtracking approach to explore multiple potential paths simultaneously, identifying both:

• Open Tours – the knight ends on a square different from the start
• Closed Tours – the knight ends one legal move away from the starting square

---

Core Technical Features

Multithreading with POSIX Threads (pthreads)

• Instead of a standard recursive depth-first search (DFS), the program spawns new threads at decision points where multiple valid moves exist.

Concurrency Control

• Uses pthread_mutex_t to protect shared global counters such as:
  • next_thread_number
  • total_tours
• Prevents race conditions during parallel execution.

Dynamic Memory Management

• Manages complex memory allocation for board states across threads.
• Ensures no memory leaks despite a highly branched execution tree.

Systems Programming Concepts

• Implements low-level synchronization primitives.
• Uses thread creation and pthread_join to aggregate results from child threads back to the main process.

---

How It Works

1. Parallel Exploration

• The algorithm begins at a user-defined starting coordinate (r, c).

Execution strategy:

• Single valid move:
  The current thread continues execution to minimize overhead.
• Multiple valid moves:
  The program spawns new threads to explore each path in parallel, turning the search into a concurrent tree traversal.

---

2. Synchronization & Data Integrity

To track global progress safely, a mutex is used during thread creation and when updating shared statistics:

• max_squares
  Tracks the maximum number of squares visited in any attempt.
• total_open_tours
  Incremented when a thread completes a full open tour.
• total_closed_tours
  Incremented when a thread completes a full closed tour.

---

3. Knight’s Movement Logic

• Validates the knight’s L-shaped movement.
• Ensures:
  • Moves remain within board boundaries.
  • Squares are not revisited.
• Board representation:
  • . — empty square
  • K — visited square

---

Usage

Compilation

Compile using gcc with the pthread library:

gcc -Wall -Werror hw3.c -lpthread -o knight_solver.out