Python-сообщество

WildEspanica · Янв. 17, 2021 09:04:14

Написал программу которое решает судоку простым перебором. На что мне сказали, мол, перебор - это слишком ресурсно-затратно. Какие вообще существуют пути оптимизации этого алгоритма, и вообще любые коментарии по коду, исправления, неточности и т.д. Заранее благодарен.

 def sudoku(A):
    def check(m, i, j):  # массив(m), координаты числа(i,j)
        for k in range(1, 10):  # по горизонтали:
            if m[i].count(k) > 1: return False
        for k in range(1, 10):  # по вертикали:
            if [m[s][j] for s in range(9)].count(k) > 1: return False
        box = []  # в квадрате:
        if   i < 3: box_y = [0, 1, 2]
        elif i > 5: box_y = [6, 7, 8]  # подпрограмма "check" проверяет, коректно ли 
        else:       box_y = [3, 4, 5]  # поставленно данное число в данной ячейке
        if   j < 3: box_x = [0, 1, 2]
        elif j > 5: box_x = [6, 7, 8]
        else:       box_x = [3, 4, 5]
        for I in box_y:
            for J in box_x:
                box += [m[I][J]]
        for k in range(1, 10):
            if box.count(k) > 1: return False 
        return True                       
    def prev_index(i, j):
        if j == 0: i, j = i-1, 8
        else: j -= 1
        return i, j
    def next_index(i, j):
        if j == 8: i, j = i+1, 0
        else: j += 1
        return i, j
    R = []
    for i in range(9): R += [A[i].copy()] # копия игрового поля
    i, j = 0, 0 # начальные координаты
    invert = False # переменная для обозначения направления следования по доске
    while i != 9:
        if A[i][j] != 0: # 'if' для игнорирования заполненных изначально ячеек
            if invert:
                i, j = prev_index(i, j)
                continue
            else:
                i, j = next_index(i, j)
                continue
        else:
            for k in range(10): 
                R[i][j] += 1 # перебираем значения в ячейке
                if R[i][j] == 10: # если дошли до 10ти, значит
                    R[i][j] = 0   # нужно обнулить данную клетку
                    i, j = prev_index(i, j) # и вернуться назад
                    invert = True
                    break
                if check(R, i, j): # если значение в ячейки корректное,
                    i, j = next_index(i, j) # то идём вперед
                    invert = False
                    break
    return R
                
def show(a, indent=''): # для красивого вывода результата
    for i in a:
        for j in i:
            print(j, end=indent)
        print()
    print()
    
a = []
print('Вводите таблицу построчно без пробелов,')
print('103[enter]\n056[enter]\n780[enter]')
print('Пустые ячейки обозначайте нулями')
print(' +++++++++')
for i in range(9): # принять от пользователя доску судоку
    a += [list(input('+'))]
for i in range(9):
    for j in range(9):
        a[i][j] = int(a[i][j])
#530070000
#600195000
#098000060 пример нерешенного судоку
#800060003
#400803001
#700020006
#060000280
#000419005
#000080079
print("Loading...")
r = sudoku(a)
show(r, ' ')
input()

Отредактировано WildEspanica (Янв. 17, 2021 09:19:07)

xam1816 · Янв. 17, 2021 10:19:37

А если бы ты сам решал,а не средством компьютера,такой же бы алгоритм выбрал?

WildEspanica · Янв. 17, 2021 10:45:17

xam1816
А если бы ты сам решал,а не средством компьютера,такой же бы алгоритм выбрал?

Нет, конечно.
то есть ключ к улучшению алгоритма в том, как судоку решает человек?

Отредактировано WildEspanica (Янв. 17, 2021 10:45:50)

py.user.next · Янв. 18, 2021 03:44:46

WildEspanica
и вообще любые коментарии по коду, исправления, неточности и т.д.

Прочитай pep8 и соблюдай его.
Прочитай pep20 и помни, что он есть.

Пиши код правильно, а не красиво.

Выдача для твоего кода из линтера

[guest@localhost codestyle]$ pylint3 codestyle.py 
No config file found, using default configuration
************* Module codestyle
C: 11, 0: Trailing whitespace (trailing-whitespace)
C: 12, 0: Exactly one space required after :
        else:       box_y = [3, 4, 5]  # поставленно данное число в данной ячейке
            ^ (bad-whitespace)
C: 15, 0: Exactly one space required after :
        else:       box_x = [3, 4, 5]
            ^ (bad-whitespace)
