2.0.0 • Published 8 years ago
nonogram-solver v2.0.0
Nonogram Solver
Solves black and white Nonogram puzzles (also known as Griddlers, Picross, Hanjie, Japanese Crosswords).
Can solve large puzzles (>100x100) with low memory usage. Typically requires less than a second for small to medium puzzles.
Installation
This program requires Node.js version 8. It might run with other versions, but has not been tested.
Installation is as simple as
$ npm install nonogram-solverUsage
Command line
Put your input as a JSON file, then run
$ npx nonogram-solver input.jsonYou can also pass multiple input files:
$ npx nonogram-solver a.json b.json
$ npx nonogram-solver *.jsonThe output directory can be set with the -o Option. Use -h for help.
As an npm module
const solve = require('nonogram-solver');
let {status, puzzle} = solve('input.json');
switch (status) {
case -1:
console.log('Puzzle is unsolvable!😖');
break;
case 0:
console.log('Could not solve puzzle!😞');
break;
case 1:
console.log('Puzzle solved!😊');
}
console.log(puzzle.snapshot);Input format
The input file must be valid JSON containing a rows and a columns attribute and an optional content attribute.
{
"rows": [[1], [2]],
"columns": [[2], [1]],
"content": [0, 0, 1, 0] // optional
}Use the content attribute to define partially solved puzzles; It should be an array of the values -1, 0, 1. Here 0 means: unsolved, 1 means: square is known to be occupied, -1: square is known to be empty.
It is an error if content contains not exactly rows.length*columns.length elements.
Output
If your puzzle is solvable, the solution will be printed to the command line and saved as an svg file to the output folder (can be overridden with the -o option).
Puzzle solved!
1
3
26
71
4 084
111 4367 34 1
2912813 2 55455 3
6 6 1111 248 2 41 1 11
338 55552 189009 2 054167353333334
5 17 1122 72 86111111
43444 433452 349744757 5 2245514333348332234228
11 1 1 41 2223322
49135436803344312521222335526667467796554434522385333359624
1 xxxxxxxxxxxxxxxxxxxxâ–ˆxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
1 2 xxxxxxxxxxxxxxxxxxxx█xxxxxxxx██xxxxxxxxxxxxxxxxxxxxxxxxxxxx
2 7 xxxxxxxxxxxxxxxxxxx██xxxxxx███████xxxxxxxxxxxxxxxxxxxxxxxxx
3 10 xxxxxxxxxxxxxxxxxxx███xxx██████████xxxxxxxxxxxxxxxxxxxxxxxx
3 11 4 xxxxxxxxxxxxxxxxxxx███xxx███████████xxxxxx████xxxxxxxxxxxxx
2 12 3 xxxxxxxxxxxxxxxxxxx██xxx████████████xxxxxx███xxxxxxxxxxxxxx
4 13 3 xxxxxxxxxxxxxxxxx████xx█████████████xxxxx███xxxxxxxxxxxxxxx
5 13 2 xxxxxxxxxxxxxxx█████xxx█████████████xxxxx██xxxxxxxxxxxxxxxx
5 12 3 xxxxxxxxxxxxxx█████xxxxx████████████xxxxx███xxxxxxxxxxxxxxx
6 11 3 4 xxxxxxxxxxxx██████xxxxxxx███████████xxxxxx███xxxxxx████xxxx
5 10 4 6 xxxxxxxxxxx█████xxxxxxxxx██████████xxxxxxx████xxxx██████xxx
4 8 3 8 xxxxxxxxxxx████xxxxxxxxxxx████████xxxxxxxxx███xxx████████xx
4 11 3 4 3 xxxxxxxxxxx████xxxxxxxxx███████████xxxxxxxx███xx████xxx███x
4 12 3 4 2 xxxxxxxxxxx████xxxxxxxxx████████████xxxxxxx███xx████xxxx██x
4 13 4 4 3 xxxxxxxxxxx████xxxxxxxxx█████████████xxxxx████xx████xxxx███
5 4 13 5 4 2 xxxx█████xx████xxxxxxxxx█████████████xxxx█████xx████xxxxx██
7 5 12 7 4 2 xxx███████x█████xxxxxxxx████████████xx███████xxx████xxxxx██
8 7 20 4 2 xx████████x███████xxxxxx████████████████████xxxx████xxxxx██
4 34 4 3 x████xxx██████████████████████████████████xxxxxx████xxx███x
3 3 29 4 3 x███xxxx███x█████████████████████████████xxxxxxx████xxx███x
3 2 28 5 x███xxxx██xxx████████████████████████████xxxxxx█████xxxxxxx
4 2 28 6 ████xxxx██xxxx████████████████████████████xxxx██████xxxxxxx
4 1 38 ████xxxx█xxxx██████████████████████████████████████xxxxxxxx
4 39 ████xxxxxxx███████████████████████████████████████xxxxxxxxx
5 40 █████xxxx████████████████████████████████████████xxxxxxxxxx
46 7 x██████████████████████████████████████████████xx███████xxx
13 30 7 x█████████████x██████████████████████████████xxxx███████xxx
11 6 6 12 3 4 xx███████████xx██████x██████xxx████████████xxxxx███xx████xx
8 5 6 13 2 3 xxx████████xxx█████xxx██████xxx█████████████xxxx██xxxx███xx
5 5 4 7 3 3 xxxxxxxxxxxxxx█████xxx█████xxxxx████xx███████xx███xxxxx███x
4 5 4 7 2 4 xxxxxxxxxxxxxxx████xxx█████xxxxx████xxx███████x██xxxxx████x
4 5 4 8 3 xxxxxxxxxxxxxxx████xxx█████xxxxx████xxxxx████████xxxxx███xx
4 4 5 14 xxxxxxxxxxxxxxxx████xxx████xxxxx█████xxxxxx██████████████xx
2 4 4 5 11 xxxxxxxxxxxx██xx████xxx████xxxxx█████xxxxxxxx███████████xxx
7 4 4 5 9 xxxxxxxxx███████x████xx████xxxxx█████xxxxxxxxx█████████xxxx
8 4 4 6 2 xxxxxxxx████████xx████xx████xxxx██████xxxxxxxx██xxxxxxxxxxx
5 4 4 4 7 2 xxxxxxx█████x████x████xx████xxxxx███████xxxxx██xxxxxxxxxxxx
4 3 3 3 10 xxxxxxx████xxx███xx███xxx███xxxxx██████████xxxxxxxxxxxxxxxx
4 3 4 3 14 xxxxxx████xxxx███x████xxx███xxxxxx██████████████xxxxxxxxxxx
4 6 3 14 xxxxxx████xxxxx██████xxxxx███xxxxxx██████████████xxxxxxxxxx
4 6 3 14 xxxxxx████xxxxx██████xxxxx███xxxxxxx██████████████xxxxxxxxx
12 3 3 xxxxxxx████████████xxxxxxx███xxxxxxxxxxxxxxxxxx███xxxxxxxxx
9 3 3 2 xxxxxxxx█████████xxxxxxxxx███xxxxxxxxxxxxx███xxx██xxxxxxxxx
9 3 3 2 xxxxxxxxx█████████xxxxxxxx███xxxxxxxxxxxxx███xxx██xxxxxxxxx
2 3 4 3 3 xxxxxxxxxxxx██x███xxxxxxx████xxxxxxxxxxxxx███xx███xxxxxxxxx
3 3 6 xxxxxxxxxxxxxxx███xxxxxxx███xxxxxxxxxxxxxxx██████xxxxxxxxxx
2 4 5 xxxxxxxxxxxxxxxx██xxxxxx████xxxxxxxxxxxxxxxx█████xxxxxxxxxx
3 4 xxxxxxxxxxxxxxxx███xxxx████xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
1 8 xxxxxxxxxxxxxxx█xx████████xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
4 xxxxxxxxxxxxxxxxxxxx████xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Output saved to output/result.svg.
The same is true if nonogram-solver cannot solve your puzzle, but this time the output is going to be a partially finished puzzle.
Could not solve puzzle
1
3
26
71
4 084
111 4367 34 1
2912813 2 55455 3
6 6 1111 248 2 41 1 11
338 55552 189009 2 054167353333334
5 17 1122 72 86111111
43444 433452 349744757 5 2245514333348332234228
11 1 1 41 2223322
49135436803344312521222335526667467796554434522385333359624
1 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xâ–‘xxâ–‘â–‘xxxâ–‘â–‘â–‘xxâ–‘xxxxxxxâ–‘â–‘xxxxxxxxxxxxx
1 2 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xâ–‘xâ–‘â–‘â–‘xâ–‘â–‘â–‘â–‘â–‘xxâ–‘xxxxxxxâ–‘â–‘xxxxxxxxxxxxx
2 7 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxxxxxxxxxxxxxxxxxxxxxxx
3 10 ░░░░░░░░░░░░░░░░░░░░░░xxx██████████xxxxxxxxxxxxxxxxxxxxxxxx
3 11 4 ░░░░░░░░░░░░░░░░░░░░░░xx░██████████░xxxxx░░░░░░░░░░░░░░░░░░
2 12 3 ░░░░░░░░░░░░░░░░░░░░░░xx████████████xxxxx░░░░░░░░░░░░░░░░░░
4 13 3 ░░░░░░░░░░░░░░░░░░░░░░x░████████████░xxxx░░░░░░░░░░░░░░░░░░
5 13 2 ░░░░░░░░░░░░░░░░░░░░░░x░████████████░xxxx░░░░░░░░░░░░░░░░░░
5 12 3 ░░░░░░░░░░░░░░░░░░░░░░xx░███████████░xxxx░░░░░░░░░░░░░░░░░░
6 11 3 4 ░░░░░░░░░░░░░░░░░░░░░░xxx░██████████░xxxx░██░░░░░░░░░░░░░░░
5 10 4 6 ░░░░░░░░░░░░░░░░░░░░░░xxx░█████████░xxxxx░███░░░░░░░░░░░░░░
4 8 3 8 ░░░░░░░░░░░░░░░░░░░░░░xxxx████████xxxxxxx░░░░░░░░░░░░░░░░░░
4 11 3 4 3 ░░░░░░░░░░░░░░░░░░░░░░x░░░████████░░░xxx░░░░░░░░░░░░░░░░░░░
4 12 3 4 2 ░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░xx░░░░░░░░░░░░░░░░░░░░
4 13 4 4 3 ░░░░░░░░░░░░░░░░░░░░░░░░██████████░░░x░░░░░░░░░░░░░░░░░░░░░
5 4 13 5 4 2 ░░░░░░░░░░░░░░░░░░░░░░░░██████████░░░░░░░░░░░░░░░░░░░░░░░░░
7 5 12 7 4 2 ░░░░░░░░░░░░░░░░░░░░░░░░██████████░░░░░░░░░░░░░░░░░░░░░░░░░
8 7 20 4 2 ░░░░░░░█░░░░░░░░░░░░░░░░█████████████░░░░░░░░░░░░░░░░░░░░░░
4 34 4 3 ░░░░░░░░░░░░░░░░███████████████████████░░░░░░░░░░░░░░░░░░░░
3 3 29 4 3 ░░░░░░░░░░░░░░░█░░░░░██████████████████░░░░░░░░░░░░░░░░░░░░
3 2 28 5 ░░░░░░░░░░░░░░░██░░░░░█░███████████████░░░░░░░░░░░░░░░░░░░░
4 2 28 6 ░░░░░░░░░░░░░░░░░░░░░░█░███████████████░░░░░░░░░░░░░░░░░░░░
4 1 38 ░░░░░░░░░░░░░░░░░█░░░████████████████████████░░░░░░░░░░░░░░
4 39 ░░░░░░░░░░░░░░░░░░░░████████████████████████░░░░░░░░░░░░░░░
5 40 ░░░░░░░░░░░░░░░░░░░███████████████████████████░░░░░░░░░░░░░
46 7 ░░░░░█████████████████████████████████████████░░░░░░██░░░░░
13 30 7 ░░░░░░░██████░░░░░░░░███████████████████████░░░░░░░░░░░░░░░
11 6 6 12 3 4 ░░░░░░░░░░░░░░░░░░░░░░░████░░░░░████░░██░░░░░░░░░░░░░░░░░░░
8 5 6 13 2 3 ░░░░░░░░░░░░░░░░░░░░░░░████░░░░░████░░░░░░░░░░░░░░░░░░░░░░░
5 5 4 7 3 3 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xx░████░░░░░░░░░░░░░░░░░░░░░░░
4 5 4 7 2 4 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx████░░░░░░░░░░░░░░░░░░░░░░░
4 5 4 8 3 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx████░░░░░░░░░░░░░░░░░░░░░░░
4 4 5 14 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx████░░░░░░░░░█░░░░░░░░░░░░░
2 4 4 5 11 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx████░░░░░░░░░░░░░░░░░░░░░░░
7 4 4 5 9 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx░███░░░░░░░░░░░░░░░░░░░░░░░
8 4 4 6 2 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx░███░░░░░░░░░░░░░░░░░░░░░░░
5 4 4 4 7 2 ░░░░░░░░░░░░░░░░░░░░░░░░███░░xxx░░██░░░░░░░░░░░░░░░░░░░░░░░
4 3 3 3 10 ░░░░░░░░░░░░░░░░░░░░░░░░░███░xxxx░██░░░░░░░░░░░░░░░░░░░░░░░
4 3 4 3 14 ░░░░░░░░░░░░░░░░░░░░░░░░░███░xxxx░██░░░░░░░░░██░░░░░░░░░░░░
4 6 3 14 ░░░░░░░░░░░░░░░░░░░░░░░░░░██░xxxxx░░░░░░░░░░░███░░░░░░░░░░░
4 6 3 14 ░░░░░░░░░░░░░░░░░░░░░░░░░░█░░xxxxx░░░░░░░░░░░███░░░░░░░░░░░
12 3 3 ░░░░░░░░░░░░░░░░░░░░░░░░░░█░░xxxxx░░░░░░░░░░░x░░░░░░░░░░░░░
9 3 3 2 ░░░░░░░░░░░░░░░░░░░░░░░░░░█░░xxxxx░░░░░░░░░░░░░░░░░░░░░░░░░
9 3 3 2 ░░░░░░░░░░░░░░░░░░░░░░░░░░█░░xxxxx░░░░░░░░░░░░░░░░░░░░░░░░░
2 3 4 3 3 ░░░░░░░░░░░░░░░░░░░░░░░░░░█░░xxxxxxx░░░░░░░░░░░░░░░░░░░░░░░
3 3 6 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxxxxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘
2 4 5 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxxxxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘
3 4 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxxxxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘
1 8 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xâ–‘â–‘xxxxxxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘
4 â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘xxxxxxxxxxâ–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘â–‘
Output saved to output/result.svg.
Additionally, it prints the current content in this case (omitted in the sample above). The content is given in the format described above.
Where can I get some puzzles for testing?
Some samples are included in the puzzles folder. If you want more, run
$ npx nonogram-dl-samplesThis will download selected puzzles from nonograms.org. The files themselves are not included in this package for copyright reasons.
Now you can run nonogram-solver puzzles/nonograms.org/*.json.
How does it work?
See internals.md.
