Bases de G öbne y su aplicación
a la esolución de Sudokus
Bá ba a Zapa e Za oca
T abajo de in de g ado en Ma emá icas
Uni e sidad de Za agoza
Di ec o es del abajo:
José Ignacio Cogolludo Agus ín y
Jo ge Ma ín Mo ales
Espacio
9 de eb e o de 2021
P ólogo
Lógica, apidez, paciencia y ma emá icas. Teniendo en cuen a es os cua o concep os podemos e-
sol e el juego del Sudoku, el cual sigue siendo un pasa iempo emocionan e pa a millones de pe sonas.
Geomé icamen e hablando, un Sudoku es un able o de amaño 9×9 di idido en cajas 3×3, las cuales
poseen núme os en e el 1 y el 9. Es e ompecabezas obedece las siguien es eglas: no puede habe
núme os epe idos en la misma ila, columna o caja 3 ×3. Pe o, ¿po , pa a qué y cómo se aplican las
ma emá icas a la esolución de es e pasa iempo? Es en es e con ex o donde se basa el p esen e abajo.
La his o ia de los Sudokus se emon a a un juego del siglo XVIII, donde los ma emá icos suizos lo
llama on “Cuad ados la inos”. Sin emba go, el juego que conocemos ac ualmen e ue in en ado a ina-
les de la década de 1970 en Nue a Yo k. Es e juego, ideado po el a qui ec o Howa d Ga ns, se conocía
como “Ubica núme os”, pues consis ía en coloca núme os en los espacios acíos de una cuad ícula.
Ac ualmen e, es e ompecabezas se conoce como “Sudoku”. El nomb e p o iene de dos palab as japo-
nesas: Su, que signi ica núme o y Doku, que signi ica solo. Es e juego ma emá ico ue muy conocido en
Japón a pa i de 1986 aunque su popula idad mundial llega ía unos años más a de, en o no al 2005.
Hoy en día el Sudoku sigue siendo un enigma habi ual en los pe iódicos, páginas online, e is as,
concu sos... Además, como se a a de un puzle numé ico que es imula las capacidades men ales y la
memo ia, pe mi e que no sea solo una di e sión, sino que ambién esul e un ap endizaje.
Po o a pa e, exis en algunas a ian es de es e amoso juego. En [7] se da un modelo ma emá ico
jun o con su sis ema de ecuaciones algeb aicas. Algunas de es as a ian es son: el able o es á colo eado
en g is y blanco de mane a que las celdas g ises con ienen núme os pa es y las celdas blancas solamen e
impa es (Sudoku pa -impa ), se puede da como pis a inicial la suma de un g upo de celdas en ez del
alo de cada celda indi idual (Sudoku kille ), el able o iene o mas dis in as de un ec ángulo (Sudo-
kus geomé icos), e c.
Aunque de p ime as esul e cuan o menos cu ioso, ealmen e el Sudoku se basa en undamen os
ma emá icos, y po ello exis en mé odos numé icos con los que pode esol e los. T a ando el Sudoku
como si ue a un g a o, inculando así la geome ía y el álgeb a, podemos esol e es e juego lógico. Un
concep o cla e pa a ello son las bases de G öbne que, de una mane a elegan e y di ec a, nos pe mi i án
conoce odas las soluciones de un sis ema de ecuaciones. Es as bases de ideales se o man de al mane a
que pa a odo polinomio del ideal, el é mino p incipal de es e polinomio es di isible po alguno de los
é minos p incipales de los polinomios que componen dicha base. Además, pa a ello, en es e abajo nos
amilia iza emos con una de las muchas aplicaciones de las bases de G öbne , la colo ación de g a os.
Cabe menciona la a iedad de aplicaciones elacionadas con es a eo ía, en e las que se encuen an
calcula el polinomio mínimo en ex ensiones de cue pos, da demos aciones au omá icas en Geome ía
Euclidiana, es udia sis emas c ip og á icos y p og amación en e a e incluso es udia algunos esul ados
de Teo ía de g a os.
III
Es e abajo es á o ganizado del siguien e modo. En el Capí ulo 1 se a an los undamen os alge-
b aicos y concep os p e ios que in oducen la eo ía de las bases de G öbne . En el Capí ulo 2 p o un-
diza emos en dicha eo ía pa a lo cual abaja emos con polinomios en a ias a iables. Pa a es os dos
p ime os capí ulos de in o mación más eó ica nos hemos basado en el lib o [5], pe o hay o as e e en-
cias sob e es e ema como son [1]y[9]. A con inuación, en el Capí ulo 3 nos cen a emos en es udia el
p oblema del colo eado en un g a o, lo cual es á undamen ado en la Sección 3 de [4]. Finalizando, en el
Capí ulo 4 aplica emos lo es udiado en los es capí ulos p e ios pa a consegui nues o obje i o, esol-
e Sudokus aplicando las ma emá icas y la compu ación. Es e capí ulo inal apoya su desa ollo y base
eó ica en [7]. Po úl imo, en el Apéndice A se p esen an a ios códigos, u ilizados pa a la esolución
de algunos ejemplos implemen ados median e el so wa e SageMa h [10], el cual usa en “backg ound”
el p og ama SINGULAR [6] pa a calcula las bases de G öbne .
Toda es a base ma emá ica es la que pe mi e que la gen e pueda pone a p ueba su ce eb o con
ace ijos lógicos, in e esan es y desa ian es. Po lo cual, el Sudoku segui á siendo un en e enimien o
que ido y popula en la ida co idiana de millones de pe sonas en odo el mundo.
Palab as cla e: polinomios, algo i mo de la di isión, o den monomial, ideales monomiales, Lema
de Dickson, bases de G öbne , Teo ema de las bases de Hilbe , algo i mo de Buchbe ge , g a o,
k-colo ación, Sudoku, Shidoku.
IV
Summa y
In his p ojec i will be explained se e al heo e ical esul s and p ac ical examples ela ed o Sudo-
kus. Mo e speci ically, his wo k will be based on he s udy o he G öbne bases and i s applica ion o
bo h g aph heo y and Sudokus esolu ion.
This p ojec is di ided in o ou chap e s. A b ie desc ip ion o each chap e will be gi en inmedia-
ely below.
-Chap e 1: P e ious concep s and undamen als
To begin wi h, he necessa y concep s o unde s anding he o he chap e s a e gi en. These con-
cep s include de ini ions such as monomial, polynomial, a ine space, a ine and linea a ie ies
and ideal, among o he s. The exis ence and uniqueness o he di ision algo i hm o polynomials
in one a iable will be s udied.
-Chap e 2: G öbne Bases
Once he p e ious pa is comple ed, he main pa o his p ojec will be s udied. In his second
chap e , he heo y o G öbne bases will be in oduced and s udied. Polinomials in K[x1,...,xn]
will be deal and how o o de monomials will be discussed, explaining some o he exis ing
monomial o de ings ypes. This concep will be impo an o s udy he di ision algo i hm in
K[x1,...,xn]which will be be e unde s ood by an example. Besides, Dickson’s Lemma and
Hilbe ’s basis Theo em will be s a ed and p o ed. Then, Buchbe ge ’s algo i hm will be unde s-
ood. Tha esul will be used o cons uc he G öbne bases. A code o his algo i hm has been
implemen ed using SageMa h, which can be ound in he Appendix A. To end his chap e , ou
p oblems abou polynomials and ideals will be sol ed hanks o he G öbne bases:
1. The ideal desc ip ion p oblem.
2. The ideal membe ship p oblm.
3. The p oblem o sol ing polinomial equa ions.
4. The implici iza ion p oblem.
-Chap e 3: G aph colo ing
G aph colo ing wi h kcolo s is he main goal o his chap e . Fi s o all, he kind o g aphs we
need will be de ined and hen, he explana ion and esolu ion o his p oblem will be ea ed. To
do his, a sys em o polynomial equa ions imposing some condi ions will be gene a ed. To sol e
his sys em, he G öbne bases will be used, o which a SageMa h code has been implemen ed.
Mo eo e , his code is explained in he Appendix A.
-Chap e 4: Sudokus and G öbne bases
Sudokus will be sol ed using G öbne bases heo y and he Sudoku will be conside ed as i i
was a g aph in o de o apply some esul s o Chap he 3. Tha is, o sol e Sudokus a sys em
o polynomial equa ions has o be ob ained, in he same way ha i is ob ained o he g aph
colo ing p oblem in he p e ious chap e . An ideal in he polynomial ing o se e al a iables will
V

