Latijns vierkant bij javascript

Status
Niet open voor verdere reacties.
thechib12

thechib12

Gebruiker
Lid geworden
26 jan 2009
Berichten
757
Dag members,

Lang geleden dat ik op dit forum ben geweest ;).

Ik ben bezig voor mijn profielwerkstuk. Helaas is informatica o.i.d. een vak dat niet op onze school wordt gegeven. Maar dat hield me niet tegen om programmeren te kiezen als onderwerp voor profielwerkstuk.
Het onderwerp is een sudokusolver programmeren in javascript. Om dit te kunnen halen, hebben wij opdrachten gekregen zodat we een idee krijgen hoe we de solver kunnen maken.
De opdrachten zijn als volgt. 1. Recursie/faculteit script maken. 2 Script om alle permutaties van een string te geven 3. Latijns vierkant (soort kleine sudoku) solver schrijven (4x4)

De eerste 2 zijn gelukt, hoewel het tegen viel. Nu kom ik bij het Latijns vierkant. Ik heb geen idee hoe ik het kan schrijven. Wat wel van belang is dat het algoritme Backtracking en/of Brute force is.
Ik hoopte dat iemand mij een schop kan geven in de goede richting. Eindeloos googlen heeft mij niks opgeleverd. Tevens heb ik ook niemand om vragen te stellen en sta ik er in principe alleen voor.

Ik heb al wel een array kunnen maken, die een veld weer geeft.

Code: 
var array = [];
for (var x = 0; x<4; x++){
    for (var y = 0; y<4; y++){
       
        

        array.push([x,y,0])
;

    }
    
    
}

Deze array maakt een veld, met x,y coordinaat en als getal 0. Dus zo

x 0 1 2 3
y ______
0 | 0 0 0 0
1 | 0 0 0 0
2 | 0 0 0 0
3 | 0 0 0 0

Ik hoop dat iemand mij kan helpen!

Chib
 
Ik heb ook eens geprobeerd een sudoku solver te maken (op mn rekenmachine). Halverwege gekomen tot het een beetje saai werd ;p

Je moet per vakje een stel variabelen maken waarin je vastlegt welke waardes het vakje niet kan hebben (kan ook kiezen voor juist wel, als je maar consistent blijft).

Ook zou ik eerst (met html input) een interface maken waar de gebruiker zijn waardes in kan vullen.

Dit is huiswerk, dus ik zal niet teveel zeggen.
 
Laatst bewerkt:
Hoi Kvothe, Bedankt voor je antwoord.

Ik heb al een begin, wat ik in de op heb gezet is niet het juiste.
Code: 
var vierkant = [[1,0,3],[2,0,1],[0,1,0]];

for(var a = 0; a<vierkant.length; a++){
    for(var b = 0; b<vierkant.length; b++){
    if(vierkant[a][b] === 0) {
    'doe de functie getal bepalen; 
    
    }    
    
    }
}

Op het punt 'doe functie hier' is de bedoeling dat ik het backtracking algoritme implenteer. dwz, ik kijk of ik op de 0 een 1 kan plaatsen, zoja, volgende. Zo nee, pak 2 e.d.
gewoon diehard alle mogelijkheden plaatsen. Dit is haalbaar met for-loops, maar ik heb geen flauw idee hoe ik dit kan vertalen.

Jij wel?
 
Wat je in je if () wilt hebben is iets dat de hoeveelheid vrijheidsgraden (hoeveel verschillende nummers er zouden kunnen) in dat vakje checkt, en als dat 1 is het nummer invult.

Je kan dat natuurlijk in elke loop berekenen, maar als je dat op mijn manier doet (het bijhouden in een andere variabele) is het

a) simpeler, zeker als je een normale 9x9 sudoku wilt oplossen,
b) minder berekeningen, vooral relevant als je het op een grafische rekenmachine doet zoals ik.
 
Het is belangrijk dat ik het backtracking algoritme gebruik. Wat jij zelf nu zegt snap ik ook eigenlijk niet
 
Sorry als ik teveel jargon gebruik ;)


Sudokus zijn logisch oplosbaar, dus ik zou geen backtracking gebruiken. Gebruik brute-force.

edit lijn-----------------

Om te beginnen kan je beter een functie maken die checkt of je het nummer zou kunnen plaatsen.

Ik zou hem zo structureren

[JS]
function check(n, x, y) {
if (nummer komt al voor op rij op hoogte y) {
return false;
}
if (nummer komt al voor op kolom op breedte x) {
return false;
}
return true
}

[/JS]
Let op: dit betekent niet dat dat nummer daar ook hoort. Dat is alleen zo als de functie false resulteert voor alle andere nummers.
 
Laatst bewerkt:
Kvothe zei:
Sorry als ik teveel jargon gebruik ;)


Sudokus zijn logisch oplosbaar, dus ik zou geen backtracking gebruiken. Gebruik brute-force.

edit lijn-----------------

Om te beginnen kan je beter een functie maken die checkt of je het nummer zou kunnen plaatsen.

Ik zou hem zo structureren

[JS]
function check(n, x, y) {
if (nummer komt al voor op rij op hoogte y) {
return false;
}
if (nummer komt al voor op kolom op breedte x) {
return false;
}
return true
}

[/JS]
Let op: dit betekent niet dat dat nummer daar ook hoort. Dat is alleen zo als de functie false resulteert voor alle andere nummers.
Klik om te vergroten...

Hoi Kvothe, bedankt. Hoe kan ik nummer komt al voor op rij- dan bepalen? Ik heb dan geen flauw benul wat ik dan moet doen.

Tevens is mij deze psuedo code gegeven:

function vulVierkantIn(vierkant) {
zoek eerste nul in het vierkant (kies wel telkens vast zoekvolgorde);
if (er is geen nul) {klaar!}
else {bepaal alle waarden die op het plek met de nul kunnen (kolom en rij van het vakje checken); sla die bijv. op in een tijdelijke rij;
for (alle waarden die nog kunnen) {
vulVierkantIn(vierkant met waarde ingevuld in het vakje);
}
}
}

Maar het zoeken van de nul kan je toch niet met een for-loop doen in dit geval? Hoe kan ik dit in javascript dan omzeten?
 
Hoe kan ik nummer komt al voor op rij- dan bepalen? Ik heb dan geen flauw benul wat ik dan moet doen.
Klik om te vergroten...

Kijk of bijvoorbeeld nummer 1 al voorkomt op 0,0 en dan op 0,1 enzovoort...
 
Heb je toevallig iets van skype of een ander chat programma, waar je me evt. op kan helpen. Je doet me dan een groot plezier ;)
 
Ja maar het is beter om het hier op te lossen, dan hebben anderen e.d. er ook nog wat aan.
 
Ook prima, ben iig blij dat je me helpt.

terugkomend op dit:

function vulVierkantIn(vierkant) {
zoek eerste nul in het vierkant (kies wel telkens vast zoekvolgorde);
if (er is geen nul) {klaar!}
else {bepaal alle waarden die op het plek met de nul kunnen (kolom en rij van het vakje checken); sla die bijv. op in een tijdelijke rij;
for (alle waarden die nog kunnen) {
vulVierkantIn(vierkant met waarde ingevuld in het vakje);
}
}
}

Als je dit doet door elke keer na te gaan bij 0,0 krijg je toch meer dit:

Code: 
function checkgetal(vierkant){
    for (var a = 0; a<vierkant.length; a++){
        for(var b = 0; b< vierkant.length; b++){
        if(vierkant[a][b] === 0){
        //doe hier de functie om het getal te veranderen
        else
        // ??????????????
        
        
        }    
    
        }
    }
    
    
}

Maar dan lijkt het alsof het niet klopt, omdat je niet kijkt of er geen een 0 in zit, wat die wel bij de psuedo code doet. De psuedo code is recursief, en de code die ik gaf niet(volgens mij)
 
Je moet later nog de hele oplos code laten loopen, maak je hierover voorlopig nog geen zorgen.
 
Ok dan heb ik nu dit:

function checkgetal(vierkant){
for (var a = 0; a<vierkant.length; a++){
for(var b = 0; b< vierkant.length; b++){
if(vierkant[a] === 0){
//doe hier de functie om het getal te veranderen
else
// ??????????????


}

}
}


}

Maar ik heb nu geen flauw idee hoe ik nu verder moet
 
Waar 'functie om het getal te veranderen' staat moet je een conditie bouwen die true is als er slechts één getal past en anders false is.

Indien true, dan mag je het getal invoeren in de sudoku.
 
Zo ver snap ik het, maar ik heb geen flauw idee hoe ik dat moet verwerken!
 
Geen flauw idee hoe je die conditie moet maken of hoe je het getal invoert in je matrix?
 
Je kan getallen invoegen in een matrix (in feite een array in een array) door bijv vierkant[j] = 1 te doen.

Op eenzelfde manier kan je ook de waarde van getallen in een matrix opzoeken.
 
Status
Niet open voor verdere reacties.
                    Steun ons                    

Nieuwste berichten

Terug
Bovenaan Onderaan