Click here to Skip to main content
15,867,330 members
Articles / Desktop Programming / Windows Forms
Article

Solving Paint-by-numbers puzzles in C#

Rate me:
Please Sign up or sign in to vote.
4.57/5 (12 votes)
11 Aug 20055 min read 131.4K   2.7K   28   9
A small program which solves the paint-by-numbers puzzles in virtually time. It is a spoiler if you're a player. If you're a programmer however I think it shows how this problem can be solved.

Sample Image - hanjie.png

From Wikipedia, the free encyclopedia.

(http://en.wikipedia.org/wiki/Paint_by_numbers)

An example of a Paint by Numbers puzzle.
Enlarge
An example of a Paint by Numbers puzzle.

Paint by numbers, also known as Japanese puzzles, nonograms, pic-a-pix, picross puzzles, pikurosu, hanjie, griddlers, or Edel, are logic puzzles in which cells in a grid have to be coloured (or left blank) according to numbers given at the side of the grid to reveal a hidden picture. The numbers measure how many unbroken lines of filled-in squares there are in any given row or column. For example, a clue of "4 8 3" would mean there are sets of four, eight, and three filled squares, in that order, with at least one blank square between successive groups.

These puzzles are often black and white but can also have some colors. If they are colored, the number clues will also be colored in order to indicate the color of the squares. Two differently-colored numbers may or may not have a space in between them. For example, a black four followed by a red two could mean four black spaces, some empty spaces, and two red spaces, or it could simply mean four black spaces followed immediately by two red ones.

Nintendo picked up on this puzzle fad awhile back and released two Picross titles for the Game Boy and nine for the Super Famicom (eight of which were released in two-month intervals for the Nintendo Power Super Famicom Cartridge Writer as the "NP Picross" series) in Japan. Only one of these, Mario's Picross for the Game Boy, was ever released in the United States.

Variations of the puzzles have appeared in recent years.

Paint by pairs or link-a-pix consists of a grid, with numbers filling some squares; pairs of numbers must be located correctly and connected with a line filling a total of squares equal to that number. When completed, the squares that have lines are filled; the contrast with the blank squares reveals the picture. (As above, coloured versions exist with matching numbers of the same colour.)

Fill-a-pix also uses a grid with numbers within; in this format, each number indicates how many of the sqares immediately surrounding it, and itself, wil be filled. A square marked '9', for example, will have all 8 surrounding squares, and itself, filled; if it is marked '0', those squares are all blank.


Paint by numbers is also a method of simple painting, often for children. A black on white line drawing contains several fully enclosed areas, each marked with a number. Each number corresponds to a certain color of paint, often provided in a set along with multiple drawings. By following the number schema, the drawing is appropriately colored.

External links

End of Wikipedia extract

Introduction

Two weeks ago I was introduced to Hanjie, the paint by numbers puzzles.

This was quite a nice discovery to me, I instantly loved it.

On the very same day I started to think on how I could progamatically solve this puzzle.

What is the technique

 I used more or less the same techniques than the Mac Mahon puzzle I posted here a while ago.

To solve this puzzles, very much like always, you have to browse a navigate inside a tree of possibilities.

So you start with the first line, put it on the board if it fits. Then you call the very same procedure for the second line.
After the call to the second line you have to put the board back to the state it was before the call.

It is very simple to solve your puzzle from up to bottom however it is not very clever.

The only problem with this technique is that it will take the age of the universe to resolve any slightly complicated puzzle.

So is there any trick ?

The trick I found is to do precisely what a human being would do.

That is make the easy parts first.

Trick 1

So you first set the cells which are certain to be of a color.

Lets say your board is 10x10, if anywhere in the color clues there is a number 8.

   +--------------------+
8  |X X X X X X X X     |
8  |  X X X X X X X X   |
8  |    X X X X X X X X |
   |                    |

The height cells can be aligne to the left, in the middle or aligned to the right.
I any case the 6 cells in the middles are definitely colored.

Trick 2

This trick took me quite a long time to write. I wanted to know how many possibilities there is per row.
So lets say the row says 5 3 2, how many combinations is there ?
The solution was found in MathLab

http://www.utexas.edu/math/Matlab/Manual/chol.html

The idea is to count the number of blank, my calculation is not 100% accurate because I do not take into account the fact that in some circumstances you can't have empty spaces.

For our algorithm the idea is to start with the rows which are easier rather than the one with more possibilities. So an approximation is far supperior that having to actually precisely count the number of possibilities.

The trick saved an awful lot of computation (twenty minutes to a few seconds).

Conclusion

There is probably more to be found and more to be done.

I put the source in the public domain. Feel free to amend edit improve.
Please don't mention the lack of comments and coding conventions, it is my hobby not my job.

Questions to the readers

I used XML serialization to save the games.
I could not manage to serialize one of the class because it was deriving a usercontrol. I would be glad if you could give me some advice or comments on the way I solved that.

Thanks

I put some sample in the hanjie\bin\Debug folder. They are coming from : www.conceptispuzzles.com this is a very well done and rich website for puzzles lovers. Please visit it for Pic-a-pix and more...

 

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Software Developer (Senior)
France France
I am a French programmer.
These days I spend most of my time with the .NET framework, JavaScript and html.

Comments and Discussions

 
GeneralVery Nice Pin
Polymorpher4-Feb-06 4:22
Polymorpher4-Feb-06 4:22 
GeneralRe: Very Nice Pin
Pascal Ganaye6-Feb-06 7:10
Pascal Ganaye6-Feb-06 7:10 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.