[JAVA] 8 Koninginnen probleem, roteren van een grid int[]

[roy-t]

Ik ben bezig met een programmeer opdracht om het 8 (N) koninginnen probleem op te lossen.

(wiki hier: Wikipedia: Eight queens puzzle ) maar in het kort gaat het erom dat je 8 (N) koninginnen neerzet op een bord van 8x8 (NxN).

Een 'naive' manier om dit op te lossen is gewoon een int[][] maken om het bord voor te stellen. Nu geeft wikipedia echter aan dat een logisch slimmere manier is om het bord te representeren door een enkele int[]. Immers kunnen er geen 2 koninginnen naast elkaar staan.

Een kongining die hier staat:
|...|...|...|x|......
wordt dus weergegeven als int[rijnummer] = 3; (3 is het kolomnummer in dit geval).

Dit werkt erg goed en op deze manier zijn er minder 'collision checks' nodig en is het allemaal wat aardiger voor het werkgeheugen. (ook al ga ik depth first).

Maar nu komt het echte probleem: op deze manier krijg je voor 8 koningingen op een 8x8 bord 92 verschillende oplossingen. Maar van deze 92 oplossingen zijn er nog 80 te maken door de echte unieke 12 te roteren of te spiegelen.

Spiegelen is vrij simpel op een 1 dimensionale array en had ik snel werkend.

Maar ik krijg het niet voor elkaar om een algoritme te bedenken wat een schaakbord een kwartslag kan draaien zonder dat ik de representatie via een int[] eerst weer omzet naar een int[][] dan draai en dan weer terug zet.

Heeft iemand hier misschien een tip voor? Ik heb al flink wat uren gespit door code van andere, maar het blijft allemaal bij voorbeeld code om de 92 te vinden en het roteren en spiegelen wordt niet gedaan. (Ik heb wel 1 oplossing gezien die er dus inderdaad weer een multidimensionale array van maakt, maar dat schiet dus ook niet op).

Is hier een handige oplossing voor? Of moet ik het toch omzetten naar een multi en dan weer terug naar een enkele?

[UltimateB]

Door alle arrays lopen en dan nieuwe arrays maken gesorteerd op de hoeveelste in de eerste arrays

aInt[1]
aInt2[1]
aInt3[1]
aInt4[1]
aInt5[1]
aInt6[1]
aInt7[1]
aInt8[1] => aIntNew1[]

[roy-t]

Ik snap je notatie niet helemaal maar volgens mij bedoel je?

Java:

int[] board, int[]original //original is de ingevoerde array die geroteerd moet worden
for(int i = 0; i < queens; i++){
  board[original[i]] = i;
}
return board;

Die code werkt wel maar dan roteer je de array in 1x 180graden opv 90graden waardoor je niet alle rotaties kan krijgen.

[Soultaker]

Je moet natuurlijk eerst bedenken welke transformatie je uit wil voeren. Je hebt een aantal punten (van de vorm (r,c) voor rij/kolom) in het eerste kwadrant (dus 0 <= r,c < 8, of eventueel 0 < r,c <= 8 als je 1-gebaseerd rekent). Daarbij is het van belang dat je van een set punten die precies één punt per rij heeft, transformeert naar een set punten die dat ook heeft, anders kun je je datastructuur niet aanhouden.

Om te roteren om de oorsprong transformeer je coordinaten bijvoorbeeld van (r,c) naar (c,-r) maar dan liggen de coordinaten in het tweede kwadrant; die wil je terugtransleren naar het eerste kwadrant, dus dan wordt 't bijvoorbeeld (r,c) => (c,-r+7). Dit had je waarschijnlijk al gevonden.

Nu is het allemaal vrij simpel geworden: je hebt een transformatie, een oude array, en een nieuwe array, dus kun je de rotatie simpelweg zo uitvoeren:

Java:

int[] board_old, board_new;
for (int r_old = 0; r_old < queens; r_old++)
{
  int c_old = board_old[r_old];

  // Oude punt is (r_old,c_old); bereken nieuwe punt (r_new,c_new)
  int r_new = c_old;
  int c_new = -r_old + 7;

  // Getransformeerd punt opslaan
  board_new[r_new] = c_new;
}

De code is nodeloos uitgebreid natuurlijk, maar ik wilde het principe duidelijk maken.

offtopic:
Een leuker vraagstuk is: is de rotatie ook in-place uit te voeren (zonder een nieuwe array te maken dus) en zo ja, hoe?

[roy-t]

Soultaker schreef op zaterdag 03 januari 2009 @ 15:37:
Je moet natuurlijk eerst bedenken welke transformatie je uit wil voeren. Je hebt een aantal punten (van de vorm (r,c) voor rij/kolom) in het eerste kwadrant (dus 0 <= r,c < 8, of eventueel 0 < r,c <= 8 als je 1-gebaseerd rekent). Daarbij is het van belang dat je van een set punten die precies één punt per rij heeft, transformeert naar een set punten die dat ook heeft, anders kun je je datastructuur niet aanhouden.

Om te roteren om de oorsprong transformeer je coordinaten bijvoorbeeld van (r,c) naar (c,-r) maar dan liggen de coordinaten in het tweede kwadrant; die wil je terugtransleren naar het eerste kwadrant, dus dan wordt 't bijvoorbeeld (r,c) => (c,-r+7). Dit had je waarschijnlijk al gevonden.

Nu is het allemaal vrij simpel geworden: je hebt een transformatie, een oude array, en een nieuwe array, dus kun je de rotatie simpelweg zo uitvoeren:

Java:

int[] board_old, board_new;
for (int r_old = 0; r_old < queens; r_old++)
{
  int c_old = board_old[r_old];

  // Oude punt is (r_old,c_old); bereken nieuwe punt (r_new,c_new)
  int r_new = c_old;
  int c_new = -r_old + 7;

  // Getransformeerd punt opslaan
  board_new[r_new] = c_new;
}

De code is nodeloos uitgebreid natuurlijk, maar ik wilde het principe duidelijk maken.

offtopic:
Een leuker vraagstuk is: is de rotatie ook in-place uit te voeren (zonder een nieuwe array te maken dus) en zo ja, hoe?

Ah ik denk dat ik daar op vast liep, ik heb toevallig net 5min voordat ik je post zag deze code gemaakt die volgens mij precies het zelfde doet:

Java:

 public static int[] RotateBoard(int[] original){
        int[] board = new int[original.length];
        for(int i = 0; i < original.length; i++){
            board[original[i]] = original.length -1 - i;
        }
        return board;
    }

Hardstikke bedankt! Ik liep er op een of andere manier telkens op vast, ondanks dat dit niet het meest ingewikkelde stuk van het probleem is! .

Of de bewerking in order kan vraag ik me sterk af aangezien je dan original[original[i]] = original.length -1 -i; krijgt waardoor je dus een andere original[] overschrijft en je niet zeker weet of je die al gehad hebt.

[Soultaker]

Ah mooi, dat komt inderdaad op hetzelfde neer.

Of de bewerking in order kan vraag ik me sterk af aangezien je dan original[original[i]] = original.length -1 -i; krijgt waardoor je dus een andere original[] overschrijft en je niet zeker weet of je die al gehad hebt.

Ik denk dat 't juist wel kan als je de translatie pas op het einde doet, want dan kun je wél zien of je punten al gehad hebt. De code wordt natuurlijk compleet onbegrijpelijk zonder documentatie, dus ik het absoluut niet als serieuze suggestie poneren, maar het is wel een leuk puzzeltje.

spoiler:

http://pastebin.com/f32643c90

_{Grmbl, geen code tags in spoilers op GoT?!}

[ Voor 8% gewijzigd door Soultaker op 03-01-2009 18:53 ]

[MrBucket]

roy-t schreef op zaterdag 03 januari 2009 @ 14:42:
Nu geeft wikipedia echter aan dat een logisch slimmere manier is om het bord te representeren door een enkele int[]. Immers kunnen er geen 2 koninginnen naast elkaar staan.

Dit werkt erg goed en op deze manier zijn er minder 'collision checks' nodig en is het allemaal wat aardiger voor het werkgeheugen. (ook al ga ik depth first).

Ik denk dat je op het verkeerde punt aan het optimaliseren bent. Er vanuitgaande dat je met 8 queens werkt (n=8) zul je vanwege depth-first search max 8 states tegelijk in je geheugen hebben staan. Zelfs voor N=100 is dit geheugengebruik miniem.

Echter, het aantal mogelijke configuraties is wel een probleem: als je 1 queen per kolom hanteert, dan zijn er nog altijd 8⁸ = 2²⁴ = ong. 16,7 miljoen mogelijke configuraties. Mijn advies zou dus zijn om te kiezen voor de representatie van een bord die het makkelijkst te analyseren is: een gewone 8x8 array.

Dan: een backtracking-algoritme zal je gegarandeerd een oplossing geven, maar niet op de snelst mogelijke manier. Een heuristiek die in Fundamentals of Algorithmics wordt gegeven is de volgende, een zgn. Las Vegas algoritme wat niet altijd een resultaat kan geven, maar door het net zo lang opnieuw uit te voeren totdat het wel een resultaat geeft, toch sneller is dan een backtracking-aanpak:

Voor kolommen 1 t/m 5, plaats een queen op een willekeurige rij die nog "vrij" is, d.w.z. waar de queen niet geslagen kan worden. Als men niet tot de 5e kolom kan komen (omdat op alle rijen van de huidige kolom de queen geslagen kan worden), dan begin je helemaal overnieuw.

Als je eenmaal de queen op de 5e kolom hebt kunnen plaatsen, dan ga je voor kolommen 6 t/m 8 wel een volledige state space search doen (i.e.: backtracken, maar niet verder terug dan de eerste 5 kolommen).

Dit werkt als een tierelier, ik heb 'm zelf uitgeprobeerd bij N=100 en state space search pas vanaf (ik meen) kolom 75 of 80, ik geloof dat ik binnen 5 seconden een antwoord had

[beelie]

algemeen vraagje: waarom los je het probleem (x queens) niet in prolog?
dan krijg je direct alle oplossingen vanwege de backtracking...

[Stefan_D]

beelie schreef op maandag 05 januari 2009 @ 01:37:
algemeen vraagje: waarom los je het probleem (x queens) niet in prolog?
dan krijg je direct alle oplossingen vanwege de backtracking...

Omdat dit betreffende probleem voor het vak Orientatie Informatica is en de taal waarmee we werken Java is.

[roy-t]

MrBucket schreef op zaterdag 03 januari 2009 @ 23:09:
[...]

Ik denk dat je op het verkeerde punt aan het optimaliseren bent. Er vanuitgaande dat je met 8 queens werkt (n=8) zul je vanwege depth-first search max 8 states tegelijk in je geheugen hebben staan. Zelfs voor N=100 is dit geheugengebruik miniem.

Echter, het aantal mogelijke configuraties is wel een probleem: als je 1 queen per kolom hanteert, dan zijn er nog altijd 8⁸ = 2²⁴ = ong. 16,7 miljoen mogelijke configuraties. Mijn advies zou dus zijn om te kiezen voor de representatie van een bord die het makkelijkst te analyseren is: een gewone 8x8 array.

Dan: een backtracking-algoritme zal je gegarandeerd een oplossing geven, maar niet op de snelst mogelijke manier. Een heuristiek die in Fundamentals of Algorithmics wordt gegeven is de volgende, een zgn. Las Vegas algoritme wat niet altijd een resultaat kan geven, maar door het net zo lang opnieuw uit te voeren totdat het wel een resultaat geeft, toch sneller is dan een backtracking-aanpak:

Voor kolommen 1 t/m 5, plaats een queen op een willekeurige rij die nog "vrij" is, d.w.z. waar de queen niet geslagen kan worden. Als men niet tot de 5e kolom kan komen (omdat op alle rijen van de huidige kolom de queen geslagen kan worden), dan begin je helemaal overnieuw.

Als je eenmaal de queen op de 5e kolom hebt kunnen plaatsen, dan ga je voor kolommen 6 t/m 8 wel een volledige state space search doen (i.e.: backtracken, maar niet verder terug dan de eerste 5 kolommen).

Dit werkt als een tierelier, ik heb 'm zelf uitgeprobeerd bij N=100 en state space search pas vanaf (ik meen) kolom 75 of 80, ik geloof dat ik binnen 5 seconden een antwoord had

Door het weer te geven als een enkele int[] kun je nog veel meer optimalisren, ik heb eerst ook een boolean[][] gehad, maar dit is significant langzamer dan een enkele int[]. Onder andere collision checks zijn veel sneller in een int[] omdat je dicht bij je data blijft en minder collisions hoeft te controleren.

Ook het roteren gaat nu lekker snel.

In Prolog zou dit probleem inderdaad in een paar regels op te lossen zijn, maar het was inderdaad voor het vok OrInf waar we percee met java moeten programmeren.

Inmiddels draait het hele programme trouwens prima en voor de standaard situatie (n=8) is de uitvoer 'direct' klaar.