be associa ed o he Sudoku. This ideal will be gene a ed by he polynomials which de ine he
sys em o equa ions. The educed G öbne basis will be calcula ed o his ideal whose gene a o s
o m a sys em equi alen o he o iginal sys em. Tha is why sol ing his new sys em o equa ions,
using ma hema ics and compu a ion, he solu ion o he Sudoku is ob ained. In he Appendix A i
is explained how o w i e wi h SageMa h a Sudoku wi h he ini ial clues gi en o be able o apply
he code gene a ed o he p e ious chap e and hen he sys em will be sol ed. Finally, some
ma hema ical conjec u es a e discussed. Mo eo e , a conclusion o his in e es ing applica ion o
he G öbne bases is gi en.
VI
Índice gene al
P ólogo III
Summa y V
1. Concep os y undamen os p e ios 1
1.1. Polinomios en espacios a ines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Va iedadesa ines ..................................... 2
1.3. Ideales........................................... 2
1.4. Polinomios en una a iable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Bases de G öbne 5
2.1. O den monomial en a ias a iables . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. El algo i mo de la di isión en a ias a iables . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Idealesmonomiales.................................... 9
2.4. El Teo ema de las bases de Hilbe y bases de G öbne . . . . . . . . . . . . . . . . . 11
2.5. C i e io y algo i mo de Buchbe ge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6. Aplicaciones de las bases de G öbne . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Colo eado de g a os 17
3.1. Resolución del p oblema del k-colo eado ........................ 18
4. Sudokus y bases de G öbne 20
4.1. Sudokus.......................................... 20
4.1.1. Caso pa icula : Shidokus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.2. ResoluciónSudokus ............................... 24
4.1.3. Gene alización n×n............................... 24
4.2. Conje u asma emá icas.................................. 25
4.3. Conclusión ........................................ 25
A. Códigos SageMa h 27
Bibliog a ía 31
VII
Capí ulo 1
Concep os y undamen os p e ios
A lo la go de es e capí ulo da emos algunas de iniciones y algunos esul ados p elimina es que se án
de ele ancia pa a comp ende las bases de G öbne , obje o p incipal de es udio del ma co eó ico.
1.1. Polinomios en espacios a ines
De inición 1. Un monomio xαen las a iables x1,...,xnes un p oduc o de la o ma
xα=xα1
1·xα2
2···xαn
n
donde odos los exponen es α1,...,αnson en e os no nega i os. El o den o al de un monomio es la
suma de sus exponen es, el cual deno a emos median e |α|.
De inición 2. Un polinomio en las a iables x1,...,xncon coe icien es en un cue po Kes una com-
binación lineal ini a de monomios con coe icien es ambién en K. Esc ibi emos el polinomio de la
siguien e mane a:
=∑
α
aαxα,aα∈K,α= (α1,...,αn).
Deno a emos median e K[x1,...,xn]al conjun o de odos los polinomios en x1,...,xncon coe icien-
es en el cue po K. Es e conjun o o ma un anillo de polinomios.
De inición 3. Sea =∑
α
aαxαun polinomio en K[x1,...,xn].En onces:
i) El coe icien e del monomio xαes aα.
ii) Si aα6=0, en onces aαxαse á un é mino del polinomio .
iii) El g ado o al de 6=0 es el máximo |α| al que el coe icien e aαes no nulo. Lo deno a emos
median e g ado( ).
Ejemplo 1. Hola
Sean los monomios −15x2y 3xy4. En onces el o den o al del p ime monomio es 2 y el o den
o al del segundo monomio es 1+4=5.
Sea aho a el polinomio =3xy4−15x2 o mado como combinación lineal de los dos monomios
an e io es. En p ime luga , no a que es un polinomio en R[x,y].
• El coe icien e del monomio 3xy4es 3 y el coe icien e de −15x2es −15.
• es á compues o po dos é minos: 3xy4y−15x2.
•g ado( ) = 5 (ya que 1 +4=5>2).
1
8Capí ulo 2. Bases de G öbne
Ejemplo 5. Veamos un ejemplo de cómo unciona es e algo i mo en Q[x,y]. Que emos di idi el po-
linomio (x,y) = x3y+x2+2xy2+xy +x+yen e 1(x,y) = x2y+1 y 2(x,y) = xy usando el o den
lexicog á ico x>y.
Pa a comenza , conside amos q1=0,q2=0, =0,p= .
Como LT ( 1) = x2ydi ide a LT (p) = x3yen onces podemos ac ualiza los alo es de q1yp
ob eniendo q1=x, y p=x2+2xy2+xy +y.
Sin emba go aho a, LT(p) = x2no es di idido po LT( 1) = x2yni po LT( 2) = xy. En onces el
algo i mo nos indica que x2pasa a o ma pa e del es o de la di isión. Ac ualizando, ob enemos
=x2, y p=2xy2+xy +y.
Aho a, LT ( 2) = xy sí di ide a LT(p) = 2xy2y ob enemos los siguien es alo es ac ualizados:
q2=2y, y p=xy +y.
Como LT ( 2) = xy di ide a LT(p) = xy en onces ac ualizando enemos q2=2y+1, y p=y.
Pa a inaliza , emos que ni LT ( 1) = x2yni LT ( 2) = xy di ide a LT(p) = yde modo que yes
pa e del es o y así =x2+y. En es e caso enemos p=0, luego hemos e minado la di isión y
el algo i mo inaliza.
Recopilando odo, enemos:
x3y+x2+2xy2+xy +x+y= (x)(x2y+1)+(2y+1)(xy)+(x2+y).
Llegados a es e pun o podemos p egun a nos si los cocien es y el es o ob enidos pueden a ia
dependiendo del cue po de polinomios en el que abajemos. Veamos con el siguien e ejemplo que
e ec i amen e, el cue po es impo an e.
Ejemplo 6. Tomamos los polinomios , 1, 2del Ejemplo 5 con la di e encia de que aho a odos ellos
es án en el cue po ini o Z3[x,y]. Al aplica el algo i mo de la di isión y di idi en e 1y 2usando
el o den lexicog á ico x>yse ob iene:
x3y+x2+2xy2+xy +x+y= (x)(x2y+1)+(−y+1)(xy)+(x2+y).
También podemos ob ene dis in os cocien es q1,...,qsy dis in o es o dependiendo de cómo es án
o denados los di iso es 1,..., s. De modo que el Ejemplo 5 nos ayuda a en ende po qué el algo i -
mo de la di isión en K[x1,...,xn]necesi a que = ( 1,..., s)sea una s- upla o denada de polinomios

Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 9
usando un o den monomial y ambién nos ilus a que el es o no es á de e minado de mane a única: Si
di idimos en e [ 1, 2]ob enemos q1=x,q2=2y+1, =x2+y( e Ejemplo 5), mien as que si
di idimos en e [ 2, 1]ob enemos q1=x2+2y+1,q2=0, =x2+x+y.
Recalca ambién que el algo i mo de la di isión depende ue emen e de la elección del o den mo-
nomial, es deci , los cocien es y el es o pueden a ia dependiendo del o den monomial elegido.
Vimos en el p ime capí ulo, al inal de la Sección 1.4, que una de las ca a e ís icas del algo i mo de
la di isión en K[x]es esol e el p oblema de pe enencia al ideal, ob eniendo en onces que la condición
=0 e a una condición su icien e y necesa ia pa a conclui que ∈ h 1,..., si.
Aho a nos encon amos en la siguien e si uación,
P oblema: P oblema de pe enencia al ideal en K[x1,...,xn].
Como hemos is o an e io men e, dado un polinomio ∈K[x1,...,xn], consis e en decidi si
∈I=h 1,..., si.
¿Se puede hace algo pa ecido al caso en una a iable? ¿Exis e algún algo i mo pa a esol e lo?
Solución:
Toda ía no podemos esol e lo, ya que aho a la condición =0 es una condición su icien e pe o no ne-
cesa ia pa a a i ma que ∈ h 1,..., si. Pa a soluciona es e p oblema que emos encon a un conjun o
gene ado del ideal, en el que el es o se de e mine de o ma única y en el que la condición =0 sea
equi alen e a pe enece al ideal. Es e conjun o se á el que, pos e io men e, llama emos base de G öb-
ne . Pa a llega has a allí, necesi amos in oduci p e iamen e los concep os y esul ados de la siguien e
sección.
2.3. Ideales monomiales
De inición 16. Un ideal I⊆K[x1,...,xn]se dice ideal monomial si exis e un subconjun o A⊆Zn
≥0
al que Ies á o mado po odos los polinomios de la o ma ∑
α∈A
hαxαdonde hα∈K[x1,...,xn]. Lo
deno a emos I=hxα|α∈Ai.
Es deci , un ideal monomial se puede gene a po monomios pe o es o no quie e deci que odos los
elemen os del ideal sean monomios. Veamos un ejemplo de ideal que es monomial, y o o que no.
Ejemplo 7. I=hxy +y2,yx −y2ies un ideal monomial y sin emba go I0=hxy +y2,x−yino lo es. En
e ec o:
Llamamos 1=xy +y2y 2=yx −y2. En onces 1
2( 1+ 2) = xy ∈Iy1
2( 1− 2) = y2∈I.
Luego podemos esc ibi hxy +y2,yx −y2i=hxy,y2i. De modo que Ies un ideal gene ado po
monomios, así que Ies un ideal monomial.
Llamamos 1=xy +y2y 2=x−y. En onces y 2+ 1=2xy ∈Iyy 2− 1=2y2∈I.
Luego podemos esc ibi hxy +y2,x−yi=hxy,y2,x−yiy e así que I0no se puede gene a po
monomios. Luego I0no es un ideal monomial.
Lema 2.3. Sea I =hxα|α∈Aiun ideal monomial. En onces un monomio xβpe enece a I si y solo si
xβes di isible po xαpa a algún α∈A.
Lema 2.4. Sea I un ideal monomial y sea ∈K[x1,...,xn]. En onces las siguien es a i maciones son
equi alen es:
i) ∈I.
10 Capí ulo 2. Bases de G öbne
ii) Todo é mino de es á en I.
iii) es una combinación lineal en el cue po K de monomios de I.
Colo a io 2.5. Dos ideales monomiales son iguales si y solo si con ienen los mismos monomios.
A con inuación, se enuncia y demues a el Lema de Dickson ya que end á g an impo ancia en
esul ados eó icos pos e io es.
Teo ema 2.6 (Lema de Dickson).Todo ideal monomial I =hxα|α∈Aise puede esc ibi como I =
hxα(1),...,xα(s)i, donde los en e os α(i)∈A,∀i=1,...,s. En pa icula , I iene una base ini a.
Demos ación. P ocedamos po inducción sob e el núme o de a iables, n.
◦Sea n=1. En onces Ies á ini amen e gene ado en K[x1]po los monomios xα
1, donde α∈A⊆
Z≥0. Es o es po que omando β≤αcomo el meno elemen o de Aen onces xβ
1di ide a odo xα
1
y así, po el Lema 2.3, I=hxβ
1i.
◦Supongamos que es cie o pa a n−1 (con n>1) y eamos si se cumple el esul ado pa a n.
Asumimos la siguien e no ación: esc ibi emos las a iables como x1,...,xn−1,yde modo que los
monomios en K[x1,...,xn−1,y]se esc ibi án como xαymcon α∈Zn−1
≥0,m∈Z≥0.
Supongamos que I⊆K[x1,...,xn−1,y]es un ideal monomial. Pa a encon a los gene ado es de
I, de inimos J⊆K[x1,...,xn−1]como un ideal gene ado po los monomios xα ales que xαym∈I
pa a algún m≥0. Es deci ,
J=hxα∈K[x1,...,xn−1]|xαym∈I,m≥0i.
Po se Jun ideal monomial en K[x1,...,xn−1], aplicando la hipó esis de inducción exis i á un
núme o ini o de gene ado es de modo que enemos J=hxα(1),...,xα(s)i, con α(i)∈A.
Pa a cada 1 ≤i≤s, po de inición de J, se cumple xα(i)ymi∈Ipa a algún mi≥0. Sea mel
máximo de los mi. En onces pa a cada 0 ≤k≤m−1 conside amos Jk⊆K[x1,...,xn−1]como un
ideal gene ado po los monomios xβ ales que xβyk∈I. Es deci ,
Jk=hxβ∈K[x1,...,xn−1]|xβyk∈I,0≤k≤m−1i.
Aplicando de nue o la hipó esis de inducción enemos Jk=hxαk(1),...,xαk(sk)i, o equi alen emen-
e, Jkes á gene ado po un núme o ini o de monomios.
Veamos que Ies á gene ado po los siguien es monomios:
p oceden es de J:xα(1)ym,...,xα(s)ym
p oceden es de J0:xα0(1),...,xα0(s0)
p oceden es de J1:xα1(1)y,...,xα1(s1)y
.
.
.
p oceden es de Jm−1:xαm−1(1)ym−1,...,xαm−1(sm−1)ym−1.
Tenemos que cada monomio de Ies di isible po alguno de la lis a an e io . En e ec o, omamos
xαyp∈I:
- Si p≥men onces xαypes di isible po algún xα(i)ymdebido a la cons ucción de J.
- Si p≤m−1 en onces xαypes di isible po algún xαp(j)ypdebido a la cons ucción de Jp.
Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 11
Así que po el Lema 2.3 enemos que la lis a an e io de monomios gene a un ideal con los mismos
monomios que I, y po el Co ola io 2.5 se iene que ambos ideales son el mismo.
Po úl imo, eamos que el conjun o ini o de gene ado es se puede escoge de los gene ado es del
ideal. Deno ando aho a las a iables como x1,...,xn, en onces I=hxα|α∈Aies nues o ideal
monomial. Que emos e que Ies á gene ado po un núme o ini o de xα’s, con α∈A. Hemos
is o que I=hxβ(1),...,xβ(s)ipa a cie os monomios xβ(i)∈I,i=1,...,s. Como xβ(i)∈I, po
el Lema 2.3 se iene que cada xβ(i)es di isible po xα(i),α(i)∈A. Po doble con enido se e
ácilmen e que I=hxα(1),...,xα(s)icomple ando así la demos ación.
Una de las consecuencias del Lema de Dickson es que dadas las dos p ime as condiciones de la
De inición 11, la condición iii) iene un equi alen e. Veámoslo:
Colo a io 2.7. Sea >una elación de o den en Zn
≥0cumpliendo:
i) >es un o den o al en Zn
≥0.
ii) Si α>β,γ∈Zn
≥0en onces α+γ>β+γ.
En onces >es un buen o den si y solo si α≥0pa a odo α∈Zn
≥0.
2.4. El Teo ema de las bases de Hilbe y bases de G öbne
En es a sección se da án esul ados eó icos los cuales se i án pa a da una solución al p oblema de
la desc ipción del ideal explicado al p incipio de es e capí ulo. La idea p incipal es que dado un o den
monomial, odo polinomio no nulo iene un único é mino p incipal. En onces pa a cualquie ideal I
podemos de ini su ideal de é minos p incipales de la siguien e mane a.
De inición 17. Sea I⊆K[x1,...,xn]un ideal dis in o del nulo. En onces, una ez ijado un o den mo-
nomial en K[x1,...,xn]:
i) Deno a emos median e LT (I)al conjun o de odos los é minos p incipales de odos los elemen os
de Ique sean no nulos. Es deci ,
LT (I) = {cxα|exis e ∈I {0} al que LT( ) = cxα}.
ii) Deno a emos median e hLT (I)ial ideal gene ado po los elemen os del conjun o LT(I).
P oposición 2.8. Sea I ⊆K[x1,...,xn]un ideal dis in o del nulo, en onces
i) hLT (I)ies un ideal monomial.
ii) Exis en g1,...,g ∈I ales que se cumple la igualdad hLT(I)i=hLT(g1),...,LT(g )i.
Pa a p oba el siguien e esul ado, ha emos uso de la P oposición 2.8 y del Teo ema 2.2 (algo i mo
de la di isión), dando así una espues a a i ma i a al p oblema de la desc ipción del ideal explicado al
p incipio de es e capí ulo.
Teo ema 2.9 (Teo ema de las bases de Hilbe ).Todo ideal I ⊆K[x1,...,xn]es á ini amen e gene ado.
En o as palab as, I =hg1,...,g icon g1,...,g ∈I.
Demos ación. Hola
◦Si I={0}, como {0}es un gene ado de Iy es un conjun o ini o en onces se iene el esul ado.
12 Capí ulo 2. Bases de G öbne
◦Si I6={0}, en onces un conjun o gene ado g1,...,g de Ise puede cons ui de la siguien e
mane a:
Como I iene un ideal de é minos p incipales, po la P oposición 2.8 exis en g1,...,g ∈I ales
que hLT (I)i=hLT(g1),...,LT (g )i. Comp obemos aho a que, e ec i amen e, I=hg1,...,g i.
Pa a ello, p ocedamos po doble con enido:
- Dado que odo gi∈I, es cla o que hg1,...,g i ⊆ I.
- Sea ∈Iun polinomio cualquie a. Fijado un o den monomial, se aplica el algo i mo de la
di isión en a ias a iables pa a di idi po [g1,...,g ]y ob enemos
=q1g1+···+q g +
donde ningún é mino de es di isible po ningún LT(gi),i=1,..., . Veamos que =0.
Pa a ello p ocedamos po educción al absu do suponiendo 6=0 . En al caso LT ( )∈
hLT (I)i=hLT(g1),...,LT (g )i(ya que = −q1g1− ··· − q g ∈I) y po el Lema 2.3
se iene que LT ( )debe se di isible po algún LT (gi),i=1,..., . Como es o con adice
la a i mación an e io de que ningún é mino de es di isible po ningún LT(gi), se iene
=0. Po lo an o =q1g1+···+q g +0∈ hg1,...,g i, comple ando así la demos ación
del segundo con enido I⊆ hg1,...,g i.
Luego, po doble con enido, I=hg1,...,g i.
De inición 18. Dado un o den monomial, un subconjun o ini o G={g1,...,g }de un ideal I⊆
K[x1,...,xn]se di á base de G öbne si
hLT (g1),...,LT(g )i=hLT(I)i.
De una mane a menos o mal, un conjun o {g1,...,g } ⊆ Ies una base de G öbne de Isi y solo si el
é mino p incipal de cada elemen o de Ies di isible po alguno de los LT (gi), pa a i=1,..., .
Hola
Po con enio se iene h/0i={0}. De inimos en onces el conjun o acío /0 como la base de G öbne del
ideal nulo {0}.
Colo a io 2.10. Dado un o den monomial, odo ideal I ⊆K[x1,...,xn] iene una base de G öbne . Es
más, cualquie base de G öbne de un ideal I es una base de I.
Veamos una consecuencia geomé ica del Teo ema 2.9 bas an e impo an e, ya que luego nos pe -
mi i á esol e sis emas de ecuaciones en a ias a iables de una o ma sencilla.
De inición 19. Sea I⊆K[x1,...,xn]un ideal. Deno a emos median e V(I)al conjun o
V(I) = {(a1,...,an)∈Kn| (a1,...,an) = 0,∀ ∈I)}.
P oposición 2.11. El conjun o V(I)es una a iedad a ín. En pa icula , si I =h 1,..., si, en onces
V(I) = V( 1,..., s).
A con inuación, eamos que, al aplica el algo i mo de la di isión en a ias a iables, el es o de la
di isión es único cuando los di iso es o man una base de G öbne .
P oposición 2.12. Fijado un o den monomial, sea G ={g1,...,g }una base de G öbne del ideal
I⊆K[x1,...,xn]y sea ∈K[x1,...,xn]. En onces exis e un es o único ∈K[x1,...,xn]que cumple las
dos siguien es p opiedades:
i) Ningún é mino de es di isible po LT(gi), pa a i =1,..., .
ii) Exis e g ∈I al que =g+ .
En pa icula , es el es o de la di isión de en e G sin impo a el o den de los elemen os de G.
Colo a io 2.13. Sea G ={g1,...,g }una base de G öbne del ideal I ⊆K[x1,...,xn]y sea ∈
K[x1,...,xn]. En onces ∈I si y solo si el es o de la di isión de en e G es ce o.
Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 13
2.5. C i e io y algo i mo de Buchbe ge
A pa i de aho a esc ibi emos ¯
Fpa a deno a el es o de la di isión del polinomio en e la s- upla
o denada F= ( 1,..., s). Si Fes una base de G öbne pa a el ideal h 1,..., sien onces la s- upla F
no es necesa io que es é o denada.
Ejemplo 8. Di idiendo =x4y2po F= (xy −1,y2−1)⊆K[x,y], u ilizando el o den lexicog á ico
(x>y), ob enemos
x4y2F=x2
ya que median e el algo i mo de la di isión se iene
x4y2= (x3y+x2)·(xy −1)+(0)·(y2−1)+x2.
A con inuación, e emos el c i e io de Buchbe ge , el cual nos ayuda á a sabe si el gene ado de un
ideal dado es una base G öbne o no. Pa a ello necesi amos in oduci p e iamen e dos de iniciones.
De inición 20. Sean ,g∈K[x1,...,xn]polinomios no nulos. Si mul ig ado( ) = αymul ig ado(g) =
β, sea γ= (γ1,...,γn)donde γi=max(αi,βi)pa a cada i=1,...,n. Llama emos xγal mínimo común
múl iplo de LM( )yLM(g), es deci , xγ=mcm(LM( ),LM(g)).
De inición 21. Sean ,g∈K[x1,...,xn]polinomios no nulos. De inimos el S-polinomio de ygcomo
S( ,g) = xγ
LT ( )· −xγ
LT (g)·g.
Aho a ya sí podemos enuncia el siguien e esul ado, el cual como ya hemos explicado, si e pa a
sabe cuándo una base de un ideal es una base de G öbne .
Teo ema 2.14 (C i e io de Buchbe ge ).Sea I un ideal de polinomios. En onces una base G ={g1,...,g }
de I es una base de G öbne de I ⇔S(gi,gj)G=0,∀i,j ales que i 6=j.
Demos ación. Ve [5, Capí ulo 2, Sección 6].
Ejemplo 9. Sea I=hx2−y2+z,z−1i. Veamos que G={x2−y2+z,z−1}es una base de G öbne
pa a Iu ilizando el o den lexicog á ico habi ual (x>y>z).
Deno amos g1=x2−y2+zy ambién g2=z−1. En onces LT(g1) = x2,LT(g2) = zyxγ=x2z(ya que
mul ig ado(g1) = (2,0,0)ymul ig ado(g2) = (0,0,1)). De es e modo
S(g1,g2) = x2z
x2·g1−x2z
z·g2=x2−y2z+z2.
Aho a, aplicando el algo i mo de la di isión ob enemos
x2−y2z+z2= (1)(−x2−y2+z)+(−y2+z)(z−1)+0.
Po lo an o
S(g1,g2)G=0.
Así que po el c i e io de Buchbe ge se iene que Ges una base de G öbne pa a I.
Ya hemos is o en el Co ola io 2.10 que odo ideal iene una base de G öbne . Además, g acias
al Teo ema 2.14 (c i e io de Buchbe ge ) ya sabemos e si una base dada es una base de G öbne o
no. Pe o dado un ideal I⊆K[x1,...,xn], ¿podemos cons ui noso os una base de G öbne pa a I? La
espues a a es o es que sí. Pa a ello u iliza emos el siguien e algo i mo.
Teo ema 2.15 (Algo i mo de Buchbe ge ).Sea I =h 1,..., si 6={0}un ideal de polinomios. En onces
podemos cons ui una base de G öbne G ={g1,...,g }de I en un núme o ini o de pasos u ilizando
el siguien e algo i mo:

14 Capí ulo 2. Bases de G öbne
Po lo an o, usando el c i e io de Buchbe ge y el algo i mo de Buchbe ge hemos conseguido un
mé odo pa a ob ene bases de G öbne . Pe o es as bases, habi ualmen e ienen más elemen os de los
necesa ios. Veamos que podemos elimina alguno u ilizando el siguien e lema.
Lema 2.16. Sea G una base de G öbne de I ⊆K[x1,...,xn]y sea p ∈G un polinomio al que LT (p)∈
hLT (G {p})i. En onces G {p}es ambién una base de G öbne de I.
Ejemplo 10. Conside amos el anillo de polinomios Q[x,y,z]con el o den lexicog á ico habi ual
(x>y>z) y sea I=h 1, 2i=hx2+y,x3+zi.
Lo p ime o es e que F={ 1, 2}no es una base de G öbne :
Como LT (S( 1, 2)) = xy /∈ hLT ( 1),LT ( 2)i=hx2,x3i, en onces el c i e io de Buchbe ge nos ga an-
iza que Fno es una base de G öbne de I.
Vamos a cons ui una base de G öbne , a pa i de F, u ilizando el algo i mo de Buchbe ge .
Iniciamos el algo i mo y así G0=F. Aho a, di idiendo S( 1, 2) = xy −zpo Fob enemos como es o
3=xy−z, el cual es no nulo. Po lo an o debemos ac ualiza nues a base G0={ 1, 2, 3}. En onces,
S( 1, 2)G0
=S( 2, 3)G0
=0,
S( 1, 3)G0
=xz +y26=0.
Po lo an o, añadiendo 4=xz +y2,G0={ 1, 2, 3, 4}. Aho a,
S( 1, 2)G0
=S( 1, 3)G0
=S( 1, 4)G0
=S( 2, 3)G0
=0,
S( 3, 4)G0
=−y3−z26=0.
Así que enemos una nue a G0={ 1, 2, 3, 4, 5}, siendo 5=−y3−z2, pa a la cual se cumple
S( i, j)G0
=0,∀1≤i<j≤5.
Así, po el c i e io de Buchbe ge enemos que G={ 1, 2, 3, 4, 5}es una base de G öbne de Icon
espec o al o den lexicog á ico.
No a aho a que LT( 2) = x·LT( 1). Así que po el Lema 2.16 podemos p escindi de 2en nues a
nue a base de G öbne . Como no hay más casos en los que el é mino p incipal de un gene ado di ida
al é mino p incipal de o o gene ado , en onces la mínima base de G öbne que podemos ob ene es:
G={ 1, 3, 4, 5}.
De inición 22. Una base de G öbne minimal de un ideal de polinomios I⊆K[x1,...,xn]es una base
de G öbne Gde Ila cual cumple:
i) ∀p∈G,LC(p) = 1.
Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 15
ii) ∀p∈G,LT (p)/∈ hLT(G {p})i.
Desa o unadamen e el ideal Iinicial puede ene a ias bases de G öbne minimales, ya que po
ejemplo omando ˜
1=x2+y+az con a∈Q ambién se ía G={˜
1, 3, 4, 5}una base de G öbne
minimal. Pe o a o unadamen e hay una base minimal que es mejo que el es o. Su de inición es la
siguien e.
De inición 23. Una base de G öbne educida de un ideal de polinomios I⊆K[x1,...,xn]es una base
de G öbne Gde Ila cual cumple:
i) ∀p∈G,LC(p) = 1.
ii) ∀p∈G, ningún monomio de pes á en hLT(G {p})i.
Teo ema 2.17. Sea I un ideal de polinomios no nulo. En onces, pa a un o den monomial dado, I iene
una única base de G öbne educida.
Demos ación. In oduzcamos la siguien e de inición: Di emos que g∈G,Gbase de G öbne minimal
de I, es un elemen o educido espec o de Gsi ningún monomio de gpe enece a hLT(G) {p}i con
p∈G. No a que si ges un elemen o educido espec o de Gen onces g ambién es educido espec o
cualquie o a base de G öbne minimal de Ique con enga a gy que enga los mismos é minos p inci-
pales.
El obje i o pa a e la exis encia de una base de G öbne educida es pa i de una base de G öbne
minimal Gy modi ica la has a que odos sus elemen os sean elemen os educidos.
Dado g∈Gun elemen o educido espec o de G, omamos g0=gG {g}yG0= (G {g})∪{g0}. Vea-
mos que G0es una base de G öbne minimal de I. Pa a ello no a que LT (g0) = LT(g)ya que al di idi
gen e G {g}, necesa iamen e LT (g)pasa a o ma pa e del es o po que no es di isible po ningún
elemen o de LT (G {g}). Así enemos que hLT(g0)i=hLT (g)i. Como cla amen e G0⊆I enemos que
G0es una base de G öbne minimal de I. Además, g0es un elemen o educido de G0po cons ucción.
Aho a omamos los elemen os de Gy aplicamos el p ocedimien o an e io has a que odo elemen o sea
educido, ob eniendo así una base de G öbne educida.
Queda po p oba la unicidad de es a base de G öbne educida, la cual acabamos de e que exis e.
Sean Gy˜
Gdos bases de G öbne educidas de I. En pa icula Gy˜
Gson ambién bases de G öbne mi-
nimales de I, luego LT (G) = LT (˜
G). En onces dado g∈G, exis i á un ˜g∈˜
G al que LT (g) = LT(˜g). Así
que si p obamos g=˜gen onces G=˜
Gy la unicidad es a á p obada. Pa a e que g=˜g, conside emos
el polinomio g−˜g, el cual es á en I. Como Ges una base de G öbne se sigue que g−˜gG=0. También,
como LT (g) = LT(˜g)en onces ambos se cancelan al e ec ua la es a g−˜gy el es o de é minos no son
di isibles po ninguno de los LT (g) = LT(˜g)ya que Gy˜
Gson bases de G öbne educidas. Se sigue
que g−˜gG=g−˜gy po lo an e io g−˜g=0, luego g=˜gcomple ando así la demos ación.
El siguien e esul ado, a pesa de es a ca ego izado como co ola io end á g an ele ancia en los
dos capí ulos pos e io es. Tene en cuen a que un cue po Kse dice algeb aicamen e ce ado si cada
polinomio de g ado al menos 1, con coe icien es en K, iene un ce o en K.
Colo a io 2.18. Sea K un cue po algeb aicamen e ce ado. Dado un ideal I ⊆K[x1,...,xn]y dada G
una base de G öbne educida de I en onces V(I) = /0 si y solo si G ={1}.
2.6. Aplicaciones de las bases de G öbne
En es a sección amos a esol e , u ilizando las bases de G öbne , los p oblemas sob e ideales y
a iedades enume ados y b e emen e explicados al p incipio de es e segundo capí ulo.
16 Capí ulo 2. Bases de G öbne
1. P oblema de la desc ipción del ideal.
Ya se explicó que es e p oblema consis e en sabe si los ideales I⊆K[x1,...,xn]es án o mados
po un conjun o ini o. Lo esol imos u ilizando el Teo ema 2.9, ya que es e esul ado a i ma que
odo ideal es á ini amen e gene ado.
2. P oblema de pe enencia al ideal.
Dado un ideal I=h 1,..., si ⊆ K[x1,...,xn]podemos sabe si un polinomo pe enece a Ide la
siguien e mane a:
- Encon a una base de G öbne G={g1,...,g }de Iu ilizando el Teo ema 2.15 (algo i mo
de Buchbe ge ).
- Po el Co ola io 2.13 podemos a i ma que ∈I⇔ G=0.
3. P oblema de esolución de un sis ema de ecuaciones.
Veamos cómo podemos aplica las bases de G öbne pa a esol e sis emas de ecuaciones en
a ias a iables:
- Si encon amos una base de G öbne de un ideal, con espec o al o den lexicog á ico, la
o ma de las ecuaciones se simpli ica bas an e, ya que las a iables se an eliminando suce-
si amen e. Un sis ema de ecuaciones de es a o ma es mucho más ácil de esol e .
- Po la P oposición 2.11, la cual dice que las a iedades a ines es án de e minadas po ideales,
se iene que las soluciones ob enidas con el p ocedimien o an e io , son odas las que exis en.
4. P oblema de implici ación en ideales.
El p oblema de encon a un sis ema de ecuaciones cuyas soluciones sean los pun os de una
a iedad puede esol e se u ilizando nue amen e las bases de G öbne . Veamos cómo:
- Conside amos las ecuaciones pa amé icas
x1= 1( 1,..., m),
.
.
.
xn= n( 1,..., m),
las cuales de inen un subconjun o de una a iedad V⊆Kn. Nos cen amos en el caso de que
isean ealmen e polinomios. Conside amos la siguien e a iedad a ín en Km+n
x1− 1( 1,..., m) = 0,
.
.
.
xn− n( 1,..., m) = 0.
La idea es elimina las a iables 1,..., mde esas ecuaciones. Pa a ello enemos que ob ene
una base de G öbne .
- Supongamos que hemos ob enido una base de G öbne pa a el ideal I=hx1− 1,...,xn− ni
con espec o al o den lexicog á ico ( 1>··· > m>x1>··· >xn). En onces los polinomios
de la base de G öbne que solo in oluc an las a iables x1,...,xnson las soluciones del
sis ema de ecuaciones.
Capí ulo 3
Colo eado de g a os
En es e capí ulo amos a de ini el concep o de g a o simple, al cual llama emos g a o, y e emos
cómo aplica las bases de G öbne a la Teo ía de g a os, en pa icula da emos una solución al p oblema
del k-colo eado en un g a o.
De inición 24. Un g a o Ges un pa G= (V,E), donde Ves un conjun o ini o de pun os, llamados
é ices, y Ees un conjun o de pa es no o denados de é ices, llamadas a is as del g a o. Además
di emos que dos é ices son adyacen es si ambos son ex emos de la misma a is a.
De inición 25. Un camino en e dos é ices u1yu es una sucesión de a is as de la o ma
{u1,u2},{u2,u3},...,{u −1,u }que une los é ices u1yu .
De inición 26. Sea G= (V,E)un g a o. Se dice que Ges un g a o conexo si pa a odo pa u, ∈V
siemp e exis e un camino que une uy .
De inición 27. Sea Gun g a o conexo con é ices V={1,...,n}y a is as E={1,...,m}. Sea Cun
conjun o ini o cuyos elemen os llama emos colo es. Una colo ación de Ges una co espondencia al
que a cada uno de los é ices de Gse le asigna un colo de Cde mane a que dos é ices adyacen es no
pueden ecibi el mismo colo . Fo malmen e, una colo ación de Ges una aplicación γ:V−→ C al que
γ(u)6=γ( )si exis e una a is a de Gque une uy . El alo de γ(u)es el colo que ecibe el é ice uen
la colo ación γ.
De inición 28. Una colo ación de un g a o Gcon kcolo es (k≥1) se llama k-colo ación de G.
De inición 29. Di emos que un g a o Ges k-colo eable si exis e una k-colo ación asignada.
Obse a que si Ges k-colo eable inmedia amen e se iene que Ges ambién (k+1)-colo eable.
No a ambién que si nes el núme o de é ices en onces Ges n-colo eable.
De inición 30. El núme o c omá ico de un g a o Gse de ine como el mínimo alo k∈N al que Ges
k-colo eable y se deno a po χ(G). Si k=χ(G)se dice que el g a o es k-c omá ico.
Ejemplo 11. Sea Gun g a o conexo o mado po 5 é ices, luego V={1,2,3,4,5}, y po 4 a is as,
luego E={{1,3},{2,4},{3,4},{3,5}}.Es e g a o es cla amen e 5-colo eable ya que iene 5 é ices.
Sin emba go, χ(G) = 2 y así Ges 2-colo eable.
17
24 Capí ulo 4. Sudokus y bases de G öbne
Figu a 4.4
4.1.2. Resolución Sudokus
Aho a que hemos en endido cómo esol e los Shidokus, podemos aumen a el amaño de ny se-
gui los mismos pasos pa a consegui el obje i o de es e capí ulo: esol e los Sudokus u ilizando el
p oblema del 9-colo eado y las bases de G öbne .
Con inuamos con el puzle Sudoku del Ejemplo 13, el cual que emos esol e . Reco da que ya ha-
bíamos hallado los polinomios co espondien es a las condiciones iniciales (los cuales gene an L) de
modo que solo al a cons ui el ideal I=J+Ly ob ene su base de G öbne G. De es e modo, siguien-
do los mismos pasos que pa a los Shidokus y u ilizando SageMa h, se iene que la solución es:
Figu a 4.5
Desa o unadamen e, los sis emas de ecuaciones polinómicas que esuel en los Sudokus no son muy
“amigables” ya que el núme o de ecuaciones es bas an e ele ado. A pesa de que exis en unciones, ya
incluidas en los paque es de la mayo ía de los lenguajes de p og amación, pa a esol e dichos sis emas,
p oduci el sis ema de ecuaciones y aplica las bases de G öbne no es un buen mé odo en gene al. Sin
emba go, es e en oque iene algunas en ajas como po ejemplo ob ene odas las posibles soluciones
al y como se ha is o en el Ejemplo 15.
4.1.3. Gene alización n×n
Al p incipio de es e capí ulo hemos de inido que un Sudoku es á o mado po una cuad ícula 9 ×9
y ambién hemos is o que se puede educi ndando así luga a los Shidokus. En onces, iene su lógica
p egun a nos ¿npuede se cualquie núme o na u al, excep uando el 0? Y e ec i amen e la espues a a
es o es a i ma i a, podemos elegi n.
La esolución de es os Sudokus amaño n×nes simplemen e una gene alización de lo es udiado
con an e io idad. Es deci , pa a esol e lo enemos que calcula la base de G öbne educida del ideal
I=J+L o mado po :
- El ideal J o mado po los polinomios ygde inidos como (xi) = n
∏
k=1
(xi−ck),
g(xi,xj) = (xi)− (xj)
xi−xj
=0,siendo 0 ≤i<j≤n2−1.
- El ideal L=hxi−cki,siendo 0 ≤i≤n2−1,1≤k≤n.

Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 25
De es e modo, una ez que enemos la base de G öbne educida G, po la P oposición 4.1 end emos la
solución pa a cualquie Sudoku de amaño n×n.
4.2. Conje u as ma emá icas
A con inuación, amos a da algunas conje u as ma emá icas, es deci , algunas a i maciones apa en-
emen e e dade as, ya que se han hecho p uebas con i mando su e acidad, pe o no hay demos ación
ma emá ica de ellas.
•Uno de los emas que podemos cues iona nos es ¿cuán os posibles Shidokus y Sudokus dis in os
hay, igno ándose las elaciones de sime ía en e soluciones simila es? Tal y como se explica en
[11], exis en 288 able os de Shidokus. Sin emba go, al in en a con a cuán os Sudokus exis en,
el núme o de posibilidades es mayo y el cos e compu acional aumen a. En [11] se explica el
camino que se ha seguido pa a ob ene una buena ap oximación al núme o o al de able os de
Sudokus álidos, siendo es e núme o 6,6571 ·1021.
•Uno de los p oblemas elacionados con el Sudoku que más ha in e esado a los ma emá icos, po
habe es ado mucho iempo sin espues a, es el del núme o mínimo de pis as que puede ene un
Sudoku pa a esol e lo de mane a única. Se ha conseguido encon a mul i ud de puzles de 17
pis as con solución única pe o ninguno con solo 16 [11]. Es e p oblema, denominado “P oblema
del Sudoku mínimo” ue esuel o en 2012 con la ayuda de un o denado e aluando odos, sal o
equi alencias, los cuad ados de Sudokus en busca de algún puzle de 16 pis as. Los a í ices de es a
demos ación son Ga y McGui e, Bas ian Tugemann y Gilles Ci a io. En el caso de los Shidokus,
es e núme o mínimo es 4, como se menciona en [11].
•Sin emba go, ni odos los Sudokus con 17 pis as, ni odos los Shidokus con 4 pis as ( éase el
Ejemplo 15), ienen solución única. Es o nos lle a a p egun a nos, ¿cuál es el núme o máximo de
pis as que puede habe en una cuad ícula y aún no ene solución única? En la página 26 de [11]
se obse a un puzle Sudoku con 77 pis as y sin solución única. De modo que 77 es el máximo
núme o de pis as pa a el cual un Sudoku no iene solución única. Además se conje u a que pa a
cualquie o a a ian e de los Sudokus, de amaño n×n, es e núme o máximo es n2−4.
•La di icul ad en los Sudokus se c ee que depende del núme o de pis as iniciales. Pe o, so p en-
den emen e, es a di icul ad se basa en la posición de las pis as. Es a es la azón po la que la
dis ibución de las pis as dis ingue un Sudoku ácil de o o di ícil. En la página 122 de [3] se
mues a un Sudoku con 20 pis as de mínima di icul ad y o o con 28 pis as de di icul ad máxima.
•Una medida más e inada de la di icul ad se hace a pa i del es udio de las écnicas de esolución
de Sudokus, como se mues a en [3]. Algunos mé odos son más simples que o os, po lo que se
puede conje u a que si un Sudoku equie e un azonamien o más complejo pa a esol e lo, se
le asocia una di icul ad mayo . Sin emba go, es ima la di icul ad de un Sudoku no es, ni mucho
menos, una ciencia exac a, debido a la eno me ca ga de subje i idad que ello conlle a.
4.3. Conclusión
A modo de conclusión, señala la impo ancia que albe ga es a aplicación de las bases de G öbne ,
ya que hemos conseguido uni concep os geomé icos y algeb aicos. Pa a una modelización geomé ica
de los Sudokus hemos es udiado un p oblema undamen al de la Teo ía de g a os el cual a a de colo ea
un g a o con kcolo es. De es e modo, hemos sido capaces de con igu a ma emá icamen e un Sudoku
como si uese un g a o con an os é ices como celdas. Además, hemos esuel o sis emas de ecuaciones
no lineales u ilizando así la pa e eó ica es udiada en el Capí ulo 2, la cual hace e e encia a un es udio
en el ma co algeb aico. Po lo an o, a pesa de que apa en emen e el Sudoku es un juego sencillo de
pu a lógica, el es udio ealizado en es e capí ulo mues a un as ondo cla amen e ma emá ico, an o en
su plan eamien o como en su esolución.
Apéndice A
Códigos SageMa h
Es a pa e inal es á des inada a mos a odos los códigos esc i os en SageMa h que se han u ilizado
pa a la esolución de a ios ejemplos a lo la go del p esen e abajo.
•Algo i mo de la di isión en a ias a iables.
- Las a iables de en ada son ( ,G,A)donde es un polinomio, Ges una lis a de polinomios
yAes un anillo de polinomios.
- Las a iables de salida son (Q,A( )) donde Qes una lis a de polinomios, que se co espon-
den con los cocien es, y A( )es el es o de la di isión.
d e d i ( , G, A ) :
s = l e n (G)
p = A( )
Q = s *[0]
= 0
w hi le p != 0 :
i = 0
d i i s i o n = a l s e
wh il e i < s and d i i s i o n == F a l s e :
i G[ i ] . l ( ) . d i i d e s ( p . l ( ) ) :
Q[ i ] = Q[ i ] + p . l ( ) / / G[ i ] . l ( )
p = p − ( p . l ( ) / / G[ i ] . l ( ) ) *G[ i ]
d i i s i o n = T ue
else :
i=i+1
i d i i s i o n == F a l s e :
= + p . l ( )
p = p − p . l ( )
e u n Q, A( )
•S-polinomio.
- Las a iables de en ada son ( ,g,A)donde ygson dos polinomios y Aes un anillo de
polinomios.
- La a iable de salida es s, co espondien e al S-polinomio buscado.
d e S_ po li no mio ( , g , A ) :
a = A( ) . lm ( )
b = A( g ) . lm ( )
27
28 Capí ulo A. Códigos SageMa h
c = lcm ( a , b )
s = A( ( c / a )* −( c / b ) *g )
e u n s
•Algo i mo de Buchbe ge .
- Las a iables de en ada son (F,A)donde Fes una lis a de polinomios y Aes un anillo de
polinomios.
- La a iable de salida es G, la cual es una lis a de polinomios (es os polinomios son los que
o man la base de G öbne ).
d e Buch ( F , A ) :
n= l e n ( F )
G=F
o i i n [ 0 . . n − 2 ] :
o j i n [ i + 1 . . n − 1 ] :
s= S_polinomio (G[ i ] ,G[ j ] ,A)
d= d i ( s , G,A) [ 1 ]
i d ! = 0 :
e u n Buch ( F+[ d ] ,A)
e u n G
•Resolución del p oblema del colo eado.
- Las a iables de en ada son (G,k)donde Ges un g a o y kes el núme o de colo es.
- Las a iables de salida son ( +g,A)donde +qson las ecuaciones de nues o sis ema y
Aes el anillo de polinomios.
de s i s e m a (G, k ) :
n = G. num_ e s ( )
xs = l i s ( a ( ’ x_ % d ’ % i ) o i i n a ng e ( n ) )
F = QQ
A = Polyn omi alR ing ( F , xs , o d e = ’ lex ’ )
c o l o e s = a n g e ( k )
= [ ]
o j i n xs :
= + [A( p od ( [ ( j − i ) o i i n c o l o e s ] ) ) ]
g = [ ]
a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n G. edges ( ) ]
o j i n a i s a s :
1 = [A( p od ( [ ( xs [ j [ 0] ] − i ) o i i n c o l o e s ] ) ) ,
A( p od ( [ ( xs [ j [ 1] ] − i ) o i i n c o l o e s ] ) ) ]
g = g + [A( ( 1 [0] − 1 [ 1 ] ) / ( xs [ j [ 0] ] − xs [ j [ 1 ] ] ) ) ]
e u n + g , A
Obse ación 2. Pa a de ini el anillo de polinomios en el que que emos abaja , se puede especi-
ica cualquie a de los ó denes monomiales explicados en el Capí ulo 2, simplemen e esc ibiendo
lo siguien e:
◦O den lexicog á ico: o de = ’lex’
◦O den lexicog á ico g aduado: o de = ’deglex’
◦O den lexicog á ico g aduado in e so: o de = ’deg e lex’
Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 29
•C eación de un able o Sudoku, de amaño n×n, sin pis as.
Pa a ello, se han enido que c ea dos unciones. P e iamen e es con enien e explica que a amos
el Sudoku como si ue a una ma iz, de modo que la celda xkco esponde al elemen o (i,j)con
i,j=0,...,n2−1. Po ejemplo, en un Sudoku 9 ×9 la celda x13 co esponde al elemen o (1,4).
1. A a és de es a unción cada celda del Sudoku se con ie e en un elemen o ma icial de la
o ma (i,j).
- Las a iables de en ada son (i,j,n)donde ico esponde al p ime elemen o del pa
(i,j),jco esponde al segundo elemen o del pa (i,j)ynhace e e encia al amaño.
- La a iable de salida es el subíndice de la celda xk.
# Pa a un Sudoku 9x9 , s e oma n=3
de c o n e i ( i , j , n ) :
e u n ZZ( i *n+ j )
2. Median e es a unción imponemos las elaciones de adyacencia, de modo que no se epi an
los dígi os en ninguna de las egiones.
- La a iable de en ada es nque hace e e encia an o al núme o de ilas como al núme o
de columnas.
- La a iable de salida es la lis a de odas las a is as Ecumpliendo las elaciones impues-
as.
# Pa a un Sudoku 9x9 , s e oma n=9
de eqs_sudoku ( n ) :
R = I n e g e s ( 3 )
E = [ ]
# P a es ( i , j ) ( i , k ) a l e s que x_ ( i , j ) y x_ ( i , k ) p e e n e c e n
a l a misma i l a
# P a es ( j , i ) ( k , i ) a l e s que x_ ( j , i ) y x_ ( k , i ) p e e n e c e n
a l a misma i l a
o i i n a ng e ( n ^ 2 ) :
o j i n a ng e ( n ^ 2 ) :
o k i n [ j + 1 . . n ^2 −1]:
a= c o n e i ( i , j , n ^2)
b= c o n e i ( i , k , n ^2)
i ( no [ a , b ] i n E) and ( no [ b , a ] i n E ) :
E = [ [ a , b ] ] + E
a= c o n e i ( j , i , n ^2)
b= c o n e i ( k , i , n ^2)
i ( no [ a , b ] i n E) and ( no [ b , a ] i n E ) :
E = [ [ a , b ] ] + E
# P a e s ( i 1 *i2 , j 1 *j 2 ) ( i 1 *i3 , j 1 *j 3 ) a l e s que
x_ ( i 1 *i2 , j 1 *j 2 ) y x_ ( i 1 *i3 , j 1 *j3) pe enecen
a l mismo bloq ue n x n
o i 1 i n an ge ( n ) :
o j 1 i n an ge ( n ) :
o i 2 i n an ge ( n ) :
o j 2 i n an ge ( n ) :
o i 3 i n an ge ( n ) :
o j 3 i n an ge ( n ) :
a=con e i (i1*n+ i2 , j 1 *n+ j2 , n ^2 )

