Thursday, September 16, 2010

Sopilandia


En un curso que estoy dando sobre lenguajes funcionales y lógico, se planteó la posibilidad de escribir un programa que hiciese y/o resolviese, los pasatiempos a los cuales se les llama "Sopilandia", o "Sopas de letras". Estos son simplemente una cuadrícula que contiene palabras, las cuales están escondidas en una maraña de letras. Las palabras en la cuadrícula pueden estar en cualquier dirección, arriba a abajo, de izquierda a derecha, en diagonal, etc. Los pasatiempos de esta naturaleza dan una lista de palabras y el lector debe intentar hallarlas dentro de la cuadrícula. Típicamente hay entre 15 o 20 palabras por acertijo, aunque en realidad, no tiene porqué haber un límite definido.

La dificultad de estos pasatiempos quizás resida en que leemos de izquierda a derecha y de arriba hacia abajo. Así, si hay palabras colocadas de abajo hacia arriba y/o de derecha a izquierda, puede ser difícil hallar la palabra que se encuentra en esa orientación pues no estamos acostumbrados a leer y a descubrir palabras que no estén en la orientación correcta.

La cuestión es que me decidí hace un par de semanas a escribir mi propio software de "Sopilandia", lo cual me llevó algunos días porque no me pude ocupar con frecuencia del problema.

La teoría de operación de programas de esta naturaleza comienza por colocar -en un arreglo bidimensional de caracteres- las palabras de una lista previamente escrita. Así, hubo que generar una rutina que leyera cada palabra y entonces el sistema me entregara la posición inicial (X,Y) de donde se ubicaría la palabra dentro del arreglo, así como su dirección u orientación dentro del mismo (de arriba a abajo, de derecha a izquierda, de abajo hacia arriba en diagonal, etc.). Hay de hecho ocho direcciones que pueden ser usadas, como puede verse en el siguiente diagrama esquemático:

Este asterisco con 8 terminales representa las posibles direcciones de las palabras.

Una vez teniendo esto, se colocan en el arreglo las palabras de acuerdo con la posición (X,Y) que el sistema haya dado, así como la orientación que se elije también al azar. Sin embargo, hay que tener presente que el algoritmo que genera números al azar es pseudoazaroso, porque es simplemente un polinomio (en principio, la computadora tiene un algoritmo de números pseudoaleatorios, pero cuya secuencia en ocasiones se puede repetir).




Igualmente una vez que se ha puesto la primera palabra, debemos estar ciertos que la siguiente debe ocuparse sin tener conflictos con la primera palabra, por ejemplo. Es decir, que la segunda palabra no debe, en ningún casillero, borrar ya una letra que esté puesta.

Sin embargo, pudiese darse el caso en que la intersección de dos palabras (en una letra), coincidan en ésta y entonces la sopa de letras puede seguir generándose. Por ejemplo, imaginemos que ponemos:

K
R
A
M
N
BOTVINNIK
K



En este caso, el generador de la sopa de letras puede seguir pues el nombre del campeón mundial de ajedrez, "Botvinnik", coincide con el de "Kramnik" en la segunda I del primer nombre. Esto, evidentemente, debe ser verificado y controlado por la computadora.

En caso de que haya conflicto de palabras, lo que hay que hacer es decirle al sistema que genere una nueva posición azarosa y de nuevo, probar que no hay conflictos en esas posiciones dentro del arreglo.

Cuando el pasatiempo está creado, podemos entonces desplegar la solución en un texto. Si queremos ya crear una sopa de letras, hay que crear una rutina extra, que genere en los espacios en blanco, letras al azar, de manera que "escondan" las palabras dentro de la matriz rectangular de caracteres.

Una vez hecho esto, basta con crear las rutinas correspondientes para guardar la Sopa de Letras y/o la Solución, así como las palabras a encontrar.

He aquí un ejemplo generado con mi programa. Se trata de hallar los apellidos de los jugadores de ajedrez que han sido campeones del mundo:

Steinitz
Lasker
Capablanca
Alekhine
Euwe
Botvinnik
Smyslov
Tal
Petrosian
Spassky
Fischer
Karpov
Kasparov
Kramnik
Kasimdzhanov
Ponomariov
Topalov
Anand
Khalifman



Este es la Sopa de Letras (las palabras anteriores están aquí escondidas):

