LogicGamesSolver

Python tool for solving logic games with AI, Computer Vision and a pinch of Deep Learning.

---

---

Table of contents

• Basic Overview
• Project structure
• System Requirements
• Setup
• How it works
• Games included
• References

Basic Overview

This project combines Computer Vision and Artificial Intelligence to solve logic puzzle games like Sudoku, Stars Battle and Skyscrapers.

The execution consists of 2 phases:

1. Board Detection	2. Game solving
The software detects the board showed by the user (in real-time or analyzing a local image). Then analyzes the structure to understand the needed informations to solve the game.	The information collected is then used to solve the puzzle considering it as a Constraints Satisfaction Problem using a Backtracking algorithm to find the solution, given the game rules.

Language: Python

Frameworks: OpenCV, Tensorflow

Algorithms: Constraints Satisfaction Problem Backtracking, Digits Classifier (CNN), Image Contours Finding and Warping

Project structure

LogicGamesSolver
│   README.md
│   LICENSE
│
└───imgs
│   │   screen_XXX	Screens for project explaination
│   │   ...
│	
│   main.py		Main file to execute the software
│   DigitClassifier.py	Class for digit classification with a pretrained CNN			
│   PuzzleDetector.py	Class for puzzle detection and analyze from an image
│   Solver.py		Class for solving the games given puzzle's informations and rules 		

System Requirements

• Python 3.8

• Numpy 1.19.2

• OpenCV 4.0.1

• Tensorflow 2.3.0

Setup

To run the project, clone it with Git and run the main.py file with desired parameters:

$ git clone https://github.com/fabridigua/LogicGamesSolver
$ cd LogicGamesSolver
$ python main.py sudoku 9 3

There are 4 arguments you can set:

[game name of the game you want to solve] = sudoku | skyscrapers | stars [default: sudoku]

[grid_len number of squares in the side of the puzzle's grid] = Integer es. 5 [default: 9]

[square_len for sudoku, number of squares in an area] = Integer es. 2 [default: 3]

[is_realtime for coose between local or real-time execution] = Boolean es. true [default true]

Note that if you set is_realtime to false you have to put an image file named input_[game].png es. input_stars.png

How it works

This project touches many fields of study:

1. Computer Vision for board detection
2. Deep Learning for puzzle analyzing
3. Artificial Intelligence for puzzle solving

1. Board Detection

The software analyzes the image in input looking for the biggest contour^[1] in the scene.

Once found the puzzle, its image is warped applying a perspective transformation to make the puzzle image a plane.

In real-time mode, the user must press space key to go ahead when the software is recognizing well the puzzle.

2. Puzzle Analyzing

The software analyzes the puzzle board to retrieve the needed informations to solve the game.

If the puzzle includes numbers (like Sudoku and Skyscrapers) a Convolutional Neural Network for digit classifying (trained with the fabulous MNIST^[2] dataset) is executed.

For the Stars game, the board image is processed to find the inner areas. Using OpenCV methods, the boldest contours are highlighted and then the connected components^[3] are analyzed (and drawn in different colors) to find the areas of the grid.

3. Game solving

Once collected all the informations about the structure of the puzzle, the game is represented as a CSP (Constraint Satisfaction Problem) and solved applying a backtracking algorithm. By the game point of view, the CSP^[4] consists in 3 elements:

• Variables: the grid cells to fill

• Domains: the sets of values that each cell can assume

• Constraints: the game's rules

If the input is correct, the algorithm finds the solution with 100% of accuracy, but it can takes a long time basing on grid length (and so the number of variables) and size of domains. For a normal Sudoku scheme it takes 3-5 seconds.

For more details see the article.

Games Included

For now, this projects includes the detection and solving procedures of these games:

• Sudoku [ ex. python main.py sudoku 9 3 ]

  Description: given a grid with some number in range [1,9] , fill the empty cells respecting the rules.

  Parameters:

  ​ grid_len: number of squares in each row, column and inner area (usually 9)

  ​ square_len: number of square in each row and column of a inner area (usually 3)

  Rules:

  • Every row, column and area have to contain all number between 1 and 9

• Stars [ex. python main.py stars 8 1 ]

  Description: given a grid divided into regions insert a star in each row, column and sector.

  Parameters:

  ​ grid_len: number of squares in each row and column

  ​ star_number: number of stars in a inner area (usually 1)

  Rules:

  • Every row, column and sector have to contain only a star (or more if setted with star_number argument)
  • Stars can't be in adjacent cells

• Skyscrapers [ ex. python main.py skyscrapers 8 ]

  Description: given a grid with some numbers near the sides, fill the grid with the number from 1 to grid_len.

  Parameters:

  ​ grid_len: number of squares in each row and column

  Rules:

  • Every row, column and have to contain all number between 1 and grid_len
  • The numbers along the edge of the puzzle indicate the number of buildings which you would see from that direction if there was a series of skyscrapers with heights equal the entries in that row or column.

References

[1]: Contours : Getting Started

[2]: MNIST Dataset

[3]: The connected-component labeling problem: A review of state-of-the-art algorithms

[4]: Constraint satisfaction problem