#/***********************************************************
#    knight.rb -- 騎士巡歴の問題
#***********************************************************/

N = 5

$board = []; row = []
(N+4).times { row.push(0) }
(N+4).times { $board.push(row.dup) }

$dx = [ 2, 1,-1,-2,-2,-1, 1, 2 ] # 横変位 
$dy = [ 1, 2, 2, 1,-1,-2,-2,-1 ] # 縦変位 

$solution = 0
def printboard                   # 番面を出力 
    printf("\n解 %d\n", $solution += 1)
    for i in 2..(N+1)
        for j in 2..(N+1); printf("%4d", $board[i][j]); end
        printf("\n")
    end
end

$count = 0
def try(x,  y)  # 再帰的に試みる 
    if ($board[x][y] != 0); return; end  # すでに訪れた 
    $board[x][y] = ($count += 1)
    if ($count == N * N); printboard()  # 完成 
    else; for i in 0...8; try(x + $dx[i], y + $dy[i]); end
    end
    $board[x][y] = 0;  $count -= 1
end

for i in 0..(N+3)
    for j in 0..(N+3); $board[i][j] = 1; end
end
for i in 2..(N+1)
    for j in 2..(N+1); $board[i][j] = 0; end
end
try(2, 2)

exit 0