Résolution de mots croisés de couleurs japonaises à la vitesse de la lumière

Les mots croisés japonais (également les nonogrammes) sont des puzzles logiques dans lesquels une image pixel est cryptée. Vous devez résoudre les mots croisés en utilisant des nombres situés à gauche des lignes et au-dessus des colonnes.

La taille des mots croisés peut atteindre jusqu'à 150x150. Le joueur utilise une logique spéciale pour calculer la couleur de chaque cellule. La solution peut prendre quelques minutes sur des puzzles de mots croisés pour les débutants et des dizaines d'heures sur des puzzles complexes.

Un bon algorithme peut résoudre le problème beaucoup plus rapidement. Le texte décrit comment écrire une solution qui fonctionne presque instantanément en utilisant les algorithmes les plus appropriés (qui conduisent généralement à une solution), ainsi que leurs optimisations et l'utilisation des fonctionnalités C ++ (qui réduisent le temps d'exécution de plusieurs dizaines de fois).

Dans la version mobile de Habr, les formules dans le texte peuvent ne pas être affichées (pas dans tous les navigateurs mobiles) - utilisez la version complète ou un autre navigateur mobile si vous remarquez des problèmes avec les formules

Règles du jeu

Initialement, la toile de mots croisés est blanche. Pour les mots croisés noir et blanc vanille, vous devez restaurer l'emplacement des cellules noires.

Dans les mots croisés en noir et blanc, le nombre de nombres pour chaque ligne (à gauche du canevas) ou pour chaque colonne (en haut du canevas) indique le nombre de groupes de cellules noires dans la ligne ou la colonne correspondante, et les nombres eux-mêmes indiquent le nombre de cellules fusionnées que contient chacun de ces groupes. Ensemble de nombres $$$[3, 2, 5]$ signifie que dans une certaine ligne, il y a trois groupes consécutifs de $$$3$ , $$$2$ et $$ cellules noires dans une rangée. Les groupes peuvent être disposés de manière aléatoire, sans violer l'ordre relatif (les nombres spécifient leur longueur, et la position doit être devinée), mais ils doivent être séparés par au moins une cellule blanche.

Exemple correct

Dans les mots croisés de couleur, chaque groupe a toujours sa propre couleur - tout, sauf le blanc, est une couleur d'arrière-plan. Des groupes voisins de couleurs différentes peuvent se tenir côte à côte, mais pour les groupes voisins de mêmes couleurs, la séparation par au moins une cellule blanche est toujours nécessaire.

Ce qui n'est pas un mot croisé japonais

Chaque image pixel peut être cryptée comme un jeu de mots croisés. Mais il peut ne pas être possible de le restaurer - le casse-tête résultant peut avoir plus d'une solution, ou avoir une solution, mais ne peut pas être résolu logiquement. Ensuite, les cellules restantes du jeu doivent être devinées à l'aide de la technologie chamanique à l'aide d' ordinateurs quantiques .

De tels mots croisés ne sont pas des mots croisés, mais de la graphomanie. On pense que les mots croisés corrects sont tels que, de manière logique, vous pouvez arriver à une solution unique.

Le "chemin logique" est la possibilité de restaurer chaque cellule une par une, en considérant la ligne / colonne séparément ou leur intersection. Si cela n'est pas possible, le nombre d'options de réponse envisagées peut être beaucoup plus que ce qu'une personne peut calculer par elle-même.

Le mauvais nonogramme est la seule solution, mais il est impossible de le résoudre normalement. Cellules "insolubles" marquées en orange. Tiré de Wikipedia.

Cette restriction est expliquée comme suit - dans le cas le plus général, le casse-tête japonais est un problème NP-complet. Cependant, deviner ne devient pas une tâche NP-terminée, s'il existe un algorithme qui, à chaque instant, indique sans ambiguïté les cellules à ouvrir davantage. Tous les mots croisés utilisés par les humains (à l'exception de la méthode Monte Carlo essais et erreurs) sont basés sur cela.

Dans la plupart des mots croisés orthodoxes, la largeur et la hauteur sont divisées par 5, il n'y a pas de lignes qui peuvent être comptées instantanément (celles où les cellules colorées obstruent tous les endroits, ou elles sont complètement absentes), et le nombre de couleurs complémentaires est limité. Ces exigences ne sont pas obligatoires.

