java_test/queen.java at master · codehoper/java_test · GitHub

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
67
68
69
70
71
72
73
74
75
76
77
package com.ub.test;

class queens
{
	static boolean finished = false;
	static final int MAXCANDIDATES = 100;
	static final int NMAX = 100;
	static int solution_count = 0;
	static void backtrack(int a[], int k, int input)
	{
		int c[] = new int [MAXCANDIDATES];
		int ncandidates, i;
		if (is_a_solution(a,k,input))
			process_solution(a,k,input);
		else
		{
			k++;
			ncandidates = construct_candidates(a,k,input,c);
			for (i=0; i<ncandidates; i++) {
				a[k] = c[i];
				make_move(a,k,input);
				backtrack(a,k,input);
				if (finished) return;
				unmake_move(a,k,input);
			}
		}
	}
	static void make_move(int a[],int k,int n)
	{
	}
	static void unmake_move(int a[],int k,int n)
	{
	}
	static void process_solution(int a[],int k, int n)
	{
		solution_count++;
	}
	static boolean is_a_solution(int a[],int k,int n)
	{
		return k==n;
	}
	static int construct_candidates(int a[],int k,int n, int c[])
	{
		int i,j;
		boolean legal_move=true;
		int ret = 0;
		for(i=1;i<=n;i++)
		{
			legal_move=true;
			for(j=1;j<k;j++)
			{
				if(Math.abs(k-j)==Math.abs(i-a[j]))
					legal_move=false;
				if(i==a[j])
					legal_move=false;
			}
			if(legal_move)
			{
				c[ret]=i;
				ret++;
			}
		}
		return ret;
	}
	static public void main(String[] args)
	{
		int a[] = new int[NMAX];
		int i;
		for (i=1; i<=10; i++)
		{
			solution_count = 0;
			finished = false;
			backtrack(a,0,i);
			System.out.printf("n=%d  solution_count=%d\n",i,solution_count);
		}
	}
}