Skip to content

Instantly share code, notes, and snippets.

@xiaohanyu
Last active April 12, 2017 10:22
Show Gist options
  • Save xiaohanyu/2b37f09b3cc8f6d05836 to your computer and use it in GitHub Desktop.
Save xiaohanyu/2b37f09b3cc8f6d05836 to your computer and use it in GitHub Desktop.
Knight problem

Problem

There’s a chess board of size $N × N$, and an piece Knight, which has the initial position $(x, y)$.

Knight can step by going forward or backward two units in one direction, and one units in the other direction.

Find a way to position $(N, N)$ for this Knight piece.

Solution

C++

#include <queue>
#include <limits>
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <queue>
#include <list>
#include <cstdlib>
using namespace std;

struct vertex
{
    int index;                  /// the vertex index, also the vertex name
    vertex* prev;               /// the prev vertex node computed by bfs and bfs_shortest
    int dist;                   /// the distance to the start computed by bfs
                                /// and bfs_shortest
    vector<vertex*> adj;        /// the adjacency list for this vertex

    vertex(int idx)
        : index(idx) {
        reset();
    }

    void reset() {
        prev = NULL;
        dist = numeric_limits<int>::max();
    }
};

class graph
{
public:
    graph() { }
    ~graph();
    void add_edge(int start, int end);
    void bfs(int start);
    void bfs_shortest(int start);
    list<int> get_path(int end) const;
    void print_graph() const;

protected:
    vertex* get_vertex(int idx);
    void reset_all();
    list<int> get_path(const vertex &end) const;

private:
    /// disable copy
    graph(const graph &rhs);
    graph& operator=(const graph &rhs);

    typedef map<int, vertex*, less<int> > vmap;
    vmap vm;
};

graph::~graph() {
    for (vmap::iterator itr = vm.begin(); itr != vm.end(); ++itr)
    {
        delete (*itr).second;
    }
}

/**
 * return a new vertex if not exists, else return the old vertex, using std::map
 * for vertex management
 *
 * @param idx vertex index
 *
 * @return a (new) vertex of index idx
 */
vertex* graph::get_vertex(int idx) {
    /// cout << "idx: " << idx << "\tvm.size(): " << vm.size() << endl;
    vmap::iterator itr = vm.find(idx);

    if (itr == vm.end())
    {
        vm[idx] = new vertex(idx);
        return vm[idx];
    }

    return itr->second;
}

/**
 * clear all vertex state flags
 *
 */
void graph::reset_all() {
    for (vmap::iterator itr = vm.begin(); itr != vm.end(); ++itr)
    {
        (*itr).second->reset();
    }
}

/**
 * add an edge(start --> end) to the graph
 *
 * @param start
 * @param end
 */
void graph::add_edge(int start, int end) {
    vertex *s = get_vertex(start);
    vertex *e = get_vertex(end);
    s->adj.push_back(e);
}

/**
 * print the graph vertex by vertex(with adj list)
 *
 */
void graph::print_graph() const {
    for (vmap::const_iterator itr = vm.begin(); itr != vm.end(); ++itr)
    {
        cout << itr->first << ": ";
        for (vector<vertex*>::const_iterator vitr = itr->second->adj.begin();
             vitr != itr->second->adj.end();
             ++vitr)
        {
            cout << (*vitr)->index << " ";
        }
        cout << endl;
    }
}

/**
 * traversal the graph breadth-first
 *
 * @param start the starting point of the bfs traversal
 */
void graph::bfs(int start) {
    if (vm.find(start) == vm.end())
    {
        cerr << "graph::bfs(): invalid point index " << start << endl;
        return;
    }

    vertex *s = vm[start];
    queue<vertex*> q;
    q.push(s);
    s->dist = -1;

    while (!q.empty()) {
        vertex *v = q.front();
        cout << v->index << " ";
        q.pop();

        for (int i = 0; i < v->adj.size(); ++i)
        {
            if (v->adj[i]->dist != -1)
            {
                q.push(v->adj[i]);
                v->adj[i]->dist = -1;
            }
        }
    }
}