Le faux mot croisé le plus simple:

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

Souvent, le pixel art codé, qui utilise un motif en «damier» pour simuler un dégradé, n'est pas résolu à l'envers. Il est préférable de comprendre si vous tapez "dégradé pixelart" dans la recherche. Le dégradé est exactement comme ce mot croisé 2x2 fayl.

Solutions possibles

Nous avons la taille du puzzle de mots croisés, une description des couleurs et de toutes les lignes et colonnes. Comment puis-je assembler une image à partir de ceci:

Recherche complète

Pour chaque cellule, nous trions tous les états possibles et vérifions qu'ils sont satisfaisants. La complexité d'une telle solution pour un mot croisé en noir et blanc $$$O (N * M * {2} ^ {N * M})$ , pour la couleur $$$O (N * M * {couleurs} ^ {N * M})$ . Par analogie avec le tri des clowns, cette solution peut également être appelée clown. Il convient à la taille 5x5.

Retour en arrière

Toutes les méthodes possibles d'organisation des groupes horizontaux de cellules sont triées. Nous mettons un groupe de cellules dans une rangée, vérifions qu'il ne casse pas la description des groupes de colonnes. S'il se casse, on met encore 1 cellule, on vérifie encore. Set - passez au groupe suivant. Si vous ne pouvez pas mettre un groupe en aucune façon, nous annulons deux groupes, réorganisons le groupe précédent, et ainsi de suite, jusqu'à ce que nous ayons réussi à mettre le dernier groupe.

Séparément pour chaque ligne

Cette décision est bien meilleure et elle est vraiment vraie. Nous pouvons analyser chaque ligne et chaque colonne individuellement. Chaque ligne tentera de révéler le maximum d'informations.

L'algorithme pour chaque cellule de la ligne apprend plus d'informations - il peut s'avérer qu'il est impossible de colorer la cellule d'une certaine couleur, les groupes ne convergeront pas. Vous ne pouvez pas développer complètement la ligne immédiatement, mais les informations reçues "aideront" à mieux s'ouvrir sur plusieurs colonnes, et lorsque nous commencerons à les analyser, elles "aideront" à nouveau les lignes, et ainsi de suite pendant plusieurs itérations, jusqu'à ce que toutes les cellules aient une couleur possible.

Décision vraiment vraie

Une ligne, deux couleurs

Il est très difficile de deviner efficacement la «ligne unique» en noir et blanc, pour laquelle certaines cellules ont déjà deviné. Elle s'est rencontrée dans des endroits tels que:

• Quart de finale d'ACM ICPC 2006 - vous pouvez essayer de résoudre le problème vous-même . La limite de temps est de 1 seconde, la limite du nombre de groupes est de 400 et la longueur de la série est également de 400. Elle présente un niveau de complexité très élevé par rapport à d'autres tâches.
• Olympiade internationale d'informatique 2016 - condition pour réussir la tâche . La limite de temps est de 2 secondes, la limite du nombre de groupes est de 100, la longueur de la ligne est de 200'000. De telles limitations sont exagérées, mais la résolution d'un problème avec les restrictions ACM gagne 80/100 points dans ce problème. Ici aussi, le niveau n'a pas déçu, des écoliers du monde entier avec un niveau de QI cruel s'entraînent depuis plusieurs années pour résoudre différents trucs, puis ils se rendent à cette Olympiade (seulement 4 personnes du pays doivent passer), décident de 2 tours de 5 heures et dans le cas d'une victoire épique (bronze dans les différentes années pour 138-240 points sur 600), l'admission à Oxford, puis offre des sociétés claires au service de recherche, une longue et heureuse vie embrassée avec dakimakura.

Les lignes monochromes peuvent également être résolues de différentes manières, et pour $$$O (N * 2 ^ N)$ (énumérer toutes les options, vérifier l'exactitude, sélectionner les cellules qui ont la même couleur dans toutes les options), et en quelque sorte moins stupide.

L'idée principale est d'utiliser un analogue de backtracking, mais sans calculs inutiles. Si nous avons en quelque sorte mis en place plusieurs groupes et que nous sommes maintenant dans une sorte de cellule, alors nous devons savoir s'il est possible de mettre les groupes restants, à partir de la cellule actuelle.

 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) 

