#!/usr/bin/python
# -*- coding: utf-8 -*-
# Jakub Burzyński 2011 Python 2.7.2
# www.algorytm.org
# Problem skoczka (konika) szachowego,
# dodatkowo mierzy czas wykonania

import sys, time

g_size = -1    # rozmiar szachownicy
g_board = []   # szachownica
g_d = 0        # zmienna do mierzenia czasu

def main():
	global g_size,g_d
	print "Problem skoczka na szachownicy"
	start_x = 0
	start_y = 0

	while g_size == -1:
		if len(sys.argv) == 2:
			try:
				g_size = int(sys.argv[1])
				break
			except:
				print("Bledny parametr! <rozmiar>")

		g_size = input("Rozmiar szachownicy: ")
		start_x = input("Pozycja X: ")
		start_y = input("Pozycja Y: ")

	for i in range(0, g_size):
		g_board.append(g_size*[0])
	
	sys.stdout.write("... ")

	g_d = time.strftime("%S")
	move(start_y, start_x, 1)
	
	print("Nie znaleziono rozwiazania")


def move(y,x,counter):
	assert g_board[y][x] == 0
	g_board[y][x] = counter
	
	if counter == g_size*g_size: # sprawdz czy znaleziono rozwiazanie - liczba ruchow równa liczbie pól	
		drawChessboard()						
		sys.exit(1)							
		
	jumps = ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)) # możliwe ruchy skoczka
	for jump in jumps:
		ty,tx = y+jump[0],x+jump[1]
		if canMove(ty,tx):
			move(ty,tx,counter+1)	# rekurencja
	g_board[y][x] = 0 

	
def canMove(ty,tx): # sprawdza czy ruch nie wychodzi poza szachownice
	return ty>=0 and tx>=0 and ty<g_size and tx<g_size and g_board[ty][tx] == 0
	
	
def drawChessboard(): # wypisuje szachownicę z rozwiązaniem
	global g_d	
	d2 = time.strftime("%S")
	delta = int(d2)-int(g_d)
	print(str(delta) + "s")
	
	scale = len(str(g_size*g_size))
	print(g_size*("+" + scale*"-") + "+")
	for linia in g_board:
		for kolumna in linia:
			sys.stdout.write("|%*d" % (scale,kolumna))
		print("|\n"+g_size*("+" + scale*"-") + "+")

		
if __name__ == "__main__":
    main()