C: 20, 0: Trailing whitespace (trailing-whitespace)
C: 21, 0: Trailing whitespace (trailing-whitespace)
C: 43, 0: Trailing whitespace (trailing-whitespace)
C: 55, 0: Trailing whitespace (trailing-whitespace)
C: 62, 0: Trailing whitespace (trailing-whitespace)
C:  1, 0: Missing module docstring (missing-docstring)
C:  3, 0: Invalid argument name "A" (invalid-name)
C:  3, 0: Missing function docstring (missing-docstring)
W: 31, 8: Redefining name 'i' from outer scope (line 68) (redefined-outer-name)
W: 32, 7: Redefining name 'j' from outer scope (line 71) (redefined-outer-name)
C:  4, 4: Invalid argument name "m" (invalid-name)
C:  4, 4: Missing function docstring (missing-docstring)
W:  4,17: Redefining name 'i' from outer scope (line 68) (redefined-outer-name)
W:  4,20: Redefining name 'j' from outer scope (line 71) (redefined-outer-name)
C:  6,34: More than one statement on a single line (multiple-statements)
C:  8,57: More than one statement on a single line (multiple-statements)
C: 10,20: More than one statement on a single line (multiple-statements)
C: 11,20: More than one statement on a single line (multiple-statements)
C: 13,20: More than one statement on a single line (multiple-statements)
C: 14,20: More than one statement on a single line (multiple-statements)
C: 16,12: Invalid variable name "I" (invalid-name)
C: 17,16: Invalid variable name "J" (invalid-name)
C: 20,33: More than one statement on a single line (multiple-statements)
R:  4, 4: Too many branches (14/12) (too-many-branches)
C: 22, 4: Missing function docstring (missing-docstring)
W: 22,19: Redefining name 'i' from outer scope (line 68) (redefined-outer-name)
W: 22,22: Redefining name 'j' from outer scope (line 71) (redefined-outer-name)
C: 23,19: More than one statement on a single line (multiple-statements)
C: 26, 4: Missing function docstring (missing-docstring)
W: 26,19: Redefining name 'i' from outer scope (line 68) (redefined-outer-name)
W: 26,22: Redefining name 'j' from outer scope (line 71) (redefined-outer-name)
C: 27,19: More than one statement on a single line (multiple-statements)
C: 30, 4: Invalid variable name "R" (invalid-name)
C: 31,23: More than one statement on a single line (multiple-statements)
C: 31,23: Invalid variable name "R" (invalid-name)
W: 40,37: Using possibly undefined loop variable 'j' (undefined-loop-variable)
W: 43,16: Unused variable 'k' (unused-variable)
C: 56, 0: Invalid argument name "a" (invalid-name)
C: 56, 0: Missing function docstring (missing-docstring)
W: 56, 9: Redefining name 'a' from outer scope (line 63) (redefined-outer-name)
W: 57, 8: Redefining name 'i' from outer scope (line 68) (redefined-outer-name)
W: 58,12: Redefining name 'j' from outer scope (line 71) (redefined-outer-name)
C: 63, 0: Invalid constant name "a" (invalid-name)
C: 83, 0: Invalid constant name "r" (invalid-name)

-----------------------------------
Your code has been rated at 4.12/10

[guest@localhost codestyle]$

[guest@localhost codestyle]$ pypep8 codestyle.py 
codestyle.py:3:1: E302 expected 2 blank lines, found 1
codestyle.py:6:33: E701 multiple statements on one line (colon)
codestyle.py:8:56: E701 multiple statements on one line (colon)
codestyle.py:10:11: E271 multiple spaces after keyword
codestyle.py:10:19: E701 multiple statements on one line (colon)
codestyle.py:11:19: E701 multiple statements on one line (colon)
codestyle.py:11:80: E501 line too long (84 > 79 characters)
codestyle.py:11:85: W291 trailing whitespace
codestyle.py:12:13: E701 multiple statements on one line (colon)
codestyle.py:12:80: E501 line too long (81 > 79 characters)
codestyle.py:13:11: E271 multiple spaces after keyword
codestyle.py:13:19: E701 multiple statements on one line (colon)
codestyle.py:14:19: E701 multiple statements on one line (colon)
codestyle.py:15:13: E701 multiple statements on one line (colon)
codestyle.py:20:32: E701 multiple statements on one line (colon)
codestyle.py:20:46: W291 trailing whitespace
codestyle.py:21:20: W291 trailing whitespace
codestyle.py:22:5: E301 expected 1 blank line, found 0
codestyle.py:23:18: E701 multiple statements on one line (colon)
codestyle.py:24:13: E701 multiple statements on one line (colon)
codestyle.py:26:5: E301 expected 1 blank line, found 0
codestyle.py:27:18: E701 multiple statements on one line (colon)
codestyle.py:28:13: E701 multiple statements on one line (colon)
codestyle.py:31:22: E701 multiple statements on one line (colon)
codestyle.py:31:42: E261 at least two spaces before inline comment
codestyle.py:32:16: E261 at least two spaces before inline comment
codestyle.py:33:19: E261 at least two spaces before inline comment
codestyle.py:35:25: E261 at least two spaces before inline comment
codestyle.py:43:32: W291 trailing whitespace
codestyle.py:44:29: E261 at least two spaces before inline comment
codestyle.py:45:34: E261 at least two spaces before inline comment
codestyle.py:47:44: E261 at least two spaces before inline comment
codestyle.py:50:35: E261 at least two spaces before inline comment
codestyle.py:51:44: E261 at least two spaces before inline comment
codestyle.py:55:1: W293 blank line contains whitespace
codestyle.py:56:1: E302 expected 2 blank lines, found 1
codestyle.py:56:24: E261 at least two spaces before inline comment
codestyle.py:62:1: W293 blank line contains whitespace
codestyle.py:68:19: E261 at least two spaces before inline comment
codestyle.py:73:1: E265 block comment should start with '# '
codestyle.py:74:1: E265 block comment should start with '# '
codestyle.py:75:1: E265 block comment should start with '# '
codestyle.py:76:1: E265 block comment should start with '# '
codestyle.py:77:1: E265 block comment should start with '# '
codestyle.py:78:1: E265 block comment should start with '# '
codestyle.py:79:1: E265 block comment should start with '# '
codestyle.py:80:1: E265 block comment should start with '# '
codestyle.py:81:1: E265 block comment should start with '# '
[guest@localhost codestyle]$

