Kommt der noch? 
µit - März
-
MatthiasG. -
15. März 2009 um 09:47
-
-
- Offizieller Beitrag
Vorschlag von Schnuffel, den ich hier mal zur Diskussion stelle:
Zitatich hätte da mal eine Idee für den µit - März.
Wie wäre es mit einem Sudoku Löse-Programm.
Man gibt in einem 9x9 großen Feld die Zahlen vor und das Programm muß vervollständigen.Vorlagen zum Testen gibt es ja überall.
gewonnen hat, wer am schnellsten und richtig löst.
Da muß man bestimmt ein wenig nachdenken ......
Bin mir über den Recheneaufwand nicht ganz im Klaren, kommentiert einfach mal ;-).
peethebee
-
Ich fänds cool. Endlich mal was, wo ich zumindest einen Ansatz hätte
-
- Offizieller Beitrag
Rechenaufwand kenne ich auch nicht, aber von der Idee her eine interessante Aufgabe.
Und da wir ja mittlerweile Mitte März haben, könnte man die Aufgabe ja auf 2 Monate (+April) ausdehnen. -
Diese Aufgabe gefällt mir!
Wenn mir nicht die Zeit ausgeht, dann bin ich dabei. Der Rechenaufwand glaube ich hält sich in Grenzen, ich kann mich aber auch täuschen. -
Hmm... Ich glaube, ich muss dazu noch mal die Hilfe öfters wälzen
-
Hi,
gefällt mir :).Der Rechenaufwand vom Lösen eines 9x9 Sudokus ist nicht sonderlich groß.
Wir haben das mal in Info (Delphi) Programmiert, die Laufzeit konnte man nicht wirklich messen.Das gilt allerdings nicht mehr, wenn die Lösung nicht mehr eindeutig ist, dann wird der Rechenaufwand sehr viel größer!
-
Aber da ein "gültiges" Sudoku immer nur eine lösung hat -
-
Hab mal ein Sudoku-Solver in C++ geschrieben. Es sollte auch möglich sein das in AutoIt umzusetzen. Wenn es meine Zeit erlaubt wäre ich dabei.
Edit: Ein Sudoku muss soweit ich mich erinnere bei einem 9x9 Feld mindestens 14 Felder vorgegeben haben, sonst ist es nicht mehr eindeutig. Dafür gibt es aber genügend Beispiele im Netz.
-
Ich hab jetzt schonmal angefangen, läuft super, kann schon einige Sudokus lösen (kann die 3x3-Kästchen-Regel noch nicht...)
Prozessortechnisch ist das kein Problem, das geht unheimlich schnell, wenn mans nicht per Ausprobieren löst...:) -
Hier mal einige Strings zum testen. (ich hoffe ich habe mich nicht verzählt)
Code000300800640800050875000001500070206000090000209080005400000769020008013007005000 - 29 050060001004800070800000052200057030000000000030690005790000008010006500500030060 - 25 000060080020000000001000000070000102500030000000000400004201000300700600000000050 - 17 000000000005010700070602090009020800060835010004070500030408020001090400000000000 - 25 060090050704050609000362000006005700982030546003600100000246000601070308050010060 - 35 007000000000010000000040005000008900400000000906007000008609000000000050030000041 - 17 530070000600195000098000060800060003400803001700020006060000280000419005000080079 - 30 100050000006009000080200004040030008007000060900000100030800002000004050000010700 - 21 000000103900050000000000800060020070001000000000300000000001460720000050000800000 - 17 -
Hallo zusammen,
ich hatte mich gar nicht getraut meinen Vorschlag öffentlich zu machen, da ich es im ersten Moment für zu einfach hielt.
Um mal einen Überblick über Strategien und mathematische Möglichkeiten zu bekommen empfehle ich die Seite:
Sudoku-Solver
ich denke wir müssen es nicht übertreiben und alle dokumentierten 35 Strategien umsetzen...
Es soll ja ein Spaß bleiben.
(Habe auch erst im Nachhinein festgestellt, dass Sudoku eigentlich schon eine mathematisch-wissenschaftliche Herausforderung ist)
Um die Regeln noch abzustecken:
gewertet wird das Erreichen der Lösung und die benötigte Zeit.
Dabei hoffe ich auf Unterstützung von peethebee
(hab mit Zeitmessung und so nicht so viel am Hut. Außerdem denke ich dass er unparteiisch messen wird.
Verwendung zur Bestimmung findet das Sudoku vom 26.04.09 von dieser Seite
Dieses wird auch erst an diesem Tag bekannt sein. Ich kenne es auch nicht
Abgabeschluß ist der 25.04.09
Na dann
Happy Coding -
- Offizieller Beitrag
Hi!
Auswerten kann ich auf jeden Fall. Mitmachen wohl eher nicht, aber mal sehen.
Ich denke, dass es wie beim BigInt sinnvoll wäre, ofiizielle Testdaten zu haben, sodass man einfach wieder eine Testsuite laufen lassen kann.
Das Format von prizma sieht mir ganz gut aus.
Hat jemand Zeit, den alten Speed-Benchmark (Größe ist diesmal nicht spannend, finde ich) entsprechend mit einigen dutzend möglichst verschiedenen Sudokus (und korrekten Lösungen!) zu füllen? Das würde eben die eigenen Tests und die (Zwischen-)Auswertung deutlich vereinfachen.Die Funktion wäre dann:
[autoit]_SolveSudoku($strSudoku)
[/autoit]mit dem gelösten Sudoku in gleichem Format als Rückgabewert
Dankeschön,
peethebee -
Diese Sodokuvorgaben sind alle lösbar.
die ersten 9 sind die obere Reihe von li. nach re, die nächsten neun die Reihe zwei von oben, usw.
Spoiler anzeigen
[autoit]
[/autoit]
000670900360005028805002100020506004009407000700100583070054261000703000084090050
628009000109056004500872001900510467807000030060020900004907103000201709091000280
076930000000108400300026000045080130010567090200310058068002005704000982020003710
120500360300009020007208004019000873403897001002350400000000087850016900200980140
906020100020050460000009730004260070700030608030871204800700041213000090490308006
007000300050908004900030060070004080102070900000500006800010000000000405060007000
060070008900104070003000500200007000008050906030900020000600010805000000000030007
000400050107000000000060003800003000001070904060900080040030001900502030006000700
004010050050900208300006000020000100000403000005000060000700005901004030070060900
500000006004902010070050900020004060900060803007100000000080200401000000000006070
009050200500000004000907000000204000100000005003010600035060720010000080074080510
700100002010070000008005300800000650006809000400300000009004000503600000000003071
200000140001209000500800000600700003070060000002004800009005000408100000000008067
000300150309001000200800000008009000100502000002000046600400007040060000005003200
003500100000010050700004008240000800000809002000700600000006009000200407015007000
000003050060004008800170000000710042040008700009005800790800000003050070004000200
000000000009040602087006010020004038040039000010008046064003050003050401000000000
000007002010000000000250108002030090006405000800090005004000609000500007607002840
000000000073080500092003070004070800708036020900000000000019650010000290000240000
060050002800000010000002600000020000500903208007010394006074000010006050200035000
004002080002000401500070060820040007060005100700000000090000023003098000000201600
000000000205980430006207009000030280040000000000090170009508006502460790000000000
000000800000640005009700004248000601060009000971000403003100008000570006000000700
000000020000008539000596080000000350051000700904700200402810000500040000086300000
000020000020000100365840070001050020840000000003060080214680030070000500000010000 -
- Offizieller Beitrag
Hast du auch die Lösungen?
Dann poste sie hier, damit jemand sie in das Benchmark einbauen kann und jeder seine Algorithmen gleich testen kann :-).Danke schon mal,
peethebee -
Die Lsg. habe ich leider nicht mehr. Weiß nur das ich die alle mal gelößt hatte.
Sorry !!! -
Hab mal alle bisher aufgeführten Strings durch meinen Solver gejagt um hier mal die Lösungen zu posten.
Ich habe die Testsuite nicht aber die Lösungen sollten uns hier mal weiterhelfen.Spoiler anzeigen
A:100050000006009000080200004040030008007000060900000100030800002000004050000010700
L:123457689456189327789263514245631978317948265968725143531876492672394851894512736A:000300800640800050875000001500070206000090000209080005400000769020008013007005000
L:192356847643817952875429631584173296761592384239684175458231769926748513317965428A:050060001004800070800000052200057030000000000030690005790000008010006500500030060
L:953762841624815973871349652289457136165283497437691285796524318318976524542138769A:000060080020000000001000000070000102500030000000000400004201000300700600000000050
L:947165283823974516651328947478596132516432879239817465764251398385749621192683754A:000000000005010700070602090009020800060835010004070500030408020001090400000000000
L:196547283285319746473682195359124867762835914814976532937458621621793458548261379A:060090050704050609000362000006005700982030546003600100000246000601070308050010060
L:368497251724158639195362874416925783982731546573684192837246915641579328259813467A:007000000000010000000040005000008900400000000906007000008609000000000050030000041
L:617985432854213796293746185321568974475391268986427513148659327762134859539872641A:530070000600195000098000060800060003400803001700020006060000280000419005000080079
L:534678912672195348198342567859761423426853791713924856961537284287419635345286179A:100050000006009000080200004040030008007000060900000100030800002000004050000010700
L:123457689456189327789263514245631978317948265968725143531876492672394851894512736A:000000103900050000000000800060020070001000000000300000000001460720000050000800000
L:584762193913458726672913845865129374231547689497386512359271468728634951146895237A:000670900360005028805002100020506004009407000700100583070054261000703000084090050
L:412678935367915428895342176128536794539487612746129583973854261251763849684291357A:628009000109056004500872001900510467807000030060020900004907103000201709091000280
L:628149375179356824543872691932518467817694532465723918284967153356281749791435286A:076930000000108400300026000045080130010567090200310058068002005704000982020003710
L:476935821952178463381426579645289137813567294297314658168792345734651982529843716A:120500360300009020007208004019000873403897001002350400000000087850016900200980140
L:128574369345169728697238514519642873463897251782351496931425687854716932276983145A:906020100020050460000009730004260070700030608030871204800700041213000090490308006
L:976423185328157469541689732184265973752934618639871254865792341213546897497318526A:007000300050908004900030060070004080102070900000500006800010000000000405060007000
L:687145392253968174914732568576394281142876953398521746835419627729683415461257839A:060070008900104070003000500200007000008050906030900020000600010805000000000030007
L:461573298952184673783296541294367185178452936536918724347625819815749362629831457A:000400050107000000000060003800003000001070904060900080040030001900502030006000700
L:623487159157329648489165273892643517531278964764951382245736891978512436316894725A:004010050050900208300006000020000100000403000005000060000700005901004030070060900
L:794812356156937248382546791429685173617423589835179462243798615961254837578361924A:500000006004902010070050900020004060900060803007100000000080200401000000000006070
L:593841726864972315172653984328594167915267843647138592736489251481725639259316478A:009050200500000004000907000000204000100000005003010600035060720010000080074080510
L:349158267587623194261947358756294831128736945493815672835461729612579483974382516A:700100002010070000008005300800000650006809000400300000009004000503600000000003071
L:765138492314972865928465317831247659256819743497356128189724536573691284642583971A:200000140001209000500800000600700003070060000002004800009005000408100000000008067
L:287356149341279658596841732614782593875963214932514876729635481468197325153428967A:000300150309001000200800000008009000100502000002000046600400007040060000005003200
L:784326159369751482251894673478639521196542738532187946623415897947268315815973264A:003500100000010050700004008240000800000809002000700600000006009000200407015007000
L:693578124824913756751624938249361875167859342538742691472136589386295417915487263A:000003050060004008800170000000710042040008700009005800790800000003050070004000200
L:421983657967524138835176429658719342142368795379245861796832514283451976514697283A:000000000009040602087006010020004038040039000010008046064003050003050401000000000
L:652981374139745682487326519926514738748639125315278946864193257293857461571462893A:000007002010000000000250108002030090006405000800090005004000609000500007607002840
L:968147532215683974473259168542831796796425381831796425124378659389564217657912843A:000000000073080500092003070004070800708036020900000000000019650010000290000240000
L:586794312473182569192653478624971835758436921931528746247819653815367294369245187A:060050002800000010000002600000020000500903208007010394006074000010006050200035000
L:469751832832649517175382649983427165541963278627518394356874921718296453294135786A:004002080002000401500070060820040007060005100700000000090000023003098000000201600
L:974162385632589471518374962821946537369725148745813296196457823253698714487231659A:000000000205980430006207009000030280040000000000090170009508006502460790000000000
L:798345612215986437436217859957631284841752963623894175179528346582463791364179528A:000000800000640005009700004248000601060009000971000403003100008000570006000000700
L:457931862132648975689725314248357691365419287971862453723196548894573126516284739A:000000020000008539000596080000000350051000700904700200402810000500040000086300000
L:895473621647128539123596487278961354351284796964735218432817965519642873786359142A:000020000020000100365840070001050020840000000003060080214680030070000500000010000
L:189527364427396158365841279691458723842173695753962481214685937978234516536719842 -
Hi,
zum Auswerten hab ich keine Ahnung wie ihr das machen wollt, aber hier mal vielleicht eine Idee (Anhang) -
Verdammt, da war ich wohl etwas zu schnell, ich hab gestern nicht mehr hier rein geguckt, und mir mein eigenes Format geschrieben.
Sieht zwar nicht so schön aus wie euer Format, aber es funzt. Mist, dann kann ich das halbe Solveprogramm nochmal neu schreiben. Dabei hat es so gut funktioniert... 
-
Also ich bin für das oben geschriebene Format, weil sich die Strings damit beliebig vergrößern/erweitern lassen.