Edukira salto egin | Salto egin nabigazioara

Tresna pertsonalak

Eibarko peoria, San Blasa baino hobia
Hemen zaude: Hasiera / Blogak / e-gorblog / Sudokuak ebazteko programa

Sudokuak ebazteko programa

e-gor 2021/03/29 20:46
Konponbidea duen edozein Sudoku (ustez) ebazteko gai den Python programa bat egin dut, erronka pertsonal txiki gisa, eta libre jarri GitHub-en

Onartu behar dut, jokoekin arazo bat dut. Kontuz, ez JOKOArekin, hau da, ez dirua jokatzen den zorizko jokoekin. Trebetasunezko jokoekin zein burua haustekoekin dut arazoa, bideo-joko zein mahaigaineko izan: behin probatuta, sarri katigatuta geratzen naiz, eta ez dut bakerik amaitzea lortu arte edo, denbora asko eman eta gero, amore eman arte. Bideo-jokoei dagokienez, haurretan Game & Watch makinatxoekin (bereziki Robot Maker) ibiltzen nintzen, nerabezaroan Sinclair ZX Spectrumeko jokoekin (Knight Lore, Manic Miner, Skool Daze, Highway Encounter edo Everyone's a Wally bezalakoekin), gaztetan PCtako lehenengotako jokoekin (Prince of Persia, Pitfall: The Mayan Adventure edo Monkey Island 2: LeChuck's Revenge adibidez). Horietako guztietako hainbat amaitu nituen (zenbaitetan aldizkarietako gidak edo tranpak baliatuta, dena esan behar bada). Eta heldutan eta nahiko berriki eta oso fuerte, semeei jarritako Wii-aren Dolphin emulagailuan joko batzuekin ere gertatu zait: Prince of Persia: Rival Swords, Prince of Persia: The Forgotten Sands eta Donkey Kong Country Returns bideo-jokoekin jo eta fuego aritu nintzen istorio osoa bukatu arte, eta Mario Kart Wii-n ere obsesionatuta egon nintzen pertsonaia eta kotxe guztiak askatu arte, zilindrada denetan (ispilua barne) eta zirkuitu guztietan urrezko kopa eta hiru izar eskuratu arte eta erlojuaren kontrakoak gainditu arte. Buruhauste jokoei dagokienez, haurretan maisuaren gurutzea eta puzzle lerrakorrak ebatzi nituen, eta Rubiken kuboa alde bat eta koroa bat (edo bi, ez nago ziur) egitea lortu nuen, eta kubo osoa egiten ikasi, jarraibideak jarraituta. Heldutan, haurrentzat erositako Rush Hour eta IQ Puzzler Pro-rekin tematuta aritu nintzen, ez dakit maila guztiak baina bai gehienak lortu artean. Tira, jokoekin arazoa izatearena esajerazioa da, joko batekin horrela tematzean, egunak edo asteak eman ditzaket orduak sartzen amaitu edo errenditu arte, bai, baina gero hilabeteak eta urteak ematen ditut beste bat probatu gabe. Baina semeek joko berri bat ongi dagoela eta probatu beharko nukeela esaten didatenean, gehienetan nahiago dut ez probatu, ezagutzen dudalako nire burua... ;-)

2005etik aurrera Sudoku jokoa mendebaldean hedatzen eta paperezko hedabideetan agertzen hasiz geroztik, batzuetan jokatu izan dut, bai egunkari eta aldizkarietan, bai ordenagailuan edo telefonoan, baina grina berezirik gabe. Errazak edo ertainak direnak erraz ebazten nituen teknika sinple batzuekin, eta zailak saiatu bai baina konplikatuak zirela ikusi eta utzi egiten nituen. Duela gutxi arte. Halako batean, ordenagailuko Linux sistemak instalatuta dakarren Sudoku programan partidatxo erraz batzuk jokatzen hasi, gero ertainetara pasatu, eta konturatu orduko zailak edo oso zailak ebazten saiatzen nenbilen...

