m*n的棋盘中有一匹（或者“个”吧）,从此无限棋盘上任一点出发,能够跳到任意一个指定的点求证m,n互质,且不全为奇数.马走“日”字应该知道

Question

m*n的棋盘中有一匹（或者“个”吧）,从此无限棋盘上任一点出发,能够跳到任意一个指定的点 【求证】m,n互质,且不全为奇数.
【马走“日”字应该知道】

Answer 1

;; 回溯算法求解马的跳棋盘问题
;; 假设一开始马在(1, 1)位置,目标为(9, 5).棋盘大小为9X5.


;; 状态表示,x, y代表马的坐标
(defstruct state x y)


;; 初始状态,马在左下角
(defconstant init-state
(make-state :x 1 :y 1))

;; 目标状态,马在左上角
(defconstant goal-state
(make-state :x 9 :y 5))


;; 状态转移 -- 代表八个方向上的马的跳跃时的坐标的变化.
(defconstant actions-table
'((1 2) (2 1) (-1 2) (-2 1)
(-1 -2) (-2 -1) (1 -2) (2 -1)))


;; 顶层调用函数, 函数值为能够达到目标状态的路径中的一条.
(defun solve ()
(reverse (backtrace (list init-state))))


;; 回溯算法求解,并不一定得到最优解.
(defun backtrace (path)
(let ((current-state (car path)))
(if (state-equal current-state goal-state) path ;找到解,返回路径
(progn
(push (make-state) path)
(loop for action in actions-table
do (setf (car path)
(next-state current-state action))
thereis (and (verify (car path))
(not (find (car path) (cdr path)
:test #'state-equal))
(backtrace path)))))))


;; 判断两个状态是否相同,状态S1的x,y和S2的x,y分别相等的
;; 时候,就认为S1和S2相同
(defun state-equal (S1 S2)
(and (equal (state-x S1) (state-x S2))
(equal (state-y S1) (state-y S2))))


;; 后续状态计算
(defun next-state (current-state action)
"current-state 为当前状态, action为活动, 函数值为当前状态加上
活动action的后续状态."
(let ((S (make-state)))
(setf (state-x S)
(+ (state-x current-state)
(first action))
(state-y S)
(+ (state-y current-state)
(second action)))
S))

;; 检查状态S是否合法,当状态S在棋盘种的时候,S就是合法的.
(defun verify (S)
(and (= (state-x S) 1)
(= (state-y S) 1)))
>(solve)