Skip to content

Latest commit

 

History

History
210 lines (149 loc) · 6.31 KB

README.md

File metadata and controls

210 lines (149 loc) · 6.31 KB
Raw

Nonopy

Build Status

CLI and library for solving nonograms (aka griddlers, picross). Supports puzzles with definite and deterministic solutions.

Quick start

Before you start, check requirements.

# clone and install
git clone git@github.com:dpetrovych/nonopy.git
cd nonopy
python -m pip install -r requirements.txt

# run
python cli.py ./data/hard/tiger.non -i

# also run
python cli.py ./data/hard/sun.non -G --solvers AC --linestats -3

# run tests
python -m unittest -v

Don't want to mess up your environment setup? You can touch-and-go with a Docker image.

CLI usage

python cli.py [-h] [--solvers ABC] [--verbose] [--interactive] [--nogrid] [--linestats [SORTBY]] path

Positional arguments
path path to .non format file

Optional arguments
--help, -h show this help message and exit
--solvers ABC, -s ABC solvers to run (one-letter code for solver algorithm)
--verbose, -v shows actions log
--interactive, -i shows grid while solving
--nogrid, -G hides grid in final output (for comparing stats only)
--linestats [SORTBY] shows statistics per line sorted by column 1-based index (negative values for sorting in descending order)

Docker usage

wget -P ./data https://github.com/dpetrovych/nonopy/main/data/hard/sun.non
docker run -t --rm -v "${PWD}/data:/data" dpetrovych/nonopy:latest /data/sun.non

--rm flag removes container when command is complete. -v argument mounts a data directory with a puzzle file into container.

A downside of this method is that you can't use --interactive flag of Nonopy CLI, since it depends on terminal resize (curses).

Requirements

  • Python 3.8 (check with python -v)
  • Pip (check with pip --version)

If you using any modern Linux distributions, you probably have one already. Here is an instruction if you need to install Python.

Glossary

  • Field - 2d grid where a solved image is constructed
  • Line - column or row on the field
    • Field line - representation of the current line state on the field
  • Block - consecutive filled cells in line (two blocks should be separated by 1+ crossed cells)
  • Task - numerical cues on top of the column (right to the row), represent block length
    • Task line - abstraction that contains task and data/methods assosiated with row/column
    • Hot task - task that has definite cells on empty line (can be solved in-place)
  • Collapse - operation of determining definite cell values based on the task and current line state

Legend

r10 - row with an index 10
c4 - column with an index 4
| - line boundary
· - empty cell
x - crossed cell
1 - filled cell

Algorithm

0 RANGE lines

Calculates number of combinations of positionment of the blocks. Add lines with hot tasks to the hot heap - heap ordered desc by number of combinations.

1 POP the next line

Pop the line from the top of the hot heap (thus with min combinations).

2 COLLAPSE the line

To speed up collapse of combinations the solver uses some divide & conquere strategies.

DIVIDE_BY_CROSSED

If a line has already crossed boxes, it can solve 2 halfs of a line as separate lines.

line: |···xx···|
task: [2, 1, 1]
---
left: |···|     right: |···|
task: []         task: [2, 1, 1]
rslt: |xxxx|     rslt: None     -- Eliminated

left: |···|     right: |···|
task: [2]        task: [1, 1]
rslt: |·1·|      rslt: |1x1|    -> |·1·xx1x1|

left: |····|    right: |···|
task: [2, 1]     task: [1]
rslt: |11x1|     rslt: None   -- Eliminated

left: |····|    right: |···|
task: [2, 1, 1]  task: [1]
rslt: None       rslt: None     -- Eliminated
---
result: |·1·xx1x1|

DIVIDE_BY_FILLED

If a line has already filled boxes, it can fit one of the block on to the filled one and solve 2 parts with remaining blocks.

line: |··1····|
task: [2, 2]
---
Fit block 0 at index 1: |x11x···|
left: ||        right: |···|
task: []         task: [2]
rslt: ||         rslt: | 1 |    -> |x11x 1 |

Fit block 0 at index 2: |·x11x··|
left: |·|       right: |··|
task: []         task: [2]
rslt: |x|        rslt: |11|     -> |xx11x11|

Fit block 1 at index 1: |x11x···|
left: ||        right: |···|
task: [2]        task: []
rslt: None       rslt: |xxx|    -- Eliminated

Fit block 1 at index 2: |·x11x··|
left: |·|       right: |··|
task: [2]        task: []
rslt: None       rslt: |xx|     -- Eliminated

---
result: |x·1··1·|

INPLACE

INPLACE runs when all line cells are empty. In the logic of the move all blocks tightly to the left boudary, then to the right and mark the intersection of the same blocks.

This technick is also known as Simple Blocks. (wiki)

task: [3, 2]
line: |·······|
---
lshift: |111·11·|
rshift: |·111·11|
---
result: |·11··1·|

3 DIFF result with the line

Hightlight cells where new solution emerged from collapse operation.

Example (from DIVIDE_BY_CROSSED):

line:   |···xx···|
result: |·1·xx1x1|
---
diff:   |·1···1x1|

4 MARK lines hot

For each highlighted diff cell mark an opposite direction (column if diff line is a row and vice versa) as hot and put to a _hot heap.

Example:

diff r2: |·1···1x1|
marked hot: c1, c5, c6, c7

5 REPEAT until solved

Goto 1