Cette approche est appelée programmation dynamique . Le pseudo-code est simplifié, et même les valeurs calculées n'y sont pas stockées.

Les fonctions CanInsertBlack/CanInsertWhite sont nécessaires pour vérifier s'il est théoriquement possible de placer un groupe de la bonne taille au bon endroit. Il leur suffit de vérifier qu'il n'y a pas de cellule «100% blanc» (pour la première fonction) ou «100% noir» (pour la seconde) dans la plage de cellules indiquée. Pour qu'ils puissent travailler pour $$$O (1)$ , cela peut être fait en utilisant des montants partiels:

 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 

La même sorcellerie avec des sommes partielles attend les lignes du formulaire

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

Ici, nous pouvons au lieu de = True augmenter le nombre de 1. Et si nous devons faire beaucoup d'ajouts sur un segment dans un certain tableau $$$array$ , et d'ailleurs nous n'utilisons pas ce tableau avant différents ajouts (ils disent à ce sujet que cette tâche est "résolue hors ligne"), puis au lieu d'une boucle:

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

Vous pouvez le faire:

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

Ainsi, l'ensemble de l'algorithme fonctionne dans $$$O (k * n)$ où $$$k$ - le nombre de groupes de cellules noires, $$$n$ Correspond à la longueur de la chaîne. Et nous allons à la demi-finale de l'ACM ICPC ou obtenons le bronze de l'interneur. Solution ACM (Java) . Solution IOI (C ++) .

Une ligne, plusieurs couleurs

Lorsque nous passons aux nonogrammes multicolores, qui ne savent toujours pas comment les résoudre, nous apprenons une terrible vérité - il s'avère que chaque colonne est affectée par magie par toutes les colonnes! Ceci est plus clair à travers un exemple:

Source - Méthodes de résolution des mots croisés japonais

Alors que les nonogrammes bicolores s'en passaient normalement, ils n'avaient pas besoin de regarder en arrière leurs amis orthogonaux.
L'image montre que dans l'exemple de gauche, les trois cellules d'extrême droite sont vides, car la configuration se casse si vous coloriez ces cellules dans ces couleurs pour te peindre couleur non blanche.

Mais cette plaisanterie est mathématiquement décidable - chaque cellule doit recevoir un numéro, où $$$i$ le ième bit signifiera si cette cellule peut être donnée $$$i$ e couleur. Initialement, toutes les cellules ont une valeur $$$2 ^ {couleurs} - 1$ . La décision de la dynamique ne changera pas beaucoup.

Vous pouvez observer l'effet suivant: dans le même exemple de gauche, selon la version des lignes, la cellule à l'extrême droite peut avoir une couleur bleue ou blanche.
Selon la version des colonnes, cette cellule a une couleur verte ou blanche.
Selon la version de bon sens, cette cellule n'aura qu'une couleur blanche. Et puis nous continuons à calculer la réponse.

Si nous considérons le bit zéro «blanc», le premier «bleu», le second «vert», la ligne a calculé l'état de la dernière cellule $$$011$ et la colonne $$$101$ . Cela signifie que l'état de cette cellule est réel $$

 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 

Beaucoup de lignes, beaucoup de couleurs

Faire constamment la mise à jour des états de toutes les lignes et colonnes, décrite dans le dernier paragraphe, jusqu'à ce qu'il n'y ait pas une seule cellule avec plus d'un bit. À chaque itération, après la mise à jour de toutes les lignes et colonnes, nous mettons à jour l'état de toutes les cellules qu'elles contiennent via AND mutuel.

Premiers résultats

Supposons que nous n'écrivions pas le code comme des pics, c'est-à-dire que nous ne copions pas d'objets par erreur au lieu de passer par référence, nous n'inventons pas de vélos n'importe où, nous n'inventons pas de vélos, pour les opérations de bits, nous utilisons __builtin_popcount et __builtin_ctz ( fonctionnalités gcc ), tout est net et propre.

Regardons le temps du programme, qui lit le puzzle du fichier et le résout complètement. Il vaut la peine d'évaluer les avantages de la machine sur laquelle tout cela a été écrit et testé:

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

Il est clair qu'un tel supercalculateur a été choisi parce que ses optimisations ont un effet plus important que sur une machine shaitane volante.