/**
 * the unweighted shortest path algorithm, using a std::queue instead of
 * priority_queue(which is used in dijkstra's algorithm)
 *
 * @param start
 */
void graph::bfs_shortest(int start) {
    if (vm.find(start) == vm.end())
    {
        cerr << "graph::bfs_shortest(): invalid point index " << start << endl;
        return;
    }

    vertex *s = vm[start];

    queue<vertex*> q;
    q.push(s);
    s->dist = 0;

    while (!q.empty()) {
        vertex *v = q.front();
        q.pop();

        for (int i = 0; i < v->adj.size(); ++i)
        {
            vertex *w = v->adj[i];
            if (w->dist == numeric_limits<int>::max())
            {
                w->dist = v->dist + 1;
                w->prev = v;
                q.push(w);
            }
        }
    }
}

/**
 * get the path from start to end
 *
 * @param end
 *
 * @return a list of vertex which denotes the shortest path
 */
list<int> graph::get_path(int end) const {
    vmap::const_iterator itr = vm.find(end);

    if (itr == vm.end())
    {
        cerr << "graph::get_path(): invalid point index " << end << endl;
        return list<int>();
    }

    const vertex &w = *(*itr).second;

    if (w.dist == numeric_limits<int>::max())
    {
        cout << "vertex " << w.index << " is not reachable";
        return list<int>();
    }
    else {
        return get_path(w);
    }
}

/**
 * the internal helper function for the public get_path function
 *
 * @param end
 *
 * @return a list of vertex index
 */
list<int> graph::get_path(const vertex &end) const {
    list<int> l;
    const vertex *v = &end;

    while (v != NULL) {
        l.push_front(v->index);
        v = v->prev;
    }

    return l;
}

class chessboard {
private:
    struct point {
        int x;
        int y;

        point(int px, int pb)
            : x(px), y(pb) { }
    };

public:
    chessboard(int s);
    void solve_knight(int x, int y);

protected:
    bool is_valid(const point &p);
    point next_point(const point &p, int i);

private:
    graph board;
    int size;
};

/**
 * constructor, build a underlying graph from a chessboard of size s
 *
 * @param s
 */
chessboard::chessboard(int s)
    : size(s) {
    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            int start = i * size + j;
            point p(i, j);

            for (int k = 0; k < 8; ++k)
            {
                /// the next possible knight position
                point np = next_point(p, k);

                if (is_valid(np))
                {
                    int end = np.x * size + np.y;

                    /// add edges in both directions
                    board.add_edge(start, end);
                    board.add_edge(end, start);
                }
            }
        }
    }
}

/**
 * find and print a path from (x, y) to (size, size)
 *
 * @param x
 * @param y
 */
void chessboard::solve_knight(int x, int y) {
    int start = (x-1) * size + (y-1);
    int end = size * size - 1;

    board.bfs_shortest(start);
    list<int> l = board.get_path(end);

    int count = 0;
    for (list<int>::const_iterator itr = l.begin(); itr != l.end(); ++itr)
    {
        cout << "(" << *itr/size + 1 << ", " << *itr%size + 1<< ")";
        if (count++ != l.size() - 1)
        {
            cout << " -> ";
        }
    }
    cout << endl;
}

/**
 * whether or not the point is valid in the chessboard
 *
 * @param p
 *
 * @return true for valid
 */
bool chessboard::is_valid(const point &p) {
    if (p.x < 0 || p.x >= size - 1 || p.y < 0 || p.y >= size - 1)
    {
        return false;
    }
    return true;
}

/**
 * the next possible position, every has 8 next possible position, though not
 * all 8 position is valid
 *
 * @param p the original knight position
 * @param i
 *
 * @return
 */
chessboard::point chessboard::next_point(const point &p, int i) {
    int knight[8][2] = {
        {2, 1}, {2, -1},
        {-2, 1}, {-2, -1},
        {1, 2}, {1, -2},
        {-1, 2}, {-1, -2}
    };

    return point(p.x + knight[i][0], p.y + knight[i][1]);
}

