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