說明
騎士旅遊（Knight
tour）在十八世紀初倍受數學家與拼圖迷的注意，它什麼時候被提出已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個位置出發，它要如何走完[所有的位置？
解法
騎士的走法，基本上可以使用遞迴來解決，一個聰明的解法由J.C.
Warnsdorff在1823年提出，簡單的說，先將最難的位置走完，接下來的路就寬廣了，騎士所要走的下一步，「為下一步再選擇時，所能走的步數
最少 的一步。」，使用這個方法，可以有較高的機率找出走法。
演算法
FOR(m = 2; m <= 總步數; m++)
測試下一步可以走的八個方向，記錄可停留的格數 count。
IF(count == 0)
遊歷失敗
ELSE IF(count == 1)
下一步只有一個可能
ELSE
找出下一步的出路最少的格子，如果出路值相同，則選第一個遇到的出路。
走最少出路的格子，記錄騎士的新位置。
def step(x, y) {
(return new Object([
['x', x],
['y', y]
]))
}
def isVisitable(board, st) {
(return st.x > -1 and st.x < 8 and
st.y > -1 and st.y < 8 and
board.get(st.x).get(st.y) == 0)
}
def possible(board, st) {
(dirs = [
[-2, 1], [-1, 2], [1, 2], [2, 1],
[2, -1], [1, -2], [-1, -2], [-2, -1]
])
return dirs.map(dir -> step(st.x + dir.get(0), st.y + dir.get(1))) \
.filter(s -> isVisitable(board, s))
}
def hard(board, steps) {
(minIdx = range(0, steps.length())
.map(i -> [i, possible(board, steps.get(i)).length()])
.sort((idxL1, idxL2) -> idxL1.get(1) - idxL2.get(1))
.get(0)
.get(0))
return steps.get(minIdx)
}
def travel(start) {
board = range(0, 8).map(_ -> List.create(8, 0))
board.get(start.x).set(start.y, 1)
current = start
s = 2
while s < 65 {
possibleSteps = possible(board, current)
if possibleSteps.isEmpty() {
break
}
current = possibleSteps.get(0) if possibleSteps.length() == 1 \
else hard(board, possibleSteps)
board.get(current.x).set(current.y, s)
s += 1
}
return board
}
def printRow(row) {
row.forEach(n -> print((n if n > 9 else ' ' + n) + ' '))
println()
}
travel(step(5, 6)).forEach(printRow)
#include <stdio.h>
#define SIZE 8
typedef struct {
int x;
int y;
} Step;
Step step(int, int);
void travel(int[][SIZE], Step);
void possible(int[][SIZE], Step, int*);
int count(int*);
Step get(Step, int*, int);
Step hard(int[][SIZE], Step, int*);
int isVisitable(int[][SIZE], Step);
int main(void) {
int board[SIZE][SIZE] = {0};
travel(board, step(5, 6));
int i;
for(i = 0; i < SIZE; i++) {
int j;
for(j = 0; j < SIZE; j++) {
printf("%3d", board[i][j]);
}
printf("\n");
}
return 0;
}
Step step(int x, int y) {
Step s = {x, y};
return s;
}
void travel(int board[][SIZE], Step start) {
board[start.x][start.y] = 1;
Step current = start;
int s;
for(s = 2; s < 65; s++) {
int possibleSteps[SIZE] = {0};
possible(board, current, possibleSteps);
int c = count(possibleSteps);
if(c == 0) {
break;
}
if(c == 1) {
current = get(current, possibleSteps, 1);
}
else {
current = hard(board, current, possibleSteps);
}
board[current.x][current.y] = s;
}
}
void possible(int board[][SIZE], Step current, int* possibleSteps) {
int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
int i;
for(i = 0; i < SIZE; i++) {
Step s = step(current.x + dirs[i][0], current.y + dirs[i][1]);
if(isVisitable(board, s)) {
possibleSteps[i] = 1;
}
}
}
int count(int* possibleSteps) {
int c, i;
for(c = 0, i = 0; i < SIZE; i++) if(possibleSteps[i]) {
c++;
}
return c;
}
Step get(Step current, int* possibleSteps, int number) {
int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
int c, i;
for(c = 0, i = 0; i < SIZE; i++) if(possibleSteps[i]) {
c++;
if(c == number) {
break;
}
}
return step(current.x + dirs[i][0], current.y + dirs[i][1]);
}
Step hard(int board[][SIZE], Step current, int* possibleSteps) {
int minPossibleSteps[SIZE] = {0};
possible(board, get(current, possibleSteps, 1), minPossibleSteps);
int minIndex, i;
for(minIndex = 0, i = 1; i < count(possibleSteps); i++) {
int nextPossibleSteps[SIZE] = {0};
Step s = get(current, possibleSteps, i + 1);
possible(board, s, nextPossibleSteps);
if(count(nextPossibleSteps) < count(minPossibleSteps)) {
minIndex = i;
int j;
for(j = 0; j < SIZE; j++) {
minPossibleSteps[j] = nextPossibleSteps[j];
}
}
}
return get(current, possibleSteps, minIndex + 1);
}
int isVisitable(int board[][SIZE], Step step) {
return step.x > -1 && step.x < SIZE &&
step.y > -1 && step.y < SIZE &&
!board[step.x][step.y];
}
import java.util.*;
import static java.lang.System.out;
public class Knight {
public static class Step {
final int x, y;
public Step(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int[][] travel(Step start) {
int[][] board = new int[8][8];
board[start.x][start.y] = 1;
Step current = start;
for(int s = 2; s < 65; s++) {
List<Step> possibleSteps = possible(board, current);
if(possibleSteps.isEmpty()) {
break;
}
if(possibleSteps.size() == 1) {
current = possibleSteps.get(0);
} else {
current = hard(board, possibleSteps);
}
board[current.x][current.y] = s;
}
return board;
}
public static List<Step> possible(int[][] board, Step step) {
int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
List<Step> steps = new ArrayList<>();
for(int[] dir : dirs) {
Step s = new Step(step.x + dir[0], step.y + dir[1]);
if(isVisitable(board, s)) {
steps.add(s);
}
}
return steps;
}
public static boolean isVisitable(int[][] board, Step step) {
return step.x > -1 && step.x < 8 &&
step.y > -1 && step.y < 8 &&
board[step.x][step.y] == 0;
}
public static Step hard(int[][] board, List<Step> steps) {
int minIndex = 0;
List<Step> minPossibleSteps = possible(board, steps.get(0));
for(int i = 1; i < steps.size(); i++) {
List<Step> possibleSteps = possible(board, steps.get(i));
if(possibleSteps.size() < minPossibleSteps.size()) {
minIndex = i;
minPossibleSteps = possibleSteps;
}
}
return steps.get(minIndex);
}
public static void main(String[] args) {
for(int[] row : travel(new Step(5, 6))) {
for(int step : row) {
out.printf("%3d", step);
}
out.println();
}
}
}
from functools import reduce
class Knight:
@staticmethod
def travel(start):
route = [start]
current = start
for m in range(1, 64):
possibleSteps = Knight.possible(route, current)
if len(possibleSteps) == 0:
break;
if len(possibleSteps) == 1:
current = possibleSteps[0]
else:
current = Knight.hard(route, possibleSteps)
route.append(current)
return route
@staticmethod
def possible(route, step):
dirs = [(-2, 1), (-1, 2), (1, 2), (2, 1),
(2, -1), (1, -2), (-1, -2), (-2, -1)]
steps = [(step[0] + dir[0], step[1] + dir[1]) for dir in dirs]
return [step for step in steps if Knight.isVisitable(route, step)]
@staticmethod
def isVisitable(route, step):
return step[0] > -1 and step[0] < 8 and \
step[1] > -1 and step[1] < 8 and \
not step in route
@staticmethod
def hard(route, steps):
allSteps = [Knight.possible(route, step) for step in steps]
minIndex = reduce(
lambda c, i: i if len(allSteps[i]) < len(allSteps[c]) else c,
range(1, len(steps)), 0)
return steps[minIndex]
route = Knight.travel((5, 6))
for i in range(8):
for j in range(8):
print("%3d" % (route.index((i, j)) + 1), end="")
print()
case class Step(x: Int, y: Int)
object Knight {
def travel(start: Step) = visit(start::Nil, start)
def visit(route: List[Step], step: Step): List[Step] = {
if(route.size == 64) route
else {
val steps = possible(route, step);
steps.size match {
case 0 => route
case 1 => visit(steps.head::route, steps.head)
case _ => val s = hard(route, steps)
visit(s::route, s)
}
}
}
def isVisitable(route: List[Step], step: Step) = {
step.x > -1 && step.x < 8 &&
step.y > -1 && step.y < 8 &&
!route.contains(step)
}
def possible(route: List[Step], step: Step) = {
val dirs = List((-2, 1), (-1, 2), (1, 2), (2, 1),
(2, -1), (1, -2), (-1, -2), (-2, -1));
(for{dir <- dirs
s = Step(step.x + dir._1, step.y + dir._2)
if isVisitable(route, s)
} yield s).toList
}
def hard(route: List[Step], steps: List[Step]) = {
val allSteps = for(step <- steps) yield possible(route, step)
val minIndex = (0 /: (1 until steps.size))((c, i) =>
if(allSteps(i).size < allSteps(c).size) i else c)
steps(minIndex)
}
}
val route = Knight.travel(Step(5, 6))
for(i <- 0 until 8) {
for(j <- 0 until 8) {
printf("%3d", 64 - route.indexOf(Step(i, j)))
}
println
}
#encoding: Big5
class Knight
def self.travel(start)
route = [start]
current = start
63.times do
possibleSteps = possible(route, current)
if possibleSteps.size == 0
break
end
if possibleSteps.size == 1
current = possibleSteps[0]
else
current = hard(route, possibleSteps)
end
route << current
end
route
end
def self.possible(route, step)
[[-2, 1], [-1, 2], [1, 2], [2, 1],
[2, -1], [1, -2], [-1, -2], [-2, -1]]
.map { |dir| {x: step[:x] + dir[0], y: step[:y] + dir[1]} }
.find_all { |s| isVisitable(route, s)}
end
def self.isVisitable(route, step)
step[:x] > -1 and step[:x] < 8 and
step[:y] > -1 and step[:y] < 8 and
not route.include? step
end
def self.hard(route, steps)
allSteps = steps.map { |step| possible(route, step) }
minIndex = (1...steps.size).reduce(0) { |c, i|
if allSteps[i].size < allSteps[c].size; i else c end
}
steps[minIndex]
end
end
route = Knight.travel x: 5, y: 6
0.upto(7) do |i|
0.upto(7) do |j|
printf "%3d ", route.index({x: i, y: j}) + 1
end
puts
end
var knight = function() {
function possible(board, step) {
return [[-2, 1], [-1, 2], [1, 2], [2, 1],
[2, -1], [1, -2], [-1, -2], [-2, -1]]
.map(function(dir) {
return {x: step.x + dir[0], y: step.y + dir[1]};
})
.filter(function(s) {
return isVisitable(board, s);
});
}
function isVisitable(board, step) {
return step.x > -1 && step.x < 8 &&
step.y > -1 && step.y < 8 &&
board[step.x][step.y] === undefined;
}
function hard(board, steps) {
minIndex = 0;
minPossibleSteps = possible(board, steps[0]);
for(var i = 0; i < steps.length; i++) {
possibleSteps = possible(board, steps[i]);
if(possibleSteps.length < minPossibleSteps.length) {
minIndex = i;
minPossibleSteps = possibleSteps;
}
}
return steps[minIndex];
}
return function(start) {
var board = [[], [], [], [], [], [], [], []];
board[start.x][start.y] = 1;
current = start;
for(var s = 2; s < 65; s++) {
possibleSteps = possible(board, current);
if(possibleSteps.length === 0) {
break;
}
if(possibleSteps.length === 1) {
current = possibleSteps[0];
} else {
current = hard(board, possibleSteps);
}
board[current.x][current.y] = s;
}
return board;
};
}();
var layout = '';
knight({x: 5, y: 6}).forEach(function(row) {
row.forEach(function(step) {
layout += ' ' + ((step + '').length === 2 ? '' : ' ') + step;
});
layout += '\n';
});
print(layout);
import Control.Monad
import Text.Printf
import Data.List
travel start = visit (start:[]) start
visit route step =
if length route == 64 then route
else case (length steps) of
0 -> route
1 -> visit ((head steps):route) (head steps)
_ -> visit (s:route) s
where steps = possible route step
s = hard route steps
possible route (x, y) = [step | step <- steps, isVisitable route step]
where dirs = [[-2, 1], [-1, 2], [1, 2], [2, 1],
[2, -1], [1, -2], [-1, -2], [-2, -1]]
steps = [(x + dir !! 0, y + dir !! 1) | dir <- dirs]
isVisitable route step@(x, y) =
x > -1 && x < 8 && y > -1 && y < 8 && not (step `elem` route)
hard route steps = steps !! (foldl (\c i ->
if length (allSteps !! i) < length (allSteps !! c)
then i else c)
0 [1..length steps - 1])
where allSteps = [possible route step | step <- steps]
main = do
let route = travel (5, 6)
forM [0..7] (\i -> do
forM [0..7] (\j -> do
let (Just a) = elemIndex (i, j) route
printf "%3d" \$ 64 - a)
putStrLn "")
contains(Pt, [Pt|_]).
contains(Pt, [_|T]) :- contains(Pt, T).
visitable([X, Y], Route) :-
X > -1, X < 8,
Y > -1, Y < 8,
not(contains([X, Y], Route)).
possible([], _, _, []).
possible([[Dx, Dy]|T], [Px, Py], Route, Npts) :-
possible(T, [Px, Py], Route, Pts),
Npx is Px + Dx, Npy is Py + Dy,
conVisitable([Npx, Npy], Route, Pts, Npts).
conVisitable(Npt, Route, Pts, [Npt|Pts]) :- visitable(Npt, Route), !.
conVisitable(_, _, Pts, Pts).
possible(Pt, Route, Pts) :-
Dirs = [[-2, 1], [-1, 2], [1, 2], [2, 1],
[2, -1], [1, -2], [-1, -2], [-2, -1]],
possible(Dirs, Pt, Route, Pts).
possibleLens([], _, []).
possibleLens([H|T], Route, [LEN|PLENS]) :-
possibleLens(T, Route, PLENS),
possible(H, Route, Pts),
length(Pts, LEN).
minIdx(Lt, LEN, CMidx, CMidx) :- length(Lt, LEN), !.
minIdx(Lt, Idx, CMidx, MinIdx) :-
Nidx is Idx + 1,
nth0(Idx, Lt, Elem), nth0(CMidx, Lt, MinValue),
(
Elem < MinValue -> minIdx(Lt, Nidx, Idx, MinIdx);
minIdx(Lt, Nidx, CMidx, MinIdx)
).
hard(Pts, Route, HardPt) :-
possibleLens(Pts, Route, LENS),
minIdx(LENS, 0, 0, MinIdx),
nth0(MinIdx, Pts, HardPt).
visit(Route, _, Route) :- length(Route, 64), !.
visit(Route, Pt, Solution) :-
possible(Pt, Route, Pts),
length(Pts, PtsLen),
visit(PtsLen, Route, Pts, Solution).
visit(0, Route, _, Route).
visit(1, Route, [H|_], Solution) :- visit([H|Route], H, Solution).
visit(_, Route, Pts, Solution) :-
hard(Pts, Route, HardPt), visit([HardPt|Route], HardPt, Solution).
indexOf(_, [], _, -1).
indexOf(Pt, [Pt|_], CIdx, CIdx).
indexOf(Pt, [_|T], CIdx, Idx) :- NIdx is CIdx + 1, indexOf(Pt, T, NIdx, Idx).
range(From, To, Xs) :- findall(X, between(From, To, X), Xs).
forEachJ([H|T], I, Solution) :-
indexOf([I, H], Solution, 0, Idx),
P is 64 - Idx,
writef("%3L", [P]),
forEachJ(T, I, Solution).
forEachJ([], _, _) :- nl.
forEachI([H|T], Solution) :-
range(0, 7, Xs),
forEachJ(Xs, H, Solution),
forEachI(T, Solution).
forEachI([], _).
main(_) :-
Start = [5, 6],
visit([Start], Start, Solution),
range(0, 7, Xs),
forEachI(Xs, Solution).
