szúdoku
Kiejtés
- IPA: [ ˈsuːdoku]
Főnév
szúdoku
- (matematika) Logikai játék, amelyben megadott szabályok szerint számjegyeket kell elhelyezni egy táblázatban.
Sudoku: Szabályok, Adatstruktúra, Algoritmus, Solver
1. Szabályok
- Cél: Egy 9x9-es rácsot kell kitölteni 1-től 9-ig terjedő számokkal úgy, hogy:
- Minden sorban minden szám egyszer szerepeljen.
- Minden oszlopban minden szám egyszer szerepeljen.
- Minden 3x3-as blokkban minden szám egyszer szerepeljen.
- Az induló tábla tartalmaz néhány előre kitöltött számot, amelyek fixek és nem módosíthatók.
2. Adatstruktúra
Tábla reprezentáció:
A tábla egy kétdimenziós lista formájában tárolható: - 0 jelöli az üres mezőket. - Az 1-től 9-ig terjedő számok jelölik a kitöltött mezőket.
Példa:
board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
3. Algoritmus
A Sudoku megoldásának legismertebb algoritmusa a Backtracking: - Lépések: 1. Keress egy üres mezőt a táblán. 2. Próbálj meg egy számot elhelyezni az üres mezőbe (1-től 9-ig). 3. Ellenőrizd, hogy a szám megfelel-e a Sudoku szabályainak. 4. Ha a szám érvényes, folytasd a következő mezővel. 5. Ha egy szám sem érvényes, lépj vissza az előző mezőhöz, és próbáld ki a következő számot. 6. Ismételd, amíg a tábla meg nem oldódik.
4. Pseudocode
function solve(board):
if no_empty_cell(board):
return True
row, col = find_empty_cell(board)
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve(board):
return True
board[row][col] = 0 # Backtrack
return False
function is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
block_row = row // 3 * 3
block_col = col // 3 * 3
for i in range(block_row, block_row + 3):
for j in range(block_col, block_col + 3):
if board[i][j] == num:
return False
return True
5. Python implementáció
def print_board(board):
for row in board:
print(" ".join(str(num) if num != 0 else '.' for num in row))
print()
def find_empty_cell(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return i, j
return None
def is_valid(board, row, col, num):
# Ellenőrzi a sort
if num in board[row]:
return False
# Ellenőrzi az oszlopot
if num in [board[i][col] for i in range(9)]:
return False
# Ellenőrzi a 3x3-as blokkot
block_row, block_col = row // 3 * 3, col // 3 * 3
for i in range(block_row, block_row + 3):
for j in range(block_col, block_col + 3):
if board[i][j] == num:
return False
return True
def solve_sudoku(board):
empty_cell = find_empty_cell(board)
if not empty_cell:
return True
row, col = empty_cell
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if solve_sudoku(board):
return True
board[row][col] = 0 # Backtrack
return False
# Példa tábla
board = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
print("Eredeti tábla:")
print_board(board)
if solve_sudoku(board):
print("Megoldott tábla:")
print_board(board)
else:
print("Nincs megoldás!")
6. C++ implementáció
#include <iostream>
using namespace std;
const int SIZE = 9;
bool isValid(int board[SIZE][SIZE], int row, int col, int num) {
// Ellenőrzi a sort és oszlopot
for (int i = 0; i < SIZE; i++) {
if (board[row][i] == num || board[i][col] == num) {
return false;
}
}
// Ellenőrzi a 3x3-as blokkot
int blockRow = (row / 3) * 3;
int blockCol = (col / 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[blockRow + i][blockCol + j] == num) {
return false;
}
}
}
return true;
}
bool solveSudoku(int board[SIZE][SIZE]) {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
if (board[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (isValid(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) {
return true;
}
board[row][col] = 0; // Backtrack
}
}
return false;
}
}
}
return true;
}
void printBoard(int board[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
}
int main() {
int board[SIZE][SIZE] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
cout << "Eredeti tábla:" << endl;
printBoard(board);
if (solveSudoku(board)) {
cout << "Megoldott tábla:" << endl;
printBoard(board);
} else {
cout << "Nincs megoldás!" << endl;
}
return 0;
}
Ezek a megoldások egy egyszerű Backtracking algoritmust implementálnak, amely működőképes a legtöbb Sudoku puzzle esetén. Ha gyorsabb megoldásra van szükséged, fejlettebb technikák, például Constraint Propagation vagy Dancing Links használható.