Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- static class QueenProblem {
- final int N = 8;
- int k = 1;
- int counter = 1;
- void printSolution(int board[][], int linha, int coluna) {
- if (board[linha - 1][coluna - 1] == 1) {
- if (k <= 9) {
- System.out.print(" " + k++ + " ");
- } else {
- System.out.print(k++ + " ");
- }
- for (int j = 0; j < N; j++) {
- for (int i = 0; i < N; i++) {
- if (board[i][j] == 1) {
- if (counter <= 7) {
- System.out.print((i + 1) + " ");
- counter++;
- break;
- } else {
- System.out.print(i + 1);
- counter++;
- break;
- }
- }
- }
- }
- System.out.println();
- }
- counter = 0;
- }
- boolean isSafe(int board[][], int row, int col) {
- int i, j;
- /* Check this row on left side */
- for (i = 0; i < col; i++)
- if (board[row][i] == 1)
- return false;
- /* Check upper diagonal on left side */
- for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
- if (board[i][j] == 1)
- return false;
- /* Check lower diagonal on left side */
- for (i = row, j = col; j >= 0 && i < N; i++, j--)
- if (board[i][j] == 1)
- return false;
- return true;
- }
- boolean solveNQUtil(int board[][], int col, int linha, int coluna) {
- if (col >= N) {
- printSolution(board, linha, coluna);
- return true;
- }
- boolean res = false;
- for (int i = 0; i < N; i++) {
- if (isSafe(board, i, col)) {
- /* Place this queen in board[i][col] */
- board[i][col] = 1;
- res = solveNQUtil(board, col + 1, linha, coluna) || res;
- board[i][col] = 0; // BACKTRACK
- }
- }
- return res;
- }
- void solveNQ(int linha, int coluna) {
- int board[][] = new int[N][N];
- if (solveNQUtil(board, 0, linha, coluna) == false) {
- System.out.print("Solution does not exist");
- return;
- }
- return;
- }
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Scanner in = new Scanner(System.in);
- int data_set = in.nextInt();
- for (int a = 0; a < data_set; a++) {
- int linha = in.nextInt();
- int coluna = in.nextInt();
- QueenProblem Queen = new QueenProblem();
- System.out.print("SOLN COLUMN\n");
- System.out.print(" # 1 2 3 4 5 6 7 8\n\n");
- Queen.solveNQ(linha, coluna);
- if (a != data_set - 1) {
- System.out.println();
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement