import?java.util.Collections;
import?java.util.Comparator;
import?java.util.List;
import?java.util.Random;
import?java.util.Stack;
public?class?T?{
private?static?final?int[][]?MOVES?=?new?int[][]?{?{?-2,?1?},?{?-1,?2?}, {?1,?2?},?{?2,?1?},?{?2,?-1?},?{?1,?-2?},?{?-1,?-2?},?{?-2,?-1?}?}; private?static?final?int?SIZE?=?8; private?static?final?int?BASE?=?SIZE?+?4; private?static?int[][]?board; private?static?NeighborComparator?neighborComparator?=?new?NeighborComparator(); public?static?void?main(String[]?args)?{board?=?new?int[BASE][BASE];
for?(int?r?=?0;?r?<?BASE;?r++)?{
for?(int?c?=?0;?c?<?BASE;?c++)?{if?(r?<?2?||?r?>?BASE?-?3?||?c?<?2?||?c?>?BASE?-?3)?{
board[r][c]?=?-1;}
}}
int?row?=?2?+?new?Random().nextInt(SIZE);
int?col?=?2?+?new?Random().nextInt(SIZE);
solve(row,?col);
} private?static?void?solve(int?r,?int?c)?{Stack<Cell>?stack?=?new?Stack<Cell>();
int?count?=?1;
Cell?cell?=?new?Cell(r,?c,?neighbors(r,?c));
stack.push(cell);
board[r][c]?=?count++;
while?(!stack.isEmpty())?{
if?(stack.size()?==?SIZE?*?SIZE)?{break;
} cell?=?stack.peek(); if?(cell.nextNeighbor?<?cell.neighbors.size())?{int[]?neighbor?=?cell.neighbors.get(cell.nextNeighbor);
r?=?neighbor[0];
c?=?neighbor[1];
board[r][c]?=?count++;
stack.push(new?Cell(r,?c,?neighbors(r,?c)));
cell.nextNeighbor++;
}?else?{stack.pop();
board[cell.r][cell.c]?=?0;
count--;
}}
if?(stack.size()?==?SIZE?*?SIZE)?{
print();}?else?{
System.out.println("無解");}
} private?static?class?NeighborComparator?implements?Comparator<int[]>?{public?int?compare(int[]?a,?int[]?b)?{
return?a[2]?-?b[2];}
} private?static?List<int[]>?neighbors(int?r,?int?c)?{List<int[]>?neighbors?=?new?ArrayList<>();
for?(int[]?m?:?MOVES)?{
int?x?=?m[0]; int?y?=?m[1]; if?(board[r?+?y][c?+?x]?==?0)?{neighbors.add(new?int[]?{?r?+?y,?c?+?x,?countNeighbors(r?+?y,?c?+?x)?});
}}
Collections.sort(neighbors,?neighborComparator);
return?neighbors;
} private?static?int?countNeighbors(int?r,?int?c)?{int?num?=?0;
for?(int[]?m?:?MOVES)?{
if?(board[r?+?m[1]][c?+?m[0]]?==?0)?{num++;
}}
return?num;
} private?static?void?print()?{for?(int?i?=?2;?i?<?board.length?-?2;?i++)?{
for?(int?j?=?2;?j?<?board[i].length?-?2;?j++)?{System.out.printf("%2d?",?board[i][j]);
} System.out.println();}
System.out.println();
} private?static?class?Cell?{int?r;
int?c;
List<int[]>?neighbors;
int?nextNeighbor?=?0;
public?Cell(int?r,?int?c,?List<int[]>?neighbors)?{
this.r?=?r; this.c?=?c; this.neighbors?=?neighbors;}
}}