Pic-a-pix Solver

Final project by

Maayan Zehavi

zehavm@post.bgu.ac.il

Introduction

What is a pic-a-pix puzzle?

Pic-a-pix is a paint-by-number logic puzzle, in which cells in a grid must be colored or left blank according to numbers at the side of the grid in order to reveal a hidden picture.

Motivation

Solving logic puzzles is enjoyable most of the time, but once confronting an error or a dead-end situation, one might get frustrated. A little help in the shape of a hint, a glance at the erroneous marks or even just a validation of current progress may give one just the nudge he needs to happily accomplish the puzzle and reveal the desired hidden figure in the puzzle.

Project Goal

To provide several options of solution presentation and validation of a partially-solved puzzle.

Approach and Method

Describe here how you addressed the problem, what observations or ideas you employed, what computational tools you used, etc... It it could simplify the presentation, go ahead and use several subsections here, or split this section into several sections.

Method:

General Steps

Image straightening, grid detection, grid completion, ‘solve’ and ‘attempt’ matrixes extraction, and presentation of the result according to the chosen revealing option.

Method:

Given: a partly-solved puzzle image, a solution image, number of rows and number of columns.

v  Image straightening – done for both puzzle and solution image

Ø  Calculating Hough transform

Ø  Calculating a score for grid fitting (namely horizontal and vertical lines) for specific degrees

§  Iteration I – degree ranges between -90:90 with jumps of 5, tolerance is 3 degrees

·         Yields a rough estimation of rotation degree, denoted ‘d1’

§  Iteration II – degree ranges between d1-5:d1+5, tolerance is 1 degree

·         Yields best rotation degree, denoted ‘d2’

Ø  Rotation of the Image by d2 degrees

Ø  Background crop

v  Grid fitting – done for both puzzle and solution image

Ø  Basic synchronization elements identifying:

§  Horizontal and vertical lines via Hough transform

§  Known outlines and bounds

Ø  Grid completion using:

§  A Histogram of adjacent lines distances

§  Known numbers of rows and columns

§  Other calculations based on the synchronization elements

v  ‘attempt’ matrix extraction

Ø  Estimating whether each square in the puzzle’s grid is marked or not

v  ‘solution’ matrix extraction

Ø  Estimating whether each square in the solution’s grid is marked or not

v  Solution presentation

Ø  Detecting errors and unmarked squares

Ø  Plotting marks on original image according to the option chosen

 

v  Off the record – an OCR attempt

Ø  Resizing the digits’ templates to estimated size according to the grid

Ø  Defining search areas and the corresponding numbers’ rows or columns

Ø  Calculating Hough Transform of flipped templates (for each digit)

Ø  Pick the best fit in each slot

Results

Input:

Solution image:Description: girlwithhorse_65_sol_bw.tif

Puzzle image:Description: girlwithhorse_30_bw.tif

Dimension parameters:

 

N = 35

M = 45

Output:

Hint :

Show Solution:

Conclusions

Discuss the results vis-a-vis your goals and make conclusions.

Additional Information