UNIVERSITY OF HERTFORDSHIRE
COMPUTER SCIENCE RESEARCH COLLOQUIUM
presents
"Holonomy Decomposition of the N-Queens Puzzle"
of Communicative Robot Gesture"
Dr. Paolo Dini *
(Royal Society Wolfson Biocomputation Laboratory,
Centre for Computer Science and Informatics Research,
University of Hertfordshire)
16 October 2013 (Wednesday)
1 pm -2 pm
Hatfield, College Lane Campus
Seminar Room C152
Everyone is Welcome to Attend
Refreshments will be available
Abstract:
This work is motivated by our desire to understand how Krohn-Rhodes
theory can be used to solve classical problems in computer science, and
to identify the advantages and difficulties of applying such theory. For
this purpose we study the N-Queens puzzle, which consists of finding
a configuration of as many queens as possible on an N x N chessboard
where no queen threatens another. In this talk I focus on N = 3, and
represent the 3-Queens puzzle as a graph-search problem. We formalize this
graph-search with a transformation semigroup, so that it is possible to
analyse it using holonomy decomposition. This yields novel, interpretable
coordinate systems for this type of problem, and we provide some insights
into how variations in modelling choices yield different decomposition
results. I will provide some context for how the N-Queens puzzle fits in
the broader framework of the BIOMICS project (www.biomicsproject.eu),
I will use extensive visualizations of the coordinatization of the
3-Queens puzzle by holonomy decomposition, and will attempt to interpret
the results in terms of their algorithmic relevance.
*This is joint work with Eric Rothstein, Chrystopher L. Nehaniv, Daniel
Schreckling, and Attila Egri-Nagy.
---------------------------------------------------
Hertfordshire Computer Science Research Colloquium
http://cs-colloq.stca.herts.ac.uk