// Arup Guha
// 4/23/2024
// Solution to Spring 2024 COP 3503 Final Exam Question #1

import java.util.*;

public class q3 {

	public static void main(String[] args) {
		
		// Here is a random test case.
		int n = 25, c = 5;
		int[] p = new int[n];
		boolean[] u = new boolean[n];
		boolean res = go(p, u, 0, c);
		
		// Print out the seating chart.
		if (res) {
			for (int i=0; i<n; i++) {
				System.out.print(p[i]+"\t");
				if (i%c == c-1) System.out.println();
			}
		}
	}
	
	public static boolean go(int[] perm, boolean[] used, int k, int numC) {
		
		// See if we got to the end of filling out the permutation.
		int n = perm.length;
		if (k == n) return true;
		
		// Try each option in seat k.
		for (int i=0; i<n; i++) {
			
			// We've already placed this student.
			if (used[i]) continue;
			
			// This row placement is not allowed.
			if (i/numC == k/numC) continue;
			
			// This column placement is not allowed.
			if (i%numC == k%numC) continue;
			
			// We're good so do the usual permutation code.
			used[i] = true;
			perm[k] = i;
			
			// Key is here, if our recursive call worked, just return true so
			// we save the state of the perm array for the first lexicographical valid solution.
			boolean tmp = go(perm, used, k+1, numC);
			if (tmp) return true;
			
			// Undo so we can put i elsewhere later.
			used[i] = false;
		}
		
		// If we get here, this prefix didn't lead to a solution.
		return false;
	}
}