Memecahkan teka-teki silang warna Jepang dengan kecepatan cahaya

Teka-teki silang Jepang (juga nonogram) adalah teka-teki logis di mana gambar piksel dienkripsi. Anda harus menyelesaikan teka-teki silang menggunakan angka yang terletak di sebelah kiri garis dan di atas kolom.

Ukuran teka-teki silang bisa mencapai 150x150. Pemain menggunakan logika khusus untuk menghitung warna setiap sel. Solusinya mungkin memerlukan beberapa menit pada teka-teki silang untuk pemula, dan puluhan jam pada teka-teki kompleks.

Algoritma yang baik dapat memecahkan masalah lebih cepat. Teks ini menjelaskan cara menulis solusi yang bekerja hampir seketika menggunakan algoritma yang paling cocok (yang umumnya mengarah ke solusi), serta optimasi mereka dan penggunaan fitur C ++ (yang mengurangi runtime beberapa puluh kali).

Di Habr versi seluler, rumus dalam teks mungkin tidak ditampilkan (tidak di semua peramban seluler) - gunakan versi lengkap atau peramban seluler lainnya jika Anda melihat masalah dengan rumus

Aturan gim

Awalnya, kanvas teka-teki silang berwarna putih. Untuk teka-teki silang vanili hitam dan putih, Anda harus mengembalikan lokasi sel hitam.

Dalam teka-teki silang hitam dan putih, jumlah angka untuk setiap baris (di sebelah kiri kanvas) atau untuk setiap kolom (di atas kanvas) menunjukkan berapa banyak grup sel hitam dalam baris atau kolom yang sesuai, dan angka itu sendiri menunjukkan berapa banyak sel yang digabungkan yang berisi masing-masing grup ini. Set angka $$$[3, 2, 5]$ berarti dalam satu baris tertentu ada tiga grup berturut-turut dari $$$3$ , $$$2$ dan $$$5$ sel hitam berturut-turut. Grup dapat diatur dalam satu baris secara acak, tanpa melanggar urutan relatif (angka menentukan panjangnya, dan posisi harus ditebak), tetapi mereka harus dipisahkan oleh setidaknya satu sel putih.

Contoh yang benar

Dalam teka-teki warna, masing-masing kelompok masih memiliki warna sendiri - apa pun, kecuali putih, adalah warna latar belakang. Kelompok tetangga dengan warna berbeda dapat berdiri berdampingan, tetapi untuk kelompok tetangga dengan warna yang sama , pemisahan oleh setidaknya satu sel putih masih diperlukan.

Apa yang bukan teka-teki silang Jepang

Setiap gambar piksel dapat dienkripsi sebagai teka-teki silang. Tetapi mungkin tidak mungkin mengembalikannya kembali - puzzle yang dihasilkan dapat memiliki lebih dari satu solusi, atau memiliki satu solusi, tetapi tidak dapat dipecahkan secara logis. Maka sel-sel yang tersisa dalam permainan harus ditebak menggunakan teknologi perdukunan menggunakan komputer kuantum .

Teka-teki silang semacam itu bukan teka-teki silang, tetapi graphomania. Diyakini bahwa teka-teki silang yang benar adalah sedemikian rupa sehingga dengan cara yang logis Anda dapat menemukan solusi yang unik.

"Jalur logis" adalah kemampuan untuk memulihkan setiap sel satu per satu, dengan mempertimbangkan baris / kolom secara terpisah, atau persimpangannya. Jika ini tidak memungkinkan, jumlah opsi jawaban yang dipertimbangkan bisa sangat banyak, jauh lebih banyak daripada yang dapat dihitung seseorang untuk dirinya sendiri.

Nonogram yang salah adalah satu-satunya solusi, tetapi tidak mungkin untuk dipecahkan secara normal. Oranye berlabel sel yang "tidak dapat dipecahkan". Diambil dari Wikipedia.

Pembatasan ini dijelaskan sebagai berikut - dalam kasus yang paling umum, teka-teki silang Jepang adalah masalah NP-complete. Namun, menebak tidak menjadi tugas NP-lengkap, jika ada algoritma yang pada setiap saat waktu jelas menunjukkan sel mana yang akan dibuka lebih lanjut. Semua teka-teki silang yang digunakan oleh manusia (kecuali metode ini Monte Carlo coba-coba) berdasarkan ini.

Pada sebagian besar teka-teki silang Orthodox, lebar dan tinggi dibagi dengan 5, tidak ada baris yang dapat dihitung secara instan (yang mana sel-sel berwarna menyumbat semua tempat, atau mereka sama sekali tidak ada), dan jumlah warna komplementer terbatas. Persyaratan ini tidak diperlukan.

Teka-teki silang salah yang paling sederhana:

|1 1| --+---+ 1| | 1| | --+---+ 

Seringkali, pixel art yang dikodekan, yang menggunakan pola "kotak-kotak" untuk mensimulasikan gradien, tidak diselesaikan mundur. Lebih baik untuk memahami jika Anda mengetik "gradien pixelart" dalam pencarian. Gradien sama seperti teka-teki silang 2x2 ini.

Kemungkinan solusi

Kami memiliki ukuran teka-teki silang, deskripsi warna dan semua baris dan kolom. Bagaimana saya bisa mengumpulkan gambar dari ini:

Pencarian lengkap

Untuk setiap sel, kami memilah-milah semua keadaan yang mungkin dan memeriksa memuaskan. Kompleksitas solusi semacam itu untuk teka-teki silang hitam dan putih $$$O (N * M * {2} ^ {N * M})$ , untuk warna $$$O (N * M * {warna} ^ {N * M})$ . Dengan analogi dengan pemilahan badut, solusi ini juga bisa disebut badut. Sangat cocok untuk ukuran 5x5.

Mundur

Semua metode yang mungkin untuk mengatur kelompok sel horizontal diurutkan. Kami menempatkan sekelompok sel dalam satu baris, memeriksa apakah itu tidak merusak deskripsi grup kolom. Jika rusak, kita lanjutkan ke 1 sel, kita periksa lagi. Atur - pergi ke grup berikutnya. Jika Anda tidak dapat membuat grup dengan cara apa pun, kami memutar kembali dua grup, menyusun ulang grup sebelumnya, dan seterusnya, hingga kami berhasil membuat grup terakhir.

Secara terpisah untuk setiap baris

Keputusan ini jauh lebih baik dan itu benar. Kami dapat menganalisis setiap baris dan setiap kolom secara terpisah. Setiap baris akan mencoba mengungkapkan informasi maksimum.

Algoritma untuk setiap sel dalam baris mempelajari lebih banyak informasi - mungkin ternyata tidak mungkin untuk mewarnai sel dalam beberapa warna, grup tidak akan bertemu. Anda tidak dapat sepenuhnya memperluas baris, tetapi informasi yang diterima akan "membantu" membuka lebih baik ke beberapa kolom, dan ketika kami mulai menganalisisnya, mereka akan kembali "membantu" baris, dan seterusnya untuk beberapa iterasi, hingga semua sel memiliki satu warna yang memungkinkan.

Keputusan yang Benar-Benar Benar

Satu baris, dua warna

Menebak secara efektif "garis-tunggal" hitam-putih, yang sudah ditebak beberapa sel, adalah tugas yang sangat sulit. Dia bertemu di tempat-tempat seperti:

• Perempat final ACM ICPC 2006 - Anda dapat mencoba menyelesaikan sendiri masalahnya . Batas waktu adalah 1 detik, jumlah grup dibatasi hingga 400, dan panjang baris juga 400. Ini memiliki tingkat kompleksitas yang sangat tinggi dibandingkan dengan tugas lain.
• Olimpiade Internasional Informatika 2016 - syarat untuk lulus tugas . Batas waktu adalah 2 detik, batas jumlah grup adalah 100, panjang baris adalah 200'000. Batasan seperti itu berlebihan, tetapi menyelesaikan masalah dengan pembatasan ACM mendapatkan 80/100 poin dalam masalah ini. Di sini, juga, levelnya tidak mengecewakan, anak-anak sekolah dari seluruh dunia dengan tingkat IQ yang kejam telah dilatih selama beberapa tahun untuk menyelesaikan berbagai trik, kemudian mereka pergi ke Olimpiade ini (hanya 4 orang dari negara yang harus lulus), mereka memutuskan 2 putaran 5 jam dan dalam kasus kemenangan epik (perunggu di tahun yang berbeda untuk 138-240 poin dari 600), masuk ke Oxford, kemudian menawarkan dari perusahaan yang jelas ke departemen pencarian, kehidupan panjang dan bahagia dianut dengan dakimakura.

Single-line Monochrome juga dapat diselesaikan dengan cara yang berbeda, dan untuk $$$O (N * 2 ^ N)$ (enumerasi semua opsi, memeriksa kebenaran, memilih sel yang memiliki warna yang sama di semua opsi), dan entah bagaimana kurang bodoh.

Gagasan utamanya adalah menggunakan analog backtracking, tetapi tanpa perhitungan yang tidak perlu. Jika kita entah bagaimana mengatur beberapa kelompok dan sekarang berada dalam semacam sel, maka kita perlu mencari tahu apakah mungkin untuk menempatkan kelompok yang tersisa, mulai dari sel saat ini.

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

Pendekatan ini disebut pemrograman dinamis . Kode semu disederhanakan, dan bahkan nilai yang dihitung tidak disimpan di sana.

Fungsi CanInsertBlack/CanInsertWhite diperlukan untuk memeriksa apakah secara teori dimungkinkan untuk menempatkan sekelompok ukuran yang tepat di tempat yang tepat. Yang perlu mereka lakukan adalah memverifikasi bahwa tidak ada sel "100% putih" (untuk fungsi pertama) atau "100% hitam" (untuk yang kedua) dalam rentang sel yang ditunjukkan. Jadi mereka bisa bekerja $$$O (1)$ , ini dapat dilakukan dengan menggunakan jumlah parsial:

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

Sihir yang sama dengan jumlah parsial menunggu garis bentuk

 can_place_black[cell .. (cell + len[group] - 1)] = True 

Di sini kita dapat bukannya = True menambah angka dengan 1. Dan jika kita perlu membuat banyak penambahan pada segmen dalam array tertentu $$$array$ , dan selain itu kami tidak menggunakan array ini sebelum penambahan yang berbeda (mereka mengatakan tentang ini bahwa tugas ini "diselesaikan secara offline"), maka alih-alih sebagai loop:

 #     for i in range(L, R + 1): array[i]++ 

Anda bisa melakukan ini:

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

Dengan demikian, seluruh algoritme berfungsi dalam $$$O (k * n)$ dimana $$$k$ - jumlah kelompok sel hitam, $$$n$ Apakah panjang string. Dan kita pergi ke semi final ACM ICPC atau mendapatkan perunggu dari interneur. Solusi ACM (Jawa) . Solusi IOI (C ++) .

Satu baris, banyak warna

Ketika kita beralih ke nonogram multi-warna, yang masih belum jelas cara mengatasinya, kita mempelajari kebenaran yang mengerikan - ternyata setiap kolom secara ajaib dipengaruhi oleh semua kolom! Ini lebih jelas melalui contoh:

Sumber - Metode untuk memecahkan teka-teki silang Jepang

Sementara non-warna dua warna biasanya tanpa itu, mereka tidak perlu melihat kembali pada teman-teman ortogonal.
Gambar menunjukkan bahwa dalam contoh kiri, tiga sel ekstrem kanan kosong, karena konfigurasi rusak jika Anda mewarnai sel-sel ini warna-warna yang digunakan untuk melukis diri sendiri warna tidak putih.