Ainsi, après avoir exécuté notre algorithme sur les mots croisés les plus compliqués (selon nonograms.ru), nous obtenons un résultat pas très bon - de 47 à 60 secondes (cela comprend la lecture d'un fichier et d'une solution). Il convient de noter que la "complexité" sur le site a été bien calculée - le même puzzle de mots croisés dans toutes les versions du programme était également le plus difficile, d'autres mots croisés les plus complexes, selon les archives, ont été conservés dans les meilleurs délais.

Mots croisés de couleur numéro 9596, la plus grande difficulté

Pour des tests rapides, la fonctionnalité de la référence a été créée. Pour obtenir des données pour lui, j'ai sparsil 4683 mots croisés de couleur (à partir de 10906 ) et 1406 noir et blanc (à partir de 8293 ) de nonograms.ru (c'est l'une des plus grandes archives de nonogrammes sur Internet) en utilisant un script spécial et les ai enregistrés dans un format que le programme comprend. Nous pouvons supposer que ces mots croisés sont un échantillon aléatoire, de sorte que la référence montrerait des valeurs moyennes adéquates. En outre, les nombres de quelques dizaines de mots croisés les plus "complexes" (également les plus grands en taille et en nombre de couleurs) ont été enregistrés dans un script pour le chargement avec des stylos.

Optimisation

Ici, vous pouvez voir les techniques d'optimisation possibles qui ont été faites (1) pendant l'écriture de l'algorithme entier, (2) pour raccourcir le temps de travail d'une demi-minute à une fraction de seconde, (3) les optimisations qui peuvent être utiles davantage.

Au moment de la rédaction de l'algorithme

• Fonctions spéciales pour les opérations sur les bits, dans notre cas __builtin_popcount pour compter les unités dans une notation binaire d'un nombre, et __builtin_ctz pour le nombre de zéros avant la première plus petite unité. Ces fonctions peuvent ne pas apparaître dans certains compilateurs. Pour Windows, ces analogues conviennent:

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

• Organisation de la baie - une taille plus petite vient en premier. Par exemple, il vaut mieux utiliser le tableau [2] [3] [500] [1024] que [1024] [500] [3] [2].
• La chose la plus importante est l'adéquation générale du code et l'évitement des soucis inutiles pour les calculs.

Ce qui réduit le temps de travail

• L'indicateur -O2 lors de la compilation.
• Afin de ne pas jeter à nouveau la ligne / colonne complètement résolue dans l'algorithme, vous pouvez définir les indicateurs pour chaque ligne dans un std :: vector / array séparé, les marquer avec une solution complète et ne pas lâcher s'il n'y a plus rien à résoudre.
• Les spécificités d'une solution multi-répétition d'un problème dynamique suggèrent qu'un tableau spécial qui contient des drapeaux marquant des morceaux déjà "calculés" du problème devrait être réinitialisé chaque fois qu'une nouvelle solution est faite. Dans notre cas, il s'agit d'un tableau / vecteur bidimensionnel, où la première dimension est le nombre de groupes, la seconde est la cellule actuelle (voir le pseudocode EpicWin ci-dessus, où ce tableau ne l'est pas, mais l'idée est claire). Au lieu de mettre à zéro, vous pouvez le faire - laissez-nous une variable "timer", et le tableau se compose de chiffres montrant la dernière "heure" lorsque cette pièce a été recomptée pour la dernière fois. Lors du démarrage d'une nouvelle tâche, le "temporisateur" augmente de 1. Au lieu de vérifier l'indicateur booléen, vous devez vérifier l'égalité de l'élément de tableau et du "temporisateur". Ceci est efficace en particulier dans les cas où loin de tous les états possibles sont couverts par l'algorithme (ce qui signifie que la mise à zéro du tableau «avons-nous déjà considéré cela» prend un gros morceau de temps).
• Remplacement d'opérations simples du même type (boucles avec affectation, etc.) par des analogues en STL ou des choses plus adéquates. Parfois, cela fonctionne plus vite qu'un vélo.
• std::vector<bool> en C ++ compresse toutes les valeurs booléennes en bits individuels en nombres, ce qui fonctionne sur l'accès un peu plus lentement que s'il s'agissait d'une valeur régulière à l'adresse. Si un programme utilise très, très souvent de telles valeurs, le remplacement de bool par un type entier peut avoir un bon effet sur les performances.
• D'autres faiblesses peuvent être recherchées via les profileurs et les modifier. J'utilise moi-même Valgrind, son analyse des performances est pratique pour parcourir kCachegrind. Les profileurs sont intégrés dans de nombreux IDE.