30 Capí ulo A. Códigos SageMa h
b=con e i (i1*n+ i3 , j 1 *n+j3 , n ^2)
i a <b and ( n o [ a , b ] i n E) and
( n o [ b , a ] i n E ) :
E=E + [ [ a , b ] ]
e u n E
Obse ación 3. Si quisié amos esol e un Sudoku de amaño 9 ×9 con pis as iniciales dadas end ía-
mos que segui los siguien es pasos:
◦P ime o, aplica el código c eado pa a la esolución del p oblema del colo eado pe o cambiando
alguno de los da os.
de s i s e m a (G, k ) −−−−−> de s i s e m a ( E , k )
n = G. num_ e s ( ) −−−−−> n = 81
a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n G. edges ( ) ] −−−−−>
a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n E]
Siendo E la lis a de odas las a is as ob enida an e io men e.
◦Una ez hayado el sis ema, conside amos el ideal gene ado po las soluciones del sis ema.
◦Conside amos ambién el ideal gene ado po los polinomios esul an es de las pis as dadas.
◦Po úl imo sumamos ambos ideales y ob enemos su base de G öbne co espondien e u ilizando
la unción I.g oebne _basis().
Bibliog a ía
[1] W. W. Adams and P. Lous aunau. An in oduc ion o G öbne bases, olume 3 o G adua e S udies
in Ma hema ics. Ame ican Ma hema ical Socie y, P o idence, RI, 1994.
[2] D. A. Baye . The di ision algo i hm and he Hilbe scheme. P oQues LLC, Ann A bo , MI,
1982. Thesis (Ph.D.)–Ha a d Uni e si y.
[3] A. Bece a Tomé, J. Núñez Valdés, and J. M. Pe ea González. ¿Cuán a Ma emá ica hay en los
sudokus? Pensamien o Ma emá ico, 6(1):113–136, 2016.
[4] S. Benne . Applica ions o G öbne bases. 2008.
[5] D. A. Cox, J. Li le, and D. O’Shea. Ideals, a ie ies, and algo i hms. Unde g adua e Tex s in
Ma hema ics. Sp inge , Cham, ou h edi ion, 2015. An in oduc ion o compu a ional algeb aic
geome y and commu a i e algeb a.
[6] Wol am Decke , Ge -Ma in G euel, Ge ha d P is e , and Hans Schönemann. SINGULAR 4-2-0
— A compu e algeb a sys em o polynomial compu a ions. h p://www.singula .uni-kl.
de, 2020.
[7] J. Gago-Va gas, I. Ha illo-He moso, J. Ma ín-Mo ales, and J. M. Ucha-En íquez. Sudokus and
G öbne bases: no only a di e imen o. In Compu e algeb a in scien i ic compu ing, olume 4194
o Lec u e No es in Compu . Sci., pages 155–165. Sp inge , Be lin, 2006.
[8] M.R. Gonzalez-Do ego. Resolu ion o sudokus using G oebne basis. Compu e ools in educa-
ion, (3):5–21, 2018.
[9] G.-M. G euel and G. P is e . ASingula in oduc ion o commu a i e algeb a. Sp inge , Be -
lin, ex ended edi ion, 2008. Wi h con ibu ions by Ola Bachmann, Ch is oph Lossen and Hans
Schönemann, Wi h 1 CD-ROM (Windows, Macin osh and UNIX).
[10] Sage De elope s. SageMa h, he Sage Ma hema ics So wa e Sys em (Ve sion 9.2.0).
h ps://www.sagema h.o g.
[11] J. Suá ez Que o. Las ma emá icas en el sudoku. Uni e sidad de Alme ía, Sep iemb e 2017.
31