Knight's Tour

knight.cpp

// Solver of Knight's Tour using Warnsdorff's algorithm and Schwenk's theorem

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <cstdlib>

using namespace std;

struct Node {
    int row, col;
    bool visited;
    vector<Node*> next;

    Node(int r, int c) : row(r), col(c), visited(false) { }
};

class IsUnvisited {
public:
    bool operator()(const Node* a) { return !a->visited; }
};

class IsVisited {
public:
    bool operator()(const Node* a) { return a->visited; }
};

class NotEqualUnvisited {
private:
    const int cnt;

public:
    NotEqualUnvisited(const Node* a) : cnt(count_if(a->next.begin(), a->next.end(), IsUnvisited())) { }
    bool operator()(const Node* a)
    { return count_if(a->next.begin(), a->next.end(), IsUnvisited()) != cnt; }
};

class LessMovable {
public:
    bool operator()(const Node* a, const Node* b)
    {
        int cnt_a = count_if(a->next.begin(), a->next.end(), IsUnvisited());
        int cnt_b = count_if(b->next.begin(), b->next.end(), IsUnvisited());
        return cnt_a < cnt_b;
    }
};

class KnightTour {
private:
    int nrow, ncol;
    vector<pair<int, int> > moves;
    vector<Node*> nodes, tour, best_tour;
    bool is_closed;

public:
    KnightTour(int r, int c, bool closed) : nrow(r), ncol(c), is_closed(closed)
    {
        // Knight can move two horizontally and one vertically,
        // or one horizontally and two vertically.
        moves.push_back(make_pair( 2,  1));
        moves.push_back(make_pair( 1,  2));
        moves.push_back(make_pair( 2, -1));
        moves.push_back(make_pair( 1, -2));
        moves.push_back(make_pair(-2,  1));
        moves.push_back(make_pair(-1,  2));
        moves.push_back(make_pair(-2, -1));
        moves.push_back(make_pair(-1, -2));
    }
    void search(Node* node);
    void run(int start_pos);
    void print();
};

void KnightTour::search(Node* node)
{
    if (node->visited) return;
    if (best_tour.size() == nrow * ncol) {
        // for Closed Knight's Tour
        if (is_closed) {
            if (find(best_tour.back()->next.begin(), best_tour.back()->next.end(), best_tour.front()) != best_tour.back()->next.end()) return;
            for (vector<Node*>::iterator p = best_tour.back()->next.begin(); p != best_tour.back()->next.end(); ++p) {
                vector<Node*>::iterator q = find(best_tour.begin(), best_tour.end(), *p) + 1;
                vector<Node*>::iterator r = find(best_tour.front()->next.begin(), best_tour.front()->next.end(), *q);
                if (r != best_tour.front()->next.end()) {
                    reverse(q, best_tour.end());
                    return;
                }
            }
            best_tour.clear();
        }
        return;
    }
    node->visited = true;
    tour.push_back(node);
    if (best_tour.size() < tour.size()) best_tour = tour;
    // Warnsdorff's algorithm
    sort(node->next.begin(), node->next.end(), LessMovable());
    vector<Node*> next(node->next);
    next.erase(remove_if(next.begin(), next.end(), IsVisited()), next.end());
    if (!next.empty())
        next.erase(remove_if(next.begin(), next.end(), NotEqualUnvisited(next.front())), next.end());
    for (vector<Node*>::iterator p = next.begin(); p != next.end(); ++p)
        search(*p);
    node->visited = false;
    tour.pop_back();
}

void KnightTour::run(int start_pos)
{
    // initialization for nodes
    for (int i = 0; i < nrow; i++)
        for (int j = 0; j < ncol; j++)
            nodes.push_back(new Node(i, j));
    for (vector<Node*>::iterator p = nodes.begin(); p != nodes.end(); ++p) {
        for (vector<pair<int, int> >::iterator q = moves.begin(); q != moves.end(); ++q) {
            int r = (*p)->row + q->first;
            int c = (*p)->col + q->second;
            if (r >= 0 && r < nrow && c >= 0 && c < ncol)
                (*p)->next.push_back(nodes[r*ncol+c]);
        }
    }
    // Schwenk's theorem
    if (is_closed && (nrow * ncol % 2 == 1 || (min(nrow, ncol) == 2 || min(nrow, ncol) == 4)
        || (min(nrow, ncol) == 3 && (max(nrow, ncol) == 4 || max(nrow, ncol) == 6 || max(nrow, ncol) == 8))))
        return;
    if (!is_closed && nrow * ncol % 2 == 1 && start_pos % 2 == 1) return;

    search(nodes[start_pos]);
}

