import java.util.*;

public class LatinSquare{

	private static int nbls=0; //nombre de latin square
	private static int size;
	private static int[][] square;

	//main
	public static void main(String[] args){
		if(args.length==0)
			System.out.println("Usage: java makeSquare <int>");
		else
			makeSquares(Integer.parseInt(args[0]));
	}

	//printSquare
	public static void printSquare(){
		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++)
				System.out.print((square[i][j]+1)+" ");
			System.out.println();
		}
	}

	//checkUp and chechLeft
	private static boolean checkUp(int i, int j){
		for(int k=0;k<j;k++)
			if(square[i][k]==square[i][j])
				return false;
		return true;
	}
	private static boolean checkLeft(int i, int j){
		for(int k=0;k<i;k++)
			if(square[k][j]==square[i][j])
				return false;
		return true;
	}

	//initSquare
	private static void initSquare(int dim){
		size=dim;
		square=new int[size][size];
		for(int k=0;k<size;k++){
			square[k][0]=k;
			square[0][k]=k;
		}
	}

	private static void increasing(int i, int j, int k){
		for(int ii=1;ii<size;ii++)
			for(int jj=1;jj<size;jj++)
				if(ii<i || (ii==i && jj<j))
					System.out.print(square[ii][jj]);
				else
					System.out.print(" ");
	}

	//backtrack
	private static void backtrack(int i,int j,int k){
		//		increasing(i,j,k);		//l'affichage de cette fonction est interessant. Pourquoi ?
												//regarde ce que produit le branchement :
												//$ java LatinSquare 4 | grep -- -- | sed 's/  --.*$//g' | sed '/^\s*$/d' | sed '$!N; /^\(.*\)\n\1$/!P; D'

		//forward
		if(i>=size){				//on a remplit tout le carre sans trouver d'erreur
										//-> on affiche, on compte et on backtrack (pour trouver d'autres carres)
			System.out.println();
			printSquare();
			nbls++;
			backtrack(i-1,size-1,square[i-1][size-1]+1);
		}
		else if(j>=size)			//on a finit la ligne -> on passe a la ligne suivante (en sautant la colonne 0)
			backtrack(i+1,1,0);

		//backward
		else if(i<=0)				//on a backtracke jusqu'a la premiere ligne -> on s'arrete
			return;
		else if(j<=0)				//on ne touche pas a la premiere colonne -> backtrack vers la ligne d'au dessus
			backtrack(i-1,size-1,square[i-1][size-1]+1);
		else if(k>=size)			//on a essaye toutes les valeurs pour cette case -> on backtrack
			backtrack(i,j-1,square[i][j-1]+1);

		//maintenant on sait que 0<i<size, 0<j<size et k<size
		else{							//on fait des essaies sur cette case.
			square[i][j]=k;
			if(checkUp(i,j) && checkLeft(i,j))
				backtrack(i,j+1,0);
			else
				backtrack(i,j,k+1);
		}
	}

	public static void makeSquares(int dim){
		initSquare(dim);
		if(dim<=0)
			return;
		else if(dim<2){
			System.out.println();
			printSquare();
			nbls++;
		}
		else
			backtrack(1,1,0);
		System.out.println();
		System.out.println("Il y a "+nbls+" carrĂŠs latin normalisĂŠs de taille "+size+".");
	}

}