Eight Queen
Eight Queen Problem
This idea is from https://www.cnblogs.com/bigmoyan/p/4521683.html. It greatly reduces the space complexity compare to any 2D array solution.
|
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 |
public class EightQueen { // layer int n = 8; int[] r = new int[n]; int count = 0; public void queen(int row) { if (row == n) { count++; return; } for (int i = 0; i < n; i++) { r[row] = i; if (isValid(row)) { queen(row + 1); } } } private boolean isValid(int row) { for (int i = 0; i < row; i++) { if (r[row] == r[i] || row - r[row] == i - r[i] || row + r[row] == i + r[i]) { return false; } } return true; } public static void main(String[] args) { EightQueen eq=new EightQueen(); eq.queen(0); System.out.println(eq.count); } } |