Errazak eta ertainak teknika sinple batzuk aplikatuta egin daitezke, aukerak bilatze hutsarekin. Baina zailentzat ez dago teknika sinplerik apuntatzen-eta ibili beharrik gabekorik, edo nik behintzat ez dakit edo ez naiz gai buruan dena gordetzeko. Baina papera eta lapitzaren laguntzarekin zailentzako ustez funtzionatu zezakeen metodo bat garatu nuen: lauki bakoitzarentzako aukera posible guztiak apuntatzen nituen, hor ikusi lerro, zutabe edo 3x3ko koadroren batean aukera bakarrik gelditzen zen... eta aukera bakarrik ez zegoenetan, aukera posibleetako bat hautatu eta hortik jarraitu, baina irteerarik gabeko aukera bat aurkituz gero, azken hautaketa punturaino atzera egin behar eta beste bide bat probatu...

Kontua da aipatutako metodo hori aplikatzea konplexua dela, kalkulu eta konbinaketa asko egin behar dira, bide asko probatu batzuetan, eta akatsak egiteko aukerak handiak dira. Orduan, oso gutxitan lortzen nuen bukatzea. Baina zalantza nuen ea metodoak balio ez zuelako edo kalkuluren batean okertzen nintzelako ote zen.

Eta zerbaitetan badira onak ordenagailuak, kalkuluak egiten eta konbinazioak azkar probatzen da. Eta zerbaitetarako naiz informatikaria, ezta? Bada, pentsatutako metodoa inplementatzen zuen programa bat idatzi nuen. Konprobatu nuen metodoak funtzionatzen zuela sudoku erraz, ertain eta zailekin, baina oso zailekin ez beti; bide bat hautatu behar zuenean ausaz hartzen duen bidearen arabera, batzuetan bai eta beste batzuetan ez. Baina programari esker metodoaren akats edo hutsunea aurkitu ahal izan nuen eta konpondu.

Sudoku ebazlea Python programa bat da eta GitHub-en jarri dut GPL lizentzia librearekin. Ustez, konponbidea duen edozein sudoku ebazteko gai da eta esaten badu ezin duela ebatzi, ebazpenik ez duelako da, baina ezin dut ziurtatu. Ordenagailuko sudoku jokoetan planteatzen diren hainbat sudokurekin eta zailtasun maila ezberdinekin probatu dut, eta beti ebatzi ditu. Ebazpenik ez dutela ziur dakidan kasuetan, ebazpenik ez dutela esan du. Sudokuak ebazpen bat baino gehiago badu, bat eman eta gelditu egiten da. Hurrengo exekuzio batean beste ezberdin bat eman dezake.

Exekutatzeko hainbat aukera daude. Aurrez definituta dakartzan sudokuetako bat ebaztea eska diezaiokegu (erraz, ertain, zail eta oso zail batzuk, hutsa, ebazpenik ez duen bat, ebazpen anitz duen bat...) edo guk sartuko dizkiogu ebatzi nahi dugun sudokuaren balioak. Azken emaitza soilik erakusteko esan diezaiokegu edo bideko pauso guztiak, une bakoitzeko aukeren egoerarekin (aukeretan lauki bakoitzerako dauden aukera posibleak erakutsiko ditu; hautatuko den aukera bakarra bada berdez markatuko du, hainbat badaude hartutakoa horiz markatuko du, eta uneren baten irteerarik gabeko bide batera iristen bada gorriz markatuko du, hautaketa bat egindako azken egoerara itzuliz eta beste hautu bat eginez). Eta pauso bakoitzaren amaieran guk tekla bat sakatu arte itxoiteko ere hauta dezakegu, edo ez.

Beraz, Sudoku jokoarekin ere izan dudan mailaz maila ebaztea lortzeko konpultsioa gainditu dut, metodo bat garatu eta programa bat eginda. Ez da beste munduko lorpenik, ziur sudokuak ebazteko milaka programa badaudela Interneten. Erronka pertsonal txiki bat, eta lortu izanaren gogobetetze eta harrotasun sentsazio xume bat besterik ez. Baina aizu, zertarako izan blog pertsonal bat horrelako gauzak kontatzeko ez bada? ;-)

