czwartek, lutego 24, 2011

Zdradliwa Java i 8 królowych ;-)

Java bywa zdradliwa ;-)

Przeczytałem dziś o czymś co się zowie problemem 8 królowych, w którym chodzi o to by przedstawić wszystkie możliwe ustawienia 8 królowych na planszy szachowej 8x8 tak by się wzajemnie nie biły.
Przeczytałem też, że to można rozwiązać przez backtracking, a że ostatnio się go nauczyłem :-) to chciałem spróbować nową zabawkę ;-)

Sam kod napisałem w 5, może 10 minut, ale wyniki były złe....
Po blisko godzinie szukania okazało się, że źle wypisywałem wyniki ;-)

Wyniki były w tablicy int[] a, którą próbowałem wypisywać tak:

for (int i:a) {
System.out.print(a[i]+" ");
}


Widzicie błąd? ;-)

Ja nie widziałem ;-)

Kod powinien wyglądać tak:
for (int i:a) {
System.out.print(i+" ");
}


Czyli i będące wartością z tablicy nie powinno być używane jako indeks tej tablicy ;-)

Sam kod rozwiązujący ten problem wygląda tak (cały program :-)):
import java.util.ArrayList;
import java.util.List;

public class EighQueens {

static int count = 0;
static int N = 8;

static void dfsSearch(int[] a, int k) {
if (k==N) {
// solution :-)
System.out.print(++count+": " );
for (int i:a) System.out.print(i+" ");
System.out.println();
return;
}
boolean[] used = new boolean[N];
for (int i=0; i<k; i++) used[a[i]]=true;
List<Integer> c = new ArrayList<Integer>();
o: for (int i=0; i<N; i++) {
if (!used[i]) {
int idx = 1;
for (int j=k-1; j>=0; j--) {
if (a[j]==i-idx) continue o;
if (a[j]==i+idx) continue o;
idx++;
}
c.add(i);
}
}
for (int i:c) {
a[k]=i;
dfsSearch(a, k+1);
}
}

public static void main(String[] args) {
int[] a = new int[N];
dfsSearch(a, 0);
}
}


Przerobiłem go też na JavaScript :-) I działa na tyle żwawo, że nie zarzyna nawet IE [fakt, że 9 bo innych chyba nie mam na laptopie do przetestowania].

Tutaj macie wynik działania skryptu [jak się wykona u was ;-)]:

Jak widać dla 8 królowych na szachownicy 8x8 są 92 rozwiązania :-)

Przy okazji się dowiedziałem, że istnieje maksymalna głębokość rekurencji w JavaScript :-) Dokładniej zaś to maksymalna wielkość stosu, która wynosi 100 i przez to musiałem trochę zmienić program, tak by używał tablicy na kandydatów [wersja Java'owa też to ma i używa do tego listy] bo dzięki temu na stos odkładana jest tylko wartość indeksu [choć możliwe, że sama tablica też, ale ma góra 8 wartości, z indeksem 9, a głębokość to maksymalnie 8, czyli powinno 100 pozycji na stosie wystarczyć :-)].


Podobne postybeta
Java i liczby pierwsze, odsłona druga
Wszystkiemu winne są szybkie komputery ;-)
Jak czytać kod...
Całkujący Dart ;-)
Niecne wykorzystanie refleksji... czyli jak poszukać tekstu w drzewie obiektów? ;-)