There’s a chess board of size
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
#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;
}#!/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)]
# $(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)