Programowanie

Odwrotna Notacja Polska (ONP) – Jest to sposób zapisu wyrażeń matematycznych, który między innymi eliminuje potrzebę nawiasów do określania kolejności operacji, co sprawia, że jest idealny do użycia w programowaniu i analizie danych. Ta metoda, choć może wydawać się nieintuicyjna na pierwszy rzut oka, oferuje szereg zalet w obliczeniach i implementacji algorytmów.

Odwrotna Notacja Polska – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Odwrotna Notacja Polska?
• Jak się oblicza Odwrotną Notację Polską?
• Jakie ma zastosowanie Odwrotna Notacja Polska?
• Jak w Javie wygląda implementacja ONP?

Odwrotna Notacja Polska – historia

Odwrotna Notacja Polska (ONP), znana także jako notacja postfiksowa, została wprowadzona przez australijskiego naukowca Charlesa Leonarda Hamblina w latach 50. XX wieku. Metoda ta jest odmianą notacji polskiej, wynalezionej przez polskiego logika Jana Łukasiewicza w 1924 roku, która używa formatu prefiksowego, gdzie operator jest umieszczany przed operandami (np. + 3 4). W przeciwieństwie do tego ONP umieszcza operator po operandach (np. 3 4 +).

Odwrotna Notacja Polska – jak to obliczyć?

Aby obliczyć wyrażenie zapisane w notacji postfiksowej, wykonujesz kroki w kolejności, używając stosu:

• Umieść Operand na Stosie: Każdą liczbę umieszczasz na stosie, gdy ją napotkasz.
• Wykonaj Operację: Gdy napotkasz operator, zdejmujesz ze stosu odpowiednią liczbę operandów (zwykle dwa dla binarnych operatorów jak +, –, *, /), wykonujesz operację, a wynik z powrotem umieszczasz na stosie.
• Wynik Końcowy: Po przetworzeniu całego wyrażenia, na stosie pozostaje jedna wartość — wynik końcowy operacji.

➡ ZOBACZ 👉: Stos (Stack)

Odwrotna Notacja Polska – rozwiązanie

Aby rozwiązać wyrażenie w Odwrotnej Notacji Polskiej (ONP) 2 3 * 4 5 * +, postępujemy zgodnie z regułami obliczania, używając stosu do przechowywania tymczasowych wyników. Oto kroki:

1. Umieść 2 na stosie:
   • Stos: [2]
2. Umieść 3 na stosie:
   • Stos: [2, 3]
3. Napotykasz operator * (mnożenie), więc zdejmujesz dwa ostatnie liczby ze stosu (3 i 2), mnożysz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 2 * 3 = 6
   • Stos: [6]
4. Umieść 4 na stosie:
   • Stos: [6, 4]
5. Umieść 5 na stosie:
   • Stos: [6, 4, 5]
6. Napotykasz kolejny operator * (mnożenie), więc znowu zdejmujesz dwa ostatnie liczby ze stosu (5 i 4), mnożysz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 4 * 5 = 20
   • Stos: [6, 20]
7. Napotykasz operator + (dodawanie), więc zdejmujesz dwa ostatnie liczby ze stosu (20 i 6), sumujesz je i wynik umieszczasz z powrotem na stosie:
   • Operacja: 6 + 20 = 26
   • Stos: [26]

Wynik Końcowy

Na stosie pozostaje jedna liczba, 26, która jest wynikiem końcowym wyrażenia 2 3 * 4 5 * +.

To samo działanie zapisane w zwyczajnej notacji, jaką znamy ze szkoły (infiksowej) wygląda następująco: (2*3) + (4*5).

Odwrotna Notacja Polska – przykłady

Oto kilka przykładów zapisu wyrażeń.

Dodawanie i odejmowanie

notacja infiksowa: 3 + 4 − 53 + 4 − 5

⇒🇵🇱 notacja postfiksowa: 3 4 − 53 + 4 − 5 +

Mnożenie i dzielenie

notacja infiksowa: 3 * 7 * 2 / 3

⇒🇵🇱 notacja postfiksowa: 3 7 * 2 * 3 /

Wyrażenie złożone

notacja infiksowa: (3 + 4) * 5(3 + 4) * 5 / 5 – 25

⇒🇵🇱 notacja postfiksowa: 3 4 + 5 * 3 4 + * 5 * 5 / 25 –

Odwrotna Notacja Polska – zastosowanie

Odwrotna Notacja Polska (ONP), choć wydaje się być abstrakcyjnym pojęciem matematycznym, znajduje szerokie zastosowanie w praktyce i w biznesie, przede wszystkim dzięki swojej efektywności i prostocie implementacji w systemach komputerowych.

Kalkulatory i narzędzia obliczeniowe

Wiele kalkulatorów naukowych wykorzystuje ONP, ponieważ pozwala to na szybsze przetwarzanie skomplikowanych wyrażeń matematycznych bez błędów wynikających z niewłaściwego użycia nawiasów. Przykładem może być popularny kalkulator HP-12C, używany przez inżynierów i finansistów.

Programowanie i rozwój oprogramowania

• Parsowanie Wyrażeń: W programowaniu często potrzebne jest przetwarzanie i ocena wyrażeń wprowadzanych przez użytkownika. Implementacja parserów wykorzystujących ONP jest prostsza i mniej podatna na błędy, co jest szczególnie przydatne w aplikacjach wymagających dynamicznego obliczania wyrażeń matematycznych.
• Kompilatory i Interpretery: ONP jest używana w kompilatorach i interpreterach języków programowania do oceny wyrażeń. Ponieważ operacje są wykonywane zgodnie z kolejnością występowania, bez potrzeby analizowania nawiasów, proces ten jest bardziej wydajny.

Nauka algorytmów

ONP jest także cennym narzędziem dydaktycznym w nauczaniu algorytmiki i struktur danych, szczególnie w kontekście stosów i kolejek, które są fundamentem dla notacji postfiksowej.

Odwrotna Notacja Polska – implementacja

Implementacja Odwrotnej Notacji Polskiej (ONP) w Javie wymaga użycia stosu do przechowywania operandów i efektywnego przetwarzania operatorów. Poniżej znajdziesz przykładowy kod, który przetwarza wyrażenie w notacji postfiksowej i oblicza jego wynik. Przykład koncentruje się na podstawowych operacjach arytmetycznych: dodawaniu, odejmowaniu, mnożeniu i dzieleniu.

class ReversePolishNotation {
    public static int evaluatePostfix(String expression) {
        Stack<Integer> stack = new Stack<>();
        // Przetwarzanie każdego elementu w ciągu wejściowym rozdzielonego spacjami
        String[] tokens = expression.split(" ");

        for (String token : tokens) {
            // Jeśli element jest liczbą, zapisz go na stosie
            if (token.matches("\\d+")) { // Regex do sprawdzania, czy token jest liczbą
                stack.push(Integer.parseInt(token));
            } else { // Token jest operatorem
                // Operator wymaga pobrania dwóch ostatnich liczb ze stosu
                int num2 = stack.pop();
                int num1 = stack.pop();

                switch(token.charAt(0)) { // Zakładamy, że operator to pojedynczy znak
                    case '+':
                        stack.push(num1 + num2);
                        break;
                    case '-':
                        stack.push(num1 - num2);
                        break;
                    case '*':
                        stack.push(num1 * num2);
                        break;
                    case '/':
                        if (num2 != 0)
                            stack.push(num1 / num2);
                        else
                            throw new UnsupportedOperationException("Division by zero.");
                        break;
                }
            }
        }
        return stack.pop(); // Wynik końcowy znajduje się na szczycie stosu
    }

    public static void main(String[] args) {
        String expression = "2 3 * 4 5 * +"; // operandy należy odzielić od siebie spacją aby były poprawnie odczytane przez program

        int result = evaluatePostfix(expression);
        System.out.println("The result of the expression is: " + result);
    }
}

Stos jest idealny do tego zadania, ponieważ pozwala łatwo dodać i usunąć elementy w odpowiedniej kolejności. Przechodzimy przez każdy znak w wyrażeniu. Jeżeli znak jest cyfrą, przekształcamy go z char na int (odejmując wartość ‘0’ od kodu znaku) i umieszczamy na stosie. Jeśli napotkamy operator, zdejmujemy dwie ostatnie liczby ze stosu, wykonujemy operację i wynik wrzucamy z powrotem na stos. Obsługiwane operacje to dodawanie (+), odejmowanie (-), mnożenie (*) i dzielenie (/). Dzielenie przez zero jest tu wyraźnie obsłużone jako wyjątek.

Odwrotna Notacja Polska – konwerter

Konwerter z Notacji Infiksowej na Postfiksową

class InfixToPostfix {

    // Metoda zwracająca priorytet operatora
    private static int getPriority(char operator) {
        if (operator == '+' || operator == '-') {
            return 1;
        }
        if (operator == '*' || operator == '/') {
            return 2;
        }
        return 0;
    }

    // Metoda konwertująca wyrażenie infiksowe na postfiksowe
    public static String convertToPostfix(String infix) {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        boolean expectOperand = true;  // Dodane do sprawdzania, czy oczekujemy na operand

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            if (Character.isDigit(c)) {
                postfix.append(c);
                if (i + 1 < infix.length() && Character.isDigit(infix.charAt(i + 1))) {
                    continue;
                } else {
                    postfix.append(' ');
                }
                expectOperand = false;  // Po dodaniu liczby oczekujemy operatora
            } else if (c == '(') {
                stack.push(c);
                expectOperand = true;  // Po '(' oczekujemy kolejnego operandu
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop());
                    postfix.append(' ');
                }
                if (stack.isEmpty()) {
                    throw new IllegalArgumentException("Mismatched parentheses in the expression.");
                }
                stack.pop();
                expectOperand = false;  // Po ')' oczekujemy operatora
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                if (expectOperand) {
                    throw new IllegalArgumentException("Missing operand before operator " + c);
                }
                while (!stack.isEmpty() && getPriority(c) <= getPriority(stack.peek())) {
                    postfix.append(stack.pop());
                    postfix.append(' ');
                }
                stack.push(c);
                expectOperand = true;  // Po operatorze oczekujemy kolejnego operandu
            }
        }

        while (!stack.isEmpty()) {
            if (stack.peek() == '(') {
                throw new IllegalArgumentException("Mismatched parentheses in the expression.");
            }
            postfix.append(stack.pop());
            postfix.append(' ');
        }
        if (expectOperand && !postfix.toString().trim().isEmpty()) {
            throw new IllegalArgumentException("Missing operand at the end of expression.");
        }

        return postfix.toString().trim();
    }
}

Metoda pomocnicza getPriority() określa priorytet operatorów matematycznych, co jest kluczowe do zarządzania kolejnością operacji podczas konwersji. Każdy znak w wyrażeniu infiksowym jest przetwarzany w pętli. Cyfry są dodawane bezpośrednio do postfix. Aby obsłużyć liczby wielocyfrowe, kod sprawdza, czy następny znak to również cyfra, zanim doda spację.

Nawiasy Otwierające ‘(’: Są umieszczane na stosie, aby wskazać początek subwyrażenia. Nawiasy Zamykające ‘)’: Powodują opróżnienie stosu z operatorów aż do napotkania nawiasu otwierającego, który jest usuwany. Operatory: Jeśli operator ma niższy lub równy priorytet do operatora na wierzchu stosu, operatory są ściągane ze stosu do wyniku. Następnie bieżący operator jest umieszczany na stosie.

Po przejściu przez wszystkie znaki, wszystkie pozostałe operatory na stosie są ściągane do wynikowego wyrażenia postfiksowego. Sprawdzanie Nawiasów: Rzuca wyjątek IllegalArgumentException, gdy nawiasy są niezbalansowane (np. brakujący ‘(’ lub ‘)’). Sprawdzanie Oczekiwanych Operandów: Rzuca wyjątek, gdy przed operatorem nie ma odpowiedniego operandu lub gdy oczekiwano na operand na końcu wyrażenia.

Konwerter z Notacji Postfiksowej na Infiksową

class PostfixToInfix {
    // Klasa pomocnicza do przechowywania wyrażeń wraz z ich priorytetem operacyjnym
    static class Expression {
        String expr;
        int precedence;

        public Expression(String expr, int precedence) {
            this.expr = expr;
            this.precedence = precedence;
        }
    }

    // Metoda zwracająca priorytet operatora
    private static int precedenceOf(char operator) {
        if (operator == '+' || operator == '-') return 1;
        if (operator == '*' || operator == '/') return 2;
        return -1;
    }

    // Metoda konwertująca wyrażenie postfiksowe na infiksowe
    public static String convertToInfix(String postfix) throws IllegalArgumentException {
        Stack<Expression> stack = new Stack<>();
        String[] tokens = postfix.split("\\s+");

        for (String token : tokens) {
            if (token.matches("\\d+")) { // Sprawdza, czy token jest liczbą
                stack.push(new Expression(token, 3));
            } else if (token.matches("[+\\-*/]")) { // Sprawdza, czy token jest operatorem
                if (stack.size() < 2) { // Sprawdza, czy na stosie są co najmniej dwa elementy
                    throw new IllegalArgumentException("Invalid Expression: Not enough operands for " + token);
                }
                Expression right = stack.pop();
                Expression left = stack.pop();

                int opPrecedence = precedenceOf(token.charAt(0));
                String leftExpr = left.expr;
                if (left.precedence < opPrecedence) {
                    leftExpr = "(" + left.expr + ")";
                }

                String rightExpr = right.expr;
                if (right.precedence < opPrecedence) {
                    rightExpr = "(" + right.expr + ")";
                }

                stack.push(new Expression(leftExpr + " " + token + " " + rightExpr, opPrecedence));
            }
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid Expression: Mismatched operands and operators");
        }
        return stack.pop().expr; // Zwrócenie ostatniego wyrażenia ze stosu jako wynik
    }
}

Metoda convertToInfix() konwertuje wyrażenie postfiksowe na infiksowe. Wyrażenie postfiksowe jest dzielone na tokeny (liczby i operatory), które są przetwarzane jeden po drugim. Wyrażenie postfiksowe jest rozdzielane na tokeny (elementy), które są następnie przetwarzane jeden po drugim.

Dla każdego tokenu sprawdzane jest, czy jest to operand (liczba) czy operator (+, -, *, /). Gdy napotykany jest operator, zdejmowane są dwa ostatnie wyrażenia ze stosu, a następnie łączone zgodnie z priorytetem operacji. Jeśli priorytet operacji jest wyższy niż priorytet wyrażeń, dodawane są nawiasy do tych wyrażeń, aby zachować właściwą kolejność operacji matematycznych. Po przetworzeniu wszystkich tokenów, na stosie powinno zostać tylko jedno wyrażenie, które jest wynikowym wyrażeniem infiksowym.

Jeśli na stosie jest więcej lub mniej niż jedno wyrażenie, rzucony zostaje wyjątek, informujący o błędzie w podanym wyrażeniu postfiksowym.

Odwrotna Notacja Polska – podsumowanie

Odwrotna Notacja Polska oferuje wyjątkową kombinację prostoty, efektywności i szerokiego zakresu zastosowań, czyniąc ją atrakcyjnym rozwiązaniem dla wielu problemów obliczeniowych zarówno w nauce, technologii, jak i biznesie. Jej zdolność do uproszczenia procesów obliczeniowych i minimalizacji potencjalnych błędów sprawia, że jest ceniona w wielu dziedzinach, od edukacji po wysokiej stawki finansowe i techniczne aplikacje.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Wieża Hanoi (ang. Hanoi Tower). To zadanie, choć proste w swojej idei, stanowi doskonałe pole do ćwiczenia umiejętności programistycznych i logicznego myślenia. Zapraszam do zgłębienia tajemnic tej zagadki, która od ponad wieku fascynuje zarówno matematyków, jak i programistów na całym świecie.

Wieża Hanoi – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Wieża Hanoi?
• Jaką naturę ma Wieża Hanoi?
• Jak rozwiązać Wieżę Hanoi?
• Jak Wieżę Hanoi wykorzystuje się w programowaniu?

Wieża Hanoi – jaki jest problem?

Wieża Hanoi to łamigłówka, która najprawdopodobniej powstała w Azji. Natomiast w Europie rozpropagował ją francuski matematyk Édouard Lucas. Zadanie polega na przeniesieniu stosu różnej wielkości dysków z jednego słupka na inny, z wykorzystaniem trzeciego słupka jako pomocniczego, z zachowaniem zasady, że na mniejszym dysku nie może spoczywać dysk większy.

Wieża Hanoi – hierarchiczna natura

Główna zasada Wież Hanoi mówi, że żaden większy dysk nie może spoczywać na mniejszym dysku. Ta reguła wprowadza zależność między dyskami, ustalając hierarchię, w której mniejsze dyski zawsze muszą leżeć na większych, niezależnie od słupka, na którym są umieszczone. Taka organizacja wymaga od gracza strategicznego planowania i przewidywania, jak przeniesienie jednego dysku wpłynie na możliwości przeniesienia innych dysków w przyszłości

Wieża Hanoi – rozwiązanie – algorytm

Rozważmy rozwiązanie problemu dla 3 dysków.

Proces rozwiązywania Wież Hanoi może być opisany następująco:

• Przenieś n-1 dysków na słupek pomocniczy, co pozwala na odsłonięcie największego dysku.

• Przenieś najmniejszy dysk na słupek pomocniczy, a największy dysk na docelowy słupek.

• Teraz największy dysk jest już na swoim miejscu i nie będzie już więcej przenoszony.

• Przenieś n-1 dysków z pomocniczego słupka na docelowy, co kończy proces.

Każdy z tych kroków jest zależny od poprzedniego, tworząc złożoną sieć zależności, która musi być przestrzegana, aby osiągnąć cel.

Możemy obliczyć minimalną liczbę ruchów potrzebnych do rozwiązania zadania za pomocą wzoru 2ⁿ-1.

gdzie n to ilość dysków.

Wieża Hanoi – rekurencyjne podejście

W praktyce rozwiązanie Wież Hanoi opiera się na rekurencyjnym podziale problemu na mniejsze części. Rekurencyjna natura rozwiązania wiąże się bezpośrednio z zależnościami między dyskami. Na przykład, przeniesienie największego dysku (podstawy) na celowy słupek jest możliwe tylko wtedy, gdy wszystkie mniejsze dyski są już na innym, pomocniczym słupku. To z kolei wymaga rozwiązania mniejszego problemu Wież Hanoi dla tych mniejszych dysków na pomocniczym słupku.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Wieża Hanoi – programowanie

Gra w Wieże Hanoi nie tylko rozwija zdolności rekurencyjnego myślenia, ale także uczy strategii i planowania. Jest również świetnym wprowadzeniem do stosów w informatyce, ponieważ dyski można traktować jako elementy stosu, co dodatkowo ilustruje zasady LIFO (Last In, First Out).

➡ ZOBACZ 👉: Stos (Stack) – 7+ tajników implementacji LIFO

Wieża Hanoi – Java

Algorytm, który rozwiązuje łamigłówkę i prezentuje każdy krok rozwiązania.

class HanoiTowers {
    public static void main(String[] args) {
        int numberOfDisks = 8;
        solveHanoi(numberOfDisks, 'A', 'C', 'B');
    }
    public static void solveHanoi(int disk, char start, char end, char auxiliary) {
        if (disk == 1) {
            System.out.println("Przenieś dysk 1 z " + start + " na " + end);
            return;
        }
        solveHanoi(disk - 1, start, auxiliary, end);
        System.out.println("Przenieś dysk " + disk + " z " + start + " na " + end);
        solveHanoi(disk - 1, auxiliary, end, start);
    }
}

Funkcja solveHanoi() Jest to rekurencyjna funkcja, która rozwiązuje problem Wież Hanoi. Przyjmuje cztery parametry: liczbę dysków (disk), oraz oznaczenia słupków: startowego (start), docelowego (end) i pomocniczego (auxiliary). Jeśli jest tylko jeden dysk, funkcja po prostu przenosi dysk bezpośrednio z słupka startowego na docelowy i kończy działanie. W przeciwnym razie przenosi dyski zgodnie z wcześniej omówionymi zasadami.

Kiedy uruchomisz ten program, wyświetlą się instrukcje na konsoli, które pokazują dokładną kolejność ruchów potrzebną do rozwiązania łamigłówki Wież Hanoi dla określonej liczby dysków. Możesz łatwo zmieniać liczbę dysków, modyfikując wartość zmiennej numberOfDisks w funkcji main().

Wieża Hanoi – wizualizacja

Jeśli kod powyżej jest dla Ciebie niewystarczający, to sprawdź rozwiązanie, które dodatkowo wizualizuje w konsoli położenie dysków w trakcie rozwiązywania zadania.

class VisualHanoi {
    private static Stack<Integer>[] towers = new Stack[3];

    public static void main(String[] args) {
        int numberOfDisks = 3;  // Ustaw liczbę dysków tutaj
        setupTowers(numberOfDisks);
        printTowers();
        solveHanoi(numberOfDisks, 0, 2, 1);
    }

    private static void setupTowers(int disks) {
        for (int i = 0; i < 3; i++) {
            towers[i] = new Stack<>();
        }
        for (int disk = disks; disk > 0; disk--) {
            towers[0].push(disk);
        }
    }

    private static void solveHanoi(int disk, int start, int end, int auxiliary) {
        if (disk == 1) {
            towers[end].push(towers[start].pop());
            System.out.println("Przenieś dysk 1 z " + (char) ('A' + start) + " na " + (char) ('A' + end));
            printTowers();
            return;
        }
        solveHanoi(disk - 1, start, auxiliary, end);
        towers[end].push(towers[start].pop());
        System.out.println("Przenieś dysk " + disk + " z " + (char) ('A' + start) + " na " + (char) ('A' + end));
        printTowers();
        solveHanoi(disk - 1, auxiliary, end, start);
    }

    private static void printTowers() {
        System.out.println("A Tower: " + towers[0] + " B Tower: " + towers[1] + " C Tower: " + towers[2]);
        System.out.println("-------------------");
    }
}

UWAGA! Ostrożnie z ilością dysków, no chyba że masz całą wieczność. 🙃

Wieża Hanoi – zastosowanie

Problem Wież Hanoi znajduje zastosowanie w nauce o algorytmach, teorii gier, a nawet w psychologii, badając sposób, w jaki ludzie i maszyny podejmują sekwencyjne decyzje. Powiązany jest również z takimi koncepcjami, jak algorytmy sortowania, przeszukiwanie przestrzeni stanów oraz algorytmy planowania.

Wieża Hanoi – ciekawostka

Rozwiązanie łamigłówki staje się coraz trudniejsze wraz ze wzrostem ilości dysków. W zasadzie nie tyle trudniejsze ponieważ sekwencja ruchów się nie zmienia, co bardziej czasochłonne. Przełożenie wieży z 8 dyskami, zajmuje około 7 minut. Gdy zwiększymy ilość dysków do 30, i poświęcilibyśmy tylko jedną sekundę na przełożenie każdego dysku, zajęłoby nam to 33 lata.

Wieża Hanoi – podsumowanie

Wieża Hanoi to znakomity przykład na to, jak prosty problem matematyczny może być użyty do nauczania kluczowych pojęć informatycznych i programistycznych. Przez próbę rozwiązania tej zagadki, programiści mogą nauczyć się nie tylko rekurencji i stosów, ale również sposobów optymalizacji i efektywnego rozwiązywania problemów. Uczy metody podziału problemów na mniejsze, co jest fundamentalną umiejętnością w programowaniu i inżynierii. Uczy również zarządzania zasobami i przestrzegania określonych ograniczeń, co ma zastosowanie w projektowaniu algorytmów, optymalizacji systemów i wielu innych dziedzinach technicznych.

Sudoku – to gra logiczna, która polega na wypełnieniu siatki 9×9 cyframi tak, aby każda kolumna, każdy wiersz i każdy z dziewięciu kwadratów 3×3 (które razem tworzą większą siatkę 9×9) zawierały wszystkie cyfry od 1 do 9.

Oto podstawowe reguły:

• Podstawowa siatka: Cała gra odbywa się na siatce 9×9, która jest podzielona na 9 mniejszych kwadratów 3×3.
• Cyfry od 1 do 9: Każda cyfra od 1 do 9 musi pojawić się dokładnie raz w każdym wierszu, każdej kolumnie i każdym kwadracie 3×3.
• Jedna cyfra na komórkę: Każda komórka w siatce może zawierać tylko jedną cyfrę.
• Początkowe wskazówki: Gra zaczyna się z pewną liczbą już wypełnionych cyfr (wskazówek), które gracze muszą użyć jako punkt wyjścia.
• Logika, nie, zgadywanie: Rozwiązanie sudoku opiera się wyłącznie na dedukcji i logice. Nie ma potrzeby zgadywania.
• Brak powtórzeń: Cyfra może pojawić się tylko raz w każdym wierszu, kolumnie i kwadracie 3×3.
• Unikalne rozwiązanie: Każda prawidłowo zaprojektowana łamigłówka sudoku ma tylko jedno możliwe rozwiązanie.

Sudoku – przygotowanie planszy

Rozpoczynamy od zdefiniowania planszy jako dwuwymiarowej tablicy liczb całkowitych, gdzie wartość 0 reprezentuje pustą komórkę:

	public static void main(String[] args) {
		int[][] board = {
				{8, 0, 0, 0, 0, 0, 0, 0, 0},
				{0, 0, 3, 6, 0, 0, 0, 0, 0},
				{0, 7, 0, 0, 9, 0, 2, 0, 0},
				{0, 5, 0, 0, 0, 7, 0, 0, 0},
				{0, 0, 0, 0, 4, 5, 7, 0, 0},
				{0, 0, 0, 1, 0, 0, 0, 3, 0},
				{0, 0, 1, 0, 0, 0, 0, 6, 8},
				{0, 0, 8, 5, 0, 0, 0, 1, 0},
				{0, 9, 0, 0, 0, 0, 4, 0, 0}
		};

		printBoard(board);
	}

	private static void printBoard(int[][] board) {
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.print("\n");
		}
		System.out.println();
	}

