騎士走棋盤

騎士旅遊（Knight tour）在十八世紀初倍受數學家與拼圖迷的注意，它什麼時候被提出已不可考，騎士走法為西洋棋的走法，騎士可以由任一位置出發，要如何走完全部位置？

解法思路

J.C. Warnsdorff 在 1823 年提出，將最難的位置走完，接下來的路就寬廣了，騎士要走的下一步，「為下一步再選擇時，能走的步數最少的一步」，使用這個方法，有較高的機率找出走法。

FOR(m = 2; m <= 總步數; m++) 
    測試下一步可以走的八個方向，記錄可停留的格數 count。

    IF(count == 0) 
        遊歷失敗
    ELSE IF(count == 1) 
        下一步只有一個可能
    ELSE 
        找出下一步的出路最少的格子，如果出路值相同，則選第一個遇到的出路。 

    走最少出路的格子，記錄騎士的新位置。

程式實作

#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: UTF-8
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).

# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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)