Untitled

import java.util.Scanner;

public class TweenProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the size of the grid (n x n): ");
        int n = scanner.nextInt();

        int[][] board = new int[n][n];

        if (solveTweenProblem(board, 0, 0, n)) {
            System.out.println("Solution found:");
            printBoard(board);
        } else {
            System.out.println("No solution exists.");
        }
    }

    private static boolean solveTweenProblem(int[][] board, int row, int col, int n) {
        // If we have placed all numbers successfully, the problem is solved
        if (row == n - 1 && col == n) {
            return true;
        }

        // Move to the next row if we have reached the end of the current row
        if (col == n) {
            row++;
            col = 0;
        }

        // Skip cells that are already filled
        if (board[row][col] != 0) {
            return solveTweenProblem(board, row, col + 1, n);
        }

        // Try placing numbers from 1 to n in the current cell
        for (int num = 1; num <= n; num++) {
            if (isValid(board, row, col, num)) {
                board[row][col] = num;

                // Recursively solve for the next cell
                if (solveTweenProblem(board, row, col + 1, n)) {
                    return true;
                }

                // Backtrack if the current placement doesn't lead to a solution
                board[row][col] = 0;
            }
        }

        return false;
    }

    private static boolean isValid(int[][] board, int row, int col, int num) {
        // Check if the number is already present in the same row or column
        for (int i = 0; i < board.length; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return false;
            }
        }

        return true;
    }

    private static void printBoard(int[][] board) {
        for (int[] row : board) {
            for (int cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}