Algorytmalgorytm z nawrotamiAlgorytm, którego użyjemy, jest bardzo prosty. W każdym kroku będziemy umieszczali hetmana w kolejnych kolumnach. Rozpatrzymy umieszczenie go w każdym z wierszy. Jeżeli znajdziemy miejsce, w którym hetman nie atakuje innych hetmanów, przejdziemy do następnego kroku. Jeżeli takiego miejsca nie znajdziemy, cofniemy się do poprzedniej kolumny i spróbujemy znaleźć miejsce dla hetmana w innym wierszu.
Pisanie kodu zaczniemy od zaimportowania biblioteki java.util.Arrays – skorzystamy z niej przy wyświetlaniu wyników. Utworzymy klasę Main (oczywiście w pliku Main.java). Zdefiniujemy ponadto statyczną tablicę zmiennych typu całkowitego – będziemy przechowywać w niej rozwiązania.
Linia 1. import java kropka util kropka Arrays średnik.
Linia 3. public class Main.
Linia 4. otwórz nawias klamrowy.
Linia 5. prawy ukośnik prawy ukośnik Tworzymy tablicę zmiennych typu int aby przechowywać pozycje hetmanów.
Linia 6. static int otwórz nawias kwadratowy zamknij nawias kwadratowy h znak równości new int otwórz nawias kwadratowy 9 zamknij nawias kwadratowy średnik.
import java.util.Arrays;
public class Main
{
// Tworzymy tablicę zmiennych typu int aby przechowywać pozycje hetmanów
static int[] h = new int[9];
Teraz zapiszmy rekurencyjną metodę implementującą algorytm. Będzie ona przyjmowała jedną zmienną typu całkowitego, oznaczającą numer wiersza, w którym umieszczamy hetmana.
Linia 1. static void problemHetmanow otwórz nawias okrągły int numerWiersza zamknij nawias okrągły otwórz nawias klamrowy.
static void problemHetmanow(int numerWiersza) {
Utwórzmy pętle for, która będzie wykonywana osiem razy (ponieważ taka jest długość boku szachownicy).
Linia 1. static void problemHetmanow otwórz nawias okrągły int numerWiersza zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości 8 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
static void problemHetmanow(int numerWiersza) {
for (int i = 1; i <= 8; i++) {
Następnie musimy sprawdzić podane wcześniej warunki. Najpierw sprawdźmy, czy w i‑tej kolumnie nie stoi już hetman. Następnie uniemożliwimy ustawienie hetmanów na ukos.
Linia 1. static void problemHetmanow otwórz nawias okrągły int numerWiersza zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości 8 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. if otwórz nawias okrągły h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 5. prawy ukośnik prawy ukośnik sprawdzamy przecinek czy dane pole jest celem ataku innego hetmana.
Linia 6. boolean atakowane znak równości false średnik.
Linia 7. for otwórz nawias okrągły int z znak równości 1 średnik z otwórz nawias ostrokątny 9 ampersant ampersant wykrzyknik atakowane średnik z plus plus zamknij nawias okrągły.
Linia 8. atakowane znak równości h otwórz nawias kwadratowy z zamknij nawias kwadratowy wykrzyknik znak równości 0 ampersant ampersant otwórz nawias okrągły Math kropka abs otwórz nawias okrągły i minus z zamknij nawias okrągły znak równości znak równości Math kropka abs otwórz nawias okrągły numerWiersza minus h otwórz nawias kwadratowy z zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły średnik.
static void problemHetmanow(int numerWiersza) {
for (int i = 1; i <= 8; i++) {
if (h[i] == 0) {
// sprawdzamy, czy dane pole jest celem ataku innego hetmana
boolean atakowane = false;
for (int z = 1; z < 9 && !atakowane; z++)
atakowane = h[z] != 0 && (Math.abs(i - z) == Math.abs(numerWiersza - h[z]));
Jeżeli zmienna logiczna po wykonaniu wewnętrznej pętli nadal będzie miała wartość false, możemy postawić hetmana na sprawdzanej pozycji. W tym celu ustawimy wartość tablicy h[i] na numerWiersza.
Linia 1. static void problemHetmanow otwórz nawias okrągły int numerWiersza zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości 8 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. if otwórz nawias okrągły h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 5. prawy ukośnik prawy ukośnik sprawdzamy przecinek czy dane pole jest celem ataku innego hetmana.
Linia 6. boolean atakowane znak równości false średnik.
Linia 7. for otwórz nawias okrągły int z znak równości 1 średnik z otwórz nawias ostrokątny 9 ampersant ampersant wykrzyknik atakowane średnik z plus plus zamknij nawias okrągły.
Linia 8. atakowane znak równości h otwórz nawias kwadratowy z zamknij nawias kwadratowy wykrzyknik znak równości 0 ampersant ampersant otwórz nawias okrągły Math kropka abs otwórz nawias okrągły i minus z zamknij nawias okrągły znak równości znak równości Math kropka abs otwórz nawias okrągły numerWiersza minus h otwórz nawias kwadratowy z zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 10. if otwórz nawias okrągły wykrzyknik atakowane zamknij nawias okrągły otwórz nawias klamrowy.
Linia 11. prawy ukośnik prawy ukośnik ustawiamy pozycję i minus tego hetmana.
Linia 12. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości numerWiersza średnik.
static void problemHetmanow(int numerWiersza) {
for (int i = 1; i <= 8; i++) {
if (h[i] == 0) {
// sprawdzamy, czy dane pole jest celem ataku innego hetmana
boolean atakowane = false;
for (int z = 1; z < 9 && !atakowane; z++)
atakowane = h[z] != 0 && (Math.abs(i - z) == Math.abs(numerWiersza - h[z]));
if (!atakowane) {
// ustawiamy pozycję i-tego hetmana
h[i] = numerWiersza;
Jeżeli nie rozmieściliśmy jeszcze wszystkich hetmanów, wywołamy funkcję rekurencyjnie. Jeżeli rozstawiliśmy już wszystkie osiem figur, możemy wypisać zawartość tablicy.
Ustawmy jeszcze wartość h[i] na 0, abyśmy mogli kontynuować szukanie następnych rozwiązań.
Linia 1. static void problemHetmanow otwórz nawias okrągły int numerWiersza zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny znak równości 8 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. if otwórz nawias okrągły h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 5. prawy ukośnik prawy ukośnik sprawdzamy przecinek czy dane pole jest celem ataku innego hetmana.
Linia 6. boolean atakowane znak równości false średnik.
Linia 7. for otwórz nawias okrągły int z znak równości 1 średnik z otwórz nawias ostrokątny 9 ampersant ampersant wykrzyknik atakowane średnik z plus plus zamknij nawias okrągły.
Linia 8. atakowane znak równości h otwórz nawias kwadratowy z zamknij nawias kwadratowy wykrzyknik znak równości 0 ampersant ampersant otwórz nawias okrągły Math kropka abs otwórz nawias okrągły i minus z zamknij nawias okrągły znak równości znak równości Math kropka abs otwórz nawias okrągły numerWiersza minus h otwórz nawias kwadratowy z zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 10. if otwórz nawias okrągły wykrzyknik atakowane zamknij nawias okrągły otwórz nawias klamrowy.
Linia 11. prawy ukośnik prawy ukośnik ustawiamy pozycję i minus tego hetmana.
Linia 12. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości numerWiersza średnik.
Linia 14. prawy ukośnik prawy ukośnik nie postawiliśmy wszystkich hetmanów minus stawiamy kolejnego.
Linia 15. if otwórz nawias okrągły row otwórz nawias ostrokątny 8 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 16. problemHetmanow otwórz nawias okrągły numerWiersza plus 1 zamknij nawias okrągły średnik.
Linia 17. zamknij nawias klamrowy.
Linia 18. prawy ukośnik prawy ukośnik postawiliśmy wszystkie hetmany minus wypisujemy otrzymany wynik.
Linia 19. else otwórz nawias klamrowy.
Linia 20. System kropka out kropka println otwórz nawias okrągły Arrays kropka toString otwórz nawias okrągły Arrays kropka copyOfRange otwórz nawias okrągły h przecinek 1 przecinek h kropka length zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 21. zamknij nawias klamrowy.
Linia 22. prawy ukośnik prawy ukośnik ustawiamy i minus te pole na 0 przecinek po czym próbujemy dalej.
Linia 23. h otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości 0 średnik.
Linia 24. zamknij nawias klamrowy.
Linia 25. zamknij nawias klamrowy.
Linia 26. zamknij nawias klamrowy.
Linia 27. zamknij nawias klamrowy.
static void problemHetmanow(int numerWiersza) {
for (int i = 1; i <= 8; i++) {
if (h[i] == 0) {
// sprawdzamy, czy dane pole jest celem ataku innego hetmana
boolean atakowane = false;
for (int z = 1; z < 9 && !atakowane; z++)
atakowane = h[z] != 0 && (Math.abs(i - z) == Math.abs(numerWiersza - h[z]));
if (!atakowane) {
// ustawiamy pozycję i-tego hetmana
h[i] = numerWiersza;
// nie postawiliśmy wszystkich hetmanów - stawiamy kolejnego
if (row < 8) {
problemHetmanow(numerWiersza + 1);
}
// postawiliśmy wszystkie hetmany - wypisujemy otrzymany wynik
else {
System.out.println(Arrays.toString(Arrays.copyOfRange(h, 1, h.length)));
}
// ustawiamy i-te pole na 0, po czym próbujemy dalej
h[i] = 0;
}
}
}
}
Zauważmy, że program sam zajmuje się wypisywaniem wyników na ekranie – nie są wymagane żadne dodatkowe instrukcje poza funkcją System.out.println().
Na końcu zapisujemy fragment kodu odpowiedzialny za działanie funkcji:
Linia 1. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. problemHetmanow otwórz nawias okrągły 1 zamknij nawias okrągły średnik.
Linia 3. zamknij nawias klamrowy.
Linia 4. zamknij nawias klamrowy.
public static void main(String[] args) {
problemHetmanow(1);
}
}
Słownik
algorytm z nawrotami
algorytm z nawrotami
typ algorytmu, w przypadku którego rozwiązanie zadania powstaje stopniowo, metodą krok po kroku; w przypadku znalezienia drogi nieprowadzącej do rozwiązania następuje powrót do poprzednich kroków i zmiana wcześniej podjętych decyzji