Tapi lelucon ini secara matematis dapat ditentukan - setiap sel harus diberi nomor, di mana $$$i$ bit engan akan berarti apakah sel ini dapat diberikan $$$i$ warna th. Awalnya, semua sel memiliki nilai $$$2 ^ {warna} - 1$ . Keputusan dinamika tidak akan banyak berubah.

Anda dapat mengamati efek berikut: pada contoh kiri yang sama, menurut versi baris, sel di paling kanan dapat memiliki warna biru atau putih.
Menurut versi kolom, sel ini memiliki warna hijau atau putih.
Menurut versi akal sehat, sel ini hanya memiliki warna putih. Dan kemudian kami terus menghitung jawabannya.

Jika kita menganggap nol sedikit "putih", yang pertama "biru", yang kedua "hijau", maka garis menghitung negara untuk sel terakhir $$$011$ , dan kolom $$$101$ . Ini berarti bahwa keadaan sel ini nyata $$$011 \ & 101 = 001$

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

Banyak garis, banyak warna

Secara konstan melakukan pembaruan status semua baris dan kolom, yang dijelaskan dalam paragraf terakhir, hingga tidak ada sel tunggal dengan lebih dari satu bit. Di setiap iterasi, setelah memperbarui semua baris dan kolom, kami memperbarui status semua sel di dalamnya melalui mutual AND.

Hasil pertama

Misalkan kita tidak menulis kode seperti pelatuk, yaitu, kita tidak menyalin objek di mana pun secara tidak sengaja alih-alih dengan referensi, kita tidak menciptakan sepeda di mana pun, kita tidak menciptakan sepeda, untuk operasi bit kita menggunakan __builtin_popcount dan __builtin_ctz ( fitur gcc ), semuanya rapi dan bersih.

Mari kita lihat waktu program, yang membaca puzzle dari file dan menyelesaikannya sepenuhnya. Sebaiknya mengevaluasi keunggulan mesin tempat semua hal ini ditulis dan diuji:

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

Jelas bahwa superkomputer seperti itu dipilih karena optimisasi padanya memiliki efek yang lebih besar daripada pada mesin terbang syaitan.

Jadi, setelah menjalankan algoritma kami pada teka-teki silang yang paling rumit (menurut nonograms.ru), kami mendapatkan hasil yang tidak terlalu baik - dari 47 hingga 60 detik (ini termasuk membaca dari file dan solusi). Perlu dicatat bahwa "kompleksitas" di situs dihitung dengan baik - teka-teki silang yang sama di semua versi program juga merupakan teka-teki silang paling rumit dan paling rumit menurut pendapat arsip yang disimpan di urutan teratas.

Warna nomor teka-teki silang 9596, kesulitan terbesar

Untuk pengujian cepat, fungsionalitas untuk tolok ukur dibuat. Untuk mendapatkan data untuknya, saya sparsil 4683 teka-teki warna (dari 10906 ) dan 1406 hitam dan putih (dari 8293 ) dari nonograms.ru (ini adalah salah satu arsip nonogram terbesar di Internet) menggunakan skrip khusus dan menyimpannya dalam format yang dimengerti oleh program. Kita dapat mengasumsikan bahwa teka-teki silang ini adalah sampel acak, sehingga tolok ukur akan menunjukkan nilai rata-rata yang memadai. Juga, jumlah beberapa lusinan teka-teki silang paling "kompleks" (juga yang terbesar dalam ukuran dan jumlah warna) dicatat dalam naskah untuk memuat dengan pena.

Optimasi

Di sini Anda dapat melihat kemungkinan teknik optimasi yang dibuat (1) selama penulisan seluruh algoritma, (2) untuk mempersingkat waktu kerja dari setengah menit menjadi sepersekian detik, (3) optimasi yang mungkin berguna lebih lanjut.

Pada saat penulisan algoritma

