[ruby] matrix verhogen

[Boudewijn]

Allereerst: excuses voor de bijzonder slechte titel, maar ik weet geen betere.


Momenteel ben ik een sudoku solver aan het schrijven in ruby, en hiervoor heb ik een array van arrays (waar je normaal een 2d array zou pakken ) gedefinieerd:

code:

        r0 = Array[9,9,9,9,9,9,9,9,9]
        r1 = Array[1,1,1,2,2,2,7,8,9]
        r2 = Array[1,1,1,2,2,2,7,8,9]
        r3 = Array[1,2,3,4,5,6,7,8,9]
        r4 = Array[1,2,3,4,5,6,7,8,9]
        r5 = Array[1,2,3,4,5,6,7,8,9]
        r6 = Array[1,2,3,4,5,6,7,8,9]
        r7 = Array[1,2,3,4,5,6,7,8,9]
        r8 = Array[1,2,3,4,5,6,7,8,9]

        rX = Array[r0,r1,r2,r3,r4,r5,r6,r7,r8]

        sq = Square.new(rX)
        sq.increment

Square is een klasse die netjes die 2d array opslaat.

Nu heb ik een functie geschreven die vanuit elke sudoku (op die met allemaal 9's na...) de volgende sudoku generereert. Dit doet hij door het getal linksboven met 1 te verhogen. Wordt dat getal dan 10, dan moet het getal ernaast met 1 worden verhoogd.

Hiervoor flatten ik die 2d array, zodat het lekker makkelijk gaat.

Dit werkt prima, maar als ik meer dan 9 9's achter elkaar heb schiet plotseling de waarde op positie 11 (als 1-9 de 9's zijn) op 11. Gevolg is dus dat ik denk dat mijn lus dan teveel optelt, ik zit er echter al de halve avond op en zie niet waar het fout gaat.

Hier zien we een voorbeeld (van een flattend versie ) van de array waar het misgaat:

code:

9,9,9,9,9,9,9,9,9,1,1,1,2,2,2,7,8,9,1,1,1,2,2,2,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9
1,1,1,1,1,1,1,1,1,1,11,9,9,9,9,9,9,9,9,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,7,7,7,7,8,8,8,8,9,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,7,7,7,7,7,7,8,9,9,9,9,9,1,1,2,3,3,3,3,3,4,4

We zien dus dat het best goed misgaat in dit geval (overige gevallen werken goed), bij gebruik van deze code:

code:

        def increment
                @fields[0][0]=@fields[0][0]+1

                #als we ergens een 10 hebben staan moet het veld erna worden geupdate
                flatFields= @fields.flatten

                while (@fields.flatten.index(10) != nil) do
                        #jaja die flatFields.index(10) kan mooi in een var...
                        idx=flatFields.index(10)
                        flatFields[idx]=1
                        flatFields[idx+1] = flatFields[idx+1]+1

                        #controleren op eindconditie, dit treedt alleen op als de sudoku unsolveable is
                        if (flatFields.sort() == flatFields && flatFields[0].sort()== 9)
                                return false
                        end

                        for i in (0..SudokuSize)
                                @fields[i]=flatFields.slice((i*SudokuSize),SudokuSize+1)
                        end


                        flatFields=@fields.flatten

                end
                puts flatFields * ","

                return true
        end

Het is mijn eerste ruby-progsel dus ik verwacht een dom stom foutje ergens ,maar heb geen idee waar.


Mijn idee is dat de increments allemaal over de 10e positie komen , die dan 10 wordt waardoor de 11e positie 11 wordt. Snap alleen niet waarom dit niet wordt opgevangen door mijn lus.

Kan iemand me een zetje geven?

[Boudewijn]

Schopje.

[Boudewijn]

bump schop, anders ga ik morgen die lus maar eens herschrijven .

[.oisyn]

Ik vind je methode maar onhandig. Ik ben verder niet bekend met Ruby, maar waarom doe je niet gewoon (in een loop) de positie van een element ophogen, en als die 10 is zet je 'm weer op 1 en verhoog je de positie van het volgende element. Wat jij nu doet is steeds het hele veld zoeken naar 10'en, wat onzin is, want alleen het element dat je zojuist hebt opgehoogd kan maar 10 zijn. Ook zou ik er geen platte array van maken, of juist ten alle tijden een platte array gebruiken (waarin een index y*9+x wordt)

Het doel van die sorts in je code snap ik ook niet helemaal...

De correcte term is trouwens "matrix permutaties"

Overigens, besef je wel dat je op deze manier 9⁸¹ ~= 1.967 *10⁷⁷ mogelijkheden moet controleren? Al check je er een miljard per seconde op een PC, en heb je een miljard PC's tot je beschikking, dan nog ben je 3.17 * 10⁵¹ jaar bezig. Niet te doen dus.

Goede sudoku solvers passen dezelfde regels toe als mensen die 'm met de hand oplossen, en gaan pas als het niet meer anders kan verschillende mogelijkheden proberen. Een naïeve solver die nog steeds vrij rap z'n werk kan doen doet alleen de basale checks (cijfers wegstrepen die al op de regel voorkomen, en dan zoeken naar vakjes waar nog maar 1 mogelijkheid is of waar een cijfer in een rij/blokje maar 1x voorkomt), en gaat daarna uitproberen. Deze werken velen en velen malen sneller dan wat jij probeert te doen - binnen enkele seconden hebben ze een sudoku opgelost.

[ Voor 56% gewijzigd door .oisyn op 12-02-2009 16:53 ]

[mithras]

Het gaat alleen mis bij het wisselen naar een volgende rij toch? Ik ben niet bekend met Ruby, maar uit je probleem lees ik af dat als rij n allemaal 9's bevat, rij n+1 op positie 2 een 11 krijgt.

Waarom flatten je dan? Ik snap dat het makkelijk is, maar hierdoor moet je wel controleren of je op een volgende rij zit. Ik zou twee keer een loop neerzetten. Eén voor de rijen, vervolgens een voor de kolommen. Dan kan het probleem (per definitie) niet meer voorkomen omdat je in een volgende iteratie van je buitenste loop zit

/edit: ah, kennelijk ben je dus op zoek naar slechts het voorkomen van een 10. Dat is iets waar bovenstaande methode niet de oplossing voor kan zijn.

[ Voor 12% gewijzigd door mithras op 12-02-2009 16:48 ]

[Boudewijn]

Ik weet dat het redelijk lompe-boer oplossing is.
Feit is dat ik zo nog een check ga maken die eerst een rij checkt en een kolom van het aangepaste getal. Als dat al niet klopt dan ga ik sowieso naar de volgende iteratie.

@mithrats, een volgende rij zit je op als id%9==0 geldt.

[.oisyn]

Boudewijn schreef op donderdag 12 februari 2009 @ 16:54:
Feit is dat ik zo nog een check ga maken die eerst een rij checkt en een kolom van het aangepaste getal. Als dat al niet klopt dan ga ik sowieso naar de volgende iteratie.

Volgens mij komt de reality check nog niet helemaal aan. Nog een poging dan: een snelle hedendaagse CPU is meestal rond de 3 GHz geklokt. Dat zijn 3 miljard kloktikken per seconde. Je kunt een loopje maken dat niets doet. Laten we voor het gemak even aannemen dat dat in 1 kloktik kan (meestal is dat duurder). Dan kun je dus 3 miljard (= 3 * 10⁹) iteraties doen per seconde. Jij wilt echter 1.967 *10⁷⁷ iteraties doen. Dat kost je ~6.55 * 10⁶⁷ seconden, oftewel ~2.08 * 10⁶⁰ jaar. Goed, wellicht heb je een octocore in je PC, kost het je "maar" ~2.60 * 10⁵⁹ jaar. En wat doe je dan uiteindelijk? Helemaal *niets*, alleen itereren, je loop is verder leeg. Dus al het werk wat daar nog in moet dat komt er nog eens bij.

[ Voor 7% gewijzigd door .oisyn op 12-02-2009 17:04 ]

[Boudewijn]

De reality check is allang aangekomen .


ik ga het anders aanpakken ,maar feit is wel dat ik wil weten waarom ^^ niet werkt (buiten de tijdsconstraint om...).

offtopic:
Sowieso weet ik al gauw al 10-12 getallen, waardoor het al veel minder dramatisch wordt, maar dat terzijde.

[ Voor 26% gewijzigd door Boudewijn op 12-02-2009 17:19 ]