Inilah saatnya untuk memulai upaya berbahaya untuk mengalahkan Intelejen Inggris. Tujuan dari tantangan ini adalah untuk menulis kode terpendek yang akan menyelesaikan Nonogram.

Apa itu Nonogram?

Aturannya sederhana. Anda memiliki kotak kotak, yang harus diisi hitam atau kosong. Di sebelah setiap baris kisi dicantumkan panjang garis kotak hitam pada baris itu. Di atas setiap kolom tercantum panjang jalur kotak hitam di kolom itu. Tujuan Anda adalah untuk menemukan semua kotak hitam. Dalam jenis teka-teki ini, angka-angka adalah bentuk tomografi diskrit yang mengukur berapa banyak garis kotak diisi yang ada di setiap baris atau kolom. Misalnya, petunjuk "4 8 3" akan berarti ada empat, delapan, dan tiga kotak yang diisi, dalam urutan itu, dengan setidaknya satu kotak kosong di antara kelompok-kelompok yang berurutan. [ 1 ] [ 2 ]

Jadi solusi untuk Nonogram di atas adalah:

Detail Implementasi

Anda dapat memilih untuk mewakili Nonogram namun Anda ingin dan mengambilnya sebagai input dengan cara apa pun yang Anda anggap cocok untuk bahasa Anda. Sama berlaku untuk output. Tujuan dari tantangan ini adalah benar-benar menyelesaikan pekerjaan; jika Anda dapat menyelesaikan nonogram dengan output apa pun yang diberikan oleh program Anda, itu valid. Satu peringatan adalah Anda tidak dapat menggunakan pemecah online :)

Masalah ini sangat menantang secara algoritmik (np-selesai) karena tidak ada solusi yang sepenuhnya efisien untuk itu dan karena itu, Anda tidak akan dihukum karena tidak dapat memecahkan yang lebih besar, meskipun jawaban Anda akan sangat dihargai jika itu mampu menangani kasus besar (lihat bonus). Sebagai patokan, solusi saya berfungsi hingga 25x25 dalam waktu 5-10 detik. Untuk memungkinkan fleksibilitas di antara berbagai bahasa, solusi yang membutuhkan waktu kurang dari 5 menit untuk nonogram 25x25 cukup baik.

Anda dapat mengasumsikan sebuah teka-teki dalam bentuk selalu non-persegi NxN.

Anda dapat menggunakan pembuat puzzle nonogram online ini untuk menguji solusi Anda.

Mencetak gol

Anda, tentu saja, bebas menggunakan bahasa apa pun yang Anda inginkan dan karena ini adalah kode golf, entri akan diurutkan dalam urutan: accuracy -> length of code -> speed.Namun, jangan berkecil hati dengan bahasa kode golf, jawaban dalam semua bahasa yang menunjukkan upaya untuk bermain golf dengan cara yang menarik akan terbalik!

Bonus

Saya sebenarnya belajar tentang Nonogram dari kartu Natal kriptografis yang dirilis oleh Intelejen Inggris di sini . Bagian pertama pada dasarnya adalah Nonogram 25x25 besar. Jika solusi Anda dapat menyelesaikan ini, Anda akan mendapatkan pujian :)

Untuk membuat hidup Anda lebih mudah dalam hal entri data, saya telah menyediakan bagaimana saya mewakili data untuk teka-teki khusus ini untuk Anda gunakan secara gratis. 25 baris pertama adalah petunjuk baris, diikuti oleh garis pemisah '-', diikuti oleh 25 baris petunjuk col, diikuti oleh garis pemisah '#', dan kemudian representasi dari grid dengan petunjuk kotak diisi.