• Fungsi khusus untuk operasi bit, dalam kasus kami __builtin_popcount untuk menghitung unit dalam notasi biner angka, dan __builtin_ctz untuk jumlah nol sebelum unit terkecil pertama. Fungsi tersebut mungkin tidak muncul di beberapa kompiler. Untuk Windows, analog seperti itu cocok:

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• Organisasi array - ukuran yang lebih kecil menjadi prioritas utama. Misalnya, lebih baik menggunakan array [2] [3] [500] [1024] daripada [1024] [500] [3] [2].
• Yang paling penting adalah kecukupan kode secara umum dan penghindaran kekhawatiran yang tidak perlu untuk perhitungan.

Yang mengurangi waktu kerja

• Bendera -O2 saat dikompilasi.
• Agar tidak membuang baris / kolom yang sepenuhnya diselesaikan ke dalam algoritma lagi, Anda dapat mengatur bendera untuk setiap baris dalam std :: vector / array yang terpisah, tandai dengan solusi penuh, dan jangan melepaskan jika tidak ada lagi yang harus dipecahkan.
• Kekhususan solusi multi-pengulangan masalah dinamis menunjukkan bahwa array khusus yang berisi tanda yang menandai bagian yang sudah "dihitung" dari masalah harus diatur ulang setiap kali solusi baru dibuat. Dalam kasus kami, ini adalah array dua dimensi / vektor, di mana dimensi pertama adalah jumlah grup, yang kedua adalah sel saat ini (lihat pseudocode EpicWin di atas, di mana array ini tidak, tetapi idenya jelas). Alih-alih mem-nolkan, Anda dapat melakukan ini - mari kita memiliki variabel "timer", dan array terdiri dari angka-angka yang menunjukkan "waktu" terakhir ketika bagian ini dihitung ulang untuk terakhir kalinya. Saat memulai tugas baru, "timer" bertambah 1. Alih-alih memeriksa flag Boolean, Anda harus memeriksa kesetaraan elemen array dan "timer". Ini efektif terutama dalam kasus-kasus di mana jauh dari semua keadaan yang mungkin dicakup oleh algoritma (yang berarti bahwa zeroing the array "apakah kita sudah mempertimbangkan ini" membutuhkan banyak waktu yang sehat).
• Mengganti operasi sederhana dari jenis yang sama (loop dengan penugasan, dll.) Dengan analog dalam STL atau hal-hal yang lebih memadai. Terkadang ini bekerja lebih cepat daripada sepeda.
• std::vector<bool> dalam C ++ mengkompres semua nilai boolean ke bit individual dalam angka, yang bekerja pada akses sedikit lebih lambat daripada jika itu adalah nilai reguler di alamat. Jika suatu program menggunakan nilai-nilai seperti itu sangat sering, mengganti bool dengan tipe integer dapat memiliki efek yang baik pada kinerja.
• Kelemahan lain dapat dicari melalui profiler dan mengeditnya. Saya sendiri menggunakan Valgrind, analisis kinerjanya nyaman untuk melihat melalui kCachegrind. Profiler dibangun ke dalam banyak IDE.

Pengeditan ini ternyata cukup untuk mendapatkan data seperti pada patokan:

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

Anda mungkin memperhatikan bahwa rata-rata silang hitam dan putih lebih “keras” daripada yang berwarna. Ini menegaskan pengamatan pecinta game, yang juga percaya bahwa "warna" diselesaikan rata-rata lebih mudah.

Dengan demikian, tanpa perubahan radikal (seperti menulis ulang semua kode dalam C atau insert assembler dengan fastcall dan menurunkan frame pointer), Anda dapat mencapai kinerja tinggi pada komputer yang sangat sederhana. Prinsip Pareto dapat diterapkan untuk optimisasi - ternyata optimasi kecil sangat memengaruhi, karena kode ini penting dan sering disebut.

Optimasi lebih lanjut

Metode berikut dapat sangat meningkatkan kinerja program. Beberapa dari mereka tidak bekerja dalam semua kasus, tetapi dalam kondisi tertentu.

• Kode penulisan ulang dalam gaya C dan lainnya 1972. Kami mengganti ifstream dengan mitra analog, vektor dengan array, mempelajari semua opsi kompiler dan berjuang untuk setiap siklus jam prosesor.
• Paralelisasi. Misalnya, dalam kode ada bagian di mana baris diperbarui secara berurutan, lalu kolom:

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

