1

我正在为 Python 上的 End View 拼图开发求解器。这就是我到目前为止所拥有的。我很抱歉代码混乱,但我是新来的。我的问题是规则。整代和运行等工作正常。
有人可以给我任何建议或帮助考虑规则吗?

import re
import sys
katia=0

def read_data(filename):
    try: f = open(filename, "r")
    except:
    print "\nERROR: File %s not found.\nNow try to open input.txt..." % filename
        try:
            f = open("input.txt", "r")
        except:
            print "\nERROR: File 'input.txt' not found."
            sys.exit(raw_input("Press enter to exit..."))

    return [ map(int, condition) for condition in 
[ re.findall(r'\d+', line) for line in f.readlines()]

#here comes the rules in which i am not sure 
    def check(tab, row, conditions):
    # check left-side conditions

    if (conditions[0][row] != 0): 
        if ( ( tab[row][0] != conditions[0][row] 
               and 
               tab[row][1] != conditions[0][row] 
               and
               tab[row][2] !=conditions[0][row]
              )
              or
              ( tab[row][1] == conditions[0][row]
              and
            tab[row][0] != 0
              )
              or
              ( tab[row][2] == conditions[0][row] 
              and 
              (tab[row][0] != 0 or tab[row][1] != 0)

                )
            ):
             return 0

    # right-side conditions
    if (conditions[1][row] != 0):
        if( ( tab[row][-1] != conditions[1][row] 
             and 
                  tab[row][-2] != conditions[1][row] 
             and
              tab[row][-3] !=conditions[1][row]
            )
            or
            ( tab[row][-2] == conditions[1][row]
                and
             tab[row][-1] != 0
            )
            or
            ( tab[row][-3] == conditions[1][row] 
                and 
            ( tab[row][-1] != 0 or tab[row][-2] != 0)

          )
           ):
               return 0
    if row < (len(tab) - 3):  # chek 3 below rows to uniqueness for uper numbers
        for i in range(len(tab)):
            if conditions[3][i] != 0:
                if tab[row][i]==conditions[3][i]:
                    return 0
    # check top-side conditions
    if row == 1:
    for col in range(len(tab)):
            if conditions[2][col] != 0 :
                if ( tab[1][col] == conditions[2][col]
                       and

                     ( tab[2][col] == conditions[2][col]
                       and
                       tab[0][col] != 0 or tab[0][col] != 7
                       and
                       tab[1][col] != 0 or tab[1][col] != 7 )
                     or 
                     ( tab[0][col] != conditions[2][col] 
                        and tab[1][col] != conditions[2][col] 
                        and tab[2][col] != conditions[2][col] )
                    ):
                    return 0
    if row == 2:
        for col in range(len(tab)):
            if conditions[2][col] != 0:
                if ( tab[1][col] != conditions[2][col] 
                     and 
                     tab[2][col] != conditions[2][col]
                   ):
                    return 0

    # check bottom-side conditions
    if row == len(tab)-2:
        for col in range(len(tab)):
            if conditions[3][col] != 0:
                if ( ( tab[-1][col] != conditions[3][col]
                     )
                     or 
                     ( tab[-2][col] == conditions[3][col]
                       and
                       tab[-1][col] == 0
                     )
                   ):
                    return 0
    if row == len(tab)-3:
        for col in range(len(tab)):
            if conditions[3][col] != 0:
                if ( tab[-3][col] != conditions[3][col] 
                     and 
                      tab[-1][col] == 0
                      and
                      tab[-2][col] == 0 
                   ):
                    return 0
    global katia
    katia+=1
    # check cols
    for col in range(len(tab)):
        for digit in range(1,4):
            if( ([tab[i][col] for i in range(len(tab))].count(digit) > 1)
            ):
                if katia%5000 == 0: 
                    print "errrrror in %d: " % col, 
                    print [tab[i][col] for i in range(len(tab))]
                return 0
    for col in range(len(tab)):
        for digit in range(len(tab)):
        if (( [tab[i][col]  for i in   range(len(tab))].count(digit)==0       
     and digit != 0 and digit !=7)
                or
    ([tab[i][col]  for i in range(len(tab))].count(digit) > 1  
     and  digit not       in range(1,7))
                or
                ([tab[i][col]  for 
    i in range(len(tab))].count(0)+ [tab[i][col] 
     for i in range(len(tab))].count(7) != 2)

                ):
                return 0
    katia++1
    if  katia/500 == 0: 
        for i in range(7):
            print tab[i]

    return 1

def generate(row):
    if (row[0] == -1):
        row[:] = range(len(row))
        return 1
    a = -1
    for j in reversed(range(len(row)-1)):
        if (row[j] < row[j+1]): 
            a = j 
            break
    if a == -1:
        return 0
    b = -1
    for j in reversed(range(a, len(row))):
        if (row[j] > row[a]): 
            b = j
            break

    row[a], row[b] = row[b], row[a]
    row[(a+1):] = reversed(row[(a+1):])
    return 1

def rekurs(tab, row, conditions):
    while (1):
        if (generate(tab[row]) == 0):
            tab[row] = [-1 for i in range( len(tab) )]
            return 0
        if check(tab, row, conditions) == 1:
            if row < 7:
                if (rekurs(tab, row+1, conditions)):
                    return 1
            else:  
                return 1

## -------------------- run program -------------------
if __name__ == '__main__':
    conditions = read_data(raw_input("Input file:  "))
    tab = [ [-1 for j in range(len(conditions[0]))] 
    for i in range( len(conditions[0]) ) ]
    print "\nSuccess. \nNow search for solutions..."
    if rekurs(tab, 0, conditions) == 0:
        print "\nThere is no solution:"
        for i in range(len(tab)): print tab[i]
    else:
        print "\nGood news:"
        for i in range(len(tab)): print tab[i]
    raw_input("Press enter to exit...")

运行代码后,您必须添加输入文件的名称,其中应包含限制:

0 4 2 6 1 0 5 0
0 6 5 0 5 4 3 0
0 1 6 2 3 2 0 0
1 3 5 4 2 3 6 6
4

1 回答 1

2

我已经完成了这个任务:这里是# - - coding: cp1251 - - import re import sys

iterations = 0  # переменная для подсчета итераций (используется при выводе)

# ------------------------------------------------------------------------------------
# Функция считывания условий из файла
def read_data(filename):
    try: f = open(filename, "r")
    except:
        print "\nERROR: File %s not found.\nNow try to open input.txt..." % filename
        try:
            f = open("input.txt", "r")
        except:
            print "\nERROR: File 'input.txt' not found."
            sys.exit(raw_input("Press enter to exit..."))

    return [ map(int, condition) for condition in                       # для каждой "строки(массива)" массива 
                                                                        # каждый элемент превращаем в число.
                [ re.findall(r'\d+', line) for line in f.readlines()]
            ]                                                           # для каждой линии из считанного файла
                                                                        # регулярным выражением выделяем массив чисел в 
                                                                        # этой строке, которые разделены пробелом.

# ------------------------------------------------------------------------------------
# Функция проверки условий
def check(tab, row, conditions):
    # Вывод матрицы на итерации с шагом 1000
    global iterations
    iterations +=1
    if  iterations % 1000000 == 0 :
        for i in range(8):
            print tab[i]
        print "   "

    #Обязательное правило №1 #top-side conditions
    # Проверка строк на соответствие верхним ограничениям

    # Проверка первой строки 
    # Тут могут быть либо нули, либо ограничивающая цифра, иначе выход на перегенерацию строки
    if row == 0:
        for col in range(8):
            if (conditions[2][col] != 0):
                if (tab[0][col] != conditions[2][col]       and
                    tab[0][col] != 0                        and
                    tab[0][col] != 7
                    ):      # Грустный смайлик. Почему, ведь всё прекрасно работает?
                    return 0

    # Если в первой строке нули, то во второй должно быть верхнее ограничение, либо ноль
    if row == 1:
        for col in range(8):
            if (conditions[2][col] != 0):
                if (
                    (tab[0][col] == 0 or tab[0][col] == 7)  and
                     tab[1][col] != conditions[2][col]      and
                     tab[1][col] != 0                       and
                     tab[1][col] != 7
                    ):
                    return 0

    # Если в первой и второй строках нули, то в третьей должно быть верхнее ограничение, без вариантов
    if row == 2:
        for col in range(8):
            if (conditions[2][col] != 0):
                if (
                    (tab[0][col] == 0 or tab[0][col] == 7)  and
                    (tab[1][col] == 0 or tab[1][col] == 7)  and
                     tab[2][col] != conditions[2][col]
                    ):
                    return 0

    #Обязательное правило №2 #left-side conditions
    # Проверка строк на соответствие левым ограничениям, вызывается для каждой строки
    if (conditions[0][row] != 0): # если первое условин не нулевое. Какое первое? Левое! Первое оно у нас в файле, зачем привязывать к формату
        if (
            (tab[row][0] != conditions[0][row]      and # если на первой позиции не стоит граничное
             tab[row][1] != conditions[0][row]      and #если на второй тоже не стоит граничное
             tab[row][2] != conditions[0][row]          #если на 3-й тоже не стоит граничное
            )
            or
            (tab[row][1] == conditions[0][row]      and # вторая позиция равна условию
            (tab[row][0] != 0 and tab[row][0] != 7)     # при этом на 1-й позиции не 0 и не 7
            )
            or
            (
                tab[row][2] == conditions[0][row]   and
                (
                tab[row][0] != 0 and tab[row][0] != 7 
                or 
                tab[row][1] != 0 and tab[row][1] != 7
                )
            )
            ):
            return 0

    #Обязательное правило №3 #right-side conditions
    # Проверка строк на соответствие правым ограничениям, вызывается для каждой строки
    if (conditions[1][row] != 0):
        if (
            (tab[row][-1] != conditions[1][row]     and # если на первой позиции не стоит граничное
             tab[row][-2] != conditions[1][row]     and #если тут тоже не стоит граничное
             tab[row][-3] != conditions[1][row]
            )
            or
            (tab[row][-2] == conditions[1][row]     and
             tab[row][-1] != 0 and tab[row][-1] != 7
            )
            or
            (
                tab[row][-3] == conditions[1][row]      and
                (
                    tab[row][-1] != 0 and tab[row][-1] != 7 
                    or 
                    tab[row][-2] != 0 and tab[row][-2] != 7
                )
            )
            ):
            return 0

    #Необязательное правило #Оптимизация
    # Проверка того, что числа в нижних ограничениях не встречаются раньше 5-й строки
    if row < (len(tab) - 3):    # 8 - 3 = 5
        for i in range(len(tab)):
            if tab[row][i]==conditions[3][i]:
                return 0


    #Обязательные правила №5-6, переставлены сюда для оптимизации
    # Проверка того, что цифры в столбце не повторились и что количество пробелов не больше 2
    for j in range(0, row) :
            for h in range(0, 8):
                    if (tab[row][h] == tab[j][h] and tab[row][h] != 0 and tab[row][h] != 7) :
                            return 0
    sum = 0
    for k in range(0, 8) :
            for n in range(0, row + 1):
                    if (tab[n][k] == 0 or tab[n][k] == 7) :
                            sum += 1
                    if (sum > 2):
                            return 0
            sum = 0

    #Обязательное правило №4 #down-side conditions
    # Проверка строк на соответствие нижним ограничениям (ТОДО: исправить и проверить)
    if (row == 7):
        for col in range(len(tab)):
            if conditions[3][col] != 0 :  #если 3-е условие не равно 0. Не 3-е, нижнее ведь. Давайте не будем путать людей
                if (
                    (tab[-1][col] != conditions[3][col] and # Исправил индексы так, чтобы они были единой системы счисления
                     tab[-2][col] != conditions[3][col] and
                     tab[-3][col] != conditions[3][col]
                    )
                    or
                    (tab[-2][col] == conditions[3][col] and
                     tab[-1][col] !=0 and tab[-1][col] !=7
                    )
                    or
                    (
                        tab[-3][col] == conditions[3][col]  and
                        (
                            tab[-1][col] !=0 and tab[-1][col] !=7 
                            or 
                            tab[-2][col] !=0 and tab[-2][col] !=7 
                        )
                    )
                    ):
                    return 0

    return 1

# ------------------------------------------------------------------------------------
# Функция генерирования строки (почти без комментариев, потому что поздно)
def generate(row):
    if (row[0] == -1):
        row[:] = range(len(row))
        return 1
    a = -1
    for j in reversed(range(len(row)-1)):
        if (row[j] < row[j+1]):
            a = j
            break
    if a == -1:
        return 0
    b = -1
    for j in reversed(range(a, len(row))):
        if (row[j] > row[a]):
            b = j
            break

    row[a], row[b] = row[b], row[a]     # Обмен значений для получения новой строки
    row[(a+1):] = reversed(row[(a+1):])
    return 1

# ------------------------------------------------------------------------------------
# Функция рекурсивного подбора строк матрицы
def rekurs(tab, row, conditions):
    while (1):
        if (generate(tab[row]) == 0):   # Если не осталось больше вариантов строк - забиваем минус единицы, выходим
            tab[row] = [-1 for i in range(len(tab))]
            return 0
        if (check(tab, row, conditions) == 1):
            if row < 7:                 # Пока не заполним таблицу полностью, спускаемся по уровням, т.е. по строкам
                if (rekurs(tab, row + 1, conditions)):
                    return 1
            else:
                return 1

## -------------------- run program -------------------
if __name__ == '__main__':
    conditions = read_data(raw_input("Input file:  "))
    tab = [ [-1 for j in range(len(conditions[0]))] for i in range( len(conditions[0]) ) ]
    print "\nSuccess. \nNow search for solutions..."
    if rekurs(tab, 0, conditions) == 0:
        print "\nThere is no solution:"
        for i in range(len(tab)): print tab[i]
    else:
        print "\nGood news:"
        for i in range(len(tab)): 
            for k in range(len(tab)):
                if (tab[i][k] == 7): tab[i][k] = 0
            print tab[i]
    raw_input("Press enter to exit...")

这是输入文件:

2 2 3 0 4 2 6 0

5 1 0 6 1 0 0 4

0 1 5 3 4 6 2 0

0 6 4 5 2 4 3 0

于 2012-11-12T11:12:40.230 回答