Ошибка при проверке диагонали - nQueens

Question

После решения моей ошибки со списком значений и возможности запуска моей программы до конца, я обнаружил, что моя диагональная проверка, похоже, имеет логическую ошибку. Мой ввод выглядит следующим образом:

(THREAT? '(1 3)' ((1 0) (2 4) (3 0) (4 0) (5 0) (6 0) (7 0) (8 0)))

Первый аргумент, который мы тестируем, является одобренным или не размещающим королеву, а вторым аргументом является состояние платы, y значения 1-8 определяют позиции столбца части и значение 0 указывает, что строка значений x не будет содержать кусок. Мой код выглядит следующим образом:

(defun diagonal(point1 point2) 
    (= (abs (- (car point1) (car point2))) 
     (abs (- (cadr point1) (cadr point2)))) 
) 

(defun THREAT?(x y) 
    ; Checks threat on the vertical 
    (when (not (eq (values-list (cdr (nth (- (car x) 1) y))) '0)) 
      (return-from THREAT? t) 
    ) 
    (loop for i from 0 to (list-length y) 

      ; Checks threat on the horizontal 
      when (eq (values-list (cdr x )) (values-list (cdr (nth i y)))) 
        do (return-from THREAT? t) 
      ; With the help of the diagonal function checks along the diagonal 
      when (diagonal x (nth i y)) 
        do (return-from THREAT? t) 
    ) 
) 

Если мое понимание правильно, моя программа должна проходить через каждый элемент y. Он передаст x и текущую пару y в диагональную функцию. Диагональная функция будет за вычетом двух и абсолютного значения и проверяет, равны ли они (если они диагональны, то они должны быть равны (1 2) и (2 3) диагональны и, следовательно, | 1 - 2 | = 1 и | 2 - 3 | = 1). Диагональная функция должна возвращать значение true, если эти числа эквивалентны. Соответствующий оператор when должен активироваться только тогда, когда он получает истинное значение от диагональной функции, и все же он всегда возвращает true, даже когда я даю программе полностью пустую доску. Как исправить диагональ, чтобы правильно определить угрозу на доске? Любая помощь очень ценится!

Answer 1

Я переписал ваш код для лучшего стиля Лиспа.

• гораздо лучше именования.
• процедуры с полезными именами комментировали резервированные
• индивидуальные процедуры лучше проверяемые
• избавились от ЗНАЧЕНИЯ-LIST нонсенс
• избавиться от всех CAR, CDR, CADR. Используйте FIRST и SECOND.
• введены аксессоры для й и у компонентов точки
• избавился от странного потока управления с RETURN-FROM, заменив его с простым или
• фактически непосредственно перебрать список, вместо того, чтобы использовать NTH все в время
• EQ не для сравнения равенства чисел, use = вместо
• не ставьте круглые скобки на линии.
• отступов и форматирования кода правильно
• не ставьте пробелы между скобками
• поставить пробел между атомом и открывающей скобкой

Код:

(defun get-x (point) 
    (first point)) 

(defun get-y (point) 
    (second point)) 

(defun diagonal? (point1 point2) 
    (= (abs (- (get-x point1) (get-x point2))) 
    (abs (- (get-y point1) (get-y point2))))) 

(defun vertical? (point) 
    (not (zerop (get-y point)))) 

(defun horizontal? (point1 point2) 
    (= (get-y point1) 
    (get-y point2))) 

(defun threat? (point list-of-columns) 
    (or (vertical? (nth (1- (get-x point)) list-of-columns)) 
     (loop for point2 in list-of-columns 
      when (or (horizontal? point point2) 
        (diagonal? point point2)) 
      return t))) 

Пример

Теперь мы можем проследить три угрозы предикаты:

? (trace vertical? diagonal? horizontal?) 
NIL 

Теперь вы можете позвонить пример:

? (threat? '(1 3) '((1 0) (2 4) (3 0) (4 0) (5 0) (6 0) (7 0) (8 0))) 
0> Calling (VERTICAL? (1 0)) 
<0 VERTICAL? returned NIL 
0> Calling (HORIZONTAL? (1 3) (1 0)) 
<0 HORIZONTAL? returned NIL 
0> Calling (DIAGONAL? (1 3) (1 0)) 
<0 DIAGONAL? returned NIL 
0> Calling (HORIZONTAL? (1 3) (2 4)) 
<0 HORIZONTAL? returned NIL 
0> Calling (DIAGONAL? (1 3) (2 4)) 
<0 DIAGONAL? returned T 
T 

Это должно помочь, так что вы можете лучше отладки кода ... Посмотрите на след мощность.

версия, которая не использует пустые описания столбцов

(defun get-x (point) 
    (first point)) 

(defun get-y (point) 
    (second point)) 

(defun diagonal? (point1 point2) 
    (= (abs (- (get-x point1) (get-x point2))) 
    (abs (- (get-y point1) (get-y point2))))) 

(defun vertical? (point list-of-columns) 
    (let ((point2 (find (get-x point) list-of-columns :key #'get-x))) 
    (and point2 (not (zerop (get-y point2)))))) 

(defun horizontal? (point1 point2) 
    (= (get-y point1) 
    (get-y point2))) 

(defun threat? (point list-of-columns) 
    (or (vertical? point list-of-columns) 
     (loop for point2 in list-of-columns 
      when (or (horizontal? point point2) 
        (diagonal? point point2)) 
      return t))) 

(defun print-board (board) 
    (format t "~%+-+-+-+-+-+-+-+-+") 
    (dotimes (y 8) 
    (terpri) 
    (dotimes (x 8) 
     (format t "|~a" (if (member (list x y) board :test #'equal) "x" " "))) 
    (format t "|~%+-+-+-+-+-+-+-+-+"))) 

Пример:

CL-USER 138 > (threat? '(1 2) '((2 4))) 
NIL 

CL-USER 139 > (print-board '((1 2) (2 4))) 

+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| |x| | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | |x| | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
NIL 

Другой пример:

CL-USER 140 > (threat? '(1 2) '((2 4) (4 5))) 
T 

CL-USER 141 > (print-board '((1 2) (2 4) (4 5))) 

+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| |x| | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | |x| | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | |x| | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
| | | | | | | | | 
+-+-+-+-+-+-+-+-+ 
NIL