Sprawdź się

Zadanie 1.4.

Napisz program, który przedstawi rozwiązanie problemu ośmiu hetmanów przy założeniu, że hetman w pierwszej kolumnie znajdzie się w trzecim wierszu. Wykorzystaj w tym celu algorytm z nawrotami, który każdorazowo będzie iterował od pierwszego do ósmego wiersza.

Oczywiście istnieje wiele rozwiązań tak skonstruowanej zagadki, lecz wynikiem będzie to, które wystąpi jako pierwsze. Zastosuj algorytm przedstawiony w postaci liczby kroków w zadaniu 1.2. Został on również przytoczony poniżej:

Lista kroków:

Wybieramy wiersz początkowy, który znajdzie się na pierwszej pozycji ciągu. Możemy wybrać liczby z przedziału <1, 8>.
Jeżeli wszystkie hetmany zostały ustawione, wypisujemy rozwiązanie.
Szukamy wolnego wiersza dla następnej kolumny, która nie jest jeszcze obsadzona. Dobieramy kolejne liczby, zaczynając od wiersza pierwszego, a kończąc na wierszu ósmym.
Jeżeli znaleźliśmy takie pole, sprawdzamy, czy nie dochodzi na nim do bicia z figurami stojącymi już na planszy.
Jeżeli nie znaleźliśmy takiego pola, które jest poza zasięgiem ruchu ustawionych już figur, zdejmujemy hetmana z poprzedniej kolumny i wracamy do kroku trzeciego.
Jeżeli znaleźliśmy pole nieatakowane przez inną figurę, ustawiamy na nim hetmana, a następnie wracamy do kroku drugiego.

Specyfikacja:

Dane:

x – pozycja pierwszego hetmana, liczba całkowita

Wynik:

Program na standardowe wyjście wypisuje 8 liczb naturalnych z zakresu $\langle 1, 8 \rangle$ będącymi numerami wierszy w których należy umieścić hetmany w kolejnych kolumnach.

Pokaż ćwiczenia:

Język C++

Ćwiczenie 1

RA9mAHEXTg5tB

Twoje zadanie: Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.

#include <iostream>
#include <cmath>

using namespace std;

bool hetmany(int* tablica, int x)
{
	// uzupełnij tę funkcję
}

int main()
{
	int* tablica = new int[8];
	tablica[0] = 2;
	hetmany(tablica, 1);

	return 0;
}
@@@
language=cpp17
@@@
Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys
__TF = open(3,'w')
def _pt(t):
    print(str(t), file=__TF)

if sys.stdin.read().strip() == '3 1 7 5 8 2 4 6':
    _pt(0)

Przykładowe rozwiązanie:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny cmath zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. bool bez podkreślnik bicia otwórz nawias okrągły int a przecinek int b przecinek int x przecinek int y zamknij nawias okrągły. Linia 7. otwórz nawias klamrowy. Linia 8. return otwórz nawias okrągły otwórz nawias okrągły a wykrzyknik znak równości x zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły b wykrzyknik znak równości y zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły abs otwórz nawias okrągły a minus x zamknij nawias okrągły wykrzyknik znak równości abs otwórz nawias okrągły b minus y zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 9. zamknij nawias klamrowy. Linia 11. bool czy podkreślnik bezpieczna otwórz nawias okrągły int asterysk tablica przecinek int x zamknij nawias okrągły. Linia 12. otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły x znak równości znak równości 0 zamknij nawias okrągły return true średnik. Linia 15. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny x średnik i plus plus zamknij nawias okrągły. Linia 16. otwórz nawias klamrowy. Linia 17. if otwórz nawias okrągły wykrzyknik bez podkreślnik bicia otwórz nawias okrągły x przecinek tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy przecinek i przecinek tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły return false średnik. Linia 18. zamknij nawias klamrowy. Linia 20. return true średnik. Linia 21. zamknij nawias klamrowy. Linia 23. bool hetmany otwórz nawias okrągły int asterysk tablica przecinek int x zamknij nawias okrągły. Linia 24. otwórz nawias klamrowy. Linia 25. if otwórz nawias okrągły x znak równości znak równości 8 zamknij nawias okrągły. Linia 26. otwórz nawias klamrowy. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny 8 średnik i plus plus zamknij nawias okrągły. Linia 28. otwórz nawias klamrowy. Linia 29. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy plus 1 otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 30. zamknij nawias klamrowy. Linia 31. return true średnik. Linia 32. zamknij nawias klamrowy. Linia 34. for otwórz nawias okrągły int y znak równości 0 średnik y otwórz nawias ostrokątny 8 średnik y plus plus zamknij nawias okrągły. Linia 35. otwórz nawias klamrowy. Linia 36. tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy znak równości y średnik. Linia 38. if otwórz nawias okrągły czy podkreślnik bezpieczna otwórz nawias okrągły tablica przecinek x zamknij nawias okrągły zamknij nawias okrągły. Linia 39. otwórz nawias klamrowy. Linia 40. if otwórz nawias okrągły hetmany otwórz nawias okrągły tablica przecinek x plus 1 zamknij nawias okrągły zamknij nawias okrągły return true średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy. Linia 44. return false średnik. Linia 45. zamknij nawias klamrowy. Linia 47. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 48. otwórz nawias klamrowy. Linia 49. int asterysk tablica znak równości new int otwórz nawias kwadratowy 8 zamknij nawias kwadratowy średnik. Linia 50. tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 2 średnik. Linia 51. hetmany otwórz nawias okrągły tablica przecinek 1 zamknij nawias okrągły średnik. Linia 53. return 0 średnik. Linia 54. zamknij nawias klamrowy.

#include <iostream>
#include <cmath>

using namespace std;

bool bez_bicia(int a, int b, int x, int y)
{
	return ((a != x) && (b != y) && (abs(a - x) != abs(b - y)));
}

bool czy_bezpieczna(int* tablica, int x)
{
	if (x == 0) return true;

	for (int i = 0; i < x; i++)
	{
		if (!bez_bicia(x, tablica[x], i, tablica[i])) return false;
	}

	return true;
}

bool hetmany(int* tablica, int x)
{
	if (x == 8)
	{
		for (int i = 0; i < 8; i++)
		{
			cout << tablica[i] + 1 << " ";
		}
		return true;
	}

	for (int y = 0; y < 8; y++)
	{
		tablica[x] = y;

		if (czy_bezpieczna(tablica, x))
		{
			if (hetmany(tablica, x + 1)) return true;
		}
	}

	return false;
}

int main()
{
	int* tablica = new int[8];
	tablica[0] = 2;
	hetmany(tablica, 1);

	return 0;
}

Język Java

Ćwiczenie 2

RRCIduaE7GpSD

Twoje zadanie: Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] tablica = new int[8];
        tablica[0] = 2;
        hetmany(tablica, 1);
    }
    
    public static void hetmany(int[] tablica) {
        // uzupełnij tę funkcję
    }
    
    // tu napisz dodatkowe funkcje potrzebne do wykonania tego zadania
}
@@@
language=java11
@@@
Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys

__TF = open(3, 'w')


def _pt(t):
    print(str(t), file=__TF)


expected_output = "3 1 7 5 8 2 4 6"
input = sys.stdin.read().strip()
if input == expected_output.strip():
    _pt(0)

Przykładowe rozwiązanie:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class Main otwórz nawias klamrowy. Linia 4. 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 5. int otwórz nawias kwadratowy zamknij nawias kwadratowy tablica znak równości new int otwórz nawias kwadratowy 8 zamknij nawias kwadratowy średnik. Linia 6. tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 2 średnik. Linia 7. hetmany otwórz nawias okrągły tablica przecinek 1 zamknij nawias okrągły średnik. Linia 8. zamknij nawias klamrowy. Linia 10. public static boolean hetmany otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tablica przecinek int x zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. if otwórz nawias okrągły x znak równości znak równości tablica kropka length zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. Arrays kropka stream otwórz nawias okrągły tablica zamknij nawias okrągły kropka forEach otwórz nawias okrągły otwórz nawias okrągły a zamknij nawias okrągły minus zamknij nawias ostrokątny System kropka out kropka print otwórz nawias okrągły otwórz nawias okrągły a plus 1 zamknij nawias okrągły plus cudzysłów cudzysłów zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 13. return true średnik. Linia 14. zamknij nawias klamrowy. Linia 16. for otwórz nawias okrągły int y znak równości 0 średnik y otwórz nawias ostrokątny tablica kropka length średnik y plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy znak równości y średnik. Linia 19. if otwórz nawias okrągły czyFiguraBezpieczna otwórz nawias okrągły x przecinek tablica zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. if otwórz nawias okrągły hetmany otwórz nawias okrągły tablica przecinek x plus 1 zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. return true średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 26. return false średnik. Linia 27. zamknij nawias klamrowy. Linia 29. public static boolean czyFiguraBezpieczna otwórz nawias okrągły int x przecinek int otwórz nawias kwadratowy zamknij nawias kwadratowy tablica zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. if otwórz nawias okrągły x znak równości znak równości 0 zamknij nawias okrągły return true średnik. Linia 32. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny x średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. if otwórz nawias okrągły wykrzyknik bezBicia otwórz nawias okrągły x przecinek tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy przecinek i przecinek tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły return false średnik. Linia 34. zamknij nawias klamrowy. Linia 36. return true średnik. Linia 37. zamknij nawias klamrowy. Linia 39. public static boolean bezBicia otwórz nawias okrągły int a przecinek int b przecinek int x przecinek int y zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. return otwórz nawias okrągły b wykrzyknik znak równości y zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły a wykrzyknik znak równości x zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły Math kropka abs otwórz nawias okrągły a minus x zamknij nawias okrągły wykrzyknik znak równości Math kropka abs otwórz nawias okrągły b minus y zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] tablica = new int[8];
        tablica[0] = 2;
        hetmany(tablica, 1);
    }

    public static boolean hetmany(int[] tablica, int x) {
        if (x == tablica.length) {
            Arrays.stream(tablica).forEach((a) -> System.out.print((a + 1) + " "));
            return true;
        }

        for (int y = 0; y < tablica.length; y++) {
            tablica[x] = y;

            if (czyFiguraBezpieczna(x, tablica)) {
                if(hetmany(tablica, x + 1)) {
                    return true;
                }
            }
        }

        return false;
    }

    public static boolean czyFiguraBezpieczna(int x, int[] tablica) {
        if (x == 0) return true;

        for (int i = 0; i < x; i++) {
            if (!bezBicia(x, tablica[x], i, tablica[i])) return false;
        }

        return true;
    }

    public static boolean bezBicia(int a, int b, int x, int y) {
        return (b != y) && (a != x) && (Math.abs(a - x) != Math.abs(b - y));
    }
}

Język Python

Ćwiczenie 3

R7IoGCWYZgKF4

Twoje zadanie: Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.

def hetmany(tablica, x):
    # uzupełnij tę funkcję


tab = [0] * 8
tab[0] = 2
hetmany(tab, 1)
@@@
language=python37
@@@
Program wypisuje pierwsze znalezione rozwiązanie problemu ośmiu hetmanów dla przypadku, w którym pierwszy hetman został umieszczony w trzecim wierszu pierwszej kolumny.
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys

__TF = open(3,'w')
def _pt(t):
    print(str(t), file=__TF)


expected_output = "3 1 7 5 8 2 4 6"
input = sys.stdin.read().strip()
if input == expected_output.strip():
    _pt(0)

Przykładowe rozwiązanie:

Linia 1. def hetmany otwórz nawias okrągły tablica przecinek x zamknij nawias okrągły dwukropek. Linia 2. rozmiar znak równości len otwórz nawias okrągły tablica zamknij nawias okrągły. Linia 3. if x znak równości znak równości rozmiar dwukropek. Linia 4. for i in tablica dwukropek. Linia 5. print otwórz nawias okrągły i plus 1 przecinek end znak równości apostrof apostrof zamknij nawias okrągły. Linia 6. return True. Linia 8. for y in range otwórz nawias okrągły rozmiar zamknij nawias okrągły dwukropek. Linia 9. tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy znak równości y. Linia 11. if czy podkreślnik bezpieczna otwórz nawias okrągły tablica przecinek x zamknij nawias okrągły dwukropek. Linia 12. if hetmany otwórz nawias okrągły tablica przecinek x plus 1 zamknij nawias okrągły dwukropek. Linia 13. return True. Linia 15. return False. Linia 18. def czy podkreślnik bezpieczna otwórz nawias okrągły tablica przecinek x zamknij nawias okrągły dwukropek. Linia 19. if x znak równości znak równości 0 dwukropek. Linia 20. return True. Linia 22. for i in range otwórz nawias okrągły x zamknij nawias okrągły dwukropek. Linia 23. if not bez podkreślnik bicia otwórz nawias okrągły x przecinek tablica otwórz nawias kwadratowy x zamknij nawias kwadratowy przecinek i przecinek tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły dwukropek. Linia 24. return False. Linia 26. return True. Linia 29. def bez podkreślnik bicia otwórz nawias okrągły a przecinek b przecinek x przecinek y zamknij nawias okrągły dwukropek. Linia 30. return otwórz nawias okrągły a wykrzyknik znak równości x zamknij nawias okrągły and otwórz nawias okrągły b wykrzyknik znak równości y zamknij nawias okrągły and otwórz nawias okrągły abs otwórz nawias okrągły a minus x zamknij nawias okrągły wykrzyknik znak równości abs otwórz nawias okrągły b minus y zamknij nawias okrągły zamknij nawias okrągły. Linia 33. tab znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk 8. Linia 34. tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości 2. Linia 35. hetmany otwórz nawias okrągły tab przecinek 1 zamknij nawias okrągły.

def hetmany(tablica, x):
    rozmiar = len(tablica)
    if x == rozmiar:
        for i in tablica:
            print(i + 1, end=' ')
        return True

    for y in range(rozmiar):
        tablica[x] = y

        if czy_bezpieczna(tablica, x):
            if hetmany(tablica, x + 1):
                return True

    return False


def czy_bezpieczna(tablica, x):
    if x == 0:
        return True

    for i in range(x):
        if not bez_bicia(x, tablica[x], i, tablica[i]):
            return False

    return True


def bez_bicia(a, b, x, y):
    return (a != x) and (b != y) and (abs(a - x) != abs(b - y))


tab = [0] * 8
tab[0] = 2
hetmany(tab, 1)

Symulacja interaktywna

Dla nauczyciela

Zadanie 1.4.