Nonogram solver: Difference between revisions

'''Extra credit''': generate nonograms with unique solutions, of desired height and width.

<br><br>

<br><br>

; Related tasks

{{trans|Python 3}}

 

‘Create all patterns of a row or col that match given runs.’

F gen_seg([[Int]] o, Int sp) -> [[Int]]

 

print(‘Extra example where there is no solution:’)

 

{{out}}

 

=={{header|C sharp}}==

using System.Collections.Generic;

using static System.Linq.Enumerable;

}

 

{{out}}

<pre style="height:30ex;overflow:scroll">

=={{header|C++}}==

===The Solver===

// A class to solve Nonogram (Hadje) Puzzles

// Nigel Galloway - January 23rd., 2017

return n.str();

}};

 

===The Task===

// For the purpose of this task I provide a little code to read from a file in the required format

// Note though that Nonograms may contain blank lines and values greater than 24

std::cout << "\n" << myN.toStr() << std::endl;

}

{{out}}

<pre>

===Bonus GCHQ Xmas Puzzle===

[[https://www.gchq.gov.uk/news-article/christmas-card-cryptographic-twist-charity GCHQ Xmas Puzzle]] is a Nonogram. They say "We pre-shaded a few cells to help people get started. Without this, the puzzle would have been slightly ambiguous, though the error correction used in QR codes means that the URL would have been recovered anyway. As a small Easter egg, the pre-shaded cells spell out “GCHQ” in Morse code."

int main(){

const std::vector<std::vector<int>> Ngchq={{ 7,3,1, 1,7},

std::cout << "\n" << myN.toStr() << std::endl;

}

{{out}}

<pre>

 

=={{header|Common Lisp}}==

(:use :cl)

(:export :var

(nonogram (parse-nonogram (read-until-line s)

(read-until-line s)))))

{{out}}

<pre>CL-USER> (time (nonogram::solve-from-file "c:/Users/cro/Dropbox/Projects/rosetta-code/nonogram_problems.txt"))

=={{header|D}}==

{{trans|Python}}

 

/// Create all patterns of a row or col that match given runs.

"Extra example where there is no solution:".writeln;

"B A A\nA A A".solve;

{{out}}

<pre>Horizontal runs: [[3], [2, 1], [3, 2], [2, 2], [6], [1, 5], [6], [1], [2]]

 

=={{header|F_Sharp|F#}}==

(*

I define a discriminated union to provide Nonogram Solver functionality.

if ((fst el) = (fst l)) && ((snd el) = (snd l)) then (n,i,g,e,(Array.forall (fun n -> n = 1) (fst l))) else fn na ia ga ea el

fn na nb x (N.fl x) ((Array.map (fun n -> List.length n) na), (Array.map (fun n -> List.length n) ga))

For the purposes of this task I provide a little code to read the input from a file

let fe (n : array<string>) i = n |> Array.collect (fun n -> [|N.fn [for g in n -> ((int)g-64)] i|])

let fl (n : array<string>) (i : array<string>) = (fe n i.Length), (fe i n.Length)

Some(fl (file.ReadLine().Split ' ') (file.ReadLine().Split ' '))

with | _ -> printfn "Error reading file" ; None

This may be used:

let n,i,g,e,l = N.presolve rFile.Value

if l then i |> Array.iter (fun n -> n |> Array.iter (fun n -> printf "%s" (N.toStr n));printfn "") else printfn "No unique solution"

{{out}}

<pre>

=={{header|Go}}==

{{trans|Java}}

 

import (

newPuzzle(puzzleData)

}

 

{{out}}

. . . . . . . . . . . . . . . . . # # # # # # # #

. . . . . . . . . . . . . . . . . . # # # # # # #

</pre>

 

=={{header|Java}}==

{{works with|Java|8}}

import static java.util.Arrays.*;

import static java.util.stream.Collectors.toList;

return countRemoved;

}

<pre>. # # # . . . .

# # . # . . . .

 

=={{header|Julia}}==

 

struct NonogramPuzzle

 

processtestpuzzles(testnonograms)

<pre>

Puzzle 1:

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.BitSet

newPuzzle(puzzleData)

}

 

{{out}}

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

VisualizeGrid[candgrid_List] := StringRiffle[StringJoin/@Replace[candgrid,{{0}->" ",{1}->"#",{0,1}|{1,0}->"."},{2}],"\n"]

Possibilities[clues_List, len_Integer] := Module[{spaces, numclue, spacecands, cands},

,

{n, 4}

{{out}}

<pre> ###

To generate the sequence, we use the Java algorithm modified to directly generate bit strings (as integers) rather than character strings.

 

 

type

Possibility = int

 

Possibilities = object

mask0: int # Mask indicating the positions of free cells.

echo ""

solve(rows, cols)

 

{{out}}

 

=={{header|Ol}}==

(import (owl parse))

 

(print))

(list first second third fourth))

{{out}}

<pre style="height:60ex;overflow:scroll">

 

=={{header|Perl}}==

use warnings;

 

. '[0.]*' # 6b append static pattern

} split ' ', shift; # 1 for each letter grouping

{{out}}

<pre>

=={{header|Phix}}==

Deduction only, no exhaustive search.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">grid</span>

<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre style="float:left">

########

#######

</pre>

 

 

Module solve-nonogram.pl

* Nonogram/paint-by-numbers solver in SWI-Prolog. Uses CLP(FD),

* in particular the automaton/3 (finite-state/RE) constraint.

nono(Rows, Cols, Grid),

label(Vars),

File nonogram.pl, used to read data in a file.

open('C:/Users/Utilisateur/Documents/Prolog/Rosetta/nonogram/nonogram.txt',

read, In, []),

compute_values([X | T], Current, Tmp, R) :-

V is X - 64,

 

=={{header|Python}}==

 

=== Python 2 ===

 

def gen_row(w, s):

solve("B A A\nA A A")

 

{{out}}

<pre>

=== Python 3 ===

Above code altered to work with Python 3:

 

def gen_row(w, s):

print("Vertical runs:", s[1])

deduce(s[0], s[1])

 

=={{header|Racket}}==

===Translation of Go===

{{trans|Go}}

 

sub reduce(\a, \b) {

"E CB BAB AAA AAA AC BB ACC ACCA AGB AIA AJ AJ "

~"ACE AH BAF CAG DAG FAH FJ GJ ADK ABK BL CM" ),

 

===Translation of Perl===

{{trans|Perl}}

 

my (@rpats,@cpats) := @_[0,1]>>.&makepatterns;

 

loop (my $prev = ''; $prev ne ~@rows; ) {

my $pos = 0;

while ( @lines[$i] ~~ m:g/\./ and $pos < @lines[$i].chars ) {

}

$pos++;

==> map( *.join: '<[0.]>+' )

==> map( '^<[0.]>*' ~ * ~ '<[0.]>*$' )

 

=={{header|REXX}}==

Nonogram Solver/Rexx:

Parse Arg fn

Parse Var fn ou'.'

If ii > mx Then mx = ii

End

{{out}}

<pre>

{{libheader|Wren-pattern}}

{{libheader|Wren-math}}

 

var p = Pattern.new("/s")

]

 

 

{{out}}