void KnightTour::print()
{
    if (best_tour.size() < nrow * ncol) {
        cout << "No solution." << endl;
        return;
    }
    vector<vector<int> > board(nrow, vector<int>(ncol));
    int cnt = 1;
    for (vector<Node*>::iterator p = best_tour.begin(); p != best_tour.end(); ++p)
        board[(*p)->row][(*p)->col] = cnt++;
    int width = static_cast<int>(log10(static_cast<double>(nrow * ncol)) + 2);
    for (int i = 0; i < nrow; i++) {
        for (int j = 0; j < ncol; j++) cout << setw(width) << board[i][j];
        cout << endl;
    }
}

int main(int argc, char* argv[])
{
    if (argc <= 2) {
        cerr << "Usage: " << argv[0] << " nrow ncol [start_row=0 start_col=0] [closed]" << endl;
        exit(1);
    }

    int nrow = atoi(argv[1]);
    int ncol = atoi(argv[2]);
    int r = 0, c = 0;
    if (argc > 4) {
        r = atoi(argv[3]);
        c = atoi(argv[4]);
    }
    bool is_closed = false;
    if (argv[argc-1][0] == 'c') is_closed = true;

    KnightTour kt(nrow, ncol, is_closed);

    kt.run(r * ncol + c);
    kt.print();

    return 0;
}

show_knight.py

#!/usr/bin/env python

import sys, os, Image, ImageDraw

def draw_board(board, nrow, ncol, size, offset_x, offset_y, out_image):
    im = Image.new("RGB", size)
    im.paste((255, 255, 255))
    draw = ImageDraw.Draw(im)
    for i in range(0, size[0], offset_x):
        draw.line((i, 0, i, size[1]), fill=0)
    for i in range(0, size[1], offset_y):
        draw.line((0, i, size[0], i), fill=0)
    for i in range(0, size[0], offset_x):
        for j in range(0, size[1], offset_y):
            if (i // offset_x + j // offset_y) % 2 == 1:
                im.paste((190, 190, 190), (i + 1, j + 1, i + offset_x, j + offset_y))
    for i in range(nrow * ncol - 1):
        draw.line((board[i] % ncol * offset_x + offset_x // 2, board[i] // ncol * offset_y + offset_y // 2, board[i+1] % ncol * offset_x + offset_x // 2, board[i+1] // ncol * offset_y + offset_y // 2), fill=(255, 0, 0))
    if sorted([abs(board[nrow*ncol-1] % ncol - board[0] % ncol), abs(board[nrow*ncol-1] // ncol - board[0] // ncol)]) == [1, 2]:
        draw.line((board[nrow*ncol-1] % ncol * offset_x + offset_x // 2, board[nrow*ncol-1] // ncol * offset_y + offset_y // 2, board[0] % ncol * offset_x + offset_x // 2, board[0] // ncol * offset_y + offset_y // 2), fill=(255, 0, 0))
    im.save(out_image)

def main(args):
    if len(args) < 3:
        print >>sys.stderr, "Usage: %s in_datafile out_imagefile [size_x=400 size_y=400]" % os.path.basename(args[0])
        sys.exit(1)

    in_file, out_image = args[1:3]
    if len(args) < 5: size = (400, 400)
    else: size = map(int, args[3:5])
    data = [map(int, l.strip().split()) for l in file(in_file)]
    nrow, ncol = len(data), len(data[0])
    board = range(nrow * ncol)
    cnt = 0
    for r in data:
        for c in r:
            board[c-1] = cnt
            cnt += 1
    offset_x, offset_y = size[0] // ncol, size[1] // nrow
    size = (offset_x * ncol + 1, offset_y * nrow + 1)
    draw_board(board, nrow, ncol, size, offset_x, offset_y, out_image)

if __name__ == "__main__": main(sys.argv)

http://handasse.blogspot.com/2010/01/c.html