Amatiño
Amatiño dio:
2021/03/30 14:39
Ez zaizu arrazoirik falta. Eta, segurutik, informatikaria izan behar ebazteko sistema aurkitu ahal izateko. Zorionak.

Nik zahartzaroan egin beharreko ariketen disziplinaz baino ez bada ere, egunero egiten dut bat edo beste. Eta, normalean, denak amaitu ohi ditut. Aukerarik aukeraz, jakina. Seguru, gero, nire eskuetara iristen direnak ez direla merkatuko zailenak, baina, behar bada, ezta, batez beste, errazenak ere. Alzheimer-Citak hirugarren adinekooi jarri ohi dizkigunak, behintzat, nabarmen errazagoak dira.

Sarri pentsatu izan dut nork arraiok egiten ote dituen sudokuak ze, gero ebatzi ahal izateko, bidea egin ahal izateko, aurretik norbaitek (edo zerbaitek?) jakin behar izango du bide guztia atzekoz aurrera burutzen, ezta?

Zurea irakurri ostean, hona galdera: sudokuak nola prestatzen edo asmatzen dira?
e-gor
e-gor dio:
2021/03/30 15:34
Ba egia esan ez dakit nola sortzen diren... Eta ez dut asmorik metodo posible bat pentsatzen hasteko eta gero programatzeko! (momentuz ;-)
Iruzkina gehitu

Erantzuna formulario hau betez utzi dezakezu. Formatua testu arruntarena da. Web eta e-posta helbideak automatikoki klikagarri agertuko dira.

Galdera: Idatzi zortzi zenbakiak erabiliz
Erantzuna:
e-gorblog

e-gorblog

Egunez, Igor Leturia Azkarate pertsona arrunta da. Errenterian bizi den arrasatearra, 8etatik 17etara Elhuyarren lan egiten du eta arratsaldeak neskalagunarekin eta bere bi umeekin pasatzen ditu.

Baina gaua iritsi eta umeak lotara joaten direnean, e-gor bihurtzen da, interneteko bere alter-egoa, ziberespazioko informatikaririk komikizaleena eta komikizalerik informatikariena! Bere superbotereekin (interneteko kable-konexioa, bloglines, informatika aldizkariak, gadget-ak, komiki-bilduma, Errenteriko liburutegiko komikien atala eta batez ere bere jakinmin aseezina) eta bere superlaguntzaileak ondoan dituela (Patxi Lurra, DabilenHarria...), euskaldunon teknofobiaren eta komikiei buruzko aurreiritzien aurka burrukatzen du etengabe! Hemen duzu bere bloga: e-gorblog!

Bai, hor goiko aurkezpena superheroi batena da (ezin aproposagoa honelako blog batentzat, ezta?). Superheroia banintz zein izango nintzatekeen jakiteko the Superhero Personality Test egin nuen eta hona emaitzak:

You are Spider-Man
You are intelligent, witty, a bit geeky and have great power and responsibility.

Spider-Man
80%
Superman
70%
Green Lantern
65%
Robin
65%
The Flash
60%
Supergirl
55%
Hulk
55%
Iron Man
45%
Wonder Woman
35%
Catwoman
25%
Batman
0%
Lizentzia

Creative Commons-en baimena
Blog honetako edukia, Igor Leturiak eta beste kolaboratzaile batzuek egiten dutena, Creative Commons Aitortu-PartekatuBerdin 3.0 Unported baimen baten mende dago (irudiak salbu).

Harpidetza
Erantzunen harpidetza
Artxiboa
2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024
Artikulu aipagarriak

MythTV sorta
2004/11

"Pololoak" sorta
2004/11-12 - 2006/10-12 - 2007/02-03

Monoblogoa
2005/01/11

"Persepolis", xalotasunaren sakontasuna
2005/01/25

Elgetako Blogs&Beers 2005: nire inpresioa eta moblogging kontuak
2005/04/18

Firefox eta bere plugin zoragarriak
2005/05/11

"El País"-en komiki bilduma
2005/05/15

Euskarazko bi blog berri (bai, beste bi, baina hauek bereziak dira!)
2005/05/25

"Watchmen" sorta
2005/09-11 - 2006/10 - 2007/10 - 2008/07

"La cárcel de papel"-eko "Mis tebeos favoritos" saila I: 1etik 20ra
2005/11/08

"Goienkaria"-n agertu naiz
2005/12/08

Komikiak eta euskal rock-a
2005/12/14

Ruben Arozena "Ruben" komikigilea hil da
2006/01/02

Zope-rako DTML Calendar Tag produktua, euskaraz
2006/02/01

"Joyas Literarias Juveniles" bilduma, osorik eMule-n
2006/08/05

Argazkigintza eta DRM-a
2006/10/09

Paul Auster eta Euskararen Herria
2006/10/29

Angoulême sorta
2007/01-02

Gaur duela 25 urte nire bizitza aldatu zen
2007/04/23

Hergé-ren defentsan
2007/05/22

Ubuntu-ren bertsio berria, hobekuntza askorekin
2007/07/02

OLPC sorta
2007/12 - 2008/01

Guillermo Zubiaga, Marvel-eko komikilari euskalduna
2008/02/05

Asus EEE PC, ordenagailu txiki eta merkeen hurrengo sorta
2008/03/11

Agur, Ipurbeltz, agur... :-(
2008/08/04

"Café Budapest", gizatasuna eta bizikidetzaren aldeko aldarria
2008/08/25

"Arturo Erregea" serie mitikoa, Euskal Encodings-en! (beste askorekin batera)
2008/09/17

"Gazteak", beste serie mitiko bat euskaraz eskuragai!
2008/10/14

Pottokiek 50 urte!
2008/10/22

Europan ere OLPC-ren XO ordenagailuak erosteko aukera!
2008/11/12

Microsoft-en web zerbitzuetako gehienak, euskaraz!
2008/12/04

"Heroes"-en 2. denboraldia: ETB kirtenkeria errepikatzera, eta Euskal Encodings konpontzera
2009/01/23

I. Euskal OLPC Party-a, apirilaren 23an Donostiako Doka kafe antzokian
2009/04/16

Elkarrizketa egin didate 7K-n
2009/06/03

Azpiriren Spectrum-entzako jokoen azalak liburu batean
2009/10/06

Asterix, heroi garaitua
2009/10/29

"Ihes ederra", euskarazko komikigintzaren heldutasunaren konfirmazioa
2009/11/13

Pololoak 3: The making of
2009/11/22

5 urte 5!
2009/12/15

Nobela grafikoa, komikien prestigiorako ala mespretxurako?
2009/12/20

"Pololoak 3 - Atxeritoko balada", trilogiaren amaiera borobila
2010/01/13

Sinclair ZX Spectrum bat oparitu didate!
2010/01/19

Zergatik ez dudan liburu elektronikorik erosiko (gauzak aldatzen ez diren artean)
2010/01/27

Errealitate areagotua: munduaren pertzepzioa aberasten
2010/02/09

e-gorblog, "Nick dut nik" telebista saioan
2010/05/20

Sarearen neutraltasunari erasoak: Interneten izaera arriskuan
2010/06/02

"Avatar, azken aire maisua" osoa eta "Heroiak"-en lehen bi denboraldiak, Euskal Encodings-en
2010/07/22

Sistema eragileen guda berria
2010/12/14

Anubis 3.0 albumarentzat 3D animazio ederra
2010/12/27

Telebistaren benetako iraultza hemen da, eta ez da LTDa
2011/01/10

"Asterix galiarra" eta "Urrezko igitaia" berrargitaratu ditu Salvatek
2011/01/13

Euskarazko komikigintza digitalizazioaren aurrean
2011/01/27

"Ihes ederra"ren gaztelaniazko eta katalanezko bertsioak eta "Alokairuan", kalean
2011/02/20

Star Wars jatorrizko trilogia, euskaraz
2011/03/21

Sare sozialetan preso
2011/04/06

Zer dudan Steve Jobsen, edo Appleren, aurka
2011/10/14

Gaur 100 urte Adèle Blanc-Sec-en abenturak hasi zirela
2011/11/04

Euskarazko 8 komiki berri
2011/12/02

Social networks killed the RSS star?
2012/06/10