Рекурсивная функция lisp для решения N-Queen

Question

ОБНОВЛЕНО: код должен компилироваться без ошибок и предупреждений. Извините за предыдущий. Проблема у меня сейчас в том, что при запуске (или с любым другим целым числом)

(NxNqueen-solver 10)

Функция getqueencol будет возвращать ноль, потому что в первую очередь на доске нет ферзей, поэтому в поле queen- a -be-be- place -here будет (= число ноль), потому что tcol будет ноль. Я думаю, что это будет происходить каждый раз, когда в строке не передается ферзь в качестве аргумента функции queen-can-be-be-here-here.

Пожалуйста, поделитесь некоторыми советами о том, как решить эту проблему. Заранее спасибо.

Вот код

(defvar *board* (make-array '(10 10) :initial-element nil)) 


(defun getqueencol (row n)
"Traverses through the columns of a certain row
 and returns the column index of the queen."
  (loop for i below n
        do (if (aref *board* row i)
               (return-from getqueencol i))))

(defun print-board (n)
"Prints out the solution, e.g. (1 4 2 5 3),
 where 1 denotes that there is a queen at the first 
 column of the first row, and so on."
  (let ((solutionlist (make-list n)))
    (loop for row below n
          do (loop for col below n
                   do (when (aref *board* row col)
                        (setf (nth row solutionlist) col))))
    (print solutionlist)))


(defun queen-can-be-placed-here (row col n)
"Returns t if (row,col) is a possible place to put queen, otherwise nil."
  (loop for i below n
       do (let ((tcol (getqueencol i n)))
            (if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
                (return-from queen-can-be-placed-here nil)))))



(defun backtracking (row n)
"Solves the NxN-queen problem with backtracking"
  (if (< row n)
      (loop for i below n
          do (when (queen-can-be-placed-here row i n)
                  (setf (aref *board* row i) 't)
                  (return-from backtracking (backtracking (+ row 1) n))
                  (setf (aref *board* row i) 'nil))
    (print-board n))))

(defun NxNqueen-solver (k)
"Main program for the function call to the recursive solving of the problem"
  (setf *board* (make-array '(k k) :initial-element nil))
  (backtracking 0 k))

Answer 1

Вы говорите, что скомпилировали свой код. Этого не может быть, с тех пор вы бы увидели, что компилятор жалуется на ошибки. Вы хотите убедиться, что вы действительно скомпилировали код и исправили его так, чтобы он компилировался без ошибок и предупреждений.

Возможно, вы захотите избавиться от ошибок / проблем в коде (см. Комментарий Рензо), а затем посмотрите на алгоритмическую проблему. У меня нет особого смысла смотреть на алгоритмическую проблему, когда код содержит ошибки.

• SETQ не вводит переменную, переменная должна быть где-то определена

• DEFVAR не имеет смысла внутри функции.

• Что-то вроде (let (x (sin a)) ...) определенно выглядит неправильно. Синтаксис LET требуется пара скобок вокруг списка привязок.

• RETURN-FROM принимает в качестве первого аргумента имя существующего блока для возврата. Необязательный второй аргумент является возвращаемым значением. Получите правильный синтаксис и вернитесь из правильного блока.

• в вызове MAKE-ARRAY укажите значение по умолчанию: (make-array ... :initial-element nil) иначе не понятно что это.

• Переменная *board* не определено

Стиль

• в LOOP: for i to (1- n) проще for i below n

• вам не нужно цитировать NIL а также T,

• (if (eq foo t) ...) может быть проще записать как (if foo ...), Особенно если значение foo либо NIL или же T,

• (if foo (progn ...)) это просто (when foo ...)

---

Я не уверен, что вы делаете, чтобы утверждать, что ваш код компилируется. Он не компилируется.

Каждая функция имеет предупреждения компилятора. Вы должны проверить предупреждения компилятора и устранить проблемы.

(defun getqueencol (row)
"Traverses through the columns of a certain row
 and returns the column index of the queen."
  (loop for i below n
        do (if (aref board row i)
               (return-from getqueencol i))))

Компилятор жалуется:

;;;*** Warning in GETQUEENCOL: N assumed special
;;;*** Warning in GETQUEENCOL: BOARD assumed special

Где n определены? Где board приходящий из?

(defun print-board (board)
"Prints out the solution, e.g. (1 4 2 5 3),
 where 1 denotes that there is a queen at the first 
 column of the first row, and so on."
  (let (solutionlist)
    (setq solutionlist (make-list n)))
  (loop for row below n
        do (loop for col below n
               do (when (aref board row col)
                      (setf (nth row solutionlist) col))))
  (print solutionlist))

LET не имеет смысла. (let (foo) (setq foo bar) ...) является (let ((foo bar)) ...),

Почему список решений не определен? Посмотрите на LET... это не имеет смысла.

Где n приходящий из?

(defun queen-can-be-placed-here (row col)
"Returns t if (row,col) is a possible place to put queen, otherwise nil."
  (loop for i below n
       do (let (tcol)
            (setq tcol (getqueencol i)))
       (if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
          (return-from queen-can-be-placed-here nil))))

где n приходящий из? LET не имеет смысла.

(defun backtracking (row)
"Solves the NxN-queen problem with backtracking"
  (if (< row n)
      (loop for i below n
          do (when (queen-can-be-placed-here row i)
                  (setf (aref board row i) 't)
                  (return-from backtracking (backtracking (+ row 1)))
                  (setf (aref board row i) 'nil))
    (print-board board))))

Где n приходящий из? Где board определены?

(defun NxNqueen-solver (k)
"Main program for the function call to the recursive solving of the problem"
    (let (n board)
          (setq n k)
          (setq board (make-array '(k k) :initial-element nil)))
        (backtracking 0))

Зачем использовать setq когда у вас есть let? Локальные переменные n а также board не используются.

MAKE-ARRAY ожидает список чисел, а не список символов.

Я предлагаю вам использовать простое введение в Lisp ( Common Lisp: Нежное введение в символьные вычисления - скачать бесплатно) и справочник Lisp ( CL Hyperspec).