🔢 NumMatch Solver

✨ Project Overview

This project implements a solver for a specific variation of the classic Number Match (or "Numbers Game") puzzle. The game is played on a fixed $4 \times 5$ rectangular grid, and the objective is to clear all numbers by finding valid pairs that can be matched and removed.

The core of this project is the implementation of a Breadth-First Search (BFS) based algorithm to exhaustively explore the move space and determine if a given initial board is solvable.

🎯 Core Features

• Board Initialization (randfill()): Randomly fills the fixed $4 \times 5$ grid with digits from 1 to 9.
• Pair Removal (take()): Executes a valid match, clearing the two numbers from the board.
• Solvability Check (solve()): Implements the required BFS search algorithm to verify if the board can be fully cleared (all cells become 0).
• Assertion Testing (test()): Includes comprehensive tests for helper functions (value checks, connectivity) and overall solver logic.

🧠 Algorithm: Brute-Force Breadth-First Search (BFS)

The solver uses a strict, non-recursive, queue-like approach, mapping directly to a standard BFS implementation, as dictated by the assignment:

1. State Storage: A large, fixed-size array (MAX_BOARDS = 100,000) is used as a queue/list to store all unique board states encountered during the search.
2. Initialization: The initial board is placed at the front of the list (list_head = 0, list_tail = 1).
3. Exploration: The algorithm iterates through the list index by index (list_head), processing the current (parent) board state.
4. Generating Children: All possible valid pairs on the parent board are identified, and the resulting (child) board states are generated.
5. Uniqueness and Goal Check:
   • If a generated child board is the empty (final) board, the search terminates successfully.
   • If the child board is unique (not seen before), it is added to the end of the list (list_tail).
   • If the child board is a duplicate, it is ignored.
6. Termination: The process continues until a solution is found or the entire list of possible states is exhausted.

Matching Rules

A pair of numbers can be matched and removed if they satisfy both value and connectivity rules:

Rule Category	Condition
Value Match	The numbers are the same (e.g., 4 and 4) OR they sum to ten (e.g., 3 and 7).
Connectivity	1. They are 8-connected (adjacent horizontally, vertically, or diagonally). OR 2. They are connected by a clear path (no other non-zero numbers between them) along a horizontal or vertical line.

🛠️ Implementation & Constraints

• Language: C (C99 standard assumed).
• Data Structures: Strictly uses fixed-size arrays for the board list (no dynamic arrays or linked lists), adhering to assignment constraints.
• File Structure:
  • nm.h: Function prototypes, constants (HEIGHT, WIDTH, MAX_BOARDS).
  • nummatch.c: Main logic implementation.
• Output: The program runs silently, reporting results via exit status.

🚀 Getting Started

Build Instructions

You can use the provided Makefile to easily compile and run the project.

# Compile the main program
make nummatch