FilesExpand file tree

 master

/

NQueensII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

50 lines (44 loc) · 1.19 KB

 master

/

NQueensII.java

Copy path

Top

File metadata and controls

• Code
• Blame

50 lines (44 loc) · 1.19 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

/**

* Practiced on 12/12/2012

*

* Follow up for N-Queens problem.

*

* Now, instead outputting board configurations, return the total number of distinct solutions.

*

* =========================

* I don't see the difference between this question and the previous one.

*/

package com.congli.leetcode;

public class NQueensII {

public int totalNQueens(int n)

{

int[] colInd = new int[n];

for(int i = 0; i < colInd.length; ++i) colInd[i] = -1;

return solve(colInd, 0);

}

private int solve(int[] colInd, int row)

{

if(row == colInd.length)

return 1;

int sum = 0;

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

{

if(isValidStep(colInd, col, row))

{

colInd[row] = col;

sum += solve(colInd, row+1);

colInd[row] = -1;

}

}

return sum;

}

private boolean isValidStep(int[] colInd, int col, int row)

{

for(int r = 0; r < row; ++r)

{

if(colInd[r] == col) return false;

if(Math.abs(colInd[r]-col) == Math.abs(row-r)) return false;

}

return true;

}

}