Fungsi-fungsi ini independen satu sama lain dan mereka tidak memiliki memori bersama, kecuali untuk pemecah variabel (tipe OneLineSolver), sehingga Anda dapat membuat dua objek pemecah (di sini, jelas, hanya satu pemecah) dan memulai dua utas dalam fungsi yang sama. Efeknya adalah ini: dalam teka-teki silang warna, yang "paling sulit" diselesaikan dua kali lebih cepat, hitam dan putih sama dengan sepertiga lebih cepat, dan waktu rata-rata telah meningkat, karena biaya pembuatan benang yang relatif tinggi.

Tetapi secara umum, saya tidak akan merekomendasikan melakukannya dengan benar dalam program saat ini dan menggunakannya dengan tenang - pertama, membuat utas adalah operasi yang mahal, Anda tidak harus terus-menerus membuat utas untuk tugas mikrodetik, dan kedua, dengan beberapa kombinasi argumen program, utas dapat merujuk ke mana memori eksternal, misalnya, saat membuat gambar solusi - ini harus diperhitungkan dan diamankan.

Jika tugasnya serius dan saya akan memiliki banyak data dan mesin multi-core, saya akan melangkah lebih jauh - Anda dapat membuat beberapa utas konstan, masing-masing akan memiliki objek OneLineSolver sendiri, dan struktur lain yang aman untuk mengontrol distribusi pekerjaan dan sesuai permintaan untuk itu memberikan referensi ke baris / kolom berikutnya untuk solusi. Thread setelah menyelesaikan masalah lain beralih ke struktur lagi untuk menyelesaikan sesuatu yang lain. Pada prinsipnya, masalah nonogram dapat dimulai tanpa menyelesaikan yang sebelumnya, misalnya, ketika struktur ini terlibat dalam mutual AND dari semua sel, dan kemudian beberapa aliran bebas dan tidak melakukan apa pun. Lebih banyak paralelisasi dapat dilakukan pada GPU melalui CUDA - ada banyak pilihan.

• Menggunakan struktur data klasik. Harap dicatat - ketika saya menunjukkan kode pseudo-solusi untuk nonogram warna, fungsi CanInsertColor dan PlaceColor tidak berfungsi sama sekali $$$O (1)$ , tidak seperti nonogram hitam dan putih. Sepertinya ini dalam sebuah program:

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

Artinya, ini berfungsi untuk garis, untuk $$$O (N)$ (Nanti akan ada penjelasan tentang arti kode seperti itu saja).

Mari kita lihat bagaimana Anda bisa mendapatkan kompleksitas terbaik. Ambil CanPlaceColor . Fungsi ini memeriksa bahwa di antara semua angka vektor di segmen $$$[terikat, terikat]$ nomor bit $$$warna$ set ke 1. Setara dengan ini, Anda dapat mengambil $$$DAN$ semua nomor segmen ini dan periksa nomor bit $$$warna$ . Menggunakan fakta bahwa operasi $$$DAN$ komutatif , serta jumlah, minimum / maksimum, produk, atau operasi $$$Xor$ , untuk penghitungan cepat $$$DAN$ , . :

1. SQRT-. $$$O(\sqrt{N})$ , $$$O(\sqrt{N})$ . .
2. . $$$O(N\log{N})$ , $$$O(\log{N})$ . .
3. (Sparse Table). $$$O(N\log{N})$ , $$$O(1)$ . .

, - ( $$$O(N)$ , $$$O(1)$ ) , , , $$$\ varphi$ , $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$ , — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$ , , — ( magic number , ). , $$$N=10^{5}$ , $$$O(N^2)$ 10 , $$$O(N\log{N})$ 0.150 , $$$N$ , . , ( ): $$$O(N\sqrt{N})$ versus $$$O(N\log^2{N})$ . $$$N$ ( ) — 15-30.
2. , .

— , - — $$$N$ , . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.