mboost-dp1
LEGO
#3 & #4
Hvis du som person kunne foretage dig andre ting i mellem tiden som robotten ikke ville kunne og som var nødvendige, så vil det af princip altid kunne betale sig at lade robotten løse soduko. Din "ekstra"-tid vil blive brugt konstruktivt og på noget som robotten ikke ville kunne løse for dig. (Kan ikke huske navnet på teorien, men det er en mikro-økonomisk betragtning). :)
Hvis du som person kunne foretage dig andre ting i mellem tiden som robotten ikke ville kunne og som var nødvendige, så vil det af princip altid kunne betale sig at lade robotten løse soduko. Din "ekstra"-tid vil blive brugt konstruktivt og på noget som robotten ikke ville kunne løse for dig. (Kan ikke huske navnet på teorien, men det er en mikro-økonomisk betragtning). :)
Nu ved jeg ikke lige om der bliver spolet i udregningerne, men det er sjovt at den bruger laaaangt størstedelen af tiden på "fysisk" arbejde og kun 2-3 sekunder til at udregne hele pladen. Det er jo lidt omvendt af hvordan et menneske ville bruge tiden. Måske en kombination af det bedste fra begge verdener? :)
Noget med alternativ-omkostninger? Altså hver gang man vælger at lave noget, så fravælger man at lave en masse andre ting, og så skal man lige overveje om værdien af den ting man vælger at lave er større end de ting man fravælger.
ZM4573R (5) skrev:(Kan ikke huske navnet på teorien, men det er en mikro-økonomisk betragtning). :)
Noget med alternativ-omkostninger? Altså hver gang man vælger at lave noget, så fravælger man at lave en masse andre ting, og så skal man lige overveje om værdien af den ting man vælger at lave er større end de ting man fravælger.
ZM4573R (5) skrev:Hvis du som person kunne foretage dig andre ting i mellem tiden som robotten ikke ville kunne og som var nødvendige, så vil det af princip altid kunne betale sig at lade robotten løse soduko.
Eller omsat til noget de fleste af os nemt kan forholde os til: Jeg bruger flittigt både vaskemaskine og opvaskemaskine, selv om jeg selv kunne gøre det langt hurtigere manuelt.
Fx. en kogevask tager næsten to timer. Det tror jeg sagtens jeg kunne gøre i hånden på 15-30 minutter. Men hvorfor skulle jeg?
taoh rihze (11) skrev:#5 og #10
Umiddelbart vil jeg tro det i tænker på er Oppertunity Cost.
Joh, hvis man foretrækker det på engelsk :)
ZM4573R (5) skrev:#3 & #4
Hvis du som person kunne foretage dig andre ting i mellem tiden som robotten ikke ville kunne og som var nødvendige, så vil det af princip altid kunne betale sig at lade robotten løse soduko. Din "ekstra"-tid vil blive brugt konstruktivt og på noget som robotten ikke ville kunne løse for dig. (Kan ikke huske navnet på teorien, men det er en mikro-økonomisk betragtning). :)
Det er teorien om de komparative fordele, der er udtænkt af Ricardo (og selvom det er små 200 år siden, at begrebet blev beskrevet, så handler vi stadig efter det).
#10 Alternativomkostninger spiller en stor rolle i teorien, men det er ikke alene nok til at forklare begrebet.
Det var også hvad jeg tænkte. Du skal bare have et computerprogram, hvor du kan indtaste talene. Så regner den en løsning ud, du kan skrive af fra skærmen.Jace (10) skrev:Nu ved jeg ikke lige om der bliver spolet i udregningerne, men det er sjovt at den bruger laaaangt størstedelen af tiden på "fysisk" arbejde og kun 2-3 sekunder til at udregne hele pladen. Det er jo lidt omvendt af hvordan et menneske ville bruge tiden. Måske en kombination af det bedste fra begge verdener? :)
Men hvorfor skulle man dog skrive det program?
Opvask kan jeg klare i hånden. Men nu hvor jeg i ca. tre år har haft opvaskemaskine får jeg kuldegysninger ved tanken om at jeg måske engang kommer til at bo et sted, hvor jeg ikke har en opvaskemaskine.myplacedk (12) skrev:Eller omsat til noget de fleste af os nemt kan forholde os til: Jeg bruger flittigt både vaskemaskine og opvaskemaskine, selv om jeg selv kunne gøre det langt hurtigere manuelt.
Fx. en kogevask tager næsten to timer. Det tror jeg sagtens jeg kunne gøre i hånden på 15-30 minutter. Men hvorfor skulle jeg?
Når det kommer til vaskemaskine ville jeg være fortabt. Jeg ville ikke ane, hvordan jeg skulle bære mig ad med at vaske mit tøj uden?
kasperd (16) skrev:Når det kommer til vaskemaskine ville jeg være fortabt. Jeg ville ikke ane, hvordan jeg skulle bære mig ad med at vaske mit tøj uden?
Mange aner ikke engang at det er en mulighed.
Hvis man lige har én trøje eller whatever der skal vaskes, så kommer den altså ikke i maskinen, så gør man det manuelt!
(En gang biotex og varmt vand i vasken, læg i blød lidt hvis der er pletter, skrub lidt (især der hvor der er pletter), skyld grundigt, vrid eller slyng det så tørt du kan, og hæng til tørre eller stryg det evt. tørt.)
OVRKLL (4) skrev:#3
Løsningstiden for et menneske skalerer kraftigt med sværhedsgraden; det er formentligt ikke tilfældet for robotten, hvorfor det bare er et spørgsmål om at gøre det svært nok, før det kan "betale sig" at lade den gøre arbejdet.
Nej faktisk kendes der ikke nogen algoritmer som kan løse Sudoku'er i konstant tid.
#21 Hvad han mente var nok, at hvis vi blot installerer en kraftig nok processor, så vil den kunne løse Sudoku'er med brute-force-metoden væsentligt (!) hurtigere end et menneske.
Et tænkt eksempel lyder på, at en "nem" Sudoku kan måske tage 5-10 minutter, hvor en "svær" tager 1-2 timer for et givent menneske. For en computer vil forskellen måske kun være 1-2 sekunder - maksimalt!
Et tænkt eksempel lyder på, at en "nem" Sudoku kan måske tage 5-10 minutter, hvor en "svær" tager 1-2 timer for et givent menneske. For en computer vil forskellen måske kun være 1-2 sekunder - maksimalt!
Jeg tror nu godt man kan konstruere en sudoku på 9x9 felter, der tager mere end 3 CPU sekunder at løse. Men det vil selvfølgelig stadigvæk være langt hurtigere end et menneske kunne gøre det.vandfarve (22) skrev:For en computer vil forskellen måske kun være 1-2 sekunder - maksimalt!
kasperd (23) skrev:Jeg tror nu godt man kan konstruere en sudoku på 9x9 felter, der tager mere end 3 CPU sekunder at løse.
Så skal det da godt nok være en sløv CPU. Og i forhold til at denne robot bruger 5-10 minutter (?) på at scanne og skrive, så synes jeg nu ikke selv 10 sekunder er noget af betydning. Det er enda noget nær "konstant tid" i praksis.
Jeg prøvede lige at indtaste en såkaldt "svær" sudoko på min telefon, og den løste det for hurtigt til at jeg kunne tage tid. Jeg vil da gerne prøve med den sværeste du kan opstøve.
(Jeg er i øvrigt ret sikker på at det er en brute-force algoritme, så meget sløvere bliver det nok ikke på den CPU uden sjusk.)
¤6 skrev:En lille skridt for en menneske, et stort skridt for menneskehedens fremtid
En lille skridt for en menneske, et stort skridt for menneskehedens fritid
myplacedk (24) skrev:
Jeg prøvede lige at indtaste en såkaldt "svær" sudoko på min telefon, og den løste det for hurtigt til at jeg kunne tage tid.
Tror du ikke, at den havde svaret kodet ind i forvejen? (Jo)
Giver dig ellers ret, det kan virkeligt ikke tage lang tid at regne en Sudoku ud for en CPU ;)
og hvad fanden sker der, var i kvickly i går og skulle bare købe opvaskemiddel og der var sort af kinesere som skulle aflevere deres flasker måske skulle man bede dem om at aflevere deres opholdstilladelse fordi det har de helt sikker ikke og betaler caroline måske skat i danmark nææ det gør hun ikke og alligevel kommer hun tilbage når hun får børn og de skal i skole og når hun snakker med pressen i den store verden så er hun polak jamen alle de som bruger en "dansk" håndværker er indirekte skyld i at der er så mange arbejdsløse hver morgen ser jeg en mand i bussen som har et kæmpemodermærke og han passer sit arbejde hver dag ikke noget pis her har aldrig haft en sygedag det har været pjæk det hele nå men jeg gider ikke at stå i kø med alle de kinesere var der ikke noget med at de allesammen have sars eller troede i at jeg havde glemt det så noget og svineinfluenza glemmer jeg ikke bare for at i skifter navn til h2o og så går jeg i kiosken med mine flasker næste gang der er ikke nogen kinereser men kun en pakistaner med det er ok fordi det er hans butik
He he og som straf er du blevet irrelevant to gange på samme side, så kan du lære det ingen skal løbe om hjørner med mig du kan selv prøve at stå i kø i 31 minuter bare fordi kinesere som ikke har opholdstilladelse skal aflevere flasker og i aldi har de ikke engang nogen flaskeautomat og så kalder det discount og i quick fakta er der sku da altid kø søndag aften og alligevel vælger du at sætte mig som irrelevant men tilykke du har fået dig en værdig modstander men modigt at dig jeg vil sætte alle dine post som irrelevant for al evighed
Mit bud var baseret på mine oplevelser med programmer, der genererer dem. Nu hvor jeg har undersøgt det lidt nærmere fandt jeg ud af, at det program jeg engang selv skrev til det brugte 1-2 sekunder på at genererer en suduko (gnome-sudoku tager væsentligt længere tid, måske fordi det er skrevet i python).myplacedk (24) skrev:Jeg prøvede lige at indtaste en såkaldt "svær" sudoko på min telefon, og den løste det for hurtigt til at jeg kunne tage tid. Jeg vil da gerne prøve med den sværeste du kan opstøve.
Jeg prøvede så at måle på hvor lang tid mit eget program skulle bruge på at løse den, og det tog normalt 1-2 millisekunder. Det største jeg fandt var 7ms.
Så jeg tror ikke mere at jeg kan konstruere en i den størrelse, der tager i nærheden af et sekund at løse for en computer.
#29 og #24
Den sværeste sudoku skulle iflg matmatikeren selv være
http://www.usatoday.com/news/offbeat/2006-11-06-su...
Måske i lige skulle smide den ind i jeres program :-)
Jeg fandt engang et program hvor man kunne følge bruteforcen step-by-step faktisk meget underholdene og lærerigt at følge med i det - dog kan jeg ikke huske hvad programmet hed, eller hvor det fandtes
Den sværeste sudoku skulle iflg matmatikeren selv være
http://www.usatoday.com/news/offbeat/2006-11-06-su...
Måske i lige skulle smide den ind i jeres program :-)
Jeg fandt engang et program hvor man kunne følge bruteforcen step-by-step faktisk meget underholdene og lærerigt at følge med i det - dog kan jeg ikke huske hvad programmet hed, eller hvor det fandtes
Mit program tager ca. 1.5ms om at løse den. Så den jeg selv gav tidligere er sværere - i hvert fald for mit program. Når man nu er nødt til at prøve sig frem, så kan man være heldig eller uheldig med i hvilken rækkefølge man prøver sig frem, så en måling af hvor lang tid det tager er ikke nok til at vurdere sværhedsgraden.LsV (30) skrev:Den sværeste sudoku skulle iflg matmatikeren selv være
http://www.usatoday.com/news/offbeat/2006-11-06-su...
Måske i lige skulle smide den ind i jeres program :-)
Jeg har en rubiks-terning hvor der i stedet for 6 farvede sider er 6 sudokuer som alle skal løses. Når terningen er samlet korrekt skal alle tallene i hver sudoku desuden vende rigtigt. Jeg kan se at fyren har lavet både en robot der kan løse en rubiks-terning og så denne der kan løse en sudoku, så denne terning må vel være næste projekt ;).
Den skriver fanme flottere end mig!
OT* Mindstorm er helt sikkert også det fedeste legetøj som er lavet på den her planet. Har jeg brugt alt for mange timer på.
OT* Mindstorm er helt sikkert også det fedeste legetøj som er lavet på den her planet. Har jeg brugt alt for mange timer på.
En Suduko vil tage i snit ligeså lang tid at løse for en CPU hvadenten det er svær eller let. Der er stadig samme antal tal og kombinationer hvis man benytte Backtracking metoden.
Har man kastet sig ud i nogle analysemodeller kan det godt være at det giver bagslag på de svære, men det hurtigste at udvikle er Backtracking, og den vil altid ramme løsningen indenfor sammen gennemsnits tid.
http://en.wikipedia.org/wiki/Backtracking
Bruteforce er dog spild af CPU her, da man kan teste på en halvfærdig Sudoku og se om den overholder regelerne.
Har man kastet sig ud i nogle analysemodeller kan det godt være at det giver bagslag på de svære, men det hurtigste at udvikle er Backtracking, og den vil altid ramme løsningen indenfor sammen gennemsnits tid.
http://en.wikipedia.org/wiki/Backtracking
Bruteforce er dog spild af CPU her, da man kan teste på en halvfærdig Sudoku og se om den overholder regelerne.
tommyb (36) skrev:En Suduko vil tage i snit ligeså lang tid at løse for en CPU hvadenten det er svær eller let.
Jeg er ikke sikker på hvad du prøver på at sige. Men en let sudo er typisk hurtigere at løse end en svær sudoku.
Backtracking-metoden kan betragtes som en udelukkelsesmetode. Jo flere tal er der angivet i forvejen, jo færre løsninger er der at udelukke. Ergo går det hurtigere.
Men der er da lidt om det. For mennesker er der meget mere i det, end hvor mange tal der er angivet på forhånd.
Det kan du roligt gå ud fra, at samtlige programmer til at løse sudoku gør. For hvis ikke de gjorde det ville de ikke kunne nå at løse en sudoku i universets levetid. Der kan selvfølgelig være forskel på, hvor meget de checker. Men hvis de ingenting checker ville de normalt have over 50 felter at udfylde med 9 muligheder for hvert. Det giver et 48 cifret antal muligheder.tommyb (36) skrev:Bruteforce er dog spild af CPU her, da man kan teste på en halvfærdig Sudoku og se om den overholder regelerne.
Hvad jeg har gjort i mit program er at konstruere en bitmaske over hvilke tal der er mulige for hver enkelt position. Jeg prøvede lige at få mit program til at virke med 16x16 felter, men det tager væsentligt længere tid i det tilfælde. Det er faktisk endnu ikke lykkedes mig at få mit program til at generere en 16x16 sudoku, det tager simpelthen længere tid end jeg gider vente på. Måske jeg skulle prøve at udfylde felterne i rækkefølge i stedet for at udfylde dem i tilfældig rækkefølge.
#39 : Kasper, hvis du bruger bruteforce istedet for backtracking kan jeg godt forstå at dit program bliver langsomt :)
Backtracking går ud på at udelukke store grene af dit træ af muligheder, istedet for at teste ALLE kombinationer som man gør med bruteforcing.
Styrken ligger i at man jo halvejs igennem kan se om man er "på rette spor". Ved fx. et password er det altid enten-eller, man kan ikke se om første halvdel er rigtig (jaja windows 7-tegns hash) - men jo normalt ikke, så derfor skal man teste på hele strengen hvergang, ergo bruteforcing.
Edit: Har lige læst dit indlæg igen, jeg er faktisk i tvivl om du mener bruteforce eller backtracking, men vi er enige om at der er rigtig mange kombinationer :)
Backtracking går ud på at udelukke store grene af dit træ af muligheder, istedet for at teste ALLE kombinationer som man gør med bruteforcing.
Styrken ligger i at man jo halvejs igennem kan se om man er "på rette spor". Ved fx. et password er det altid enten-eller, man kan ikke se om første halvdel er rigtig (jaja windows 7-tegns hash) - men jo normalt ikke, så derfor skal man teste på hele strengen hvergang, ergo bruteforcing.
Edit: Har lige læst dit indlæg igen, jeg er faktisk i tvivl om du mener bruteforce eller backtracking, men vi er enige om at der er rigtig mange kombinationer :)
#30
Den soduko, skulle den være den sværeste for et menneske eller maskine at løse?
Jeg løste den på lidt over 12 minutter og synes langt fra den var svær.
Jeg kunne endda nøjes med at bruge 3-4 af standard metoderne.
Den soduko, skulle den være den sværeste for et menneske eller maskine at løse?
Jeg løste den på lidt over 12 minutter og synes langt fra den var svær.
Jeg kunne endda nøjes med at bruge 3-4 af standard metoderne.
#45
Tjae... når jeg har brugt standard udelukkelses metoderne, plejer jeg at kigge efter dubletter og tripletter.
Mange af tallene springer mig bare i øjnene, det er svært at forklare hvordan jeg finder dem.
Tjae... når jeg har brugt standard udelukkelses metoderne, plejer jeg at kigge efter dubletter og tripletter.
Mange af tallene springer mig bare i øjnene, det er svært at forklare hvordan jeg finder dem.
Jeg bruger naturligvis backtracking for at løse en sudoku. Som tidligere nævnt ville det aldrig have kunnet virke for 9x9 felter uden at bruge backtracking. Jeg starter med at tage de allerede udfyldte felter og bruge dem til at konstruere en bitmaske af muligheder. Hvis et felt er udfyldt er der kun én bit sat, hvis et felt ikke er udfyldt er der ni bits sat.tommyb (40) skrev:#39 : Kasper, hvis du bruger bruteforce istedet for backtracking kan jeg godt forstå at dit program bliver langsomt :)
Backtracking går ud på at udelukke store grene af dit træ af muligheder, istedet for at teste ALLE kombinationer som man gør med bruteforcing.
Derefter reducerer jeg masken ved at finde felter, hvor kun en bit er sat og fjerne den fra resten af felterne i samme række, søjle, eller kvadrat.
Derefter tager jeg alle bits som kun er sat et enkelt sted indenfor en række eller søjle og fjerner alle de andre bits fra det felt. (Jeg burde også gøre det for hvert enkelt kvadrat og se om det hjælper).
Denne reduktion gentages indtil der ikke sker mere.
Når dette er gjort undersøger jeg hvor mange felter, der har nul eller en bit sat. Hvis der er nul i et felt findes der ingen løsning. Hvis der er en i alle felter, så har jeg fundet en løsning.
Hvis ingen af de to var tilfældet udvælger jeg et felt med mere end én bit sat og kalder rekursivt med hvert muligt tal.
Denne fremgangsmåde løser de 9x9 sudokuer jeg har prøvet med på få millisekunder.
For at generere en tilfældig sudoku starter jeg med en tom plade, hvor jeg prøver at udfylde et felt. Så undersøger jeg om der findes en løsning, og hvis ikke der gør fjerner jeg talet igen.
Metoden virker glimrende med 9x9, men for 16x16 tager det for lang tid at finde ud af om der er en løsning for tilfældet hvor blot et enkelt felt er udfyldt.
Jeg prøvede den anden med mit program. Det tog mit program 2ms at løse den. Hvilket er langt under de 7ms som er det sværeste mit program har været udsat for. Nu vil jeg prøve at se hvor lang tid jeg tager om at løse den manuelt.XorpiZ (42) skrev:Er vi ikke enige om, at det er denne du skal løse og ikke denne?
Edit:
For at uddybe - den sudoku USAToday har på deres side er bare en tilfældig sudoko, og altså ikke noget specielt.
#47
hmm .. kunne være man skulle tage sit LINQ 2 Sudoku projekt frem igen...
En ting jeg har tænkt på, er om man ikke kunne bruge Sudoku'er til at endten encrypte eller komprimere data...
sagen er jo at
- et lille antal tal på bestemte positioner kan udgøre et 9x9 felt
- hele feltets tal (eller hver række) kan angive en position i et array
mon ik man kan bruge det til noget ?
hmm .. kunne være man skulle tage sit LINQ 2 Sudoku projekt frem igen...
En ting jeg har tænkt på, er om man ikke kunne bruge Sudoku'er til at endten encrypte eller komprimere data...
sagen er jo at
- et lille antal tal på bestemte positioner kan udgøre et 9x9 felt
- hele feltets tal (eller hver række) kan angive en position i et array
mon ik man kan bruge det til noget ?
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Nyheder
Gå til bund