Lankide:GorkaIoritz/Zortzi erreginen problema

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Zortzi erreginen problemarako soluzio posible bat 8x8 taula batean.

Zortzi erreginen problema 8×8 xake-taula batean zortzi erregina jartzean eta erreginak bata bestearen artean ez mehatxatzean datzan problema da. Hori gerta dadin, bi erreginak ezin dute lerro, zutabe edo diagonal bera partekatu. Soluzio posible guztiak 92 dira, baina oinarrizko soluzioak soilik 12 dira gainerakoak soluzio baliokideak baitira. Arazoa XIX. mendearen erdialdean planteatu zen lehen aldiz eta aro modernoan problema hau sarritan adibidetzat erabiltzen da programazio informatikoko teknika batzuetarako.

Zortzi erreginen problema n erreginen problema orokorrenaren kasu berezi bat da non n erregin ipintzen diren euren artean erasotzen ez direnak n×n taula batean. n zenbaki arrunt guztietarako soluzioak daude, n=2 eta n=3 kasuetan izan ezik. Soluzio kopuru zehatza n ≤ 27 denean soilik ezagutzen den arren, soluzio-kopuruaren hazkunde asintotikoaren tasa (0.143 n)ⁿ da gutxi gorabehera.

Historia

Max Bezzel xake-konpositorea izan zen zortzi erreginen problema argitaratzen lehena 1848an. Franz Nauck-ek 1850ean argitaratu zituen lehen soluzioak eta n erreginen arazora zabaldu zuen problema n×n karratuko xake-taula batentzako.

Harrezkero, matematikari askok, Carl Friedrich Gauss-ek barne, zortzi erreginen probleman eta n erreginen bertsio orokorrean lan egin dute. 1874an, S. Guntherrek metodo bat proposatu zuen, determinatzaileak erabiliz soluzioak aurkitzeko. J.W.L. Glaisherrek Guntherren ikuspegia findu zuen.

1972an, Edsger Dijkstrak problema hau erabili zuen programazio egituratua deitu zuenaren indarra ilustratzeko. Backtraking algoritmoaren garapenaren deskribapen oso zehatza argitaratu zuen Sakonera-bilaketa izenekoa.

Soluzioak eraikitzen eta zenbatzen, n = 8 denean

Zortzi erreginen problemarako irtenbide guztiak aurkitzea arazo nahiko garestia izan daiteke konputazionalki, izan ere, 8x8 taula batentzako zortzi erreginekin 4.426.165.368 konbinaketa egin daitezke 92 soluzio baino ez dauden arren. Baldintza konputazionalak murrizten dituzten lasterbideak edo indar gordin konputazionaleko teknikak saihesten dituzten arau praktikoak erabil daitezke. Adibidez, zutabe bakoitzeko erregina bat aukeratzen duen erregela sinple bat aplikatuz, aukera-kopurua 16.777.216 (hau da, 8⁸) konbinaziotara murriztu daiteke. Permutazioak sortzeak are gehiago murrizten ditu aukerak 40,320 (hau da, 8! ) aukera posibletara eta aurrerago eraso diagonalik badagoen egiazta daiteke.

Zortzi erreginen problemak 92 irtenbide ditu. Taula errotatzeko eta islatzeko simetria-eragiketengatik bakarrik bereizten diren soluzioak bat balira bezala kontatzen badira, problemak 12 irtenbide ditu. Soluzio hauei oinarrizko soluzio deitzen zaie eta beherago aurkezten dira.

Oinarrizko soluzio batek zortzi aldaera ditu (jatorrizko forma barne), 90°, 180° edo 270° biratuz lortuak, eta ondoren, lau aldaera hauetako bakoitza ispilu bat erabiliko bagenu bezala islatuz. Hala ere, funtsezko 12 irtenbideetako bat (12 soluzioa beheran) 180º-ko bere errotazioaren berdina da, eta ondorioz lau aldaera besterik ez ditu (bere burua, bere islapena, 90º-ko errotatuta eta honen islapena). Soluzio horiek bi aldaera baino ez dituzte (haien burua eta haien isla). Horrela, soluzio desberdinen guztizko kopurua 11 x 8 + 1 x 4 = 92 da.

Hona hemen oinarrizko soluzio guztiak:

10. Soluzioaren propietate gehigarria da ez daudela lerro zuzenean hiru erreginik. Bestalde, 1. eta 8. soluzioek 4 erreginez osatutako lerroa dute.

Soluzioen existentzia

Ebazpen kopurua zenbatzeko indar gordia erabiltzen duten algoritmoak, konputazionalki erabil daitezke n = 8 denean, baina ezin dira tratatu n ≥ 20 den problemetan, hala nola 20! = 2,433 × 1018 baita. Helburua irtenbide bakarra aurkitzea bada, n ≥ 4 guztientzako soluzioak erakuts daitezke, inolako bilaketarik egin gabe. Soluzio horiek eredu mailakatuak erakusten dituzte, n = 8, 9 eta 10erako adibide hauetan bezala:

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 1

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 2

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 3

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 4

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 5

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 6

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 7

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 8

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 9

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 10

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 11

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Solution 12