Nonogram solver: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H and removed unnecessary import.
m (→{{header|Wren}}: Changed to Wren S/H and removed unnecessary import.) |
|||
| (43 intermediate revisions by 21 users not shown) | |||
Line 49:
'''Extra credit''': generate nonograms with unique solutions, of desired height and width.
<br><br>
This task is the problem n.98 of the "[https://sites.google.com/site/prologsite/prolog-problems 99 Prolog Problems]" [https://web.archive.org/web/20230406102539/https://sites.google.com/site/prologsite/prolog-problems (archived)] by Werner Hett (also thanks to Paul Singleton for the idea and the examples).
<br><br>
; Related tasks
Line 60:
* http://picolisp.com/5000/!wiki?99p98 (PicoLisp)
<br><br>
=={{header|11l}}==
{{trans|Python 3}}
<syntaxhighlight lang="11l">F gen_row(w, s)
‘Create all patterns of a row or col that match given runs.’
F gen_seg([[Int]] o, Int sp) -> [[Int]]
I o.empty
R [[2] * sp]
[[Int]] r
L(x) 1 .< sp - o.len + 2
L(tail) @gen_seg(o[1..], sp - x)
r [+]= [2] * x [+] o[0] [+] tail
R r
R gen_seg(s.map(i -> [1] * i), w + 1 - sum(s)).map(x -> x[1..])
F deduce(hr, vr)
‘Fix inevitable value of cells, and propagate.’
F allowable(row)
R row.reduce((a, b) -> zip(a, b).map((x, y) -> x [|] y))
F fits(a, b)
R all(zip(a, b).map((x, y) -> x [&] y))
V (w, h) = (vr.len, hr.len)
V rows = hr.map(x -> gen_row(@w, x))
V cols = vr.map(x -> gen_row(@h, x))
V can_do = rows.map(allowable)
V mod_rows = Set[Int]()
V mod_cols = Set(0 .< w)
F fix_col(n)
‘See if any value in a given column is fixed;
if so, mark its corresponding row for future fixup.’
V c = @can_do.map(x -> x[@n])
@cols[n] = @cols[n].filter(x -> @@fits(x, @c))
L(x) @allowable(@cols[n])
V i = L.index
I x != @can_do[i][n]
@mod_rows.add(i)
@can_do[i][n] [&]= x
F fix_row(n)
‘Ditto, for rows.’
V c = @can_do[n]
@rows[n] = @rows[n].filter(x -> @@fits(x, @c))
L(x) @allowable(@rows[n])
V i = L.index
I x != @can_do[n][i]
@mod_cols.add(i)
@can_do[n][i] [&]= x
F show_gram(m)
L(x) m
print(x.map(i -> ‘x#.?’[i]).join(‘ ’))
print()
L !mod_cols.empty
L(i) mod_cols
fix_col(i)
mod_cols.clear()
L(i) mod_rows
fix_row(i)
mod_rows.clear()
I all(multiloop((0 .< w), (0 .< h), (j, i) -> @can_do[i][j] C (1, 2)))
print(‘Solution would be unique’)
E
print(‘Solution may not be unique, doing exhaustive search:’)
V out = [[Int]()] * h
F try_all(Int n) -> Int
I n >= @h
L(j) 0 .< @w
I @out.map(x -> x[@j]) !C @cols[j]
R 0
@show_gram(@out)
R 1
V sol = 0
L(x) @rows[n]
@out[n] = x
sol += @try_all(n + 1)
R sol
V n = try_all(0)
I n == 0
print(‘No solution.’)
E I n == 1
print(‘Unique solution.’)
E
print(n‘ solutions.’)
print()
F solve(p, show_runs = 1B)
[[[Int]]] s
L(l) p.split("\n")
s [+]= l.split(‘ ’).map(w -> w.map(c -> c.code - ‘A’.code + 1))
I show_runs
print(‘Horizontal runs: ’s[0])
print(‘Vertical runs: ’s[1])
deduce(s[0], s[1])
L(p) File(‘nonogram_problems.txt’).read().split("\n\n")
solve(p)
print(‘Extra example not solvable by deduction alone:’)
solve("B B A A\nB B A A")
print(‘Extra example where there is no solution:’)
solve("B A A\nA A A")</syntaxhighlight>
{{out}}
<pre>
Horizontal runs: [[3], [2, 1], [3, 2], [2, 2], [6], [1, 5], [6], [1], [2]]
Vertical runs: [[1, 2], [3, 1], [1, 5], [7, 1], [5], [3], [4], [3]]
Solution would be unique
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .
Unique solution.
(... etc. ...)
</pre>
=={{header|C sharp}}==
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using static System.Linq.Enumerable;
public static class NonogramSolver
{
public static void Main2() {
foreach (var (x, y) in new [] {
("C BA CB BB F AE F A B", "AB CA AE GA E C D C"),
("F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA"),
("CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC"),
("E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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")
})
{
Solve(x, y);
Console.WriteLine();
}
}
static void Solve(string rowLetters, string columnLetters) {
var r = rowLetters.Split(" ").Select(row => row.Select(s => s - 'A' + 1).ToArray()).ToArray();
var c = columnLetters.Split(" ").Select(column => column.Select(s => s - 'A' + 1).ToArray()).ToArray();
Solve(r, c);
}
static void Solve(int[][] rowRuns, int[][] columnRuns) {
int len = columnRuns.Length;
var rows = rowRuns.Select(row => Generate(len, row)).ToList();
var columns = columnRuns.Select(column => Generate(rowRuns.Length, column)).ToList();
Reduce(rows, columns);
foreach (var list in rows) {
if (list.Count != 1) Console.WriteLine(Repeat('?', len).Spaced());
else Console.WriteLine(list[0].ToString().PadLeft(len, '0').Replace('1', '#').Replace('0', '.').Reverse().Spaced());
}
}
static List<BitSet> Generate(int length, params int[] runs) {
var list = new List<BitSet>();
BitSet initial = BitSet.Empty;
int[] sums = new int[runs.Length];
sums[0] = 0;
for (int i = 1; i < runs.Length; i++) sums[i] = sums[i - 1] + runs[i - 1] + 1;
for (int r = 0; r < runs.Length; r++) initial = initial.AddRange(sums[r], runs[r]);
Generate(list, BitSet.Empty.Add(length), runs, sums, initial, 0, 0);
return list;
}
static void Generate(List<BitSet> result, BitSet max, int[] runs, int[] sums, BitSet current, int index, int shift) {
if (index == runs.Length) {
result.Add(current);
return;
}
while (current.Value < max.Value) {
Generate(result, max, runs, sums, current, index + 1, shift);
current = current.ShiftLeftAt(sums[index] + shift);
shift++;
}
}
static void Reduce(List<List<BitSet>> rows, List<List<BitSet>> columns) {
for (int count = 1; count > 0; ) {
foreach (var (rowIndex, row) in rows.WithIndex()) {
var allOn = row.Aggregate((a, b) => a & b);
var allOff = row.Aggregate((a, b) => a | b);
foreach (var (columnIndex, column) in columns.WithIndex()) {
count = column.RemoveAll(c => allOn.Contains(columnIndex) && !c.Contains(rowIndex));
count += column.RemoveAll(c => !allOff.Contains(columnIndex) && c.Contains(rowIndex));
}
}
foreach (var (columnIndex, column) in columns.WithIndex()) {
var allOn = column.Aggregate((a, b) => a & b);
var allOff = column.Aggregate((a, b) => a | b);
foreach (var (rowIndex, row) in rows.WithIndex()) {
count += row.RemoveAll(r => allOn.Contains(rowIndex) && !r.Contains(columnIndex));
count += row.RemoveAll(r => !allOff.Contains(rowIndex) && r.Contains(columnIndex));
}
}
}
}
static IEnumerable<(int index, T element)> WithIndex<T>(this IEnumerable<T> source) {
int i = 0;
foreach (T element in source) {
yield return (i++, element);
}
}
static string Reverse(this string s) {
char[] array = s.ToCharArray();
Array.Reverse(array);
return new string(array);
}
static string Spaced(this IEnumerable<char> s) => string.Join(" ", s);
struct BitSet //Unused functionality elided.
{
public static BitSet Empty => default;
private readonly int bits;
public int Value => bits;
private BitSet(int bits) => this.bits = bits;
public BitSet Add(int item) => new BitSet(bits | (1 << item));
public BitSet AddRange(int start, int count) => new BitSet(bits | (((1 << (start + count)) - 1) - ((1 << start) - 1)));
public bool Contains(int item) => (bits & (1 << item)) != 0;
public BitSet ShiftLeftAt(int index) => new BitSet((bits >> index << (index + 1)) | (bits & ((1 << index) - 1)));
public override string ToString() => Convert.ToString(bits, 2);
public static BitSet operator &(BitSet a, BitSet b) => new BitSet(a.bits & b.bits);
public static BitSet operator |(BitSet a, BitSet b) => new BitSet(a.bits | b.bits);
}
}</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .
. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #
. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #</pre>
=={{header|C++}}==
===The Solver===
<
// A class to solve Nonogram (Hadje) Puzzles
// Nigel Galloway - January 23rd., 2017
Line 77 ⟶ 399:
if ((n+1) < ng.size()) {if (fe(g+e+l,1,false)) fn(n+1,i-e-1,g+e+l+1,ng[n+1],0);}
else {
if (fe(g+e+l,gNG-(g+e+l),false)){Tb &= T.flip(); Tx &= T.flip(); ++En;}
if (l<=gNG-g-i-1) fn(n,i,g,e,l+1);
}
Line 96 ⟶ 415:
return En;
}}; // end of N
std::vector<N<_G>> ng;
std::vector<N<_N>> gn;
int En, zN, zG;
void setCell(uint n, uint i, bool g){ng[n].fi(i,g); gn[i].fi(n,g);}
Line 118 ⟶ 437:
}
if (i == En) return false; else En = i;
if (i == zN+zG) return true; else return solve();
}
const std::string toStr() const {
Line 125 ⟶ 444:
return n.str();
}};
</syntaxhighlight>
===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
Line 158 ⟶ 478:
std::cout << "\n" << myN.toStr() << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
C BA CB BB F AE F A B
AB CA AE GA E C D C
.###....
##.#....
.###..##
..##..##
..######
#.#####.
######..
....#...
...##...
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
..........######....
........###.#..###..
...#..###...#....###
..###.##############
...#..#............#
..#.#.##..........##
#####..##........##.
#####...#........#..
#####..###.###.###..
########.###.###.###
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
....###.#...........
....##.####.#.......
....#.###.###.......
..##.####...........
.###.###.#....###...
###..##.##...#.###..
##..##.##....##.##..
....##.#.#..##.#.#..
....#.##.#...####...
....#.#.##.....##...
.....##.##..########
....##.##...##..####
....#.##.##.#...#..#
###..###.#####.....#
#.#.###.#....#....##
##..###.#....###.###
.#.###.##.########..
.####.###.########..
...#.####.##.#####..
...#.####.##...##...
....####..##...#####
...#####.###...#####
...####.#..........#
..####.##...........
..###.###...........
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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
....................#####
..##..............###..##
.##..............#####..#
##.............########..
##....#####.###########..
#.#..##....#....######...
#..##.....#.......###....
##........#.............#
.##.....######.........##
..###############....####
.....##########..########
....##.#.####.###..######
........#################
........#################
.......##################
.......#...##############
.......#.#.##############
........#####...#########
.................########
..................#######
</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},
Line 240 ⟶ 643:
std::cout << "\n" << myN.toStr() << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
#######.###...#.#.#######
#.....#.##.##.....#.....#
#.###.#.....###.#.#.###.#
#.###.#.#..######.#.###.#
#.###.#..#####.##.#.###.#
#.....#..##.......#.....#
#######.#.#.#.#.#.#######
........###...###........
#.##.###..#.#.###.#..#.##
#.#......###.##....#...#.
.####.#.####.##.#....##..
.#.#...#...#.#.####.#.###
..##..#.#.#......##.#####
...###.##.##.######.###.#
#.#########.#.#..##....#.
.##.#..##...##.###.....#.
###.#.#.#..#....#####.#..
........#...##.##...#####
#######.#..##...#.#.#.###
#.....#.##..#..##...##.#.
#.###.#...####..#####..#.
#.###.#.###.##########.##
#.###.#.#..######.######.
#.....#..##......#.#.##..
#######.##...#.##...#####
</pre>
=={{header|Common Lisp}}==
<
(:use :cl)
(:export :var
Line 395 ⟶ 826:
(defun parse-word (word)
(map 'list (lambda (c) (
(defun parse-line (line)
Line 417 ⟶ 848:
(nonogram (parse-nonogram (read-until-line s)
(read-until-line s)))))
(end-of-file ())))</
{{out}}
<pre>CL-USER> (time (nonogram::solve-from-file "c:/Users/cro/Dropbox/Projects/rosetta-code/nonogram_problems.txt"))
Line 508 ⟶ 939:
=={{header|D}}==
{{trans|Python}}
<
/// Create all patterns of a row or col that match given runs.
Line 643 ⟶ 1,074:
"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]]
Line 762 ⟶ 1,193:
=={{header|F_Sharp|F#}}==
<
(*
I define a discriminated union to provide Nonogram Solver functionality.
Line 798 ⟶ 1,229:
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))
</syntaxhighlight>
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)
Line 808 ⟶ 1,239:
Some(fl (file.ReadLine().Split ' ') (file.ReadLine().Split ' '))
with | _ -> printfn "Error reading file" ; None
</syntaxhighlight>
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"
</syntaxhighlight>
{{out}}
<pre>
Line 895 ⟶ 1,326:
.................XXXXXXXX
..................XXXXXXX
</pre>
=={{header|Go}}==
{{trans|Java}}
<syntaxhighlight lang="go">package main
import (
"fmt"
"strings"
)
type BitSet []bool
func (bs BitSet) and(other BitSet) {
for i := range bs {
if bs[i] && other[i] {
bs[i] = true
} else {
bs[i] = false
}
}
}
func (bs BitSet) or(other BitSet) {
for i := range bs {
if bs[i] || other[i] {
bs[i] = true
} else {
bs[i] = false
}
}
}
func iff(cond bool, s1, s2 string) string {
if cond {
return s1
}
return s2
}
func newPuzzle(data [2]string) {
rowData := strings.Fields(data[0])
colData := strings.Fields(data[1])
rows := getCandidates(rowData, len(colData))
cols := getCandidates(colData, len(rowData))
for {
numChanged := reduceMutual(cols, rows)
if numChanged == -1 {
fmt.Println("No solution")
return
}
if numChanged == 0 {
break
}
}
for _, row := range rows {
for i := 0; i < len(cols); i++ {
fmt.Printf(iff(row[0][i], "# ", ". "))
}
fmt.Println()
}
fmt.Println()
}
// collect all possible solutions for the given clues
func getCandidates(data []string, le int) [][]BitSet {
var result [][]BitSet
for _, s := range data {
var lst []BitSet
a := []byte(s)
sumBytes := 0
for _, b := range a {
sumBytes += int(b - 'A' + 1)
}
prep := make([]string, len(a))
for i, b := range a {
prep[i] = strings.Repeat("1", int(b-'A'+1))
}
for _, r := range genSequence(prep, le-sumBytes+1) {
bits := []byte(r[1:])
bitset := make(BitSet, len(bits))
for i, b := range bits {
bitset[i] = b == '1'
}
lst = append(lst, bitset)
}
result = append(result, lst)
}
return result
}
func genSequence(ones []string, numZeros int) []string {
le := len(ones)
if le == 0 {
return []string{strings.Repeat("0", numZeros)}
}
var result []string
for x := 1; x < numZeros-le+2; x++ {
skipOne := ones[1:]
for _, tail := range genSequence(skipOne, numZeros-x) {
result = append(result, strings.Repeat("0", x)+ones[0]+tail)
}
}
return result
}
/* If all the candidates for a row have a value in common for a certain cell,
then it's the only possible outcome, and all the candidates from the
corresponding column need to have that value for that cell too. The ones
that don't, are removed. The same for all columns. It goes back and forth,
until no more candidates can be removed or a list is empty (failure).
*/
func reduceMutual(cols, rows [][]BitSet) int {
countRemoved1 := reduce(cols, rows)
if countRemoved1 == -1 {
return -1
}
countRemoved2 := reduce(rows, cols)
if countRemoved2 == -1 {
return -1
}
return countRemoved1 + countRemoved2
}
func reduce(a, b [][]BitSet) int {
countRemoved := 0
for i := 0; i < len(a); i++ {
commonOn := make(BitSet, len(b))
for j := 0; j < len(b); j++ {
commonOn[j] = true
}
commonOff := make(BitSet, len(b))
// determine which values all candidates of a[i] have in common
for _, candidate := range a[i] {
commonOn.and(candidate)
commonOff.or(candidate)
}
// remove from b[j] all candidates that don't share the forced values
for j := 0; j < len(b); j++ {
fi, fj := i, j
for k := len(b[j]) - 1; k >= 0; k-- {
cnd := b[j][k]
if (commonOn[fj] && !cnd[fi]) || (!commonOff[fj] && cnd[fi]) {
lb := len(b[j])
copy(b[j][k:], b[j][k+1:])
b[j][lb-1] = nil
b[j] = b[j][:lb-1]
countRemoved++
}
}
if len(b[j]) == 0 {
return -1
}
}
}
return countRemoved
}
func main() {
p1 := [2]string{"C BA CB BB F AE F A B", "AB CA AE GA E C D C"}
p2 := [2]string{
"F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA",
}
p3 := [2]string{
"CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH " +
"BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF " +
"AAAAD BDG CEF CBDB BBB FC",
}
p4 := [2]string{
"E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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",
}
for _, puzzleData := range [][2]string{p1, p2, p3, p4} {
newPuzzle(puzzleData)
}
}</syntaxhighlight>
{{out}}
<pre>
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .
. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #
. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #
</pre>
=={{header|Haskell}}==
{{works with|GHC|8.10.7}}
{{libheader|csp}}
<syntaxhighlight lang="haskell">import Control.Applicative ((<|>))
import Control.Monad
import Control.Monad.CSP
import Data.List (transpose)
import System.Environment (getArgs)
import Text.ParserCombinators.ReadP (ReadP)
import qualified Text.ParserCombinators.ReadP as P
import Text.Printf (printf)
main :: IO ()
main = do
file <- parseArgs
printf "reading problem file from %s\n" file
ps <- parseProblems file
forM_ ps $ \p -> do
print p
putStrLn ""
printSolution $ solve p
putStrLn ""
-------------------------------------------------------------------------------
-- parsing
-------------------------------------------------------------------------------
parseArgs :: IO FilePath
parseArgs = do
args <- getArgs
case args of
[file] -> return file
_ -> ioError $ userError "expected exactly one command line argument, the name of the problem file"
data Problem = Problem
{ rows :: [[Int]]
, cols :: [[Int]]
} deriving (Show, Read, Eq, Ord)
entryP :: ReadP Int
entryP = do
n <- fromEnum <$> P.get
if n < 65 || n > 90
then P.pfail
else return $ n - 64
blankP, eolP :: ReadP Char
blankP = P.char ' '
eolP = P.char '\n'
entriesP :: ReadP [Int]
entriesP = ([] <$ blankP) <|> P.many1 entryP
lineP :: ReadP [[Int]]
lineP = P.sepBy1 entriesP blankP <* eolP
problemP :: ReadP Problem
problemP = Problem <$> lineP <*> lineP
problemsP :: ReadP [Problem]
problemsP = P.sepBy1 problemP (P.many blankP <* eolP) <* P.eof
parseProblems :: FilePath -> IO [Problem]
parseProblems file = do
s <- readFile file
case P.readP_to_S problemsP s of
[(ps, "")] -> return ps
_ -> ioError $ userError $ "error parsing file " <> file
-------------------------------------------------------------------------------
-- CSP
-------------------------------------------------------------------------------
solve :: Problem -> [[Bool]]
solve = oneCSPSolution . problemCSP
problemCSP :: Problem -> CSP r [[DV r Bool]]
problemCSP p = do
let rowCount = length $ rows p
colCount = length $ cols p
cells <- replicateM rowCount
$ replicateM colCount
$ mkDV [False, True]
forM_ (zip cells $ rows p) $ uncurry rowOrColCSP
forM_ (zip (transpose cells) $ cols p) $ uncurry rowOrColCSP
return cells
rowOrColCSP :: [DV r Bool] -> [Int] -> CSP r ()
rowOrColCSP ws [] = forM_ ws $ constraint1 not
rowOrColCSP ws xs = do
let vs = zip [0 ..] ws
n = length ws
blocks <- forM xs $ \x ->
mkDV [(i, i + x - 1) | i <- [0 .. n - x]] -- the blocks, given by first and last index
-- blocks must be separate and not overlapping
f blocks
-- cells in blocks are set
forM_ blocks $ \x ->
forM_ vs $ \(i, y) ->
constraint2 (\(x1, x2) b -> i < x1 || i > x2 || b) x y
-- cells before the first block are not set
forM_ vs $ \(i, y) ->
constraint2 (\(y', _) b -> i >= y' || not b) (head blocks) y
-- cells after the last block are not set
forM_ vs $ \(i, y) ->
constraint2 (\(_, y') b -> i <= y' || not b) (last blocks) y
-- cells between blocks are not set
forM_ (zip blocks $ tail blocks) $ \(x, y) ->
forM_ vs $ \(i, z) ->
constraint3 (\(_, x') (y', _) b -> i <= x' || i >= y' || not b) x y z
where
f :: [DV r (Int, Int)] -> CSP r ()
f (u : v : bs) = do
constraint2 (\(_, u') (v', _) -> v' >= u' + 2) u v
f $ v : bs
f _ = return ()
-------------------------------------------------------------------------------
-- printing
-------------------------------------------------------------------------------
printSolution :: [[Bool]] -> IO ()
printSolution bss =
forM_ bss $ \bs -> do
forM_ bs $ \b ->
putChar $ if b then '#' else '.'
putChar '\n'</syntaxhighlight>
{{out}}
<pre>
time cabal run nonogram-solver -- nonogram-problems.txt
reading problem file from nonogram-problems.txt
Problem {rows = [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]], cols = [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]]}
.###....
##.#....
.###..##
..##..##
..######
#.#####.
######..
....#...
...##...
Problem {rows = [[6],[3,1,3],[1,3,1,3],[3,14],[1,1,1],[1,1,2,2],[5,2,2],[5,1,1],[5,3,3,3],[8,3,3,3]], cols = [[4],[4],[1,5],[3,4],[1,5],[1],[4,1],[2,2,2],[3,3],[1,1,2],[2,1,1],[1,1,2],[4,1],[1,1,2],[1,1,1],[2,1,2],[1,1,1],[3,4],[2,2,1],[4,1]]}
..........######....
........###.#..###..
...#..###...#....###
..###.##############
...#..#............#
..#.#.##..........##
#####..##........##.
#####...#........#..
#####..###.###.###..
########.###.###.###
Problem {rows = [[3,1],[2,4,1],[1,3,3],[2,4],[3,3,1,3],[3,2,2,1,3],[2,2,2,2,2],[2,1,1,2,1,1],[1,2,1,4],[1,1,2,2],[2,2,8],[2,2,2,4],[1,2,2,1,1,1],[3,3,5,1],[1,1,3,1,1,2],[2,3,1,3,3],[1,3,2,8],[4,3,8],[1,4,2,5],[1,4,2,2],[4,2,5],[5,3,5],[4,1,1],[4,2],[3,3]], cols = [[2,3],[3,1,3],[3,2,1,2],[2,4,4],[3,4,2,4,5],[2,5,2,4,6],[1,4,3,4,6,1],[4,3,3,6,2],[4,2,3,6,3],[1,2,4,2,1],[2,2,6],[1,1,6],[2,1,4,2],[4,2,6],[1,1,1,1,4],[2,4,7],[3,5,6],[3,2,4,2],[2,2,2],[6,3]]}
....###.#...........
....##.####.#.......
....#.###.###.......
..##.####...........
.###.###.#....###...
###..##.##...#.###..
##..##.##....##.##..
....##.#.#..##.#.#..
....#.##.#...####...
....#.#.##.....##...
.....##.##..########
....##.##...##..####
....#.##.##.#...#..#
###..###.#####.....#
#.#.###.#....#....##
##..###.#....###.###
.#.###.##.########..
.####.###.########..
...#.####.##.#####..
...#.####.##...##...
....####..##...#####
...#####.###...#####
...####.#..........#
..####.##...........
..###.###...........
Problem {rows = [[5],[2,3,2],[2,5,1],[2,8],[2,5,11],[1,1,2,1,6],[1,2,1,3],[2,1,1],[2,6,2],[15,4],[10,8],[2,1,4,3,6],[17],[17],[18],[1,14],[1,1,14],[5,9],[8],[7]], cols = [[5],[3,2],[2,1,2],[1,1,1],[1,1,1],[1,3],[2,2],[1,3,3],[1,3,3,1],[1,7,2],[1,9,1],[1,10],[1,10],[1,3,5],[1,8],[2,1,6],[3,1,7],[4,1,7],[6,1,8],[6,10],[7,10],[1,4,11],[1,2,11],[2,12],[3,13]]}
....................#####
..##..............###..##
.##..............#####..#
##.............########..
##....#####.###########..
#.#..##....#....######...
#..##.....#.......###....
##........#.............#
.##.....######.........##
..###############....####
.....##########..########
....##.#.####.###..######
........#################
........#################
.......##################
.......#...##############
.......#.#.##############
........#####...#########
.................########
..................#######
real 0m0,244s
user 0m0,208s
sys 0m0,031s
</pre>
=={{header|Java}}==
{{works with|Java|8}}
<
import static java.util.Arrays.*;
import static java.util.stream.Collectors.toList;
Line 1,040 ⟶ 1,953:
return countRemoved;
}
}</
<pre>. # # # . . . .
# # . # . . . .
Line 1,108 ⟶ 2,021:
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">using Base.Iterators
struct NonogramPuzzle
nrows::Int
ncols::Int
xhints::Vector{Vector{Int}}
yhints::Vector{Vector{Int}}
solutions:: Vector{Any}
NonogramPuzzle(xh, yh) = new(length(xh), length(yh), xh, yh, Vector{NTuple{4,Array{Int64,1}}}())
end
ycols2xrows(ycols) = [[ycols[i][j] for i in eachindex(ycols)] for j in eachindex(ycols[1])]
function hintsfromcol(rowvec, col, nrows)
hints = Vector{Int}()
hintrun = 0
for row in rowvec
if row[col] != 0
hintrun += 1
if col == nrows
push!(hints, hintrun)
end
elseif hintrun > 0
push!(hints, hintrun)
hintrun = 0
end
end
hints
end
function nonoblocks(hints, len)
minsized(arr) = vcat(map(x -> vcat(fill(1, x), [0]), arr)...)[1:end-1]
minlen(arr) = sum(arr) + length(arr) - 1
if isempty(hints)
return fill(0, len)
elseif minlen(hints) == len
return minsized(hints)
end
possibilities = Vector{Vector{Int}}()
allbuthead = hints[2:end]
for leftspace in 0:(len - minlen(hints))
header = vcat(fill(0, leftspace), fill(1, hints[1]), [0])
rightspace = len - length(header)
if isempty(allbuthead)
push!(possibilities, rightspace <= 0 ? header[1:len] : vcat(header, fill(0, rightspace)))
elseif minlen(allbuthead) == rightspace
push!(possibilities, vcat(header, minsized(allbuthead)))
else
foreach(x -> push!(possibilities, vcat(header, x)), nonoblocks(allbuthead, rightspace))
end
end
possibilities
end
function exclude!(xchoices, ychoices)
andvec(a) = findall(x -> x == 1, foldl((x, y) -> [x[i] & y[i] for i in 1:length(x)], a))
orvec(a) = findall(x -> x == 0, foldl((x, y) -> [x[i] | y[i] for i in 1:length(x)], a))
filterbyval!(arr, val, pos) = if !isempty(arr) filter!(x -> x[pos] == val, arr); end
ensurevecvec(arr::Vector{Vector{Int}}) = arr
ensurevecvec(arr::Vector{Int}) = [arr]
function excl!(choices, otherchoices)
for i in 1:length(choices)
if length(choices[i]) > 0
all1 = andvec(choices[i])
all0 = orvec(choices[i])
foreach(n -> filterbyval!(otherchoices[n], 1, i), all1)
foreach(n -> filterbyval!(otherchoices[n], 0, i), all0)
end
end
end
xclude!(x, y) = (excl!(x, y); x = map(ensurevecvec, x); y = map(ensurevecvec, y); (x, y))
xlen, ylen = sum(map(length, xchoices)), sum(map(length, ychoices))
while true
ychoices, xchoices = xclude!(ychoices, xchoices)
if any(isempty, xchoices)
return
end
xchoices, ychoices = xclude!(xchoices, ychoices)
if any(isempty, ychoices)
return
end
newxlen, newylen = sum(map(length, xchoices)), sum(map(length, ychoices))
if newxlen == xlen && newylen == ylen
return
end
xlen, ylen = newxlen, newylen
end
end
function trygrids(nonogram)
xchoices = [nonoblocks(nonogram.xhints[i], nonogram.ncols) for i in 1:nonogram.nrows]
ychoices = [nonoblocks(nonogram.yhints[i], nonogram.nrows) for i in 1:nonogram.ncols]
exclude!(xchoices, ychoices)
if all(x -> length(x) == 1, xchoices)
println("Unique solution.")
push!(nonogram.solutions, [x[1] for x in xchoices])
elseif all(x -> length(x) == 1, ychoices)
println("Unique solution.")
ycols = [y[1] for y in ychoices]
push!(nonogram.solutions, ycols2xrows(ycols))
else
println("Brute force: $(prod(map(length, xchoices))) possibilities.")
for stack in product(xchoices...)
arr::Vector{Vector{Int}} = [i isa Vector ? i : [i] for i in stack]
if all(x -> length(x) == nonogram.ncols, arr) &&
all(y -> hintsfromcol(arr, y, nonogram.nrows) == nonogram.yhints[y], 1:nonogram.ncols)
push!(nonogram.solutions, arr)
end
end
nsoln = length(nonogram.solutions)
println(nsoln == 0 ? "No" : nsoln, " solutions.")
end
end
# The first puzzle below requires brute force, and the second has no solutions.
const testnonograms = """
B B A A
B B A A
B A A
A A A
C BA CB BB F AE F A B
AB CA AE GA E C D C
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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
"""
function processtestpuzzles(txt)
solutiontxt(a) = (s = ""; for r in a for c in r; s *= (c == 0 ? "." : "#") end; s *= "\n" end; s)
txtline2ints(s) = [[UInt8(ch - 'A' + 1) for ch in r] for r in split(s, r"\s+")]
linepairs = uppercase.(string.(split(txt, "\n\n")))
pcount = 0
for xyhints in linepairs
xh, yh = map(x -> txtline2ints(strip(x)), split(xyhints, "\n"))
nonogram = NonogramPuzzle(xh, yh)
println("\nPuzzle $(pcount += 1):")
trygrids(nonogram)
foreach(x -> println(solutiontxt(x), "\n"), nonogram.solutions)
end
end
processtestpuzzles(testnonograms)
</syntaxhighlight>
<pre>
Puzzle 1:
Brute force: 144 possibilities.
2 solutions.
.##.
##..
#...
...#
##..
##..
..#.
...#
Puzzle 2:
Brute force: 8 possibilities.
No solutions.
Puzzle 3:
Unique solution.
.###....
##.#....
.###..##
..##..##
..######
#.#####.
######..
....#...
...##...
Puzzle 4:
Unique solution.
..........######....
........###.#..###..
...#..###...#....###
..###.##############
...#..#............#
..#.#.##..........##
#####..##........##.
#####...#........#..
#####..###.###.###..
########.###.###.###
Puzzle 5:
Unique solution.
....###.#...........
....##.####.#.......
....#.###.###.......
..##.####...........
.###.###.#....###...
###..##.##...#.###..
##..##.##....##.##..
....##.#.#..##.#.#..
....#.##.#...####...
....#.#.##.....##...
.....##.##..########
....##.##...##..####
....#.##.##.#...#..#
###..###.#####.....#
#.#.###.#....#....##
##..###.#....###.###
.#.###.##.########..
.####.###.########..
...#.####.##.#####..
...#.####.##...##...
....####..##...#####
...#####.###...#####
...####.#..........#
..####.##...........
..###.###...........
Puzzle 6:
Unique solution.
....................#####
..##..............###..##
.##..............#####..#
##.............########..
##....#####.###########..
#.#..##....#....######...
#..##.....#.......###....
##........#.............#
.##.....######.........##
..###############....####
.....##########..########
....##.#.####.###..######
........#################
........#################
.......##################
.......#...##############
.......#.#.##############
........#####...#########
.................########
..................#######</pre>
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.2.0
import java.util.BitSet
typealias BitSets = List<MutableList<BitSet>>
val rx = Regex("""\s""")
fun newPuzzle(data: List<String>) {
val rowData = data[0].split(rx)
val colData = data[1].split(rx)
val rows = getCandidates(rowData, colData.size)
val cols = getCandidates(colData, rowData.size)
do {
val numChanged = reduceMutual(cols, rows)
if (numChanged == -1) {
println("No solution")
return
}
}
while (numChanged > 0)
for (row in rows) {
for (i in 0 until cols.size) {
print(if (row[0][i]) "# " else ". ")
}
println()
}
println()
}
// collect all possible solutions for the given clues
fun getCandidates(data: List<String>, len: Int): BitSets {
val result = mutableListOf<MutableList<BitSet>>()
for (s in data) {
val lst = mutableListOf<BitSet>()
val a = s.toCharArray()
val sumChars = a.sumBy { it - 'A' + 1 }
val prep = a.map { "1".repeat(it - 'A' + 1) }
for (r in genSequence(prep, len - sumChars + 1)) {
val bits = r.substring(1).toCharArray()
val bitset = BitSet(bits.size)
for (i in 0 until bits.size) bitset[i] = bits[i] == '1'
lst.add(bitset)
}
result.add(lst)
}
return result
}
fun genSequence(ones: List<String>, numZeros: Int): List<String> {
if (ones.isEmpty()) return listOf("0".repeat(numZeros))
val result = mutableListOf<String>()
for (x in 1 until numZeros - ones.size + 2) {
val skipOne = ones.drop(1)
for (tail in genSequence(skipOne, numZeros - x)) {
result.add("0".repeat(x) + ones[0] + tail)
}
}
return result
}
/* If all the candidates for a row have a value in common for a certain cell,
then it's the only possible outcome, and all the candidates from the
corresponding column need to have that value for that cell too. The ones
that don't, are removed. The same for all columns. It goes back and forth,
until no more candidates can be removed or a list is empty (failure).
*/
fun reduceMutual(cols: BitSets, rows: BitSets): Int {
val countRemoved1 = reduce(cols, rows)
if (countRemoved1 == -1) return -1
val countRemoved2 = reduce(rows, cols)
if (countRemoved2 == -1) return -1
return countRemoved1 + countRemoved2
}
fun reduce(a: BitSets, b: BitSets): Int {
var countRemoved = 0
for (i in 0 until a.size) {
val commonOn = BitSet()
commonOn[0] = b.size
val commonOff = BitSet()
// determine which values all candidates of a[i] have in common
for (candidate in a[i]) {
commonOn.and(candidate)
commonOff.or(candidate)
}
// remove from b[j] all candidates that don't share the forced values
for (j in 0 until b.size) {
val fi = i
val fj = j
if (b[j].removeIf { cnd ->
(commonOn[fj] && !cnd[fi]) ||
(!commonOff[fj] && cnd[fi]) }) countRemoved++
if (b[j].isEmpty()) return -1
}
}
return countRemoved
}
val p1 = listOf("C BA CB BB F AE F A B", "AB CA AE GA E C D C")
val p2 = listOf(
"F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA"
)
val p3 = listOf(
"CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH " +
"BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF " +
"AAAAD BDG CEF CBDB BBB FC"
)
val p4 = listOf(
"E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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"
)
fun main(args: Array<String>) {
for (puzzleData in listOf(p1, p2, p3, p4)) {
newPuzzle(puzzleData)
}
}</syntaxhighlight>
{{out}}
<pre>
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .
. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #
. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[VisualizeGrid, Possibilities, TryRow, TryColumn]
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},
numclue = Length[clues];
spaces = len - Total[clues];
spacecands = IntegerPartitions[spaces, {numclue - 1}];
spacecands = DeleteDuplicates[Catenate[Permutations /@ spacecands]];
cands = Catenate[Riffle[ConstantArray[1, #] & /@ clues, ConstantArray[0, #] & /@ #]] & /@ spacecands;
spacecands = IntegerPartitions[spaces, {numclue}];
spacecands = DeleteDuplicates[Catenate[Permutations /@ spacecands]];
cands = Join[cands, Catenate[Riffle[ConstantArray[1, #] & /@ clues, ConstantArray[0, #] & /@ #]] & /@ spacecands];
cands = Join[cands, Catenate[Riffle[ConstantArray[0, #] & /@ #, ConstantArray[1, #] & /@ clues]] & /@ spacecands];
spacecands = IntegerPartitions[spaces, {numclue + 1}];
spacecands = DeleteDuplicates[Catenate[Permutations /@ spacecands]];
cands = Join[cands, Catenate[Riffle[ConstantArray[0, #] & /@ #, ConstantArray[1, #] & /@ clues]] & /@ spacecands];
cands
]
TryRow[candgrid_List, i_Integer, hclues_List] := Module[{row, clue, len, poss, newgrid},
row = candgrid[[i]];
clue = hclues[[i]];
len = Length[row];
poss = Possibilities[clue, len];
poss //= Select[MatchQ[Alternatives @@@ row]];
poss //= Transpose;
poss //= Map[Union];
newgrid = candgrid;
newgrid[[i]] = poss;
newgrid
]
TryColumn[candgrid_List, i_Integer, hclues_List] := Transpose[TryRow[Transpose[candgrid], i, hclues]]
puzzles = "C BA CB BB F AE F A B
AB CA AE GA E C D C
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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";
puzzles = StringSplit[puzzles, "\n\n"];
puzzles = StringSplit[#, "\n"] & /@ puzzles;
puzzles = Map[StringSplit[#, " "] &, puzzles, {2}];
puzzles = Map[Characters, puzzles, {3}];
puzzles = puzzles /. Thread[CharacterRange["A", "Z"] -> (ToString /@ Range[26])];
puzzles = Map[ToExpression, puzzles, {4}];
Do[
hclues = puzzles[[n, 1]];
vclues = puzzles[[n, 2]];
{hsize, vsize} = {vclues // Length, hclues // Length};
cand = ConstantArray[{0, 1}, {vsize, hsize}];
oldcand = {};
While[oldcand =!= cand,
oldcand = cand;
Do[cand = TryRow[cand, i, hclues], {i, Length[hclues]}];
Do[cand = TryColumn[cand, i, vclues], {i, Length[vclues]}];
];
Print@VisualizeGrid[cand]
,
{n, 4}
]</syntaxhighlight>
{{out}}
<pre> ###
## #
### ##
## ##
######
# #####
######
#
##
######
### # ###
# ### # ###
### ##############
# # #
# # ## ##
##### ## ##
##### # #
##### ### ### ###
######## ### ### ###
### #
## #### #
# ### ###
## ####
### ### # ###
### ## ## # ###
## ## ## ## ##
## # # ## # #
# ## # ####
# # ## ##
## ## ########
## ## ## ####
# ## ## # # #
### ### ##### #
# # ### # # ##
## ### # ### ###
# ### ## ########
#### ### ########
# #### ## #####
# #### ## ##
#### ## #####
##### ### #####
#### # #
#### ##
### ###
#####
## ### ##
## ##### #
## ########
## ##### ###########
# # ## # ######
# ## # ###
## # #
## ###### ##
############### ####
########## ########
## # #### ### ######
#################
#################
##################
# ##############
# # ##############
##### #########
########
#######</pre>
=={{header|Nim}}==
To generate the sequence, we use the Java algorithm modified to directly generate bit strings (as integers) rather than character strings.
<syntaxhighlight lang="nim">import std/[bitops, math, sequtils, strutils]
type
# Lengths of distinct runs of occupied cells.
Lengths = seq[int]
# Possibility, i.e. sequence of bits managed as an integer.
Possibility = int
# Possibilities described by two masks and a list of integer values.
Possibilities = object
mask0: int # Mask indicating the positions of free cells.
mask1: int # Mask indicating the positions of occupied cells.
list: seq[int] # List of possibilities.
proc genSequence(ones: seq[int]; numZeroes: Natural): seq[Possibility] =
## Generate a sequence of possibilities.
if ones.len == 0: return @[0]
for x in 1..(numZeroes - ones.len + 1):
for tail in genSequence(ones[1..^1], numZeroes - x):
result.add (tail shl countSetBits(ones[0]) or ones[0]) shl x
proc initPossibilities(lengthsList: openArray[Lengths]; length: Positive): seq[Possibilities] =
## Initialize the list of possibilities from a list of lengths.
let initMask0 = 1 shl length - 1
for lengths in lengthsList:
let sumLengths = sum(lengths)
let prep = lengths.mapIt(1 shl it - 1)
let possList = genSequence(prep, length - sumLengths + 1).mapIt(it shr 1)
result.add Possibilities(mask0: initMask0, mask1: 0, list: possList)
func updateUnset(possList: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits not set only).
var mask = mask
for poss in possList.mitems:
if (mask and 1) == 0:
for i in countdown(poss.list.high, 0):
if poss.list[i].testBit(rank):
# Bit is set, so the value is not compatible: remove it.
poss.list.delete(i)
mask = mask shr 1
func updateSet(possList: var seq[Possibilities]; mask, rank: int) =
## Update the lists of possibilities keeping only those
## compatible with the mask (for bits set only).
var mask = mask
for poss in possList.mitems:
if (mask and 1) != 0:
for i in countdown(poss.list.high, 0):
if not poss.list[i].testBit(rank):
# Bit is not set, so the value is not compatible: remove it.
poss.list.delete(i)
mask = mask shr 1
proc process(poss1, poss2: var seq[Possibilities]): bool =
## Look at possibilities in list "poss1", compute the masks for
## bits unset and bits set and update "poss2" accordingly.
var num = 0
for poss in poss1.mitems:
# Check bits unset.
var mask = 0
for value in poss.list:
mask = mask or value
if mask != poss.mask0:
# Mask has changed: update.
result = true
poss2.updateUnset(mask, num)
poss.mask0 = mask
# Check bits set.
mask = 1 shl poss2.len - 1
for value in poss.list:
mask = mask and value
if mask != poss.mask1:
# Mask has changed: update.
result = true
poss2.updateSet(mask, num)
poss.mask1 = mask
inc num
proc solve(rowLengths, colLengths: openArray[Lengths]) =
## Solve nonogram defined by "rowLengths" and "colLengths".
var
rowPoss = initPossibilities(rowLengths, colLengths.len)
colPoss = initPossibilities(colLengths, rowLengths.len)
# Solve nonogram.
var hasChanged = true
while hasChanged:
hasChanged = process(rowPoss, colPoss) or process(colPoss, rowPoss)
# Check if solved.
for poss in rowPoss:
if poss.list.len != 1:
echo "Unable to solve the nonogram."
return
# Display the solution.
for poss in rowPoss:
var line = ""
var val = poss.list[0]
for i in 0..colPoss.high:
line.add if val.testBit(i): "# " else: " "
echo line
func expand(s: string): seq[Lengths] =
## Expand a compact description into a sequence of lengths.
for elem in s.splitWhitespace():
result.add elem.mapIt(ord(it) - ord('A') + 1)
proc solve(rows, cols: string) =
## Solve using compact description parameters.
solve(rows.expand(), cols.expand())
when isMainModule:
const
Data1 = ("C BA CB BB F AE F A B", "AB CA AE GA E C D C")
Data2 = ("F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA")
Data3 = ("CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC")
Data4 = ("E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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")
for (rows, cols) in [Data1, Data2, Data3, Data4]:
echo rows
echo cols
echo ""
solve(rows, cols)
echo ""</syntaxhighlight>
{{out}}
<pre>C BA CB BB F AE F A B
AB CA AE GA E C D C
# # #
# # #
# # # # #
# # # #
# # # # # #
# # # # # #
# # # # # #
#
# #
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
# # # # # #
# # # # # # #
# # # # # # # #
# # # # # # # # # # # # # # # # #
# # #
# # # # # #
# # # # # # # # #
# # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
# # # #
# # # # # # #
# # # # # # #
# # # # # #
# # # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # #
# # # # # # # #
# # # # # # # #
# # # # # #
# # # # # # # # # # # #
# # # # # # # # # #
# # # # # # # #
# # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # #
# # # # # # # # #
# # # # # # # # # # #
# # # # # # # # # # # # #
# # # # # #
# # # # # #
# # # # # #
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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
# # # # #
# # # # # # #
# # # # # # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # #
# # # # # # #
# # # #
# # # # # # # # # #
# # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # #
# # # # # # # # # # # # # #
# # # # # # # #
# # # # # # # </pre>
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(import (owl parse))
; notation parser
(define (subA x) (- x #\A -1))
(define line
(let-parse* (
(words (greedy+ (let-parse* (
(* (greedy* (imm #\space)))
(word (greedy+ (byte-if (lambda (x) (<= #\A x #\Z))))))
(map subA word))))
(* (maybe (imm #\newline) #f)))
words))
(define nonogram-parser
(let-parse* (
(rows line)
(cols line))
(cons rows cols)))
; nonogram printer
(define (print-nonogram ng solve)
(for-each (lambda (row y)
(for-each (lambda (x)
(if (list-ref (list-ref (car solve) y) x)
(display "X ")
(display ". ")))
(iota (length (cdr ng))))
(for-each (lambda (i)
(display " ")
(display i))
row)
(print))
(car ng)
(iota (length (car ng))))
(for-each (lambda (i)
(for-each (lambda (col)
(let ((n (lref col i)))
(if n (display n) (display " ")))
(display " "))
(cdr ng))
(print))
(iota (fold (lambda (f col) (max f (length col))) 0 (cdr ng)) 0)))
; possible permutation generator
(define (permutate blacks len)
; empty cells distibutions (with minimal count)
(define whites (append '(0) (repeat 1 (- (length blacks) 1)) '(0)))
(define total (- len (apply + blacks))) ; total summ of empty cells
(define (combine whites blacks)
; size of whites is always equal to size of blacks+1
(let loop ((line #null) (v #f) (w (reverse whites)) (b (reverse blacks)))
(if (null? w)
line
else
(loop (append (repeat v (car w)) line)
(not v)
b
(cdr w)))))
(map (lambda (whites) (combine whites blacks))
(let loop ((ll whites) (max total))
(if (null? (cdr ll))
(list (list max))
else
(define sum (apply + ll))
(define left (- max sum))
(if (eq? left 0)
(list ll)
else
(define head (car ll))
(fold (lambda (f i)
(define sublist (loop (cdr ll) (- max head i)))
(fold (lambda (f x)
(cons (cons (+ head i) x) f))
f
sublist))
#null
(iota (+ left 1))))))))
; siever of impossible combinations
(define (sieve rows cols) ; -> new cols
(fold (lambda (cols i)
; for every cell define a "definitely black" and "definitely white" cells
(define blacks (fold (lambda (f x)
(map (lambda (a b) (and a b)) f x))
(repeat #t (length cols))
(list-ref rows i)))
(define whites (fold (lambda (f x)
(map (lambda (a b) (or a b)) f x))
(repeat #f (length cols))
(list-ref rows i)))
; now filter the second list
(map (lambda (cols j)
(filter (lambda (col)
(not (or
(and (list-ref blacks j) (not (list-ref col i)))
(and (not (list-ref whites j)) (list-ref col i)))))
cols))
cols
(iota (length cols))))
cols
(iota (length rows))))
; main solver cycle
(define (solve rows-permuted cols-permuted)
(let loop ((rows rows-permuted) (cols cols-permuted) (flip #f))
(define new-cols (sieve rows cols))
(define fail (fold (lambda (f l) (or f (null? l))) #f new-cols))
(define done (fold (lambda (f l) (and f (null? (cdr l)))) #t new-cols))
(cond
(fail
#false)
(done
(if flip
(cons (map car new-cols) (map car rows))
(cons (map car rows) (map car new-cols))))
(else
(loop new-cols rows (not flip))))))
; -=( main )=----------------------------------
(define first "C BA CB BB F AE F A B
AB CA AE GA E C D C")
(define second "F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA")
(define third "CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC")
(define fourth "E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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")
(for-each (lambda (str)
(print "nonogram:")
(print str) (print)
; decode nonogram notation
(define nonogram (parse nonogram-parser (str-iter str) #f #f #f))
; prepare arrays of all possible line b/w permutations
(define rows (car nonogram))
(define cols (cdr nonogram))
(define row-length (length cols))
(define col-length (length rows))
(define rows-permuted (map (lambda (x) (permutate x row-length)) rows))
(define cols-permuted (map (lambda (x) (permutate x col-length)) cols))
; solve nonogram
(define answer (solve rows-permuted cols-permuted))
; show the output
(if answer
(print-nonogram nonogram answer)
(print "Sorry, no aorrect answer found."))
(print))
(list first second third fourth))
</syntaxhighlight>
{{out}}
<pre style="height:60ex;overflow:scroll">
nonogram:
C BA CB BB F AE F A B
AB CA AE GA E C D C
. X X X . . . . 3
X X . X . . . . 2 1
. X X X . . X X 3 2
. . X X . . X X 2 2
. . X X X X X X 6
X . X X X X X . 1 5
X X X X X X . . 6
. . . . X . . . 1
. . . X X . . . 2
1 3 1 7 5 3 4 3
2 1 5 1
nonogram:
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
. . . . . . . . . . . X X X X X X . . . 6
. . . . . . . . X X X . X . . X X X . . 3 1 3
. . . X . . X X X . . . X . . . . X X X 1 3 1 3
. . X X X . X X X X X X X X X X X X X X 3 14
. . . X . . X . . . . . . . . . . . . X 1 1 1
. . X . X . X X . . . . . . . . . . X X 1 1 2 2
X X X X X . . X X . . . . . . . . X X . 5 2 2
X X X X X . . . X . . . . . . . . X . . 5 1 1
X X X X X . . X X X . X X X . X X X . . 5 3 3 3
X X X X X X X X . X X X . X X X . X X X 8 3 3 3
4 4 1 3 1 1 4 2 3 1 2 1 4 1 1 2 1 3 2 4
5 4 5 1 2 3 1 1 1 1 1 1 1 1 4 2 1
2 2 1 2 2 1 2 1 1
nonogram:
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
. . . . X X X . X . . . . . . . . . . . 3 1
. . . . X X . X X X X . X . . . . . . . 2 4 1
. . . . X . X X X . X X X . . . . . . . 1 3 3
. . X X . X X X X . . . . . . . . . . . 2 4
. X X X . X X X . X . . . . X X X . . . 3 3 1 3
. X X X . X X . X X . . . X . X X X . . 3 2 2 1 3
. X X . X X . X X . . . . X X . X X . . 2 2 2 2 2
. . . . X X . X . X . . X X . X . X . . 2 1 1 2 1 1
. . . . X . X X . X . . . X X X X . . . 1 2 1 4
. . . . X . X . X X . . . . . X X . . . 1 1 2 2
. . . . . X X . X X . . X X X X X X X X 2 2 8
. . . . X X . X X . . . X X . . X X X X 2 2 2 4
. . . . X . X X . X X . X . . . X . . X 1 2 2 1 1 1
X X X . . X X X . X X X X X . . . . . X 3 3 5 1
X . X . X X X . X . . . . X . . . . X X 1 1 3 1 1 2
X X . . X X X . X . . . . X X X . X X X 2 3 1 3 3
. X . X X X . X X . X X X X X X X X . . 1 3 2 8
. X X X X . X X X . X X X X X X X X . . 4 3 8
. . . X . X X X X . X X . X X X X X . . 1 4 2 5
. . . X . X X X X . X X . . . X X . . . 1 4 2 2
. . . . X X X X . . X X . . . X X X X X 4 2 5
. . . X X X X X . X X X . . . X X X X X 5 3 5
. . . X X X X . X . . . . . . . . . . X 4 1 1
. . X X X X . X X . . . . . . . . . . . 4 2
. . X X X . X X X . . . . . . . . . . . 3 3
2 3 3 2 3 2 1 4 4 1 2 1 2 4 1 2 3 3 2 6
3 1 2 4 4 5 4 3 2 2 2 1 1 2 1 4 5 2 2 3
3 1 4 2 2 3 3 3 4 6 6 4 6 1 7 6 4 2
2 4 4 4 6 6 2 2 1 2
5 6 6 2 3 1 4
1
nonogram:
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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
. . . . . . . . . . . . . . . . . . . . X X X X X 5
. . X X . . . . . . . . . . . . . . X X X . . X X 2 3 2
. X X . . . . . . . . . . . . . . X X X X X . . X 2 5 1
X X . . . . . . . . . . . . . X X X X X X X X . . 2 8
X X . . . . X X X X X . X X X X X X X X X X X . . 2 5 11
X . X . . X X . . . . X . . . . X X X X X X . . . 1 1 2 1 6
X . . X X . . . . . X . . . . . . . X X X . . . . 1 2 1 3
X X . . . . . . . . X . . . . . . . . . . . . . X 2 1 1
. X X . . . . . X X X X X X . . . . . . . . . X X 2 6 2
. . X X X X X X X X X X X X X X X . . . . X X X X 15 4
. . . . . X X X X X X X X X X . . X X X X X X X X 10 8
. . . . X X . X . X X X X . X X X . . X X X X X X 2 1 4 3 6
. . . . . . . . X X X X X X X X X X X X X X X X X 17
. . . . . . . . X X X X X X X X X X X X X X X X X 17
. . . . . . . X X X X X X X X X X X X X X X X X X 18
. . . . . . . X . . . X X X X X X X X X X X X X X 1 14
. . . . . . . X . X . X X X X X X X X X X X X X X 1 1 14
. . . . . . . . X X X X X . . . X X X X X X X X X 5 9
. . . . . . . . . . . . . . . . . X X X X X X X X 8
. . . . . . . . . . . . . . . . . . X X X X X X X 7
5 3 2 1 1 1 2 1 1 1 1 1 1 1 1 2 3 4 6 6 7 1 1 2 3
2 1 1 1 3 2 3 3 7 9 10 10 3 8 1 1 1 1 10 10 4 2 12 13
2 1 1 3 3 2 1 5 6 7 7 8 11 11
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">use strict;
use warnings;
my $file = 'nonogram_problems.txt';
open my $fd, '<', $file or die "$! opening $file";
while(my $row = <$fd> )
{
$row =~ /\S/ or next;
my $column = <$fd>;
my @rpats = makepatterns($row);
my @cpats = makepatterns($column);
my @rows = ( '.' x @cpats ) x @rpats;
for( my $prev = ''; $prev ne "@rows"; )
{
$prev = "@rows";
try(\@rows, \@rpats);
my @cols = map { join '', map { s/.//; $& } @rows } 0..$#cpats;
try(\@cols, \@cpats);
@rows = map { join '', map { s/.//; $& } @cols } 0..$#rpats;
}
print "\n", "@rows" =~ /\./ ? "Failed\n" : map { tr/01/.#/r, "\n" } @rows;
}
sub try
{
my ($lines, $patterns) = @_;
for my $i ( 0 .. $#$lines )
{
while( $lines->[$i] =~ /\./g )
{
for my $try ( 0, 1 )
{
$lines->[$i] =~ s/.\G/$try/r =~ $patterns->[$i] or
$lines->[$i] =~ s// 1 - $try /e;
}
}
}
}
sub makepatterns { # numbered to show the 'logical' order of operations
map { qr/^$_$/ # 7 convert strings to regex
} map { '[0.]*' # 6a prepend static pattern
. join('[0.]+', # 5 interleave with static pattern
map { "[1.]{$_}" # 4 require to match exactly 'n' times
} map { -64+ord # 3 convert letter value to repetition count 'n'
} split // # 2 for each letter in group
)
. '[0.]*' # 6b append static pattern
} split ' ', shift; # 1 for each letter grouping
}</syntaxhighlight>
{{out}}
<pre>
.###....
##.#....
.###..##
..##..##
..######
#.#####.
######..
....#...
...##...
..........######....
........###.#..###..
...#..###...#....###
..###.##############
...#..#............#
..#.#.##..........##
#####..##........##.
#####...#........#..
#####..###.###.###..
########.###.###.###
....###.#...........
....##.####.#.......
....#.###.###.......
..##.####...........
.###.###.#....###...
###..##.##...#.###..
##..##.##....##.##..
....##.#.#..##.#.#..
....#.##.#...####...
....#.#.##.....##...
.....##.##..########
....##.##...##..####
....#.##.##.#...#..#
###..###.#####.....#
#.#.###.#....#....##
##..###.#....###.###
.#.###.##.########..
.####.###.########..
...#.####.##.#####..
...#.####.##...##...
....####..##...#####
...#####.###...#####
...####.#..........#
..####.##...........
..###.###...........
....................#####
..##..............###..##
.##..............#####..#
##.............########..
##....#####.###########..
#.#..##....#....######...
#..##.....#.......###....
##........#.............#
.##.....######.........##
..###############....####
.....##########..########
....##.#.####.###..######
........#################
........#################
.......##################
.......#...##############
.......#.#.##############
........#####...#########
.................########
..................#######
</pre>
=={{header|Phix}}==
Deduction only, no exhaustive search.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">unsolved</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">count_grid</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)*</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">'?'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">match_mask</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ms</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">me</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ms</span> <span style="color: #008080;">to</span> <span style="color: #000000;">me</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">'?'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">innr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">neat</span><span style="color: #0000FF;">=</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">mi</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">match_mask</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">neat</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'?'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">blocks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">b</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">mi</span> <span style="color: #008080;">to</span> <span style="color: #000000;">e</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'#'</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">match_mask</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">)))</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">innr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">inner</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">innr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">res</span><span style="color: #0000FF;">:</span><span style="color: #000000;">mask</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">global</span> <span style="color: #008080;">function</span> <span style="color: #000000;">vmask</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">source</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">column</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">source</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">source</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">source</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">column</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">logic</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">wasunsolved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unsolved</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inner</span><span style="color: #0000FF;">(</span><span style="color: #000000;">vmask</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">),</span><span style="color: #000000;">y</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">unsolved</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">count_grid</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">wasunsolved</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">unsolved</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
C BA CB BB F AE F A B
AB CA AE GA E C D C
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--Alternatively:
--integer fn = open("nonogram_problems.txt","r")
--tests = get_text(fn,GT_LF_STRIPPED)
--close(fn)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">unpack</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">by</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unpack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unpack</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'?'</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">unsolved</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)*</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">unsolved</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">logic</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"partial"</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</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>
<!--</syntaxhighlight>-->
{{out}}
<pre style="float:left">
###
## #
### ##
## ##
######
# #####
######
#
##
</pre>
<pre style="float:left">
######
### # ###
# ### # ###
### ##############
# # #
# # ## ##
##### ## ##
##### # #
##### ### ### ###
######## ### ### ###
</pre>
<pre style="font-size: 10px; float:left">
### #
## #### #
# ### ###
## ####
### ### # ###
### ## ## # ###
## ## ## ## ##
## # # ## # #
# ## # ####
# # ## ##
## ## ########
## ## ## ####
# ## ## # # #
### ### ##### #
# # ### # # ##
## ### # ### ###
# ### ## ########
#### ### ########
# #### ## #####
# #### ## ##
#### ## #####
##### ### #####
#### # #
#### ##
### ###
</pre>
<pre>
#####
## ### ##
## ##### #
## ########
## ##### ###########
# # ## # ######
# ## # ###
## # #
## ###### ##
############### ####
########## ########
## # #### ### ######
#################
#################
##################
# ##############
# # ##############
##### #########
########
#######
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">import util, sat.
main =>
Hr = "E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
Hc = "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",
Lr = [token_to_hints(Token) : Token in split(Hr)],
Lc = [token_to_hints(Token) : Token in split(Hc)],
MaxR = len(Lr),
MaxC = len(Lc),
foreach (Hints in Lr)
constrain_starts(Hints,MaxC)
end,
foreach (Hints in Lc)
constrain_starts(Hints,MaxR)
end,
M = new_array(MaxR,MaxC),
M :: 0..1,
foreach ({R,Hints} in zip(1..MaxR, Lr))
sum([M[R,C] : C in 1..MaxC]) #= sum([Num : (Num,_) in Hints])
end,
foreach ({R,Hints} in zip(1..MaxR, Lr), (Num,Start) in Hints, C in 1..MaxC-Num+1)
Start #= C #=> sum([M[R,C+I] : I in 0..Num-1]) #= Num
end,
%
foreach ({C,Hints} in zip(1..MaxC, Lc))
sum([M[R,C] : R in 1..MaxR]) #= sum([Num : (Num,_) in Hints])
end,
foreach ({C,Hints} in zip(1..MaxC, Lc), (Num,Start) in Hints, R in 1..MaxR-Num+1)
Start #= R #=> sum([M[R+I,C] : I in 0..Num-1]) #= Num
end,
solve((Lr,Lc,M)),
foreach (R in 1..MaxR)
foreach (C in 1..MaxC)
printf("%2c", cond(M[R,C] == 1, '#', '.'))
end,
nl
end.
% convert "BCB" to [(2,_),(3,_),(2,_)]
% a hint is a pair (Num,Start), where Num is the length of the 1 segment and Start is the starting row number or column number
token_to_hints([]) = [].
token_to_hints([C|Cs]) = [(ord(C)-ord('A')+1, _)|token_to_hints(Cs)].
% there must be a gap between two neighboring segments
constrain_starts([(Num,Start)],Max) =>
Start :: 1..Max,
Start+Num-1 #<= Max.
constrain_starts([(Num1,Start1),(Num2,Start2)|L],Max) =>
Start1 :: 1..Max,
Start1+Num1 #< Start2,
constrain_starts([(Num2,Start2)|L],Max).
</syntaxhighlight>
{{out}}
<pre>
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #
</pre>
=={{header|Prolog}}==
Line 1,115 ⟶ 3,539:
Module solve-nonogram.pl
<syntaxhighlight lang="prolog">/*
* Nonogram/paint-by-numbers solver in SWI-Prolog. Uses CLP(FD),
* in particular the automaton/3 (finite-state/RE) constraint.
Line 1,181 ⟶ 3,605:
nono(Rows, Cols, Grid),
label(Vars),
print(Grid).</
File nonogram.pl, used to read data in a file.
<
open('C:/Users/Utilisateur/Documents/Prolog/Rosetta/nonogram/nonogram.txt',
read, In, []),
Line 1,206 ⟶ 3,630:
compute_values([X | T], Current, Tmp, R) :-
V is X - 64,
compute_values(T, [V | Current], Tmp, R).</
=={{header|Python}}==
First fill cells by deduction, then search through all combinations. It could take up a huge amount of storage, depending on the board size.
=== Python 2 ===
<syntaxhighlight lang="python">from itertools import izip
def gen_row(w, s):
Line 1,328 ⟶ 3,754:
solve("B A A\nA A A")
main()</
{{out}}
<pre>
Line 1,348 ⟶ 3,774:
(... etc. ...)
</pre>
=== Python 3 ===
Above code altered to work with Python 3:
<syntaxhighlight lang="python">from functools import reduce
def gen_row(w, s):
"""Create all patterns of a row or col that match given runs."""
def gen_seg(o, sp):
if not o:
return [[2] * sp]
return [[2] * x + o[0] + tail
for x in range(1, sp - len(o) + 2)
for tail in gen_seg(o[1:], sp - x)]
return [x[1:] for x in gen_seg([[1] * i for i in s], w + 1 - sum(s))]
def deduce(hr, vr):
"""Fix inevitable value of cells, and propagate."""
def allowable(row):
return reduce(lambda a, b: [x | y for x, y in zip(a, b)], row)
def fits(a, b):
return all(x & y for x, y in zip(a, b))
def fix_col(n):
"""See if any value in a given column is fixed;
if so, mark its corresponding row for future fixup."""
c = [x[n] for x in can_do]
cols[n] = [x for x in cols[n] if fits(x, c)]
for i, x in enumerate(allowable(cols[n])):
if x != can_do[i][n]:
mod_rows.add(i)
can_do[i][n] &= x
def fix_row(n):
"""Ditto, for rows."""
c = can_do[n]
rows[n] = [x for x in rows[n] if fits(x, c)]
for i, x in enumerate(allowable(rows[n])):
if x != can_do[n][i]:
mod_cols.add(i)
can_do[n][i] &= x
def show_gram(m):
# If there's 'x', something is wrong.
# If there's '?', needs more work.
for x in m:
print(" ".join("x#.?"[i] for i in x))
print()
w, h = len(vr), len(hr)
rows = [gen_row(w, x) for x in hr]
cols = [gen_row(h, x) for x in vr]
can_do = list(map(allowable, rows))
# Initially mark all columns for update.
mod_rows, mod_cols = set(), set(range(w))
while mod_cols:
for i in mod_cols:
fix_col(i)
mod_cols = set()
for i in mod_rows:
fix_row(i)
mod_rows = set()
if all(can_do[i][j] in (1, 2) for j in range(w) for i in range(h)):
print("Solution would be unique") # but could be incorrect!
else:
print("Solution may not be unique, doing exhaustive search:")
# We actually do exhaustive search anyway. Unique solution takes
# no time in this phase anyway, but just in case there's no
# solution (could happen?).
out = [0] * h
def try_all(n = 0):
if n >= h:
for j in range(w):
if [x[j] for x in out] not in cols[j]:
return 0
show_gram(out)
return 1
sol = 0
for x in rows[n]:
out[n] = x
sol += try_all(n + 1)
return sol
n = try_all()
if not n:
print("No solution.")
elif n == 1:
print("Unique solution.")
else:
print(n, "solutions.")
print()
def solve(s, show_runs=True):
s = [[[ord(c) - ord('A') + 1 for c in w] for w in l.split()]
for l in p.splitlines()]
if show_runs:
print("Horizontal runs:", s[0])
print("Vertical runs:", s[1])
deduce(s[0], s[1])
</syntaxhighlight>
=={{header|Racket}}==
<div><small>''<nowiki>[</nowiki>See [[Example:Nonogram solver/Racket]] for editing of this section<nowiki>]</nowiki>''</small></div>
{{Example:Nonogram solver/Racket}}
=={{header|Raku}}==
===Translation of Go===
{{trans|Go}}
<syntaxhighlight lang="raku" line># 20220401 Raku programming solution
sub reduce(\a, \b) {
my \countRemoved = $ = 0;
for ^+a -> \i {
my \commonOn = @ = True xx b.elems;
my \commonOff = @ = False xx b.elems;
a[i].map: -> \candidate { commonOn <<?&=>> candidate ;
commonOff <<?|=>> candidate }
# remove from b[j] all candidates that don't share the forced values
for ^+b -> \j {
my (\fi,\fj) = i, j;
for ((+b[j])^...0) -> \k {
my \cnd = b[j][k];
if (commonOn[fj] ?& !cnd[fi]) ?| (!commonOff[fj] ?& cnd[fi]) {
b[j][k..*-2] = b[j][k+1..*-1];
b[j].pop;
countRemoved++
}
}
return -1 if b[j].elems == 0
}
}
return countRemoved
}
sub genSequence(\ones, \numZeros) {
if ( my \le = ones.elems ) == 0 { return [~] '0' xx numZeros }
my @result;
loop ( my $x = 1; $x < ( numZeros -le+2); $x++ ) {
my @skipOne = ones[1..*];
for genSequence(@skipOne, numZeros -$x) -> \tail {
@result.push: ( '0' x $x )~ones[0]~tail
}
}
return @result
}
# If all the candidates for a row have a value in common for a certain cell,
# then it's the only possible outcome, and all the candidates from the
# corresponding column need to have that value for that cell too. The ones
# that don't, are removed. The same for all columns. It goes back and forth,
# until no more candidates can be removed or a list is empty (failure).
sub reduceMutual(\cols, \rows) {
return -1 if ( my \countRemoved1 = reduce(cols, rows) ) == -1 ;
return -1 if ( my \countRemoved2 = reduce(rows, cols) ) == -1 ;
return countRemoved1 + countRemoved2
}
# collect all possible solutions for the given clues
sub getCandidates(@data, \len) {
return gather for @data -> \s {
my \sumBytes = [+] (my @a = s.ords)>>.&{ $_ - 'A'.ord + 1 }
my @prep = @a.values.map: { [~] '1' xx ($_ - 'A'.ord + 1) }
take ( gather for genSequence(@prep, len -sumBytes+1) -> \r {
my \bits = r.substr(1..*).ords;
take ( bits.values.map: *.chr == '1' ).Array
} ).Array
}
}
sub newPuzzle (@data) {
my (@rowData,@colData) := @data.map: *.split: ' ' ;
my \rows = getCandidates(@rowData, @colData.elems);
my \cols = getCandidates(@colData, @rowData.elems);
loop {
my \numChanged = reduceMutual(cols, rows);
given (numChanged) { when -1 { say "No solution" andthen return }
when 0 { last } }
}
for rows -> \row {
for ^+cols -> \k { print row[0][k] ?? '# ' !! '. ' }
print "\n"
}
print "\n"
}
newPuzzle $_ for (
( "C BA CB BB F AE F A B", "AB CA AE GA E C D C" ),
( "F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA" ),
( "CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH "
~"BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF "
~"AAAAD BDG CEF CBDB BBB FC" ),
( "E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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" ),
);</syntaxhighlight>
===Translation of Perl===
{{trans|Perl}}
<syntaxhighlight lang="raku" line>for './nonogram_problems.txt'.IO.lines.rotor(3, :partial) {
my (@rpats,@cpats) := @_[0,1]>>.&makepatterns;
my @rows = ( '.' x +@cpats ) xx +@rpats ;
loop (my $prev = ''; $prev ne ~@rows; ) {
$prev = ~@rows;
try(@rows, @rpats);
my @cols = (^+@cpats).map: { [~] @rows.map: { ~ s/.// } }
try(@cols, @cpats);
@rows = (^+@rpats).map: { [~] @cols.map: { ~ s/.// } }
}
say();
@rows ~~ /\./ ?? say "Failed" !! say TR/01/.@/ for @rows
}
sub try(@lines, @patterns) {
for ^+@lines -> $i {
my $pos = 0;
while ( @lines[$i] ~~ m:g/\./ and $pos < @lines[$i].chars ) {
for 0, 1 -> $try {
with @lines[$i] { S:pos($pos)/\./$try/ ~~ /<{@patterns[$i]}>/ or
s:pos($pos)/./{ 1 - $try }/ }
}
$pos++;
}
}
}
sub makepatterns($input) {
$input ==> split( ' ' )
==> map( *.comb )
==> map( *>>.&{ .ord - 64 } )
==> map( '<[1.]>**' <<~<< * )
==> map( *.join: '<[0.]>+' )
==> map( '^<[0.]>*' ~ * ~ '<[0.]>*$' )
}</syntaxhighlight>
=={{header|REXX}}==
Nonogram Solver/Rexx:
<syntaxhighlight lang="rexx">/*REXX*/
Parse Arg fn
Parse Var fn ou'.'
maxpn = 10000 /* maximum possibilities to check through */
output = ou'.out.txt'
/* read row/col values into rowpp. and colpp. arrays */
cc = linein(fn)
rows = words(cc)
dd = linein(fn)
cols = words(dd)
char = '0ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijk'
cntr = 0
Do i = 1 To rows
rowpp.i = CV(cc,i)
cntr = cntr + sum
End
cntc = 0
Do i = 1 To cols
colpp.i = CV(dd,i)
cntc = cntc + sum
End
If (cntr <> cntc)|(cntr = 0) Then Do
Say 'error Sum of rows <> sum of cols'
Exit 999
End
Say cntr 'colored cells'
ar = copies('-',rows*cols)
/* values are -=unknown .=blank @=Color */
/* PREFILL array */
'erase' output
/**********COL PREFILL ************/
Do col = 1 To cols
r = colpp.col
Parse Var r z r
Do While r <> ''
Parse Var r q r
z = z + q + 1
End
result = copies('-',rows)
If z = rows Then result = FILL_LINE(colpp.col)
Else If z = 0 Then result = copies('.',rows)
Do row = 1 To rows
ar = overlay(substr(result,row,1),ar,(row-1)*cols+col)
End
End
/**********ROW PREFILL ************/
Do row = 1 To rows
c = rowpp.row
Parse Var c t c
Do While c <> ''
Parse Var c q c
t = t + q + 1
End
result = substr(ar,(row-1)*cols+1,cols)
If t = cols Then result = left(FILL_LINE(rowpp.row),cols)
Else If t = 0 Then result = copies('.',cols)
ar = overlay(result,ar,(row-1)*cols+1)
End
/********** ok here we loop ************/
cnttry = 1
nexttry = 2
next.cnttry = ar
sol = 0
Do label nextpos While cnttry < nexttry
Say 'trying' cnttry 'of' nexttry-1
ar = next.cnttry
cnttry = cnttry + 1
Do Until sar = ar
sar = ar
Do row = 1 To rows
/**********process rows ************/
rowcol = substr(ar,(row-1)*cols+1,cols)
pp = rowpp.row
If PROCESSROW() Then Iterate nextpos
Else ar = overlay(left(rowcol,cols),ar,(row-1)*cols+1)
End
Do col = 1 To cols
rowcol = ''
Do row = 1 To rows
rowcol = rowcol || substr(ar,(row-1)*cols+ col,1)
End
pp = colpp.col
If PROCESSROW() Then Iterate nextpos
Do row = 1 To rows
ar = overlay(substr(rowcol,row,1),ar,(row-1)*cols + col)
End
End
If pos('-',ar) = 0 Then Do /* hurray we have a solution */
/* at this point we need to verify solution */
If CHECKBOARD() Then Iterate nextpos /* too bad didn't match */
sol = sol + 1
Call LINEOUT output,'This is solution no:' sol
Call DUMPBOARD
Iterate nextpos
End
If sar = ar Then Do
fnd = pos('-',ar)
next.nexttry = overlay('.',ar,fnd)
nexttry = nexttry + 1
ar = overlay('@',ar,fnd)
End
End
End nextpos
If sol = 0 Then sol = 'No'
Say sol 'solutions found'
Exit
CHECKBOARD:
Do row = 1 To rows
/**********process rows ************/
rowcol = substr(ar,(row-1)*cols+1,cols)
pp = rowpp.row
If CHECKROW() Then Return 1
End
Do col = 1 To cols
rowcol = ''
Do row = 1 To rows
rowcol = rowcol || substr(ar,(row-1)*cols+ col,1)
End
pp = colpp.col
If CHECKROW() Then Return 1
End
Return 0 /* we did it */
CHECKROW:
len_item = length(rowcol)
st = 1
If pp = 0 Then Return rowcol <> copies('.',len_item)
Else If pp = len_item Then Return rowcol <> copies('@',len_item)
Do While (pp <> '') & (st <= len_item)
Parse Var pp p1 pp
of = pos('@',rowcol'@',st)
If of > len_item Then Return 1
If substr(rowcol,of,p1) <> copies('@',p1) Then Return 1
st = of + p1
If substr(rowcol'.',st,1) <> '.' Then Return 1
End
Return 0
DUMPBOARD:
Parse Arg qr
p = '..'
q = '..'
Do i = 1 To cols
n = right(i,2)
p = p left(n,1)
q = q right(n,1)
End
Call LINEOUT output, p
Call LINEOUT output, q
Do i = 1 To rows
o = right(i,2)
p = substr(ar,(i-1)*cols+1,cols)
Do j = 1 To cols
Parse Var p z +1 p
o = o z
End
Call LINEOUT output, o
End
Return
FILL_LINE:
Parse Arg items
oo = ''
Do While items <> ''
Parse Var items a items
oo = oo||copies('@',a)'.'
End
Return oo
CV:
Parse Arg cnts, rwcl
str = word(cnts,rwcl)
ret = ''
sum = 0
Do k = 1 To length(str)
this = pos(substr(str,k,1),char)-1
ret = ret this
sum = sum + this
End
Return space(ret)
PROCESSROW: /* rowcol pp in, rowcol pp of ol */
prerow = rowcol
len_item = length(rowcol)
If pos('-',rowcol) = 0 Then Do
pp = ''
Return 0
End
of = 1
kcnt = 0
/* reduce the left side with already populated values */
Do While (of < len_item) & (pp <> '')
kcnt = kcnt + 1
If kcnt > len_item Then Return 1
If substr(rowcol,of,1) = '.' Then Do
k = verify(substr(rowcol,of)'%','.')
of = of + k - 1
Iterate
End
nl = word(pp,1)
len = verify(substr(rowcol,of)'%','-@') - 1
If len < nl Then Do
rowcol = overlay(copies('.',len),rowcol,of)
of = of + len
Iterate
End
If (len = nl) & (pos('@',substr(rowcol,of,nl))>0) Then Do
rowcol = overlay(copies('@',nl),rowcol,of)
of = of + nl
pp = subword(pp,2)
Iterate
End
If substr(rowcol,of,1) = '@' Then Do
rowcol = overlay(copies('@',nl)'.',rowcol,of)
of = of + nl
pp = subword(pp,2)
Iterate
End
Leave
End
/* reduce the right side with already populated values */
ofm = len_item + 1 - of
ol = 1
kcnt = 0
Do While (ol < ofm) & (pp <> '')
kcnt = kcnt + 1
If kcnt > len_item Then Return 1
revrow = reverse(rowcol)
If substr(revrow,ol,1) = '.' Then Do
k = verify(substr(revrow,ol)'%','.')
ol = ol + k - 1
Iterate
End
nl = word(pp,words(pp))
len = verify(substr(revrow,ol)'%','-@') - 1
If len < nl Then Do
rowcol = overlay(copies('.',len),rowcol,len_item-ol-len+2)
ol = ol + len
Iterate
End
If (len = nl) & (pos('@',substr(revrow,ol,nl))>0) Then Do
rowcol = overlay(copies('@',nl),rowcol,len_item-ol-nl+2)
ol = ol + nl
pp = subword(pp,1,words(pp)-1)
Iterate
End
If substr(revrow,ol,1) = '@' Then Do
rowcol = overlay('.'copies('@',nl),rowcol,len_item-ol-nl+1)
ol = ol + nl
pp = subword(pp,1,words(pp)-1)
Iterate
End
Leave
End
If pp = 0 Then pp = ''
If pp = '' Then rowcol = changestr('-',rowcol,'.')
If pp <> '' Then Do
lv = len_item-of-ol+2
pos. = ''
pn = 0
pi = substr(rowcol,of,lv)
If (copies('-',length(pi)) = pi) Then Do
len = CNT(pp)
If (len + mx) <= lv Then Do
Return 0
End
End
/* oh oh need to check for posibilities */
Call TRY '',pp
If pn > maxpn Then Do
over = over + 1
Return 0
End
fnd = 0
fu = pos.1
Do z = 2 To pn
Do j = 1 To lv
If substr(fu,j,1) <> substr(pos.z,j,1) Then fu = overlay('-',fu,j)
End
End
Do z = 1 To lv
If substr(fu,z,1) <> '-' Then rowcol = overlay(substr(fu,z,1),rowcol,of+z-1)
End
End
Return 0
TRY: Procedure Expose pn pos. maxpn lv pi
Parse Arg prev,pp
If pp = '' Then Do
rem = substr(pi,length(prev)+1)
If translate(rem,'..','.-') <> copies('.',length(rem)) Then Return
prev = left(prev||copies('.',lv),lv)
pn = pn + 1
If pn > maxpn Then Return
pos.pn = prev
Return
End
Parse Var pp p1 pp
If length(prev)+p1 > lv Then Return
Do i = 0 To lv - length(prev)-p1
If translate(substr(pi,length(prev)+1,i),'..','.-') = copies('.',i) Then
If translate(substr(pi,length(prev)+i+1,p1),'@@','@-') = copies('@',p1) Then
If substr(pi,length(prev)+i+p1+1,1) <> '@' Then
Call TRY prev||copies('.',i)||copies('@',p1)'.',pp
End
Return
CNT: Procedure Expose mx
Parse Arg len items
mx = len
Do While items <> ''
Parse Var items ii items
len = len + ii + 1
If ii > mx Then mx = ii
End
Return len</syntaxhighlight>
{{out}}
<pre>
Puzzle
C BA CB BB F AE F A B
AB CA AE GA E C D C
This is solution no: 1
..
.. 1 2 3 4 5 6 7 8
1 . @ @ @ . . . .
2 @ @ . @ . . . .
3 . @ @ @ . . @ @
4 . . @ @ . . @ @
5 . . @ @ @ @ @ @
6 @ . @ @ @ @ @ .
7 @ @ @ @ @ @ . .
8 . . . . @ . . .
9 . . . @ @ . . .
Puzzle
F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC
D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA
This is solution no: 1
.. 1 1 1 1 1 1 1 1 1 1 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
1 . . . . . . . . . . @ @ @ @ @ @ . . . .
2 . . . . . . . . @ @ @ . @ . . @ @ @ . .
3 . . . @ . . @ @ @ . . . @ . . . . @ @ @
4 . . @ @ @ . @ @ @ @ @ @ @ @ @ @ @ @ @ @
5 . . . @ . . @ . . . . . . . . . . . . @
6 . . @ . @ . @ @ . . . . . . . . . . @ @
7 @ @ @ @ @ . . @ @ . . . . . . . . @ @ .
8 @ @ @ @ @ . . . @ . . . . . . . . @ . .
9 @ @ @ @ @ . . @ @ @ . @ @ @ . @ @ @ . .
10 @ @ @ @ @ @ @ @ . @ @ @ . @ @ @ . @ @ @
Puzzle
CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC
BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF AAAAD BDG CEF CBDB BBB FC
This is solution no: 1
.. 1 1 1 1 1 1 1 1 1 1 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
1 . . . . @ @ @ . @ . . . . . . . . . . .
2 . . . . @ @ . @ @ @ @ . @ . . . . . . .
3 . . . . @ . @ @ @ . @ @ @ . . . . . . .
4 . . @ @ . @ @ @ @ . . . . . . . . . . .
5 . @ @ @ . @ @ @ . @ . . . . @ @ @ . . .
6 @ @ @ . . @ @ . @ @ . . . @ . @ @ @ . .
7 @ @ . . @ @ . @ @ . . . . @ @ . @ @ . .
8 . . . . @ @ . @ . @ . . @ @ . @ . @ . .
9 . . . . @ . @ @ . @ . . . @ @ @ @ . . .
10 . . . . @ . @ . @ @ . . . . . @ @ . . .
11 . . . . . @ @ . @ @ . . @ @ @ @ @ @ @ @
12 . . . . @ @ . @ @ . . . @ @ . . @ @ @ @
13 . . . . @ . @ @ . @ @ . @ . . . @ . . @
14 @ @ @ . . @ @ @ . @ @ @ @ @ . . . . . @
15 @ . @ . @ @ @ . @ . . . . @ . . . . @ @
16 @ @ . . @ @ @ . @ . . . . @ @ @ . @ @ @
17 . @ . @ @ @ . @ @ . @ @ @ @ @ @ @ @ . .
18 . @ @ @ @ . @ @ @ . @ @ @ @ @ @ @ @ . .
19 . . . @ . @ @ @ @ . @ @ . @ @ @ @ @ . .
20 . . . @ . @ @ @ @ . @ @ . . . @ @ . . .
21 . . . . @ @ @ @ . . @ @ . . . @ @ @ @ @
22 . . . @ @ @ @ @ . @ @ @ . . . @ @ @ @ @
23 . . . @ @ @ @ . @ . . . . . . . . . . @
24 . . @ @ @ @ . @ @ . . . . . . . . . . .
25 . . @ @ @ . @ @ @ . . . . . . . . . . .
Puzzle
E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G
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
This is solution no: 1
.. 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 . . . . . . . . . . . . . . . . . . . . @ @ @ @ @
2 . . @ @ . . . . . . . . . . . . . . @ @ @ . . @ @
3 . @ @ . . . . . . . . . . . . . . @ @ @ @ @ . . @
4 @ @ . . . . . . . . . . . . . @ @ @ @ @ @ @ @ . .
5 @ @ . . . . @ @ @ @ @ . @ @ @ @ @ @ @ @ @ @ @ . .
6 @ . @ . . @ @ . . . . @ . . . . @ @ @ @ @ @ . . .
7 @ . . @ @ . . . . . @ . . . . . . . @ @ @ . . . .
8 @ @ . . . . . . . . @ . . . . . . . . . . . . . @
9 . @ @ . . . . . @ @ @ @ @ @ . . . . . . . . . @ @
10 . . @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ . . . . @ @ @ @
11 . . . . . @ @ @ @ @ @ @ @ @ @ . . @ @ @ @ @ @ @ @
12 . . . . @ @ . @ . @ @ @ @ . @ @ @ . . @ @ @ @ @ @
13 . . . . . . . . @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @
14 . . . . . . . . @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @
15 . . . . . . . @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ @
16 . . . . . . . @ . . . @ @ @ @ @ @ @ @ @ @ @ @ @ @
17 . . . . . . . @ . @ . @ @ @ @ @ @ @ @ @ @ @ @ @ @
18 . . . . . . . . @ @ @ @ @ . . . @ @ @ @ @ @ @ @ @
19 . . . . . . . . . . . . . . . . . @ @ @ @ @ @ @ @
20 . . . . . . . . . . . . . . . . . . @ @ @ @ @ @ @
Puzzle
GCAAG AABBAA ACACAACA ACAAFACA ACAEBACA AABAA GAAAAAG CC ABCAACAAB AACBAA DADBAB AAAAADAC BAAABE CBBFCA AIAABA BABBCA CAAAAEA ABBE GABAAAC AABABBA ACADEA ACACJB ACAAFF AABAAB GBABE
GBAAG AABBAA ACACACACA ACAAEACA ACAADACA AAABAA GAAAAAG AAC BABAHBA BBABAAAB AGCBA ABCAAAAA DAABF CCAAACA ABEBB BBAAAAABA ACCBAHA FBA GADAAC AAAAD ACACGA ACAAABAAD ACADCC AABBBFA GACBAA
This is solution no: 1
.. 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 @ @ @ @ @ @ @ . @ @ @ . . . @ . @ . @ @ @ @ @ @ @
2 @ . . . . . @ . @ @ . @ @ . . . . . @ . . . . . @
3 @ . @ @ @ . @ . . . . . @ @ @ . @ . @ . @ @ @ . @
4 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ . @ @ @ . @
5 @ . @ @ @ . @ . . @ @ @ @ @ . @ @ . @ . @ @ @ . @
6 @ . . . . . @ . . @ @ . . . . . . . @ . . . . . @
7 @ @ @ @ @ @ @ . @ . @ . @ . @ . @ . @ @ @ @ @ @ @
8 . . . . . . . . @ @ @ . . . @ @ @ . . . . . . . .
9 @ . @ @ . @ @ @ . . @ . @ . @ @ @ . @ . . @ . @ @
10 @ . @ . . . . . . @ @ @ . @ @ . . . . @ . . . @ .
11 . @ @ @ @ . @ . @ @ @ @ . @ @ . @ . . . . @ @ . .
12 . @ . @ . . . @ . . . @ . @ . @ @ @ @ . @ . @ @ @
13 . . @ @ . . @ . @ . @ . . . . . . @ @ . @ @ @ @ @
14 . . . @ @ @ . @ @ . @ @ . @ @ @ @ @ @ . @ @ @ . @
15 @ . @ @ @ @ @ @ @ @ @ . @ . @ . . @ @ . . . . @ .
16 . @ @ . @ . . @ @ . . @ @ . . @ @ @ . . . . . @ .
17 @ @ @ . @ . @ . @ . . . . @ . . @ @ @ @ @ . @ . .
18 . . . . . . . . @ . . @ @ . . @ @ . . . @ @ @ @ @
19 @ @ @ @ @ @ @ . @ . . . @ @ . . @ . @ . @ . @ @ @
20 @ . . . . . @ . @ @ . . @ . . @ @ . . . @ @ . @ .
21 @ . @ @ @ . @ . . . @ @ @ @ . . @ @ @ @ @ . . @ .
22 @ . @ @ @ . @ . @ @ @ . @ @ @ @ @ @ @ @ @ @ . @ @
23 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ @ @ @ @ @ .
24 @ . . . . . @ . . @ @ . . . . . . @ . @ . @ @ . .
25 @ @ @ @ @ @ @ . @ @ . . . @ . @ @ . . . @ @ @ @ @
This is solution no: 2
.. 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 @ @ @ @ @ @ @ . @ @ @ . . . @ . @ . @ @ @ @ @ @ @
2 @ . . . . . @ . @ @ . @ @ . . . . . @ . . . . . @
3 @ . @ @ @ . @ . . . . . @ @ @ . @ . @ . @ @ @ . @
4 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ . @ @ @ . @
5 @ . @ @ @ . @ . . @ @ @ @ @ . @ @ . @ . @ @ @ . @
6 @ . . . . . @ . . @ @ . . . . . . . @ . . . . . @
7 @ @ @ @ @ @ @ . @ . @ . @ . @ . @ . @ @ @ @ @ @ @
8 . . . . . . . . @ @ @ . . . @ @ @ . . . . . . . .
9 @ . @ @ . @ @ @ . . @ . @ . @ @ @ . . @ . @ . @ @
10 @ . @ . . . . . . @ @ @ . @ @ . . . @ . . . . @ .
11 . @ @ @ @ . @ . @ @ @ @ . @ @ . @ . . . . @ @ . .
12 . @ . @ . . . @ . . . @ . @ . @ @ @ @ . @ . @ @ @
13 . . @ @ . . @ . @ . @ . . . . . . @ @ . @ @ @ @ @
14 . . . @ @ @ . @ @ . @ @ . @ @ @ @ @ @ . @ @ @ . @
15 @ . @ @ @ @ @ @ @ @ @ . @ . @ . . @ @ . . . . @ .
16 . @ @ . @ . . @ @ . . @ @ . . @ @ @ . . . . . @ .
17 @ @ @ . @ . @ . @ . . . . @ . . @ @ @ @ @ . @ . .
18 . . . . . . . . @ . . @ @ . . @ @ . . . @ @ @ @ @
19 @ @ @ @ @ @ @ . @ . . . @ @ . . @ . @ . @ . @ @ @
20 @ . . . . . @ . @ @ . . @ . . @ @ . . . @ @ . @ .
21 @ . @ @ @ . @ . . . @ @ @ @ . . @ @ @ @ @ . . @ .
22 @ . @ @ @ . @ . @ @ @ . @ @ @ @ @ @ @ @ @ @ . @ @
23 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ @ @ @ @ @ .
24 @ . . . . . @ . . @ @ . . . . . . @ . @ . @ @ . .
25 @ @ @ @ @ @ @ . @ @ . . . @ . @ @ . . . @ @ @ @ @
This is solution no: 3
.. 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 @ @ @ @ @ @ @ . @ @ @ . . . @ . @ . @ @ @ @ @ @ @
2 @ . . . . . @ . @ @ . @ @ . . . . . @ . . . . . @
3 @ . @ @ @ . @ . . . . . @ @ @ . @ . @ . @ @ @ . @
4 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ . @ @ @ . @
5 @ . @ @ @ . @ . . @ @ @ @ @ . @ @ . @ . @ @ @ . @
6 @ . . . . . @ . . @ @ . . . . . . . @ . . . . . @
7 @ @ @ @ @ @ @ . @ . @ . @ . @ . @ . @ @ @ @ @ @ @
8 . . . . . . . . @ @ @ . . . @ @ @ . . . . . . . .
9 @ . @ @ . @ @ @ . . @ . @ . @ @ @ . @ . . @ . @ @
10 @ . @ . . . . . . @ @ @ . @ @ . . . . @ . . . @ .
11 . @ @ @ @ . @ . @ @ @ @ . @ @ . @ . . . . @ @ . .
12 . @ . @ . . . @ . . . @ . @ . @ @ @ @ . @ . @ @ @
13 . . @ @ . . @ . @ . @ . . . . . . @ @ . @ @ @ @ @
14 . . . @ @ @ . @ @ . @ @ . @ @ @ @ @ @ . @ @ @ . @
15 @ . @ @ @ @ @ @ @ @ @ . @ . @ . . @ @ . . . . @ .
16 . @ @ . @ . . @ @ . . . @ @ . @ @ @ . . . . . @ .
17 @ @ @ . @ . @ . @ . . @ . . . . @ @ @ @ @ . @ . .
18 . . . . . . . . @ . . . @ @ . @ @ . . . @ @ @ @ @
19 @ @ @ @ @ @ @ . @ . . @ @ . . . @ . @ . @ . @ @ @
20 @ . . . . . @ . @ @ . . @ . . @ @ . . . @ @ . @ .
21 @ . @ @ @ . @ . . . @ @ @ @ . . @ @ @ @ @ . . @ .
22 @ . @ @ @ . @ . @ @ @ . @ @ @ @ @ @ @ @ @ @ . @ @
23 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ @ @ @ @ @ .
24 @ . . . . . @ . . @ @ . . . . . . @ . @ . @ @ . .
25 @ @ @ @ @ @ @ . @ @ . . . @ . @ @ . . . @ @ @ @ @
This is solution no: 4
.. 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
.. 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
1 @ @ @ @ @ @ @ . @ @ @ . . . @ . @ . @ @ @ @ @ @ @
2 @ . . . . . @ . @ @ . @ @ . . . . . @ . . . . . @
3 @ . @ @ @ . @ . . . . . @ @ @ . @ . @ . @ @ @ . @
4 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ . @ @ @ . @
5 @ . @ @ @ . @ . . @ @ @ @ @ . @ @ . @ . @ @ @ . @
6 @ . . . . . @ . . @ @ . . . . . . . @ . . . . . @
7 @ @ @ @ @ @ @ . @ . @ . @ . @ . @ . @ @ @ @ @ @ @
8 . . . . . . . . @ @ @ . . . @ @ @ . . . . . . . .
9 @ . @ @ . @ @ @ . . @ . @ . @ @ @ . . @ . @ . @ @
10 @ . @ . . . . . . @ @ @ . @ @ . . . @ . . . . @ .
11 . @ @ @ @ . @ . @ @ @ @ . @ @ . @ . . . . @ @ . .
12 . @ . @ . . . @ . . . @ . @ . @ @ @ @ . @ . @ @ @
13 . . @ @ . . @ . @ . @ . . . . . . @ @ . @ @ @ @ @
14 . . . @ @ @ . @ @ . @ @ . @ @ @ @ @ @ . @ @ @ . @
15 @ . @ @ @ @ @ @ @ @ @ . @ . @ . . @ @ . . . . @ .
16 . @ @ . @ . . @ @ . . . @ @ . @ @ @ . . . . . @ .
17 @ @ @ . @ . @ . @ . . @ . . . . @ @ @ @ @ . @ . .
18 . . . . . . . . @ . . . @ @ . @ @ . . . @ @ @ @ @
19 @ @ @ @ @ @ @ . @ . . @ @ . . . @ . @ . @ . @ @ @
20 @ . . . . . @ . @ @ . . @ . . @ @ . . . @ @ . @ .
21 @ . @ @ @ . @ . . . @ @ @ @ . . @ @ @ @ @ . . @ .
22 @ . @ @ @ . @ . @ @ @ . @ @ @ @ @ @ @ @ @ @ . @ @
23 @ . @ @ @ . @ . @ . . @ @ @ @ @ @ . @ @ @ @ @ @ .
24 @ . . . . . @ . . @ @ . . . . . . @ . @ . @ @ . .
25 @ @ @ @ @ @ @ . @ @ . . . @ . @ @ . . . @ @ @ @ @
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-pattern}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./pattern" for Pattern
import "./math" for Nums, Boolean
var p = Pattern.new("/s")
var genSequence // recursive
genSequence = Fn.new { |ones, numZeros|
if (ones.isEmpty) return ["0" * numZeros]
var result = []
var x = 1
while (x < numZeros - ones.count + 2) {
var skipOne = ones.skip(1).toList
for (tail in genSequence.call(skipOne, numZeros - x)) {
result.add("0" * x + ones[0] + tail)
}
x = x + 1
}
return result
}
/* If all the candidates for a row have a value in common for a certain cell,
then it's the only possible outcome, and all the candidates from the
corresponding column need to have that value for that cell too. The ones
that don't, are removed. The same for all columns. It goes back and forth,
until no more candidates can be removed or a list is empty (failure).
*/
var reduce = Fn.new { |a, b|
var countRemoved = 0
for (i in 0...a.count) {
var commonOn = List.filled(b.count, true)
var commonOff = List.filled(b.count, false)
// determine which values all candidates of a[i] have in common
for (candidate in a[i]) {
for (i in 0...b.count) {
commonOn[i] = Boolean.and(commonOn[i], candidate[i])
commonOff[i] = Boolean.or(commonOff[i], candidate[i])
}
}
// remove from b[j] all candidates that don't share the forced values
for (j in 0...b.count) {
var fi = i
var fj = j
var removals = false
b[j].each { |cnd|
if ((commonOn[fj] && !cnd[fi]) || (!commonOff[fj] && cnd[fi])) {
b[j].remove(cnd)
removals = true
}
}
if (removals) countRemoved = countRemoved + 1
if (b[j].isEmpty) return -1
}
}
return countRemoved
}
var reduceMutual = Fn.new { |cols, rows|
var countRemoved1 = reduce.call(cols, rows)
if (countRemoved1 == -1) return -1
var countRemoved2 = reduce.call(rows, cols)
if (countRemoved2 == -1) return -1
return countRemoved1 + countRemoved2
}
// collect all possible solutions for the given clues
var getCandidates = Fn.new { |data, len|
var result = []
for (s in data) {
var lst = []
var a = s.bytes
var sumChars = Nums.sum(a.map { |b| b - 64 })
var prep = a.map { |b| "1" * (b - 64) }.toList
for (r in genSequence.call(prep, len - sumChars + 1)) {
var bits = r[1..-1].bytes
var len = bits.count
if (len % 64 != 0) len = (len/64).ceil * 64
var bitset = List.filled(len, false)
for (i in 0...bits.count.min(bitset.count)) bitset[i] = bits[i] == 49
lst.add(bitset)
}
result.add(lst)
}
return result
}
var newPuzzle = Fn.new { |data|
var rowData = p.splitAll(data[0])
var colData = p.splitAll(data[1])
var rows = getCandidates.call(rowData, colData.count)
var cols = getCandidates.call(colData, rowData.count)
while (true) {
var numChanged = reduceMutual.call(cols, rows)
if (numChanged == -1) {
System.print("No solution")
return
}
if (numChanged <= 0) break
}
for (row in rows) {
for (i in 0...cols.count) {
System.write(row[0][i] ? "# " : ". ")
}
System.print()
}
System.print()
}
var p1 = ["C BA CB BB F AE F A B", "AB CA AE GA E C D C"]
var p2 = [
"F CAC ACAC CN AAA AABB EBB EAA ECCC HCCC",
"D D AE CD AE A DA BBB CC AAB BAA AAB DA AAB AAA BAB AAA CD BBA DA"
]
var p3 = [
"CA BDA ACC BD CCAC CBBAC BBBBB BAABAA ABAD AABB BBH " +
"BBBD ABBAAA CCEA AACAAB BCACC ACBH DCH ADBE ADBB DBE ECE DAA DB CC",
"BC CAC CBAB BDD CDBDE BEBDF ADCDFA DCCFB DBCFC ABDBA BBF AAF BADB DBF " +
"AAAAD BDG CEF CBDB BBB FC"
]
var p4 = [
"E BCB BEA BH BEK AABAF ABAC BAA BFB OD JH BADCF Q Q R AN AAN EI H G",
"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"
]
for (puzzleData in [p1, p2, p3, p4]) newPuzzle.call(puzzleData)</syntaxhighlight>
{{out}}
<pre>
. # # # . . . .
# # . # . . . .
. # # # . . # #
. . # # . . # #
. . # # # # # #
# . # # # # # .
# # # # # # . .
. . . . # . . .
. . . # # . . .
. . . . . . . . . . # # # # # # . . . .
. . . . . . . . # # # . # . . # # # . .
. . . # . . # # # . . . # . . . . # # #
. . # # # . # # # # # # # # # # # # # #
. . . # . . # . . . . . . . . . . . . #
. . # . # . # # . . . . . . . . . . # #
# # # # # . . # # . . . . . . . . # # .
# # # # # . . . # . . . . . . . . # . .
# # # # # . . # # # . # # # . # # # . .
# # # # # # # # . # # # . # # # . # # #
. . . . # # # . # . . . . . . . . . . .
. . . . # # . # # # # . # . . . . . . .
. . . . # . # # # . # # # . . . . . . .
. . # # . # # # # . . . . . . . . . . .
. # # # . # # # . # . . . . # # # . . .
# # # . . # # . # # . . . # . # # # . .
# # . . # # . # # . . . . # # . # # . .
. . . . # # . # . # . . # # . # . # . .
. . . . # . # # . # . . . # # # # . . .
. . . . # . # . # # . . . . . # # . . .
. . . . . # # . # # . . # # # # # # # #
. . . . # # . # # . . . # # . . # # # #
. . . . # . # # . # # . # . . . # . . #
# # # . . # # # . # # # # # . . . . . #
# . # . # # # . # . . . . # . . . . # #
# # . . # # # . # . . . . # # # . # # #
. # . # # # . # # . # # # # # # # # . .
. # # # # . # # # . # # # # # # # # . .
. . . # . # # # # . # # . # # # # # . .
. . . # . # # # # . # # . . . # # . . .
. . . . # # # # . . # # . . . # # # # #
. . . # # # # # . # # # . . . # # # # #
. . . # # # # . # . . . . . . . . . . #
. . # # # # . # # . . . . . . . . . . .
. . # # # . # # # . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . # # # # #
. . # # . . . . . . . . . . . . . . # # # . . # #
. # # . . . . . . . . . . . . . . # # # # # . . #
# # . . . . . . . . . . . . . # # # # # # # # . .
# # . . . . # # # # # . # # # # # # # # # # # . .
# . # . . # # . . . . # . . . . # # # # # # . . .
# . . # # . . . . . # . . . . . . . # # # . . . .
# # . . . . . . . . # . . . . . . . . . . . . . #
. # # . . . . . # # # # # # . . . . . . . . . # #
. . # # # # # # # # # # # # # # # . . . . # # # #
. . . . . # # # # # # # # # # . . # # # # # # # #
. . . . # # . # . # # # # . # # # . . # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . . # # # # # # # # # # # # # # # # #
. . . . . . . # # # # # # # # # # # # # # # # # #
. . . . . . . # . . . # # # # # # # # # # # # # #
. . . . . . . # . # . # # # # # # # # # # # # # #
. . . . . . . . # # # # # . . . # # # # # # # # #
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #
</pre>
| |||