FilesExpand file tree

 main

/

NQueens.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (57 loc) · 1.75 KB

 main

/

NQueens.java

Copy path

Top

File metadata and controls

• Code
• Blame

66 lines (57 loc) · 1.75 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

import java.util.*;

public class NQueens {

public static void main(String[] args) {

int n = 4;

boolean[][] board = new boolean[n][n];

System.out.println(queens(board, 0));

}

static int queens(boolean[][] board, int row) {

if (row == board.length) {

display(board);

System.out.println();

return 1;

}

int count = 0;

for (int col = 0; col < board.length; col++) {

// place the queen if safe

if (isSafe(board, row, col)) {

board[row][col] = true; // if safe then place it

count += queens(board, row + 1); // recursive call

board[row][col] = false; // backtracking

}

}

return count;

}

static boolean isSafe(boolean[][] board, int row, int col) {

for (int i = 0; i < row; i++) {

if (board[i][col]) {

return false;

}

}

int maxLeft = Math.min(row, col);

for (int i = 1; i <= maxLeft; i++) {

if (board[row - i][col - i]) {

return false;

}

}

int maxRight = Math.min(row, board.length - col - 1);

for (int i = 1; i <= maxRight; i++) {

if (board[row - i][col + i]) {

return false;

}

}

return true;

}

static void display(boolean[][] board) {

for (int i = 0; i < board.length; i++) {

for (int j = 0; j < board[0].length; j++) {

if (board[i][j]) {

System.out.print("Q ");

} else {

System.out.print("X ");

}

}

System.out.println();

}

}

}