View Proposal

---

Proposer

Zi Hau Chin

Title

Elite-Diversity Beam Search for Path-Based Grid Puzzle Optimisation

Goal

To design, implement, and evaluate an improved beam-search algorithm that balances high-scoring candidate states with structurally diverse board states when solving path-based grid puzzles under limited time and memory.

Description

This project involves developing an intelligent solver for a configurable drag-and-swap grid puzzle inspired by AutoDora. In this type of puzzle, a tile is moved through adjacent cells, swapping positions with other tiles along the selected path. The resulting board is evaluated based on matched tile groups, tile removal, gravity, cascades, and a configurable scoring function. The original AutoDora approach uses fixed-width beam search to expand, score, sort, and prune candidate movement paths First of all, implement random search, greedy search, and conventional fixed-width beam search as baseline algorithms. The main contribution will be Elite-Diversity Beam Search, which divides the available beam into: --An elite portion that retains the highest-scoring candidates。 --A diversity portion that retains high-quality candidates representing different board states。 Board-state diversity will initially be measured by counting the proportion of grid cells that differ between two candidate boards. This approach aims to reduce redundant candidates and prevent the search from converging too early on a narrow set of similar solutions. Also need to develop: --A tested puzzle simulation engine. --A simple board generator for creating reproducible test cases. --A batch experiment runner. --An interactive board editor. --An animated solution viewer. --An algorithm-comparison dashboard. The proposed algorithm will be evaluated against the baseline algorithms using final score, number of combinations, optimality gap on small boards, candidate-state diversity, execution time, memory consumption, and number of explored states. NOTE!!! This project requires student to: --Implement a correct puzzle simulator --Understand heuristic and state-space search --Develop a modified beam-selection strategy --Manage runtime and memory constraints --Design reproducible experiments --Perform statistical and algorithmic evaluation ->It is suitable for a student with strong programming skills and an interest in algorithms, artificial intelligence, optimisation, or game technology.

Resources

Nothing? No external dataset is required. The student will create a reproducible benchmark containing generated puzzle boards.

Background

Programming and data structures；Search algorithms and algorithmic complexity；Object-oriented or modular software design；Basic statistics and experimental evaluation；Python, C++, Java, or another suitable programming language

Url

Difficulty Level

Challenging

Ethical Approval

None

Number Of Students

0

Supervisor

Zi Hau Chin

Keywords

beam search, diversity-aware search, heuristic search, state-space search, grid puzzle optimisation，path planning, puzzle solving, search visualisation, algorithm evaluation, exploitation and exploration

Degrees

Bachelor of Science in Computing Science