7 3 1 1 7
1 1 2 2 1 1
1 3 1 3 1 1 3 1
1 3 1 1 6 1 3 1
1 3 1 5 2 1 3 1
1 1 2 1 1
7 1 1 1 1 1 7
3 3
1 2 3 1 1 3 1 1 2
1 1 3 2 1 1
4 1 4 2 1 2
1 1 1 1 1 4 1 3
2 1 1 1 2 5
3 2 2 6 3 1
1 9 1 1 2 1
2 1 2 2 3 1
3 1 1 1 1 5 1
1 2 2 5
7 1 2 1 1 1 3
1 1 2 1 2 2 1
1 3 1 4 5 1
1 3 1 3 10 2
1 3 1 1 6 6
1 1 2 1 1 2
7 2 1 2 5
-
7 2 1 1 7
1 1 2 2 1 1
1 3 1 3 1 3 1 3 1
1 3 1 1 5 1 3 1
1 3 1 1 4 1 3 1
1 1 1 2 1 1
7 1 1 1 1 1 7
1 1 3
2 1 2 1 8 2 1
2 2 1 2 1 1 1 2
1 7 3 2 1
1 2 3 1 1 1 1 1
4 1 1 2 6
3 3 1 1 1 3 1
1 2 5 2 2
2 2 1 1 1 1 1 2 1
1 3 3 2 1 8 1
6 2 1
7 1 4 1 1 3
1 1 1 1 4
1 3 1 3 7 1
1 3 1 1 1 2 1 1 4
1 3 1 4 3 3
1 1 2 2 2 6 1
7 1 3 2 1 1
#
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Dan ini adalah versi yang sedikit berbeda untuk kenyamanan Anda; tuple yang dipisahkan koma (baris, col) di mana setiap elemen adalah daftar daftar.

([[7, 3, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 1, 3, 1],
  [1, 3, 1, 1, 6, 1, 3, 1],
  [1, 3, 1, 5, 2, 1, 3, 1],
  [1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [3, 3],
  [1, 2, 3, 1, 1, 3, 1, 1, 2],
  [1, 1, 3, 2, 1, 1],
  [4, 1, 4, 2, 1, 2],
  [1, 1, 1, 1, 1, 4, 1, 3],
  [2, 1, 1, 1, 2, 5],
  [3, 2, 2, 6, 3, 1],
  [1, 9, 1, 1, 2, 1],
  [2, 1, 2, 2, 3, 1],
  [3, 1, 1, 1, 1, 5, 1],
  [1, 2, 2, 5],
  [7, 1, 2, 1, 1, 1, 3],
  [1, 1, 2, 1, 2, 2, 1],
  [1, 3, 1, 4, 5, 1],
  [1, 3, 1, 3, 10, 2],
  [1, 3, 1, 1, 6, 6],
  [1, 1, 2, 1, 1, 2],
  [7, 2, 1, 2, 5]],
 [[7, 2, 1, 1, 7],
  [1, 1, 2, 2, 1, 1],
  [1, 3, 1, 3, 1, 3, 1, 3, 1],
  [1, 3, 1, 1, 5, 1, 3, 1],
  [1, 3, 1, 1, 4, 1, 3, 1],
  [1, 1, 1, 2, 1, 1],
  [7, 1, 1, 1, 1, 1, 7],
  [1, 1, 3],
  [2, 1, 2, 1, 8, 2, 1],
  [2, 2, 1, 2, 1, 1, 1, 2],
  [1, 7, 3, 2, 1],
  [1, 2, 3, 1, 1, 1, 1, 1],
  [4, 1, 1, 2, 6],
  [3, 3, 1, 1, 1, 3, 1],
  [1, 2, 5, 2, 2],
  [2, 2, 1, 1, 1, 1, 1, 2, 1],
  [1, 3, 3, 2, 1, 8, 1],
  [6, 2, 1],
  [7, 1, 4, 1, 1, 3],
  [1, 1, 1, 1, 4],
  [1, 3, 1, 3, 7, 1],
  [1, 3, 1, 1, 1, 2, 1, 1, 4],
  [1, 3, 1, 4, 3, 3],
  [1, 1, 2, 2, 2, 6, 1],
  [7, 1, 3, 2, 1, 1]])

Brachylog , 70 69 byte

[R:C]hlL~l:L:1f=.:3aR,.z:3aC,
tL,?he##ElL,E:2a
.<2,_1<
@b:4f:la
e.h1,

Ini mengambil daftar dua daftar (pertama indikator baris, lalu yang kolom). Setiap indikator itu sendiri adalah daftar (untuk posisi seperti [3,1]pada satu baris).

Versi ini membutuhkan waktu sekitar 3 menit untuk menyelesaikan 5 dari 5 contoh tantangan.

Versi yang jauh lebih efisien, 91 byte

[R:C]hlL~l:L:1f:Cz:3az:Rz:3a=.:4aR,.z:4aC,
tL,?he##ElL,E:2a
.<2,_1<
:+a#=,?h
@b:5f:la
e.h1,

Cobalah online!

Yang ini bukan kekuatan kasar lengkap: satu-satunya perbedaan adalah bahwa yang satu ini memaksakan batasan pada nilai sel sedemikian sehingga jumlah 1s di setiap baris dan kolom cocok dengan angka yang diberikan sebagai indikator dalam input. Satu-satunya bagian brute force adalah kemudian dalam menemukan satu grid dengan batasan-batasan yang "blok" dari 1s cocok dengan apa yang diberikan sebagai indikasi.

Yang ini membutuhkan waktu sekitar 0,05 detik pada 5 dari 5 contoh tantangan. Ini masih terlalu lambat untuk kasus bonus, karena saya tidak tahu bagaimana mengekspresikan blok yang dipisahkan oleh satu atau lebih nol dalam hal kendala.

Penjelasan

Saya akan menjelaskan di bawah versi 93 byte. Satu-satunya perbedaan antara keduanya adalah panggilan ke predikat 3 yang tidak ada dalam versi 70 byte, dan penomoran predikat (karena ada satu kurang).

• Predikat utama:

  [R:C]     Input = [R, C]
  hlL       The length of R is L
  ~l        Create a list of length L
  :L:1f     Each element of that list is a sublist of length L with cells 0 or 1 (Pred 1)
            %%% Part unique to the 93 bytes version
  :Cz       Zip the rows of the list of lists with C
  :3a       The sum of 1s in each row is equal to the sum of the indicators (Pred 3)
  z         Transpose
  :Rz       Zip the columns of the list of lists with R
  :3a       The sum of 1s in each column is equal to the sum of the indicators (Pred 3)
            %%%
  =.        Assign values to the cells of the list of lists which satisfy the constraints
  :4aR,     The blocks of 1s must match the indicators on rows
  .z        Transpose
  :4aC,     The blocks of 1s must match the indicators on columns
  

• Predikat 1: Memaksa baris memiliki panjang tertentu, dan bahwa setiap sel adalah 0 atau 1.

  tL,       L is the length given as second element of the input
  ?he       Take an element from the list
  ##ElL,    That element E is itself a list of length L
  E:2a      The elements of E are 0s and 1s (Pred 2)
  

• Predikat 2: Batasi variabel menjadi 0 atau 1

  .<2,      Input = Output < 2
  _1<       Output > -1
  

• Predikat 3: Jumlah 1 dalam daftar harus sama dengan jumlah indikator (mis. Jika indikatornya [3: 1] maka daftar harus memiliki jumlah 4)

  :+a       Sum the elements of the list and sum the indicator
  #=,       Both sums must be equal
  ?h        Output is the list
  

• Predikat 4: Periksa apakah blok 1 cocok dengan indikator

  @b        Split the list in blocks of the same value
  :5f       Find all blocks of 1s (Pred 5)
  :la       The list of lengths of the blocks results in the indicator (given as output)
  

• Predikat 5: Benar untuk blok 1s, false jika tidak

  e.        Output is an element of the input
    h1,     Its first value is 1
  

Haskell, 242 230 201 199 177 163 160 149 131 byte

import Data.Lists
m=map
a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b]
g=m$list[0]id.m sum.wordsBy(<1)

Akhirnya di bawah 200 byte, kredit ke @Bergi. Terima kasih banyak kepada @nimi yang telah membantu mengurangi ukurannya.

Wow. Hampir setengah ukuran sekarang, sebagian karena aku tetapi terutama karena @nimi.