WJSYUAIQYWOUHWMGHLWKZUJDCCMKJYULHCFEZZJSA CQZDBGOWECKANCRLNQCREBQIIHSQQFAROIMKVGQZG JWEMHMUCJHIGTIERUWIWWGWPNNXWVCCYUOSOFPXVM OCLVMSBIQNNMZONXADOCUNCVUUECNLIEZUPQLVOFT VNAISORTEPMRFUICFITIETIAAZKABQOKGRZXRNDLY BIRDTYHOVTAYLAHJLPZOEYOGGFLIIXUQABHCABJRF GOXMYENUKZRERGKPSVGUKFUNMBQONDAKMHNHXHPXK NUEVFKTBIFKJYMEREHCSIFASAMWXUJGWRNZIDMVCQ TAJCLQZGNLVQDSLVYBLBRLGPRSCGAQLCYDTOJTBJW YGQIRXGNNRBVJXABFHSGWRABYZIMFVSJMUAVPAHPC EMWPXCLSIXHREKSALAYNDCLKEEPSMBYIEZOUVFNUI KTBVDISZVDNCPEYHKNDTIXSSJKUXRHSOKIGBBMTBO QZHAJOYGTJTIVKEMSAJZODKHALIFMANWRGLGHRZHU XFNGPUEMOPZNBQKTXNQFVJYAQQBEKNDAQMSMNXFMA CLTNVBKSBUFUIXQZDDVKAPDJWWGKYTMBWRYTTELSH IRZSAHPXCALAZTINIETSGVJTBCMPEOKHCXDYZJRZM PXFAHNVDILATOCWEJNBQOVPYIITWNZQOIEJFFPXEJ VDLFNTCJNGRFUICLSTILMBVEOOYOKEWTPJQLLWDLP CJRLSZHPTMSPASSKYMAXSHBNTUPCQLCZVRVQRBJRY HPXSYFOVKSYMAOJQPPYCYNHUABEHWRHGBYBWXHOWF NVCXFMUBAAESGUOWOZNSFTNCGGLOBWNLGFHCDOVDO TBIELRZHFZSXMAVTVFTILZTILMQTHDVRMKNIJTBJT ZHPKRXFNMEKPSHBEBLZPKOZOSSXZOJAXTRUOPZGQZ FNUQWEMUSKPEANHJHSFUQFVXYYDFTPGDYWAUVGMWF MUAXCJSZYRWKYRNQNXLAXNFDDFILAWMJEEGZCLSCL RZGCJPYFEWCPETOVTERHDSLKKKPRGBSPKLMHHSXIU XFMIOWEMKDIWKZTVYKXMJYRQPQVXLHYUQSSMNYEOD EMSPUBKRPJOBQFZBFPDTPEXWVFBDRNEBWXXTTDKUJ


Y esta es la solución al pasatiempo:


-----------------------------------------
----------K---------E---------A-----V----
----------I---E-----W--------C-----O---V-
----------N---N-----U-------N-----P---O--
-NAISORTEPM---I-----E------A-----R---N---
----------A---H-----------L-----A---A----
--------K-R---K----------B-----K---H-----
--------I-K---EREHCSIF--A---------Z------
--------N-----L--------P---------D-------
--------N-----A-------A---------M--V-----
--------I--REKSALA---C---------I--O------
--------V--------N------------S--I-------
--------T--------A----KHALIFMAN-R--------
--------O--------N----------K--A---------
--------B--------D------------M----------
------------ZTINIETS-V-------O-----------
---------LAT--------O-------N------------
----------------S--L-------O-------------
----------SPASSKYMA-------P--------------
--------K--------PY----------------------
---------A------O--S---------------------
----------S----T----L--------------------
-----------P---------O-------------------
------------A---------V------------------
-------------R---------------------------
--------------O--------------------------
---------------V-------------------------
-----------------------------------------


A quien le interese mi programa, escríbame a morsa@la-morsa.com, y se lo mandaré de forma gratuita a vuelta de correo electrónico.

3 comments:

Guillermo said...

Hola Morsa,

Curiosamente este fue uno de los primeros juegos que hice cuando trabajé en Vermic, (pequeña compañía de software educativo localizada en Morelia, Mich). Hace como 4 años hice una versión Flash con niveles.

http://bit.ly/bTKwQK

Saludos

Tonat said...

hOLA Manuel,

Disculpa, el programa está en Delphi o ¿en qué lenguaje?


blaccer

Morsa said...

Tonat,

en delphi.

saludos
Manuel