[UVa]750:8 Queens Chess Problem

8皇后問題，利用backtracking得解。

[C](0.012)

	#include<stdio.h>
	int solution = 0;
	void backtracking( int n, int row, int col, int x[], int y[], int slash1[], int slash2[] )
	{
	int i;
	if( n == col )
	{
	backtracking( n+1, row, col, x, y, slash1, slash2 );
	return;
	}
	if( n == 9 )
	{
	solution++;
	printf( "%2d ", solution );
	for( i = 1 ; i <= 8 ; i++ )
	{
	printf( " %d", x[i] );
	}
	printf( "\n" );
	return;
	}
	for( i = 1 ; i <= 8 ; i++ )
	{
	if( !y[i] && !slash1[i+n] && !slash2[i-n+8] )
	{
	x[n] = i;
	y[i] = 1;
	slash1[i+n] = 1;
	slash2[i-n+8] = 1;
	backtracking( n+1, row, col, x, y, slash1, slash2 );
	x[n] = 0;
	y[i] = 0;
	slash1[i+n] = 0;
	slash2[i-n+8] = 0;
	}
	}
	}
	int main()
	{
	int dataset;
	while( scanf( "%d", &dataset ) != EOF )
	{
	int i;
	int print = 0;
	for( i = 1 ; i <= dataset ; i++ )
	{
	if( print )
	printf( "\n" );
	print = 1;
	int row, col;
	scanf( "%d%d", &row, &col );
	int x[15] = {0}, y[15] = {0}, slash1[20] = {0}, slash2[20] = {0};
	x[col] = row;
	y[row] = 1;
	slash1[row+col] = 1;
	slash2[row-col+8] = 1;
	printf( "SOLN COLUMN\n");
	printf( " # 1 2 3 4 5 6 7 8\n\n" );
	solution = 0;
	backtracking( 1, row, col, x, y, slash1, slash2 );
	}
	}
	return 0;
	}

view raw UVa750.c hosted with ❤ by GitHub