Fungsi sihirnya adalah (#). Ia menemukan semua solusi dari nonogram yang diberikan.

Ini dapat menyelesaikan semua kasus, tetapi mungkin sangat lambat, karena kompleksitasnya adalah soal O(2^(len a * len b)). Patokan cepat mengungkapkan 86GB dialokasikan untuk nonogram 5x5.

Fakta menyenangkan: Ini bekerja untuk semua nonogram, tidak hanya yang persegi.

Bagaimana itu bekerja:

• a#b: Diberikan daftar daftar bilangan bulat yang mewakili jumlah kotak, hasilkan semua kisi (map(chunk$length b).mapM id$a>>b>>[[0,1]] ) dan filter hasilnya untuk hanya menyimpan yang valid.
• g: Diberikan nonogram potensial, ini menjumlahkan jalannya 1 secara horizontal.

Pyth, 91 72 71 byte

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb

Suatu program yang mengambil input dari daftar bentuk di [size, [horizontal clues], [vertical clues]]mana setiap petunjuk adalah daftar bilangan bulat (petunjuk kosong adalah daftar kosong, []), dan mencetak setiap solusi, dipisahkan dengan baris baru, dalam bentuk kotak biner di mana1 berbayang dan 0adalah unshaded .

Ini adalah kekuatan kasar, demikian juga kira-kira O(2^n^2) . Ini mulai memakan waktu yang sangat lama untuk teka-teki yang lebih besar, tetapi akan menyelesaikan setiap ukuran arbritrary diberikan waktu yang cukup.

Cobalah online

Bagaimana itu bekerja

Program ini menghasilkan setiap tata letak yang mungkin dengan mengambil produk Cartesian berulang [0, 1]dengan panjang sama dengan size^2. Ini kemudian dibagi menjadi potongan-potongan, memberikan daftar untuk setiap garis horizontal. Setiap baris dikode panjangnya, disaring oleh kehadiran 1dan diratakan, meninggalkan petunjuk untuk garis itu. Ini kemudian diperiksa terhadap input. Proses di atas diulang untuk transpos potongan, memeriksa garis vertikal. Jika ada klik, setiap potongan disatukan, dan potongan digabungkan digabungkan pada baris baru dan dicetak secara implisit, dengan baris baru tambahan.

D:GHdRq@@QdG.nCf.)TrH8V^,01^hQ2=TcNhQ=Y1VhQ=*Y*:H@TH1:H@CTH2)IYjbmjkdTb  Program. Input: Q
                            hQ                                           Q[0], size
                           ^  2                                          Square
                        ,01                                              [0, 1]
                       ^                                                 Cartesian product
                      V                                     )            For N in the Cartesian product:
                                 cNhQ                                    Split N into Q[0] chunks
                               =T                                        Assign that to T
                                     =Y1                                 Y=1
                                        VhQ                              For H in range [0, Q[0]-1]:
D:GHd                                                                     def :(G, H, d)
                   rH8                                                     Run-length-encode(H)
               f.)T                                                        Filter by presence of 1 in character part
            .nC                                                            Transpose and flatten, giving the clue
       @@QdG                                                               Q[d][G], the relevant input clue
     Rq                                                                    Return clue==input clue
                                               :H@TH1                     :(H, T, 1)
                                                     :H@CTH2              :(H, transpose(T), 2)
                                           =*Y*                           Y=Y*product of above two
                                                             IY           If Y:
                                                                 mjkdT     Conacatenate each element of T
                                                               jb          Join on newlines
                                                                      b    Add a newline and implicitly print

Terima kasih kepada @ Pietu1998 untuk beberapa tips

Javascript (ES6), 401 386 333 byte

Ini merupakan upaya awal. Ini tidak terlalu efisien tetapi saya ingin menguji solusi menggunakan ekspresi reguler pada representasi biner dari baris dan kolom.

Misalnya, itu akan menerjemahkan petunjuk [3,1]ke ekspresi reguler berikut:

/^0*1{3}0+1{1}0*$/

Saat ini, versi ini tidak memperhitungkan petunjuk kuadrat. Saya mungkin akan menambahkan ini nanti.

Kode