Sudoku java przykład

Sudoku – rozwiązanie

Kluczową częścią algorytmu jest metoda solve(), która rekurencyjnie przeszukuje możliwości wypełnienia planszy:

    private boolean solve(int[][] board) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == NO_VALUE) {
                    for (int k = 1; k <= 9; k++) {
                        board[i][j] = k;
                        if (isValid(board, i, j) && solve(board)) {
                            return true;
                        }
                        board[i][j] = NO_VALUE;
                    }
                    return false;
                }
            }
        }
        return true;
    }

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Dla każdej pustej komórki (NO_VALUE), metoda próbuje wstawić każdą możliwą wartość od 1 do 9, sprawdzając za każdym razem, czy nie narusza to zasad sudoku przy użyciu metody isValid().

Sudoku – walidacja

    private boolean isValid(int[][] board, int row, int column) {
        return (rowConstraint(board, row)
                && columnConstraint(board, column)
                && subsectionConstraint(board, row, column));
    }

Korzystając z pomocniczych metod, algorytm weryfikuje, czy dane umieszczenie liczby nie powoduje konfliktów.

Sudoku – pomocnicze metody walidacyjne

    private boolean rowConstraint(int[][] board, int i) {
        boolean[] constraint = new boolean[SIZE];
        return IntStream.range(1, 9)
                .allMatch(column -> checkConstraint(board, i, constraint, column));
    }

    private boolean columnConstraint(int[][] board, int j) {
        boolean[] constraint = new boolean[SIZE];
        return IntStream.range(1, 9)
                .allMatch(row -> checkConstraint(board, row, constraint, j));
    }

    private boolean subsectionConstraint(int[][] board, int i, int j) {
        boolean[] constraint = new boolean[SIZE];
        int subsectionRowStart = (i / 3) * 3;
        int subsectionRowEnd = subsectionRowStart + 3;

        int subsectionColumnStart = (j / 3) * 3;
        int subsectionColumnEnd = subsectionColumnStart + 3;

        for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
            for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
                if (!checkConstraint(board, r, constraint, c)) return false;
            }
        }
        return true;
    }

Metody takie jak rowConstraint() i columnConstraint() używają strumieni IntStream do sprawdzania, czy każda liczba w danym wierszu lub kolumnie jest unikalna. Z kolei metoda subsectionConstraint() odpowiada za weryfikację małych kwadratów 3×3.

Sudoku – optymalizacja sprawdzania

    boolean checkConstraint(int[][] board, int i, boolean[] constraint, int j) {
        if (board[i][j] != NO_VALUE) {
            if (!constraint[board[i][j] - 1]) {
                constraint[board[i][j] - 1] = true;
            } else {
                return false;
            }
        }
        return true;
    }

Metoda checkConstraint() zapewnia, że wstawiona liczba nie powtarza się już w danym kontekście (wiersz, kolumna, kwadrat 3×3).

Sudoku – wizualizacja rozwiązania

    private void printBoard(int[][] board) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
        System.out.println();
    }

Choć algorytm zwraca wartość logiczną wskazującą, czy znaleziono rozwiązanie, dla lepszego zrozumienia procesu warto również wyświetlić końcową konfigurację planszy.

Sudoku – podsumowanie

Wyżej przedstawiony algorytm, jest potężnym narzędziem, które przez systematyczne próbowanie i eliminowanie możliwości, pozwala znaleźć prawidłowe rozwiązanie łamigłówki. Tutaj istotna jest dokładna walidacja każdego ruchu zgodnie z zasadami sudoku oraz rekurencyjne szukanie rozwiązania, które spełnia wszystkie ograniczenia. Mimo że algorytm ten jest skuteczny, istnieje wiele możliwości jego optymalizacji, na przykład poprzez wprowadzenie bardziej zaawansowanych technik eliminacji i sprawdzania możliwości, co może znacząco przyspieszyć proces znajdowania rozwiązania.

➡ ZOBACZ 👉: StormIT | Oferta