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 posty^beta
Spectre powinno działać nawet w Java'ie ;-)
Java i liczby pierwsze, odsłona druga
Sudoku - atak pierwszy ;-)
Całkujący Dart ;-)
Wszystkiemu winne są szybkie komputery ;-)