int main(int argc, char *argv[])
{
    if (argc != 4)
    {
        cerr << "Wrong arguments! Usage: knight.bin N x y" << endl;
        return -1;
    }

    int N = atoi(argv[1]);
    int x = atoi(argv[2]);
    int y = atoi(argv[3]);

    chessboard chess(N);

    chess.solve_knight(x, y);

    return 0;
}

Python

#!/usr/bin/env python2

import sys

class graph(object):
    """unweighted directed graph
    """

    def __init__(self):
        """set _vmap to and _vprev an empty python dict
        all vertex are represented by a simple index

        _vmap: {vertex x: x's adjacency list}
        _vprev: {vertex x: x's prev vertex computed by bfs routine}
        """
        self._vmap = {};
        self._vprev = {};

    def add_edge(self, start, end):
        """add an edge to the graph
        """
        if self._vmap.has_key(start):
            self._vmap[start].append(end)
        else:
            self._vmap[start] = [end]

    def bfs_shortest(self, start):
        """one-source shortest-path algorithm
        """
        queue = [start]

        self._vprev[start] = None

        while len(queue) != 0:
            v = queue[0]
            queue.pop(0)

            if self._vmap.has_key(v):
                v_adj = self._vmap[v]
            else:
                continue

            for nextv in v_adj:
                if self._vprev.has_key(nextv):# and self._vprev[nextv] is not None:
                    # nextv has already found its parent""
                    continue
                else:
                    queue.append(nextv)
                    self._vprev[nextv] = v

    def get_path(self, end):
        """return the shortest path as a python list
        """
        v = end;
        path = []
        while self._vprev.has_key(v) and self._vprev[v] is not None:
            path.insert(0, v)
            v = self._vprev[v]

        if self._vprev.has_key(v):
            path.insert(0, v)   # insert the start point to the path
        else:
            print "destination %d is not exist or unreachable" % v

        return path

class chessboard(object):
    """a chessboard of size n*n class
    """

    def __init__(self, n):
        """build the internal graph representation of the chessboard

        Arguments:
        - `n`: size of the chessboard
        """
        self._size = n
        self._board = graph()

        next_point = ((2, 1), (2, -1), \
                      (1, 2), (1, -2), \
                      (-2, 1), (-2, -1), \
                      (-1, 2), (-1, -2))

        for x in range(n):
            for y in range(n):
                start = self.point2index(x, y)
                for dx, dy in next_point:
                    nx = x + dx
                    ny = y + dy

                    if self.is_valid(nx, ny):
                        end = self.point2index(nx, ny)
                        self._board.add_edge(start, end)

    def is_valid(self, x, y):
        """whether or not point (x, y) is valid in the chessboard
        """
        return 0 <= x < self._size and 0 <= y < self._size

    def point2index(self, x, y):
        """convert a chessboard point to the internal graph vertex index
        """
        return x * self._size + y

    def index2point(self, p):
        """convert the internal graph vertex index back to a chessboard point
        """
        return (p / self._size, p % self._size)

    def solve_knight(self, x, y):
        """just solve it
        """
        start = self.point2index(x, y)
        end = self.point2index(self._size - 1, self._size - 1)
        self._board.bfs_shortest(start)
        path = [self.index2point(x) for x in self._board.get_path(end)]
        return [(x + 1, y + 1) for x, y in path]

def main():
    """main routine
    """
    # g = graph()
    # g.add_edge(1, 2)
    # g.add_edge(1, 3)
    # g.add_edge(2, 3)
    # g.add_edge(3, 4)
    # g.bfs_shortest(1)
    # print g.get_path(4)

    if len(sys.argv) != 4:
        print """Wrong arguments! Usage: ./knight.py N x y
        """
        return -1

    N = int(sys.argv[1])
    x = int(sys.argv[2])
    y = int(sys.argv[3])

    chess = chessboard(N)

    print chess.solve_knight(x - 1, y - 1)

    return 0

if __name__ == "__main__":
    main()


