Nenogzar

Untitled

Feb 6th, 2024
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.97 KB | None | 0 0
  1. # N is the size of the 2D matrix N*N
  2. N = 9
  3.  
  4. # Помощна функция за отпечатване на мрежа в посочения формат
  5. def printing(arr):
  6.     print("+-----+-------+-------+")
  7.     for i in range(N):
  8.         if i > 0 and i % 3 == 0:
  9.             print("+-----+-------+-------+")
  10.         for j in range(N):
  11.             if j > 0 and j % 3 == 0:
  12.                 print("|", end=" ")
  13.             print(arr[i][j], end=" ")
  14.         print("|")
  15.     print("+-----+-------+-------+")
  16.  
  17. # Проверява дали ще бъде правилно да присвоите num на дадения ред, кол
  18. def isSafe(grid, row, col, num):
  19.     # Проверете за дублиращи числа в подобен ред, връщаме false
  20.     for x in range(N):
  21.         if grid[row][x] == num:
  22.             return False
  23.  
  24.     # Проверете за дублиращи колона в подобен ред, връщаме false
  25.     for x in range(N):
  26.         if grid[x][col] == num:
  27.             return False
  28.  
  29.     # Проверете дали намерим същото число в конкретната матрица 3*3, връщаме false
  30.     startRow = row - row % 3
  31.     startCol = col - col % 3
  32.     for i in range(3):
  33.         for j in range(3):
  34.             if grid[i + startRow][j + startCol] == num:
  35.                 return False
  36.     return True
  37.  
  38. # Взема частично попълнена решетка и се опитва да присвои стойности на всички неприсвоени местоположения по такъв начин,
  39. # че да отговаря на изискванията за решение за судоку (без дублиране в редове, колони и кутии) */
  40. def solveSudoku(grid, row, col):
  41.     # Проверете дали сме достигнали последния ред и колона, връщаме true, за да избегнем по-нататъшно връщане назад
  42.     if row == N - 1 and col == N:
  43.         return True
  44.  
  45.     # Проверете дали стойността на колоната става N, преминете към следващия ред и започнете колоната от 0
  46.     if col == N:
  47.         row += 1
  48.         col = 0
  49.     # Проверете дали текущата позиция на мрежата вече съдържа стойност > 0, итерирайте до следващата колона
  50.     if grid[row][col] > 0:
  51.         return solveSudoku(grid, row, col + 1)
  52.     for num in range(1, N + 1, 1):
  53.         # Проверете дали е безопасно да се постави числото (1-9) в дадения ред, колона, преминава към следващата колона
  54.         if isSafe(grid, row, col, num):
  55.             # Priema числото в текущата (ред, колона) позиция на мрежата и приемете,
  56.             # че зададеното ни число в позицията е правилно
  57.             grid[row][col] = num
  58.  
  59.             # Проверка за следващата възможност със следващата колона
  60.             if solveSudoku(grid, row, col + 1):
  61.                 return True
  62.  
  63.         grid[row][col] = 0
  64.     return False
  65.  
  66. # Инициализация на матрицата
  67. matrix = [[0 for _ in range(N)] for _ in range(N)]
  68.  
  69. # Въвеждане на стойности от конзолата
  70. for i in range(N):
  71.     for j in range(N):
  72.         # Въвеждане на стойност от конзолата и преобразуване към int
  73.         element = int(input(f"Въведете стойност за ред {i + 1}, колона {j + 1}: "))
  74.         matrix[i][j] = element
  75.  
  76. # Извеждане на матрицата
  77. for row in matrix:
  78.     print(row)
  79.  
  80. # Driver Code
  81. solveSudoku(matrix, 0, 0)
  82. printing(matrix)
Tags: Sudoku
Add Comment
Please, Sign In to add comment