Nonogram solver: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H and removed unnecessary import.
Alextretyak (talk | contribs) m (→{{header|11l}}) |
m (→{{header|Wren}}: Changed to Wren S/H and removed unnecessary import.) |
||
(10 intermediate revisions by 8 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 64:
{{trans|Python 3}}
<
‘Create all patterns of a row or col that match given runs.’
F gen_seg([[Int]] o, Int sp) -> [[Int]]
Line 172:
print(‘Extra example where there is no solution:’)
solve("B A A\nA A A")</
{{out}}
Line 195:
=={{header|C sharp}}==
<
using System.Collections.Generic;
using static System.Linq.Enumerable;
Line 311:
}
}</
{{out}}
<pre style="height:30ex;overflow:scroll">
Line 384:
=={{header|C++}}==
===The Solver===
<
// A class to solve Nonogram (Hadje) Puzzles
// Nigel Galloway - January 23rd., 2017
Line 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 478:
std::cout << "\n" << myN.toStr() << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 564:
===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 643:
std::cout << "\n" << myN.toStr() << std::endl;
}
</syntaxhighlight>
{{out}}
<pre>
Line 674:
=={{header|Common Lisp}}==
<
(:use :cl)
(:export :var
Line 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 939:
=={{header|D}}==
{{trans|Python}}
<
/// Create all patterns of a row or col that match given runs.
Line 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 1,193:
=={{header|F_Sharp|F#}}==
<
(*
I define a discriminated union to provide Nonogram Solver functionality.
Line 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 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 1,330:
=={{header|Go}}==
{{trans|Java}}
<
import (
Line 1,513:
newPuzzle(puzzleData)
}
}</
{{out}}
Line 1,584:
. . . . . . . . . . . . . . . . . # # # # # # # #
. . . . . . . . . . . . . . . . . . # # # # # # #
</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,729 ⟶ 1,953:
return countRemoved;
}
}</
<pre>. # # # . . . .
# # . # . . . .
Line 1,799 ⟶ 2,023:
=={{header|Julia}}==
<
struct NonogramPuzzle
Line 1,949 ⟶ 2,173:
processtestpuzzles(testnonograms)
</syntaxhighlight>
<pre>
Puzzle 1:
Line 2,060 ⟶ 2,284:
=={{header|Kotlin}}==
{{trans|Java}}
<
import java.util.BitSet
Line 2,189 ⟶ 2,413:
newPuzzle(puzzleData)
}
}</
{{out}}
Line 2,261 ⟶ 2,485:
. . . . . . . . . . . . . . . . . . # # # # # # #
</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.
<
type
Line 2,275 ⟶ 2,634:
Possibility = int
# Possibilities described by
Possibilities = object
mask0: int # Mask indicating the positions of free cells.
Line 2,415 ⟶ 2,774:
echo ""
solve(rows, cols)
echo ""</
{{out}}
Line 2,499 ⟶ 2,858:
=={{header|Ol}}==
<
(import (owl parse))
Line 2,661 ⟶ 3,020:
(print))
(list first second third fourth))
</syntaxhighlight>
{{out}}
<pre style="height:60ex;overflow:scroll">
Line 2,764 ⟶ 3,123:
=={{header|Perl}}==
<
use warnings;
Line 2,804 ⟶ 3,163:
}
sub
map { qr/^$_$/ # 7 convert strings to regex
} map { '[0.]*' # 6a prepend static pattern
Line 2,814 ⟶ 3,173:
. '[0.]*' # 6b append static pattern
} split ' ', shift; # 1 for each letter grouping
}</
{{out}}
<pre>
Line 2,888 ⟶ 3,247:
=={{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
<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">
Line 3,092 ⟶ 3,454:
########
#######
</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>
Line 3,100 ⟶ 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 3,166 ⟶ 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 3,191 ⟶ 3,630:
compute_values([X | T], Current, Tmp, R) :-
V is X - 64,
compute_values(T, [V | Current], Tmp, R).</
=={{header|Python}}==
Line 3,197 ⟶ 3,636:
=== Python 2 ===
<
def gen_row(w, s):
Line 3,315 ⟶ 3,754:
solve("B A A\nA A A")
main()</
{{out}}
<pre>
Line 3,338 ⟶ 3,777:
=== Python 3 ===
Above code altered to work with Python 3:
<
def gen_row(w, s):
Line 3,442 ⟶ 3,881:
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:
<
Parse Arg fn
Parse Var fn ou'.'
Line 3,765 ⟶ 4,348:
If ii > mx Then mx = ii
End
Return len</
{{out}}
<pre>
Line 3,982 ⟶ 4,565:
{{libheader|Wren-pattern}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./pattern" for Pattern
var p = Pattern.new("/s")
Line 4,116 ⟶ 4,697:
]
for (puzzleData in [p1, p2, p3, p4]) newPuzzle.call(puzzleData)</
{{out}}
|