# some test data
# $ ./knight.py 6 2 2
# [(2, 2), (4, 3), (6, 4), (4, 5), (6, 6)]
# $ ./knight.py 6 2 2
# [(2, 2), (4, 3), (6, 4), (4, 5), (6, 6)]
# $ ./knight.py 4 2 2
# [(2, 2), (4, 3), (2, 4), (3, 2), (4, 4)]
# $ ./knight.py 4 1 1
# [(1, 1), (3, 2), (4, 4)]
# $ ./knight.py 4 2 3
# [(2, 3), (4, 4)]
# $ ./knight.py 20 2 3
# [(2, 3), (4, 4), (6, 5), (8, 6), (10, 7), (12, 8), (14, 9), (16, 10), (18, 11), (20, 12), (19, 14), (20, 16), (19, 18), (20, 20)]
# $

Lisp

(defun point2index (x y n)
  "convert a coordinate point to an index"
  (+ (* x n) y))

(defun index2chess (index n)
  "convert an index back to a coordinate point"
  (floor index n))

(defun build-graph (n)
  "build a undirected unweighted graph according to the chess rules about
knight"
  ;; use lisp array to keep the vertex map
  (let ((vm (make-array (* n n) :initial-element nil)))
    ;;; define some auxiliary function
    (defun is-valid (x y)
      "whether or not the point is valid in the chess board"
      (and (>= x 0) (< x n)
           (>= y 0) (< y n)))
    (defun all-adj-points (x y)
      "build the adjacency list for point (x, y)"
      (let ((adj-list))
        ;; return every possible next knight position as a list
        (dolist (next-step
                  '((2 . -1) (2 . 1)
                    (-2 . -1) (-2 . 1)
                    (1 . -2) (1 . 2)
                    (-1 . -2) (-1 . 2)))
          (let ((nx (+ x (car next-step)))
                (ny (+ y (cdr next-step))))
            (if (is-valid nx ny)
                ;; build the adjacency list
                (push (point2index nx ny n) adj-list))))
        adj-list))
    (dotimes (i n)
      (dotimes (j n)
        (setf (aref vm (point2index i j n)) (all-adj-points i j))))
   vm))

(defun shortest-path (start end graph)
  "one-source unweighted shortest-path algorithm using bfs method"
  (bfs end (list (list start)) graph))

(defun bfs (end queue graph)
  "the internal bfs routine to find shortest path"
  (if (null queue)
      nil
      (let* ((path (car queue))
             (node (car path)))
        (if (eql node end)
            (reverse path)
            (bfs end
                 ;; pop the queue and push some new path into the queue
                 (append (cdr queue)
                         (new-paths path node graph))
                 graph)))))

(defun new-paths (path node graph)
  "return the new-paths according to the node's adj list"
  (mapcar #'(lambda (n)
              (cons n path))
          (cdr (aref graph node))))

(defun solve-knight (n x y)
  "the main function to solve knight problem"
  (let ((path (shortest-path (point2index (- x 1) (- y 1) n)
                             (point2index (- n 1) (- n 1) n)
                             (build-graph n))))
    ;; print the start point first
    (multiple-value-bind (x1 y1)
        (index2point (car path) n)
      (format t "(~A, ~A)" (+ x1 1) (+ y1 1)))
    ;; print the path
    (mapcar #'(lambda (obj)
                (multiple-value-bind (px py)
                    (index2point obj n)
                  (format t " -> (~A, ~A)"
                          (+ px 1)
                          (+ py 1))))
     (cdr path))
    ;; return the path
    path))


;;; some test
;; CL-USER> (SOLVE-KNIGHT 6 1 1)
;; (1, 1) -> (3, 2) -> (4, 4) -> (5, 6) -> (6, 4) -> (4, 5) -> (6, 6)
;; (0 13 21 29 33 22 35)
;; CL-USER> (SOLVE-KNIGHT 8 1 1)
;; (1, 1) -> (3, 2) -> (4, 4) -> (5, 6) -> (6, 8) -> (7, 6) -> (8, 8)
;; (0 17 27 37 47 53 63)
;; CL-USER> (SOLVE-KNIGHT 8 2 1)
;; (2, 1) -> (3, 3) -> (4, 5) -> (5, 7) -> (7, 6) -> (8, 8)
;; (8 18 28 38 53 63)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment