[JAVA] Code verkorten naar methode

[Famous Copra]

Ik ben net begonnen met java, het leek mij namelijk een leuke uitdaging om een programma te schrijven dat sudoku's oplost.

Nu heb ik uiteindelijk een programma geschreven wat sudoku's van 4x4 op kan lossen, de code is alleen erg lang en moet voor een groot gedeelte als methode kunnen.
Het gaat om dit stuk:

Java:

// Als eerste testen we of 1 een goede waarde kan zijn
if (n == 1) {
    // Als een 2 voorkomt in de rij of in de kolom gaan we verder
    if (number[r][0] == 2 || number[r][1] == 2 || number[r][2] == 2 || number[r][3] == 2 || number[0][c] == 2 || number[1][c] == 2 || number[2][c] == 2 || number[3][c] == 2) {
        // Als een 3 voorkomt in de rij of in de kolom gaan we verder
        if (number[r][0] == 3 || number[r][1] == 3 || number[r][2] == 3 || number[r][3] == 3 || number[0][c] == 3 || number[1][c] == 3 || number[2][c] == 3 || number[3][c] == 3) {
            // Als een 4 voorkomt in de rij of in de kolom gaan we verder
            if (number[r][0] == 4 || number[r][1] == 4 || number[r][2] == 4 || number[r][3] == 4 || number[0][c] == 4 || number[1][c] == 4 || number[2][c] == 4 || number[3][c] == 4) {
                // Alle nummers staan nu in de rij of kolom, staat de gekozen mogelijkheid nog niet in de rij
                if (number[r][0] != n && number[r][1] != n && number[r][2] != n && number[r][3] != n) {
                    // Staat de gekozen mogelijkheid ook niet in de kolom
                    if (number[0][c] != n && number[1][c] != n && number[2][c] != n && number[3][c] != n) {
                        // Dan vullen we de mogelijkheid in in de array
                        number[r][c] = n;
                        // we veranderen de teller van de lege vakjes, zodat het programma weet wanneer het klaar is
                        leeg = leeg - 1;
                    }
                }
            }
        }
    }
}

Dit herhaalt zich voor elke mogelijkheid (1 t/m 4), hoe kan ik dit mooi verwerken in bijvoorbeeld een methode zodat ik maar één keer de code moet schrijven en daarna de methode toe kan passen.

Alle hulp is welkom

*snip*

[ Voor 12% gewijzigd door RobIII op 11-07-2013 19:02 . Reden: Link naar volledige code verwijderd (irrelevant) en code indenting verbeterd zodat de code i.i.g. op kolom 0 begint i.p.v. op kolom 30 ]

[Slurpie]

code:

 function checkField(int n, int r, int c, array number) {
  //geposte code
}


 // gaan we alle mogelijkheden af 1 t/m 4 in dit geval
                                                for (int n = 1; n <= 4; n++) {
 checkField(n,r,c,number); //run functie
}

FF snel.

[RobIII]

Nogmaals: we zitten hier niet om je code (helemaal) te bekijken of voor je te verbeteren. Dat kun je prima zelf als we je wat op/aanmerkingen geven. De gegeven snippet code is voldoende voor ons om iets over te zeggen en als we meer willen zien vragen we er wel om. (Daarbij: neem gerust van mij aan dat niemand hier zin heeft om naar code te gaan lopen staren die, wat, 14, 15 niveaus diep genest is ).

Maar wat ik mis in je topicstart: wat heb je zélf al geprobeerd? Heb je al eens geprobeerd herhalende lappen code in een functie te stoppen? Wat lukte daar niet aan? Wat lukte wel? Je topic voldoet op een aantal punten niet aan onze Quickstart en is niets meer dan

• "dit wil ik"
• *dump* "dit is mijn code"
• "help me"
• *dump* "hier heb je nog een bak code veel plezier ermee"

en zo werkt 't hier dus niet

Wat Slurpie hierboven laat zien had je, als je dat zelf al geprobeerd had, al kunnen vermelden in je topicstart waarbij je dan ook had kunnen aangeven waar je probleem zat als 't niet zou werken ofzo. En heb je dat nog niet geprobeerd: waarom niet?

[ Voor 25% gewijzigd door RobIII op 11-07-2013 19:13 ]

[Daos]

Voor herhalingen in je code kan je functies en loops gebruiken.

Je oude code wordt dan (Slurpie gaat nog een stap verder en stopt de checks ook nog in een loop):

Java:

// Als eerste testen we of 1 een goede waarde kan zijn 
if (n == 1) { 
    // Als een 2 voorkomt in de rij of in de kolom gaan we verder 
    if (IsFoundInRowOrColumn(number, r, c, 2)) { 
        // Als een 3 voorkomt in de rij of in de kolom gaan we verder 
        if (IsFoundInRowOrColumn(number, r, c, 3)) { 
// etc

Voorbeeldje (niet getest; uit losse pols):

Java:

boolean IsFoundInRowOrColumn(int[][] number, int row, int column, int value) {
    return IsFoundInRow(number, row, value) || IsFoundInColumn(number, column, value);
}

boolean IsFoundInRow(int[][] number, int row, int value) {
    boolean res = false;
    
    for (int c = 0; c < 4; c++) {
        res = res || number[row][c] == value;
    }
    
    return res;
}

De conditie in de if-statements met de && kan je ook vervangen door functies met daarin een loop. Je moet daar dan wel beginnen boolean res = true;. Of misschien kan je diezelfde functies hergebruiken met een ! (not):

Java:

// Alle nummers staan nu in de rij of kolom, staat de gekozen mogelijkheid nog niet in de rij 
if (!IsFoundInRow(number, r, n)) {
    // Staat de gekozen mogelijkheid ook niet in de kolom 
    if (!IsFoundInColumn(number, c, n)) {
// etc

[Famous Copra]

Ik had Daos post nog niet gezien

Ik zal proberen in woorden uit te leggen wat ik wil bereiken.

Ik heb een array waarin alle waarden van de sudoku staan, respectievelijk 16 (4x4) of 81 (9x9). Als het vakje leeg is krijgt dat hokje de waarde 0.

Nu los ik de sudoku op door elke mogelijkheid uit te proberen (1 t/m 4 bij een 4x4 sudoku of 1 t/m 9 bij een 9x9 sudoku) hiervoor moet je dus kijken of elk getal behalve de gekozen mogelijkheid in de rij of kolom voorkomt.

Kortom hoe maak ik een methode die alles uittest behalve de gekozen mogelijkheid?

Het enige wat ik zou kunnen bedenken is een methode met als input de mogelijkheid ( 1 t/m 4) en dan voor elke testregel die checkt of het getal in de rij of kolom voorkomt een if (mogelijkheid != 1) t/m if (mogelijkheid != 4).
Het lijkt me dat dit effecienter kan.

[Daos]

Je kan in 1 keer een rij/kolom aflopen en alles wat daar staat verzamelen. Als er 1 getal niet in je verzameling voorkomt, dan moet dat op die plek. Je kan het sneller maken door de verzamelingen per rij/kolom te cachen/los van tevoren te berekenen. Voorbeeldje:

code:

1 2 ?  -> rij-verzameling = {1, 2}
    4
    
    |
   \/
   kolom-verzameling = {4}

op de plek van het vraagteken moet de enige die over is: 3

[edit]
Een ander regeltje voor het oplossen van makkelijke sudoku's is dat soms een nummer nog maar op 1 plek kan staan in een rij/kolom.

code:

1   ? 4 
3 
  3
      3

de plek van het vraagteken is de enige in die rij waar nog een 3 mag staan en daar komt daarom: 3

[ Voor 28% gewijzigd door Daos op 11-07-2013 21:25 ]

[Famous Copra]

Helaas kom ik er nog niet uit.

Ik weet niet hoe ik een loop laat doen met alle waardes van 1 t/m 9 behalve een gekozen waarde. zou iemand mij dit kunnen uitleggen?

[RobIII]

Famous Copra schreef op donderdag 11 juli 2013 @ 21:49:
Ik weet niet hoe ik een loop laat doen met alle waardes van 1 t/m 9 behalve een gekozen waarde. zou iemand mij dit kunnen uitleggen?

Again: wat heb je zelf al geprobeerd? Ik neem aan dat je googlen op "Java loop" toch nog wel zelf verzonnen kreeg? En hoe moeilijk is 't dan op de proppen te komen met iets als:

code:

skipnumber = 7

loop with var x from 1 to 9
  if x is_not_equalto skipnumber
    dosomething
  endif
endloop

?

[Daos]

Ik heb mijn eerste algoritme eventjes uitgewerkt in C#. Zie hier de belangrijkste onderdelen.

We beginnen met een voorbeeldje:

C#:

int[,] number = new int[SIZE, SIZE];
number[0, 0] = 1;
number[0, 3] = 4;
number[2, 1] = 3;
number[2, 2] = 4;
number[3, 3] = 3;

Before:
1     4

  3 4
      3

We bepalen de rij- en kolom-verzamelingen:

C#:

SortedSet<int>[] rowSets = new SortedSet<int>[SIZE];
for (int r = 0; r < SIZE; r++)
{
    rowSets[r] = new SortedSet<int>();
    for (int c = 0; c < SIZE; c++)
    {
        if (number[r, c] > 0)
        {
            rowSets[r].Add(number[r, c]);
        }
    }
}

We loopen net zolang er veranderingen zijn:

C#:

bool change_seen = true;
while (change_seen)
{
    change_seen = false; 
    //...

We lopen alle velden af op zoek naar lege velden:

C#:

for (int r = 0; r < SIZE; r++)
{
    for (int c = 0; c < SIZE; c++)
    {
        if (number[r, c] > 0)
        {
            // process empty cells only; this one is not empty
            continue;
        }
        //...

Bij een leeg veld combineren we de rij- en kolomverzamelingen:

C#:

        
SortedSet<int> combined = new SortedSet<int>(rowSets[r]);
combined.UnionWith(columnSets[c]);

Console.WriteLine("combined ({0}, {1}): ", r, c);
PrintSet(combined);

Als er maar 1 getal mist stoppen wij die op de huidige locatie en voegen wij die ook aan de rij- en kolomverzamelingen toe:

C#:

        
if (combined.Count == SIZE - 1)
{
    // only one left...

    SortedSet<int> new_set = new SortedSet<int>(all);
    new_set.ExceptWith(combined);
    
    Console.WriteLine("leftover: ");
    PrintSet(new_set);

    number[r, c] = new_set.ElementAt(0);
    rowSets[r].Add(number[r, c]);
    columnSets[c].Add(number[r, c]);

    change_seen = true;
}

Achteraf ziet het er dan zo uit:

After:
1 2 3 4
3 4 1 2
2 3 4 1
4 1 2 3

[Famous Copra]

Na wat research heb ik de continue functie gevonden, hierdoor kan ik mijn programma aanzienelijk verkort uitvoeren.

Het enige wat nu nog toegevoegd moet worden is het checken of het cijfer al aanwezig is in het vierkant.

Voor de geïnteresseerden:

Java:

        // Check of alle vakjes ingevuld zijn
        while (leeg != 0) {

            // ga elke rij af (0 t/m 3)
            for (int r = 0; r <= 3; r++) {
                // ga elke kolom af (0 t/m 3)
                for (int c = 0; c <= 3; c++) {
                    // als de waarde van het vakje 0 is en het dus leeg is
                    if (number[r][c] == 0) {
                        // gaan we alle mogelijkheden af 1 t/m 4 in dit geval
                        for (int n = 1; n <= 4; n++) {
                            Check(number, r, c, n);
                        }
                    }
                }
            }
        }

    
    public static void Check(int[][] number, int row, int column, int value) {
        int waar;
        waar = 0;
            for (int i = 1; i < 5; i++) {
                if ( i == value) {
                    continue;
                }
                if (IsFoundInRowOrColumn( number, row, column, i)) {

                    waar++;
                }
                else {
                    waar = 0;
                }
            }
                
                if (waar == 3) {
                    if (!IsFoundInRowOrColumn(number, row, column, value)) {
                        number[row][column] = value;
                        leeg = leeg - 1;
                        waar = 0;
                    } else {
                        waar = 0;
                    }
                } else {
                    waar = 0;
                }
            }

[Daos]

Ik heb de blokken toegevoegd aan mijn algoritme: Je kan in 1 keer een rij/kolom/blok aflopen en alles wat daar staat verzamelen. Als er 1 getal niet in je verzameling voorkomt, dan moet dat op die plek. Je kan het sneller maken door de verzamelingen per rij/kolom/blok te cachen/los van tevoren te berekenen.

We bepalen van te voren de rij-, kolom-, en blokverzamelingen:

C#:

SortedSet<int>[] rowSets = new SortedSet<int>[SIZE];
SortedSet<int>[] columnSets = new SortedSet<int>[SIZE];
SortedSet<int>[] blockSets = new SortedSet<int>[SIZE];
for (int x = 0; x < SIZE; x++)
{
    rowSets[x] = new SortedSet<int>();
    columnSets[x] = new SortedSet<int>();
    blockSets[x] = new SortedSet<int>();
}

for (int r = 0; r < SIZE; r++)
{
    for (int c = 0; c < SIZE; c++)
    {
        if (number[r, c] > 0)
        {
            columnSets[c].Add(number[r, c]);
            rowSets[r].Add(number[r, c]);

            int b = GetBlock(r, c);
            blockSets[b].Add(number[r, c]);
        }
    }
}

Bij een leeg veld combineren we de rij-, kolom- en blokverzamelingen:

C#:

SortedSet<int> combined = new SortedSet<int>(rowSets[r]);
combined.UnionWith(columnSets[c]);
int b = GetBlock(r, c);
combined.UnionWith(blockSets[b]);

Als er maar 1 getal mist stoppen wij die op de huidige locatie en voegen wij die ook aan de rij-, kolom- en blokverzamelingen toe.

Om het bloknummer te berekenen uit rij, kolom coordinaten gebruiken we deze functie:

C#:

private static int GetBlock(int r, int c)
{
    return (r / SQRT_SIZE) * SQRT_SIZE + (c / SQRT_SIZE);
}

Nog wat test Sudoku's:
4 x 4:

Java:

number[0][0] = 1;
number[0][3] = 4;
number[2][1] = 3;
number[2][2] = 4;

code:

1..4.....34.....

very easy 9 x 9:

Java:

            
number[0][0] = 7;
number[0][2] = 6;
number[0][3] = 5;
number[0][7] = 2;
number[0][8] = 9;
number[1][0] = 2;
number[1][1] = 5;
number[1][4] = 4;
number[2][2] = 1;
number[2][4] = 8;
number[2][5] = 2;
number[2][6] = 6;
number[3][1] = 2;
number[3][6] = 9;
number[3][7] = 6;
number[4][1] = 3;
number[4][3] = 4;
number[4][5] = 9;
number[4][7] = 8;
number[5][1] = 9;
number[5][2] = 5;
number[5][7] = 4;
number[6][2] = 9;
number[6][3] = 2;
number[6][4] = 7;
number[6][6] = 3;
number[7][4] = 9;
number[7][7] = 1;
number[7][8] = 4;
number[8][0] = 3;
number[8][1] = 7;
number[8][5] = 1;
number[8][6] = 2;
number[8][8] = 8;

code:

7.65...2925..4......1.826...2....96..3.4.9.8..95....4...927.3......9..1437...12.8

easy 9 x 9:

Java:

number[1][0] = 8;
number[1][3] = 3;
number[1][5] = 5;
number[1][8] = 2;
number[2][2] = 6;
number[2][6] = 9;
number[3][1] = 4;
number[3][3] = 5;
number[3][5] = 6;
number[3][7] = 8;
number[4][0] = 7;
number[4][2] = 1;
number[4][6] = 4;
number[4][8] = 9;
number[5][3] = 9;
number[5][5] = 1;
number[6][0] = 9;
number[6][1] = 7;
number[6][4] = 6;
number[6][7] = 3;
number[6][8] = 5;
number[7][2] = 3;
number[7][6] = 1;
number[8][2] = 4;
number[8][4] = 2;
number[8][6] = 7;           

code:

.........8..3.5..2..6...9...4.5.6.8.7.1...4.9...9.1...97..6..35..3...1....4.2.7..

[ Voor 14% gewijzigd door Daos op 13-07-2013 21:29 ]

[Soultaker]

Vind je dat echt het meest zinnige formaat om Sudoku's in te posten?

Dit is meer gebruikelijk:

code:

...|...|..8
..3|...|4..
.9.|.2.|.6.
---+---+----
...|.79|...
...|.61|2..
.6.|5.2|.7.
---+---+---
..8|...|5..
.1.|...|.2.
4.5|...|..3

Of nog compacter (en vooral geschikt voor programma's):

code:

........8..3...4...9..2..6.....79.......612...6.5.2.7...8...5...1.....2.4.5.....3

[Daos]

Dan moet je weer een parser schrijven. Mijne kan je direct in de code kopieren

[Soultaker]

Klopt, maar dat lijkt me nogal snel uitkunnen als je je code af en toe wil testen met verschillende puzzels. Sowieso vind ik het wel een goed programmeerprincipe dat je code en data enigzins probeert te scheiden.

[Daos]

Soultaker zijn puzzel:

Java:

number[0][8] = 8;
number[1][2] = 3;
number[1][6] = 4;
number[2][1] = 9;
number[2][4] = 2;
number[2][7] = 6;
number[3][4] = 7;
number[3][5] = 9;
number[4][4] = 6;
number[4][5] = 1;
number[4][6] = 2;
number[5][1] = 6;
number[5][3] = 5;
number[5][5] = 2;
number[5][7] = 7;
number[6][2] = 8;
number[6][6] = 5;
number[7][1] = 1;
number[7][7] = 2;
number[8][0] = 4;
number[8][2] = 5;
number[8][8] = 3;

Gemaakt met mijn leet-"Soultaker's one line Sudoku format"-naar-Java converter

Nu het oplossen nog... Ik zie met het blote oog dat er een 2 rechtsboven onder de 8 moet komen omdat hij nergens anders in dat blok mag.

edit:
Daar heb je een tweede algoritme voor nodig zoals ik eerder al schreef:

Daos schreef op donderdag 11 juli 2013 @ 20:14:
[edit]
Een ander regeltje voor het oplossen van makkelijke sudoku's is dat soms een nummer nog maar op 1 plek kan staan in een rij/kolom.

code:

1   ? 4 
3 
  3
      3

de plek van het vraagteken is de enige in die rij waar nog een 3 mag staan en daar komt daarom: 3

[ Voor 24% gewijzigd door Daos op 12-07-2013 18:54 ]