Выучи правила, чтобы код сразу правильно писать, не запуская линтеры.
Если не знаешь, зачем соблюдать какое-то правило, соблюдай его, если оно есть. Зачем его соблюдать, ты узнаешь потом, когда у тебя будет время читать книги по правильному оформлению и написанию кода.

Например, вот этот кусок кода

WildEspanica

  
        for k in range(1, 10):  # по вертикали:
            if [m[s][j] for s in range(9)].count(k) > 1: return False

Должен быть записан вот так

  
        for k in range(1, 10):  # по вертикали:
            name = [m[s][j] for s in range(9)]
            if name.count(k) > 1:
                return False

Надо прочитать кучу книг про оформление кода, читать исходные тексты программ профессионалов и много писать своего кода. Тогда у тебя со временем начнёт формироваться понимание, почему это надо делать так. Сходу ты это не поймёшь. Это приходит только с опытом, в том числе и с личным. Пропустить через себя для этого нужно много материала.

Например
Вот так записано (это якобы красивее записано и умнее - в одну строчку)

  
if i % m == n % m: print(i % n)

И вот так записано (это то, как надо писать)

  
if i % m == n % m:
    print(i % n)

Ты думаешь “а почему?”

Дальше мы это всё запускаем

Вот мы запускаем “умный” вариант

  
>>> i, m, n = 0, 1, 0
>>> if i % m == n % m: print(i % n)
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
>>>

Он говорит “там в первой строке деление неправильное”. Ты смотришь и думаешь “а какое из них? там этих делений три и любое из них может неправильным быть”. Потом ты думаешь “надо бы это разделить на части, чтобы понять точно, потому что номер строки line 1 мне не говорит ни о чём, потому что все три деления в этой строке line 1 находятся”. Так проходит пять минут. Ты просто пять минут пытаешься разобраться, про что речь идёт вообще, потому что текст интерпретатора не информативен.

Дальше мы запускаем правильный вариант

  
>>> i, m, n = 0, 1, 0
>>> if i % m == n % m:
...     print(i % n)
... 
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
ZeroDivisionError: integer division or modulo by zero
>>>

И мы видим “вот она ошибка! во второй строке line 2, а в первой строке line 1 всё в порядке и два первых деления работают нормально, иначе бы он выпал на первой строке line 1”. И мы не тратим пять минут на это всё, потому что сообщение интерпретатора информативно. И мы эти пять минут тратим на исправление самой ошибки, а не на поиск этой ошибки, чтобы потом ещё минуть пять её исправлять.

Вот таких моментов там много. Ты их не знаешь. В книгах всё это расписано вдоль и поперёк. Но так как времени на книги не хватает, ты просто смотришь, как принято делать, и копируешь это просто точь в точь. А почему это надо делать, ты узнаешь потом, когда у тебя будет время читать книги эти все, материалы и прочее.

То же самое касается функций, который ты засунул в функцию sudoku(). Тоже такая же “умная” идея. Вытащи их наружу. Функции должны быть снаружи, чтобы их можно было протестировать модульными тестами. Про их существование ты не знаешь, но потом ты про них узнаешь. Это придёт из другой пачки книг, до которой ты тоже потом дойдёшь. А сейчас на это нет времени.

tags: clean code

Отредактировано py.user.next (Янв. 18, 2021 03:52:46)

Python-сообщество

Уведомления

#1 Янв. 17, 2021 09:04:14

Судоку солвер

#2 Янв. 17, 2021 10:19:37

Судоку солвер

#3 Янв. 17, 2021 10:45:17

Судоку солвер

#4 Янв. 18, 2021 03:44:46

Судоку солвер

Board footer