FilesExpand file tree

 master

/

NQueens.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (60 loc) · 1.85 KB

 master

/

NQueens.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (60 loc) · 1.85 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

import java.util.Arrays;

import java.util.LinkedList;

import java.util.List;

public class NQueens {

public List<List<String>> solveNQueens(int n) {

List<List<String>> result = new LinkedList<>();

/**

* 这里f[i]表示第i行皇后应该放置在第几列

*/

int[] f = new int[n];

dfs(f, result, 0);

return result;

}

private void dfs(int[] f, List<List<String>> result, int row) {

if (row == f.length) {

List<String> list = new LinkedList<>();

char[] c = new char[f.length];

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

Arrays.fill(c, '.');

for (int j = 0; j < f.length; j++) {

if (j == f[i]) {

c[j] = 'Q';

break;

}

}

list.add(String.valueOf(c));

}

result.add(list);

}

/**

* 对于当前第row行，一列一列地尝试放置皇后，看是否合法，j表示列，如果合法则保存到f中

*/

for (int j = 0; j < f.length; j++) {

if (isValid(f, row, j)) {

/**

* 第row行皇后应该放置在第j列

*/

f[row] = j;

/**

* 再来看下一行

*/

dfs(f, result, row + 1);

/**

* 这里不用break，还要尝试其它可能

*/

}

}

}

private boolean isValid(int[] f, int row, int col) {

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

if (f[i] == col) {

return false;

}

if (Math.abs(i - row) == Math.abs(f[i] - col)) {

return false;

}

}

return true;

}

}