Revision of NQueenProblem.java

kristofer 已修改 1718984322. 還原成這個修訂版本

1 file changed, 113 insertions

NQueenProblem.java(檔案已創建)

		@@ -0,0 +1,113 @@
1	+	// Java program to solve N Queen Problem using backtracking
2	+
3	+	public class NQueenProblem {
4	+	final int N = 4;
5	+
6	+	// A utility function to print solution
7	+	void printSolution(int board[][])
8	+	{
9	+	for (int i = 0; i < N; i++) {
10	+	for (int j = 0; j < N; j++) {
11	+	if (board[i][j] == 1)
12	+	System.out.print("Q ");
13	+	else
14	+	System.out.print(". ");
15	+	}
16	+	System.out.println();
17	+	}
18	+	}
19	+
20	+	// A utility function to check if a queen can
21	+	// be placed on board[row][col]. Note that this
22	+	// function is called when "col" queens are already
23	+	// placeed in columns from 0 to col -1. So we need
24	+	// to check only left side for attacking queens
25	+	boolean isSafe(int board[][], int row, int col)
26	+	{
27	+	int i, j;
28	+
29	+	// Check this row on left side
30	+	for (i = 0; i < col; i++)
31	+	if (board[row][i] == 1)
32	+	return false;
33	+
34	+	// Check upper diagonal on left side
35	+	for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
36	+	if (board[i][j] == 1)
37	+	return false;
38	+
39	+	// Check lower diagonal on left side
40	+	for (i = row, j = col; j >= 0 && i < N; i++, j--)
41	+	if (board[i][j] == 1)
42	+	return false;
43	+
44	+	return true;
45	+	}
46	+
47	+	// A recursive utility function to solve N
48	+	// Queen problem
49	+	boolean solveNQUtil(int board[][], int col)
50	+	{
51	+	// Base case: If all queens are placed
52	+	// then return true
53	+	if (col >= N)
54	+	return true;
55	+
56	+	// Consider this column and try placing
57	+	// this queen in all rows one by one
58	+	for (int i = 0; i < N; i++) {
59	+
60	+	// Check if the queen can be placed on
61	+	// board[i][col]
62	+	if (isSafe(board, i, col)) {
63	+
64	+	// Place this queen in board[i][col]
65	+	board[i][col] = 1;
66	+
67	+	// Recur to place rest of the queens
68	+	if (solveNQUtil(board, col + 1) == true)
69	+	return true;
70	+
71	+	// If placing queen in board[i][col]
72	+	// doesn't lead to a solution then
73	+	// remove queen from board[i][col]
74	+	board[i][col] = 0; // BACKTRACK
75	+	}
76	+	}
77	+
78	+	// If the queen can not be placed in any row in
79	+	// this column col, then return false
80	+	return false;
81	+	}
82	+
83	+	// This function solves the N Queen problem using
84	+	// Backtracking. It mainly uses solveNQUtil () to
85	+	// solve the problem. It returns false if queens
86	+	// cannot be placed, otherwise, return true and
87	+	// prints placement of queens in the form of 1s.
88	+	// Please note that there may be more than one
89	+	// solutions, this function prints one of the
90	+	// feasible solutions.
91	+	boolean solveNQ()
92	+	{
93	+	int board[][] = { { 0, 0, 0, 0 },
94	+	{ 0, 0, 0, 0 },
95	+	{ 0, 0, 0, 0 },
96	+	{ 0, 0, 0, 0 } };
97	+
98	+	if (solveNQUtil(board, 0) == false) {
99	+	System.out.print("Solution does not exist");
100	+	return false;
101	+	}
102	+
103	+	printSolution(board);
104	+	return true;
105	+	}
106	+
107	+	// Driver program to test above function
108	+	public static void main(String args[])
109	+	{
110	+	NQueenProblem Queen = new NQueenProblem();
111	+	Queen.solveNQ();
112	+	}
113	+	}