Scraping Nonograms to Build a Solver Using Machine Learning
What and Why?
Nonograms are logic puzzles that create an image when solved and they are build from machine learning. Originally invented in the 1980's by two different people simultaneously. They became popular in the late 80s-90s. Now they're known by almost 30 different names; the most popular ones being nonograms, hanjie puzzles, picross puzzles, and griddlers. The clues on the side and top denote which squares should be empty or filled in. The numbers denote the black squares and each group of black squares must be separated by at least one empty space. Here's a really simple puzzle being solved step-by-step.
Each move has a reason and nothing is a guess. My dad, after ordering a book of puzzles, thought they might be a good machine learning project. So this web scraping project is the first step of building a nonogram solver using machine learning.
Scraping code
From this website: http://www.nonograms.org/nonograms I scraped around 8K puzzles for the size, clues, solutions, and difficulty of the puzzles. The biggest issue I came across was scraping the actual clues themselves. The actual table was hidden behind the javascript and I couldn't scrape it like everything else in the html. My solution to this was using scrapy splash in my spider as a work around as was able to get the clues as a list of empty spaces and numbers. Here is the data and its corresponding puzzle.
| sizeCol | 14 |
| sizeRow | 16 |
| title | Snail |
| number | 15868 |
| solution | http://static.nonograms.org/files/nonograms/large/ulitka40_12_1_1p.png |
| difficulty | 5 |
| colClues | , , ,1,1, , , ,1,1, , , , ,3, , , , ,4, , , , ,4, , , ,2,6, , ,2,2,2, , ,4,2,2, ,3,1,2,1,1,2,2,1,1, ,1,1,2,1, , ,2,4,1, , ,2,1,2, , , ,7,4 |
| rowClues | , , , , , , , ,1, , , , , , , , , , , , , , ,1,1,1, , , , , , , , , , ,1,2,2,2,1,2,1, ,2, , , ,1, , ,8,3,2,1,1,1,2,3,2,1,4, , ,2,4,10,2,2,1,1,1,1,1,1,1,1,2,2,1 |
| size | 224 |
For my code and data, visit my GitHub Page: https://github.com/susarip/test/tree/master/hanjie_scraper/hanjie_scraper
What's next?
- Convert output images (solutions) into data which becomes the Y value
- Split input data set into training set and test set (90:10)
- Use the training set to train a few statistical machine learning algorithms
- Use the test set to test the trained model
- If the accuracy is good enough, use the model to predict answers for new puzzles.
- Areas of research: Use neural networks to find answers instead of statistical models
About Author