(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

Keluaran

Solusinya ditampilkan dalam format biner. Seperti:

00110
01110
11100
11101
00001

Uji

Ini adalah tes sederhana pada contoh grid.

let f =
(c,r)=>{W=c.length;w=[];S=0;M=(n,p)=>eval(`/^0*${p.map(v=>`1{${v}}`).join`0+`}0*$/`).exec(n);R=(y,i=0)=>S||(w[y]=r[y][i],y+1<W?R(y+1):c.every((c,y)=>(n=0,w.map((_,x)=>n+=w[W-1-x][y]),M(n,c)))&&(S=w.join`
`),r[y][i+1]&&R(y,i+1));r=r.map(r=>[...Array(1<<W)].map((_,n)=>((1<<30)|n).toString(2).slice(-W)).filter(n=>M(n,r)));return R(0)}

console.log(f(
  [[2],[3],[4],[2],[2]],
  [[2],[3],[3],[3,1],[1]]
));

Haskell, 109 byte

Penafian: ini berasal dari jawaban @ ThreeFx . Saya membantunya mengurangi jawabannya, tetapi ia tampaknya tidak berminat untuk memasukkan peningkatan substansial terakhir saya, jadi saya mempostingnya sebagai jawaban baru.

import Data.List
n=mapM id
a#b=[x|x<-n$(n$" #"<$a)<$b,g x==a,g(transpose x)==b]
g=map$max[0].map length.words

Contoh penggunaan: [[2],[3],[3],[3,1],[1]] # [[2],[3],[4],[2],[2]]->[[" ## "," ### ","### ","### #"," #"]] .

Paksaan. Coba semua kombinasi dan #, pisahkan potongan int #, hitung panjangnya dan bandingkan dengan input.

PHP, 751 833 (720) 753 724 726 710 691 680 682 byte

Saya sangat ingin membangun kenaikan urutan khusus dan mencoba generator kartesian saya sekali lagi;
tetapi menjatuhkan kartesian demi mundur untuk memecahkan teka-teki besar lebih cepat.

$p=[];foreach($r as$y=>$h){for($d=[2-($n=count($h)+1)+$u=-array_sum($h)+$w=count($r)]+array_fill($i=0,$n,1),$d[$n-1]=0;$i<1;$d[0]+=$u-array_sum($d)){$o=$x=0;foreach($d as$i=>$v)for($x+=$v,$k=$h[$i];$k--;)$o+=1<<$x++;if(($s[$y]|$o)==$o){$p[$y][]=$o;$q[$y]++;}for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);if(++$i<$n)for($d[$i]++;$i--;)$d[$i]=1;}}
function s($i,$m){global$c,$w,$p;for(;!$k&&$i[$m]--;$k=$k&$m<$w-1?s($i,$m+1):$k){for($k=1,$x=$w;$k&&$x--;){$h=$c[$x];for($v=$n=$z=$y=0;$k&&$y<=$m;$y++)$n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];if($k&$v)$k=$n<=$h[$z];}}return$k?is_array($k)?$k:$i:0;}
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));

• mengharapkan petunjuk dalam array $runtuk petunjuk baris, $cuntuk petunjuk kolom dan$s untuk petunjuk persegi.
• melempar invalid argument supplied for foreachjika tidak menemukan solusi.
• untuk mendapatkan jumlah byte yang benar, gunakan fisik \ndan hapus dua jeda baris lainnya.

deskripsi

1) dari petunjuk baris
menghasilkan kemungkinan baris yang memenuhi petunjuk persegi
dan mengingat jumlah mereka untuk setiap indeks baris.

2) mundur mengikuti kombinasi baris:
Jika kombinasi memenuhi petunjuk kolom, cari lebih dalam atau kembalikan kombinasi yang berhasil,
jika tidak coba kemungkinan berikutnya untuk baris ini

3) solusi cetak

Golf terakhir memiliki dampak besar pada kinerja;
tapi saya menghapus tugas pembuatan profil untuk tolok ukur terakhir.

Ganti $n=$n*($f=($p[$y][$i[$y]]>>$x&1)==$v)+$k=$f?:($v=!$v)||$n==$h[$z++];
dengan if(($p[$y][$i[$y]]>>$x&1)-$v){$k=($v=!$v)||$n==$h[$z++];$n=1;}else$n++;
untuk membatalkan langkah golf terakhir.

contoh

Untuk contoh kecil ( 17 hingga 21 sekitar 12 8 7 6,7 5,3 ms), gunakan

$r=[[2],[3],[3],[3,1],[1]];$c=[[2],[3],[4],[2],[2]];$s=[0,0,0,0,0];

untuk teka-teki natal:

• membunuh server rumah kecil saya dengan solusi lama
• membunuh browser dengan hasil tes
• sekarang diselesaikan dalam 50 37,8 45,5 sekitar 36 detik

