Computational intelligence (CI), such as evolutionary computation or swarm intelligence methods, is a set of bio-inspired algorithms that have been widely used to solve problems in areas like planning, scheduling or constraint satisfaction problems. Constrained satisfaction problems (CSP) have taken an important attention from the research community due to their applicability to real problems. Any CSP problem is usually modelled as a constrained graph where the edges represent a set of restrictions that must be verified by the variables (represented as nodes in the graph) which will define the solution of the problem. This paper studies the performance of two particular CI algorithms, ant colony optimization (ACO) and genetic algorithms (GA), when dealing with graph-constrained models in video games problems. As an application domain, the "Lemmings" video game has been selected, where a set of lemmings must reach the exit point of each level. In order to do that, each level is represented as a graph where the edges store the allowed movements inside the world. The goal of the algorithms is to assign the best skills in each position on a particular level, to guide the lemmings to reach the exit. The paper describes how the ACO and GA algorithms have been modelled and applied to the selected video game. Finally, a complete experimental comparison between both algorithms, based on the number of solutions found and the levels solved, is analysed to study the behaviour of those algorithms in the proposed domain.