Ces modifications se sont avérées suffisantes pour obtenir de telles données sur l'indice de référence:

 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 

Vous remarquerez peut-être qu'en moyenne, les mots croisés en noir et blanc sont «plus difficiles» que ceux en couleur. Cela confirme les observations des amateurs de jeux, qui pensent également que la «couleur» se résout en moyenne plus facilement.

Ainsi, sans changements radicaux (comme la réécriture de tout le code en C ou les insertions d'assembleur avec fastcall et l'abaissement du pointeur de trame), vous pouvez obtenir des performances élevées sur un ordinateur très modeste. Le principe de Pareto peut être applicable aux optimisations - il s'avère que l'optimisation mineure influence fortement, car ce morceau de code est critique et est appelé très souvent.

Optimisation supplémentaire

Les méthodes suivantes peuvent améliorer considérablement les performances du programme. Certains d'entre eux ne fonctionnent pas dans tous les cas, mais sous certaines conditions.

• Réécriture de code en style C et autres 1972. Nous remplaçons ifstream par l'homologue analogique, les vecteurs avec des tableaux, apprenons toutes les options du compilateur et nous battons pour chaque cycle d'horloge du processeur.
• Parallélisation. Par exemple, dans le code, il y a un morceau où les lignes sont mises à jour séquentiellement, puis les colonnes:

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

Ces fonctions sont indépendantes les unes des autres et elles n'ont pas de mémoire partagée, à l'exception du solveur variable (type OneLineSolver), vous pouvez donc créer deux objets solveur (ici, évidemment, un seul est solveur) et démarrer deux threads dans la même fonction. L'effet est le suivant: dans les mots croisés de couleur, le «plus dur» est résolu deux fois plus vite, en noir et blanc, le même est un tiers plus rapide, et le temps moyen a augmenté, en raison du coût relativement élevé de la création de fils.

Mais en général, je ne recommanderais pas de le faire correctement dans le programme actuel et de l'utiliser calmement - premièrement, la création de threads est une opération coûteuse, vous ne devriez pas constamment créer des threads pour des tâches en microsecondes, et deuxièmement, avec une combinaison d'arguments du programme, les threads peuvent se référer à quels la mémoire externe, par exemple, lors de la création d'images d'une solution - cela doit être pris en compte et sécurisé.

Si la tâche était sérieuse et que j'aurais beaucoup de données et de machines multicœurs, j'irais encore plus loin - vous pouvez créer plusieurs threads constants, chacun aura son propre objet OneLineSolver et une autre structure thread-safe qui contrôle la distribution du travail et à la demande donne une référence à la ligne / colonne suivante pour la solution. Les threads après avoir résolu un autre problème se tournent à nouveau vers la structure pour résoudre autre chose. En principe, un problème de non-programmation peut être démarré sans terminer le précédent, par exemple, lorsque cette structure est engagée dans le ET mutuel de toutes les cellules, puis que certains flux sont libres et ne font rien. Plus de parallélisation peut être effectuée sur le GPU via CUDA - il existe de nombreuses options.

• Utilisation de structures de données classiques. Veuillez noter - lorsque j'ai montré le pseudo-code de la solution pour les nonogrammes de couleur, les fonctions CanInsertColor et PlaceColor ne fonctionnent pas du tout $$$O (1)$ , contrairement aux nonogrammes noir et blanc. Cela ressemble à ceci dans un programme:

 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); } } 

Autrement dit, cela fonctionne pour la ligne, pour $$$O (N)$ (Plus tard, il y aura une explication de la signification d'un tel code).

Voyons comment vous pouvez obtenir la meilleure complexité. Prenez CanPlaceColor . Cette fonction vérifie que parmi tous les nombres du vecteur dans le segment $$$[lbound, rbound]$ nombre de bits $$$couleur$ mis à 1. Équivalent à cela, vous pouvez prendre $$$ET$ tous les numéros de ce segment et vérifier le numéro de bit $$$couleur$ . En utilisant le fait que l'opération $$$ET$ commutative , ainsi que somme, minimum / maximum, produit ou opération $$$Xor$ , pour un comptage rapide $$$ET$ , . :

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, .

.