4 

 

Abstract 

 

With the advent of solutions provided to science by computers, automation solidified 

its  place  as  the  basis  of  performance.  Through  automated  solvers,  dynamic  problems  of 

increased complexity  and changing  nature  are solved. Although  solvers provide solutions  in 

such problems, studying and optimizing them brings new questions to the surface. One of the 

challenges is solving games as their extensive studies leads to complex computing problems. 

Utilizing  a  medium  such  as  games  facilitates  the  observation  of  solver  results.  As  a  result, 

there have been many milestones in the history of game solving. 

 

In  the  present  diploma  thesis,  the  game  of  Minesweeper  is  examined  and  a  unique 

approach  is  implemented  with  the  aim  of  extending  pre-existing  methods  of  visual  parsing 

and solving. The Automated Solver combines machine vision techniques to find the board and 

identify  the  state  of  individual  blocks.  At  the  same  time,  it  utilized  deterministic  algorithms 

for  simple  board  states  while  modeling  the  more  complex  ones  as  Constraint  Satisfaction 

Problems (CSP). This model is input in a CP-SAT solver based on the hybrid LCG technique, 

to  be  encoded  and  solved  by  the  internal  SAT  solver  with  the  corresponding  computational 

advantages.  Based  on  the  solutions  provided  by  CP-SAT  for  possible  mine  assignments,  a 

possibility analysis is performed on the board giving precision to the next moves. 

 

The  implementation  of  the  diploma  thesis  presents  both  the  advantages  of  visual 

parsing and solution as a CSP, as well as the limitations and challenges involved. At the same 

time, through an experimental process, the correlations between metrics and the influence of 

mine density are analyzed. 

 

 

 

 

Keywords:

 Machine vision, digital image processing, image parsing, constraint satisfaction 

problems, C#