Color Block Jam

A Java-based solver for a block-puzzle game, built as part of a Smart Search Algorithms course.

The project combines a JavaFX graphical interface with a state-space representation of the puzzle and multiple search algorithms. The main goal is to allow the computer to find solutions and compare different search strategies.

Overview

The board contains colored blocks, matching gates, walls, movement restrictions, and optional movement locks.

A solution consists of moving blocks through valid states until every block reaches its matching gate.

The application provides an interactive graphical interface and can automatically solve a board using several search algorithms.

Features

• Interactive JavaFX board.
• Drag blocks using the mouse.
• Undo previous moves.
• Reset the current puzzle.
• Load puzzle configurations from JSON files.
• Multiple predefined boards in boards/.
• Automatic solving using several search algorithms.
• Displays the number of moves in the UI.
• Reports algorithm execution statistics in the console:
  • Execution time
  • Estimated memory usage
  • Number of iterations
  • Number of solution moves

Search Algorithms

The project implements the following algorithms:

• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Recursive Depth-First Search (RDFS)
• Uniform-Cost Search (UCS)
• Greedy Best-First Search
• A* Search
• Hill Climbing

All search algorithms operate on the same Board state representation through the SearchAlgorithm interface.

Heuristic and Search Design

For informed search, the project uses the sum of Manhattan distances between blocks and their corresponding gates as a heuristic:

h(n) = Σ ManhattanDistance(block, matching gate)

A* evaluates:

f(n) = g(n) + h(n)

Uniform-Cost Search additionally accounts for movement cost based on the moved block and gives a strong preference to states in which a block exits through its matching gate.

The search implementation also keeps track of visited states or best-known costs to avoid unnecessary exploration.

Board Representation

The board is modeled using:

• Board — complete puzzle state and state transitions.
• Grid — 2D cell occupancy and block movement/collision rules.
• Block — colored block shape, positions, allowed movement direction, and optional movement threshold.
• Gate — target area for blocks of a matching color.
• Wall — blocked cells.
• Cell — common board-cell abstraction.

Blocks may have:

• Horizontal movement restrictions.
• Vertical movement restrictions.
• Free movement in both directions.
• A movement threshold that keeps them frozen until enough blocks have exited.

State Expansion

For each board state, possible moves are generated by attempting to move each block in each of the four directions:

UP
DOWN
LEFT
RIGHT

Invalid moves caused by walls, other blocks, board constraints, or movement restrictions are rejected.

Successful states are copied into new Board instances and used as nodes in the search tree.

State Hashing

The project includes Zobrist hashing for board states.

Zobrist generates deterministic random values for board positions and cell types, while Board uses the resulting hash to support efficient state comparison and hashing.

This is particularly useful for search algorithms that need to store many explored states in hash-based collections.

Puzzle Configuration

Boards are loaded from JSON files using Gson.

Example structure:

{
  "rows": 8,
  "cols": 7,
  "shapes": [],
  "blocks": [],
  "exists": []
}

The project currently includes:

boards/
├── board1.json
├── board2.json
└── board3.json

Project Structure

src/
├── controllers/
│   └── GameController.java
├── models/
│   ├── Block.java
│   ├── Board.java
│   ├── Cell.java
│   ├── Gate.java
│   ├── Grid.java
│   └── Wall.java
├── search_algorithms/
│   ├── SearchAlgorithm.java
│   ├── DFS_BFS.java
│   ├── RDFS.java
│   ├── UCS_Greedy_AStar.java
│   └── HillClimbing.java
├── util/
│   ├── Algorithm.java
│   ├── Direction.java
│   ├── Move.java
│   ├── MoveResult.java
│   ├── Node.java
│   ├── Position.java
│   └── Zobrist.java
├── view/
│   ├── CellView.java
│   ├── GameView.java
│   └── GridView.java
├── GameInitializer.java
└── Main.java

Requirements

• JDK 18
• JavaFX 21.x
• Gson 2.11.x

The original project was developed in IntelliJ IDEA as a plain Java project rather than a Maven/Gradle project.

Running in IntelliJ IDEA

1. Configure the JDK

Set the project SDK to JDK 18:

File → Project Structure → Project
→ Project SDK → JDK 18

2. Add JavaFX

Download/extract a JavaFX SDK and add its lib directory as an IntelliJ library.

The original project configuration references:

../javafx-sdk-21.0.9/lib

relative to the project directory.

In IntelliJ:

File
→ Project Structure
→ Libraries
→ +
→ Java
→ select javafx-sdk-21.0.9/lib

Then make sure the library is added as a dependency of the project module.

3. Add Gson

The project uses Gson for loading JSON board files.

The original project expects:

libs/gson-2.11.0.jar

Add that JAR to the module dependencies if it is not already configured.

4. Run configuration

Because JavaFX is modular, add the JavaFX module path to the run configuration.

Example for Windows:

--module-path "C:\path\to\javafx-sdk-21.0.9\lib" --add-modules javafx.controls

Example for Linux:

--module-path /path/to/javafx-sdk-21.0.9/lib --add-modules javafx.controls

Then run:

Main

Notes

This project was created for a Smart Search Algorithms course. Its main purpose was to model a puzzle as a state-space search problem and implement multiple uninformed, informed, and local search strategies over the same representation.

The project is especially useful as a demonstration of:

• Graph/state-space modeling
• Search algorithms
• Heuristics
• Cost functions
• State deduplication
• Hashing
• Object-oriented design
• JavaFX GUI programming
• JSON-based configuration

Author

Khaled Tello