Python. Валидность поля SUDOKU
Все знают SUDOKU.
На входе дают 9 строк. Например
195743862
431865927
876192543
387459216
612387495
549216738
763524189
928671354
254938671
Это построчные наборы цифр.
Необходимо проверить чтобы каждая строка содержала от 1 до 9
Каждый столбец содержал от 1 до 9
И каждый маленький квадратик 3*3 (9 шт) содержал от 1 до 9
Чтобы было все и не повторялось.
Считать циферки можно так:
A=[list(input()) for i in range(9)]
И это уже даже будет списком двухмерным.
Затем можно проверить строки быстро
for i in range(9):
if len(set(A[i]))!=9: print('все плохо :)') #здесь проверка когда еще был одномерный список, но идея должна быть понятна.
но надо еще столбцы проверить, что в принципе легко и самое интересное квадратики. Кто подскажет нерутинные интересные решения?
Еще для теста
295743861
431865927
876192543
387459216
612387495
549216738
763524189
928671354
154938672
На выходе Yes/No (валидное игровое поле или где-то накосячено).
Можно и рутинные, но чтоб не очень сильно :). Предлагайте.
Не знающим - проходите мимо.
Ответы
Для проверки столбцов вы можете использовать простой цикл с вложенным циклом. Внешний цикл будет проходить по всем столбцам, а внутренний цикл будет проходить по всем строкам, и проверять каждый элемент столбца с помощью set.
for j in range(9):
column = [A[i][j] for i in range(9)]
if len(set(column)) != 9:
print("Invalid column")
Для проверки квадратов 3x3 вы можете использовать три цикла, один для каждой строки квадрата, один для каждого столбца квадрата, и один для каждого квадрата.
for i in range(0, 9, 3):
for j in range(0, 9, 3):
square = [A[x][y] for x in range(i, i+3) for y in range(j, j+3)]
if len(set(square)) != 9:
print("Invalid square")
И если в ходе этих операций не было выведено Invalid column и Invalid square то это валидное поле.
import random
def print_sudoku(sudoku): # вывод судоку на экран
for i in range(9): # 9 строк судоку
for j in range(9): # 9 столбцов судоку
print(sudoku[i][j], end=' ') # вывод значения судоку
print() # переход на новую строку
def check_sudoku(sudoku, row, col, num): # проверка судоку на правильность
for i in range(9): # 9 строк судоку
if sudoku[i][col] == num: # проверка строки
return False
for j in range(9): # 9 столбцов судоку
if sudoku[row][j] == num: # проверка столбца
return False
for i in range(3): # 3 строки в квадрате 3x3
for j in range(3): # 3 столбца в квадрате 3x3
if sudoku[(row // 3) * 3 + i][(col // 3) * 3 + j] == num: # проверка квадрата 3x3
return False
return True
def generate_sudoku(sudoku, row, col): # генерация судоку
if row == 9: # если все строки судоку заполнены
return True
if col == 9: # если все столбцы судоку заполнены
return generate_sudoku(sudoku, row + 1, 0)
if sudoku[row][col] != 0: # если ячейка судоку не пустая
return generate_sudoku(sudoku, row, col + 1)
for num in range(1, 10): # перебор чисел от 1 до 9
if check_sudoku(sudoku, row, col, num): # проверка судоку на правильность
sudoku[row][col] = num # заполнение ячейки судоку
if generate_sudoku(sudoku, row, col + 1): # генерация судоку
return True
sudoku[row][col] = 0 # очистка ячейки судоку
return False
def main(): # главная функция программы
sudoku = [[0 for j in range(9)] for i in range(9)] # создание судоку
generate_sudoku(sudoku, 0, 0) # генерация судоку
print_sudoku(sudoku) # вывод судоку на экран
if __name__ == '__main__': # проверка на запуск файла
main() # запуск главной функции программы
