苗火 Nicholas

[Data structures]Backtrack

2019-8-8 萧 写技术

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 20 
#define INFINIT	65535

int k;
void GetPowerSet(int i, int *A, int *B)
{
	int x;
	int j;
	if(i>A[0]){
		for(j=1; j<=B[0]; j++){
			printf("%d", B[j]);
		}
		printf("\n");
	}else{
		x = A[i];

		k = B[0];
		B[k+1] = x;
		B[0]++;	
		GetPowerSet(i+1, A, B);

		B[0]--;
		GetPowerSet(i+1, A, B);
	}	
}

int queue[MAX] = {-1};
int times = 0;
void Trial(int i, int n)
{
	int error = 0;
	int j,k;

	if(i>n){
		printf("%d times:\n", ++times);
		for(j=1; j<=n; j++){
			for(k=1; k<=n; k++){
				if(queue[j] == k){
					printf("[*]");
				}else{
					printf("[ ]");
				}
			}
			printf("\n");
		}
		printf("\n");
	}else{
		for(j=1; j<=n; j++){
			/* Judge */
			error = 0;
			for(k=1; k<=i-1; k++){
				if(queue[k] == j){
					error = 1;
					break;
				}
				if(queue[k] + (k-i) == j 
				|| queue[k] - (k-i) == j){
					error = 1;
					break;
				}
			}
			if(!error){
				queue[i] = j;
				Trial(i+1,n); 
			}
		}	
	}
}

void main()
{
	int i;
	int A[] = {3, 1, 2, 3};
	int B[] = {0, 0, 0, 0};

	printf("log.anycle.com\n\n");

	printf("Get power set:\n");
	GetPowerSet(1, A, B);
	printf("\n");

	printf("Queens:\n");
	Trial(1,4);
	printf("\n");
}

标签: Data Structures data_structures