API library

Module for formulating nonogram puzzles (a.k.a. Picross, paint-by-number, and crucipixel), and for solving these puzzles in JuMP using integer linear programming.

eval_aux_quantities(p::Puzzle) -> AuxPuzzleQuantities

Construct intermediate quantities that describe a Puzzle p, to aid solve_puzzle.

See the documentation for AuxPuzzleQuantities for a list of these quantities.

read_puzzle_from_cwc(cwcFileName::String) -> Puzzle

Import a puzzle that was exported from Web Paint-by-Number as a .CWC file.

Example

With puzzle.cwc exported from Web Paint-by-Number and placed in the working directory, we may then build:

puzzle = read_puzzle_from_cwc("puzzle.cwc")

recover_aux_data(p::AuxPuzzleQuantities)

Recover a Tuple containing all fields of an AuxPuzzleQuantities object p.

solve_puzzle(p::Puzzle) -> PuzzleSolution

solve_puzzle(
    p::Puzzle,
    auxQs::AuxPuzzleQuantities = eval_aux_quantities(p);
    optimizer = GLPK.Optimizer,
    solverAttributes = ("msg_lev" => GLPK.GLP_MSG_OFF,),
    verbosity::Int = 1
) -> PuzzleSolution

Solve the Puzzle p, and construct a corresponding PuzzleSolution.

This puzzle is solved according to a method by Khan, using an integer linear programming (ILP) solver in the optimization framework JuMP. If successful, returns one solution. Uses the freely available solver GLPK by default. All arguments other than p are optional.

The puzzle instance p may be constructed using either a Puzzle constructor or read_puzzle_from_cwc. The arguments optimizer and solverAttributes specify your choice of ILP solver and settings to JuMP, for use in JuMP's command:

JuMP.optimizer_with_attributes(optimizer, solverAttributes...)

See JuMP's documentation for more details about setting up these inputs.

Reports JuMP's solution summary by default; set verbosity=0 to suppress this.

Holds intermediate quantities describing the Puzzle p.

These quantities are used by solve_puzzle to solve a puzzle. Quantities are named as in Khan's article (2022, doi:10.1109/TG.2020.3036687), and their purposes are described there.

Fields

• sigmaR::Array{Int, 2}: Spacing quantities for blocks in rows.
• sigmaC::Array{Int, 2}: Spacing quantities for blocks in columns.
• fSetR::Array{UnitRange{Int}, 2}: First-position sets for blocks in rows.
• fSetC::Array{UnitRange{Int}, 2}: First-position sets for blocks in columns.
• oSetR::Array{UnitRange{Int}, 3}: Overlap-checking sets for blocks in rows.
• oSetC::Array{UnitRange{Int}, 3}: Overlap-checking sets for blocks in columns.
• mSetR::Array{Vector{Int}, 2}: Monochrome index sets for rows.
• mSetC::Array{Vector{Int}, 2}: Monochrome index sets for columns.
• maxBR::Int: Upper bound on number of blocks in each row.
• maxBC::Int: Upper bound on number of blocks in each column.

Holds one puzzle instance.

Fields of Puzzle{T}

• palette: Iterable collection of the puzzle's permitted colors, each of type T. Lack of color is represented by zero(T), so zero(T) must be defined and must not be in palette.
• sR::Vector{Vector{Int}}: Numerical clues for each row, from top to bottom. Empty rows are entered as Int[] (and not e.g. [0]).
• cR::Vector{Vector{T}}: Colors in palette corresponding to the clues in sR.
• sC::Vector{Vector{Int}}: Numerical clues for each column, from left to right. Empty columns are entered as Int[].
• cC::Vector{Vector{T}}: Colors in palette corresponding to the clues in sC.

Non-default constructors

The following constructors for Puzzle are recommended over the default constructor.

For monochrome puzzles

Puzzle(sR::Vector{Vector{Int}}, sC::Vector{Vector{Int}})

Hold a monochrome puzzle, with sR containing row clues and sC containing column clues.

This constructor sets the puzzle's single color (traditionally "black") to 1, lack of color (traditionally "white") to 0, and Puzzle.palette to 1:1.

For multicolored puzzles

Puzzle(sR, cR, sC, cC)

Build Puzzle.palette from cR and cC; otherwise identical to the default constructor.

See also read_puzzle_from_cwc.

Holds JuMP's termination status after a solution attempt, and the solution itself if successful.

Fields

• jumpTerminationStatus: the eventual output of JuMP.termination_status, indicating the outcome of the solution attempt.
• z::Matrix{T}: Spatial array of cell colors (of type T) in solution, if successful.
• palette::P: Collection of possible cell colors (each of type T). Does not include lack of color, which is indicated as zero(T).