letakkan data dari pertanyaan ke file christmas.nonogramdan gunakan kode ini untuk mengimpor:

$t=r;foreach(file('christmas.nonogram')as$h)if('-'==$h=trim($h))$t=c;elseif('#'==$h){$t=s;$f=count($h).b;}else
{$v=explode(' ',$h);if(s==$t)for($h=$v,$v=0,$b=1;count($h);$b*=2)$v+=$b*array_shift($h);${$t}[]=$v;}

kerusakan

$p=[];  // must init $p to array or `$p[$y][]=$o;` will fail
foreach($r as$y=>$h)
{
    // walk $d through all combinations of $n=`hint count+1` numbers that sum up to $u=`width-hint sum`
    // (possible `0` hints for $h) - first and last number can be 0, all others are >0
    for(
        $d=[2-
            ($n=count($h)+1)+               // count(0 hint)=count(1 hint)+1
            $u=-array_sum($h)+$w=count($r)  // sum(0 hint) = width-sum(1 hint)
        ]                           // index 0 to max value $u-$n+2
        +array_fill($i=0,$n,1)      // other indexes to 1
        ,$d[$n-1]=0;                // last index to 0
                                    // --> first combination (little endian)
        $i<1;   // $i:0 before loop; -1 after increment; >=$n after the last combination
        $d[0]+=$u-array_sum($d) // (see below)
    )
    {
        // A: create row (binary value) from 1-hints $h and 0-hints $d
        $o=$x=0;
        foreach($d as$i=>$v)
            for($x+=$v,$k=$h[$i];$k--;)
                $o+=1<<$x++;
        // B: if $o satisfies the square hints
        if(($s[$y]|$o)==$o)
        {
            $p[$y][]=$o;    // add to possible combinations
            $q[$y]++;       // increase possibility counter
        }
        // C: increase $d
            // find lowest index with a value>min
                // this loop doesn´t need to go to the last index:
                // if all previous values are min, there is nothing left to increase
        for($i=0;$i<$n-1&$d[$i]==($i?1:0);$i++);
        if(++$i<$n)             // index one up; increase $d if possible
            for($d[$i]++        // increase this value
            ;$i--;)$d[$i]=1;    // reset everything below to 1
            // adjust $d[0] to have the correct sum (loop post condition)
    }
}

// search solution: with backtracking on the row combinations ...
function s($i,$m)
{
    global $c,$w,$p;
    for(;
        !$k // solution not yet found
        &&$i[$m]    // if $i[$m]==0, the previous iteration was the last one on this row: no solution
            --;     // decrease possibility index for row $m
        $k=$k&$m<$w-1? s($i,$m+1) : $k      // if ok, seek deeper while last row not reached ($m<$w-1)
    )
    {
        // test if the field so far satisfies the column hints: loop $x through columns
        for($k=1,$x=$w;$k&&$x--;)   // ok while $k is true
        {
            $h=$c[$x];
            // test column hints on the current combination: loop $y through rows up to $m
            for($v=$n=$z=   // $v=temporary value, $n=temporary hint, $z=hint index
                $y=0;$k&&$y<=$m;$y++)
                // if value has not changed, increase $n. if not, reset $n to 1
                // (or 0 for $k=false; in that case $n is irrelevant)
                $n=$n*  
                    // $f=false (int 0) when value has changed, true (1) if not
                    ($f=($p[$y][$i[$y]]>>$x&1)==$v)
                    +$k=$f?:    // ok if value has NOT changed, else
                        ($v=!$v)        // invert value. ok if value was 0
                        || $n==$h[$z    // value was 1: ok if temp hint equals current sub-hint
                        ++]             // next sub-hint
                ;
            // if there is a possibly incomplete hint ($v==1)
            // the incomplete hint ($n) must be <= the next sub-hint ($c[x][$z])
            // if $n was <$h[$z] in the last row, the previous column hints would not have matched
            if($k&$v)$k=$n<=$h[$z];
        }
        // ok: seek deeper (loop post condition)
        // not ok: try next possibility (loop pre condition)
    }
    return$k?is_array($k)?$k:$i:0;  // return solution if solved, 0 if not
}

// print solution
foreach(s($q,0)as$y=>$o)echo strrev(sprintf("\n%0{$w}b",$p[$y][$o]));