Sudoku

Dobrý večer,
potreboval by som algoritmus (slovný návod, nie program) ako to mám spraviť, aby to fungovalo a doplnilo celé pole...
... viem, že to má kontrolovať či sa už nenachádza to číslo v stĺpci, riadku a tom štvorci... ale to podľa mňa nestačí, stačí?

vďaka za všetky odpovede !

no podla toho aky pristup chces zvolit. ak chces zvolit brute force tak to uplne staci.

V niektorých prípadoch sa stane, že nejaké číslo už môže byť iba v konkrétnom riadku/stĺpci (ak tam nepridáš aj takúto kontrolu, tak veľa hracích polí sa ti nepodarí vyriešiť).
Keď tam zapracuješ aj takú kontrolu, tak nájdeš niektoré čísla, ktoré by si iba kontrolou v riadku, stĺpci a štvorci nenašiel (na tom obrázku je to tá žltá jednotka).

chrono: tie tri podmienky ktore napisal mu musia stacit. samozrejme zlozitost toho algoritmu bude velmi velka

Nestačia.

Robil som taký program a nedokázal vyriešiť všetky hracie polia. Ale viem, na čo myslíš ty. Okrem toho, čo navrhujem ja tam bude asi potrebné pridať aj to riešenie hrubou silou, lebo v niektorých prípadoch sa hracie pole nevyrieši ani s pridaním toho "môjho" rozšírenia. Ale pridávanie "náhodných" čísel by sa robilo až v prípade, že by ostatné spôsoby zlyhali (ale je pravda, že algoritmus by to nezjednušilo, iba by to skrátilo dobu výpočtu).

V tom mojom programe som zrušil tú prídavnú kontrolu a hneď prvé hracie pole, čo som skúšal, sa nevyriešilo (nemám tam pridané to riešenie hrubou silou).

chces povedat ze keby som pouzil len tieto tri podmienky a nasledne postupne generovanie moznych rieseni tak by som na to neprisiel?

Nie. Chcem povedať, že keby si použil iba tie tri podmienky (bez toho skúšania hrubou silou), tak by si to nenašiel. Len tie tri podmienky na úspešné vyriešenie nestačia. Treba niečo navyše (napr. v tvojom prípade to generovanie všetkých možností).

jaj no jasne ze bez brute force su tie tri podmienky nedostatocne. tak sa da vyriesit len zlomok.

xivo · Príspevok od používateľa **xivo** » 05 nov 2007, 15:51

No ja len ze sme to v skole riesili a ako tu pisete robili sme to backtrackingom - vlstne je to brute force takze ked si das do googlu sudoku - backtracking tak nemas problem

mastermind napísal:no podla toho aky pristup chces zvolit. ak chces zvolit brute force tak to uplne staci.

čo je konkrétne to brute force?... dosadzovanie čísiel, kam sa mi zapáči?
musí mať aj to nejaké podmienky...
a inak spravil som program len čisto s tými tromi základnými kontrolami a nevyriešilo to nič:D skúšal som síce len dve polia, ale aj tak... nula bodov:)

beluský napísal:čo je konkrétne to brute force?... dosadzovanie čísiel, kam sa mi zapáči?
musí mať aj to nejaké podmienky...
a inak spravil som program len čisto s tými tromi základnými kontrolami a nevyriešilo to nič:D skúšal som síce len dve polia, ale aj tak... nula bodov:)

no ano kam sa ti zapaci, ale nie uplne nahodne. brute force je o skuseni vsetkych moznosti. teda treba zvolit sposob ktory vygeneruje postupne vsetky moznosti. SYSTEMATICKY

chrono napísal:V niektorých prípadoch sa stane, že nejaké číslo už môže byť iba v konkrétnom riadku/stĺpci (ak tam nepridáš aj takúto kontrolu, tak veľa hracích polí sa ti nepodarí vyriešiť)....

nechápem akú kontrolu máš na mysli... môžeš dať príklad?:)

Príklad tam už je. Skús sa zamyslieť nad tým, ako sa prišlo na tú žltú jednotku.

http://www.hojko.com/post717362.html#717362

chrono napísal:Príklad tam už je. Skús sa zamyslieť nad tým, ako sa prišlo na tú žltú jednotku.
http://www.hojko.com/post717362.html#717362

hútam hútam... hm.. .hádam dačo vymyslím, dík

chrono napísal:->

to je backtracking?

... lebo v škole nám povedali, že backtracking nie je najlepším riešením a neodporúčajú nám to tak robiť...

...vie niekto iný spôsob pls?...

backtracking je prave skusanie vsetkych alternativ. keby ze mas pouzit backtracking tak pouzi prolog. program na par riadkov

mastermind napísal:backtracking je prave skusanie vsetkych alternativ. keby ze mas pouzit backtracking tak pouzi prolog. program na par riadkov

musí byť v C

beluský napísal:to je backtracking?

... lebo v škole nám povedali, že backtracking nie je najlepším riešením a neodporúčajú nám to tak robiť...

...vie niekto iný spôsob pls?...

Nie je. Funguje to tak, že ak sa nájde nejaké číslo, ktoré môže byť iba v niektorom stĺpci/riadku bunky (aj keď nepoznáme jeho presnú polohu), ovplyvní ostatné bunky.

diky zas prispevky... vyriešil som to brute force -om... len ked algoritmus skonci vypise sa program prestal pracovat... a neviem kde by mohla byt chyba... ked si dam to sudoku vypisat (je to posledny prikaz), tak vypise vsetko okrem posledneho prvku

pise mi takuto chybu ked dam ladit a otvori mi to v builder c++

ntdll.RtlSetLastWin32Error:
772E2EAF mov edi, edi

ja viem, ze to je malovravne, ale... tak mozno sa najde nejaky expert:)