Sudoku

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 – 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