Python每日一点(001)

Python每日一点:八皇后问题

//C实现
#include <bits/stdc++.h>
#define len 8
using namespace std;
int matrix[len][len];

void Init()
{
	for(int i = 0; i < len; i++)
		for(int j = 0; j < len; j++)
			matrix[i][j] = 0;
}
int Judge(int i , int j)
{
	for(int a = 0; a < len; a++)
		for(int b = 0; b < j; b++)
			if((a == i && matrix[a][b] == 1) || (abs(i - a) == abs(j - b)) && matrix[a][b] == 1)
				return 0; 
	return 1;
}

int Solve(int k)
{
	if(k == len)
	{
		for(int x = 0 ; x < len; x++)
			for(int y = 0 ; y < len; y++)
				printf("%d%c", matrix[x][y], (y == len - 1) ? '\n' : ' ');
		return 1;
	}
				
			
	for(int i = 0; i < len; i++)
	{
		if(Judge(i , k) == 1)
		{
			matrix[i][k] = 1;
			if(Solve(k + 1) == 0)
			{
				matrix[i][k] = 0;
				continue;
			}
			else
				return 1;	
			
		}
	}
	return 0;
}
int main()
{
	Init(); 
	Solve(0);
	return 0;
}
#Python实现
len = 8
matrix = [[0 for i in range(len)] for i in range(len)]

def Judge(i, j):
    for a in range(len):
        for b in range(j):
            if(a == i and matrix[a][b] == 1 ) or ( (abs(a - i) == abs(b - j)) and matrix[a][b] == 1 ):
                return False
    return True
        
def Solve(k):
    if( k == len):
        print(matrix)
        return True
    for i in range(len):
        if Judge(i, k) == True:#可以放置
            matrix[i][k] = 1
            if Solve(k + 1) == False:#后面的放不了了
                matrix[i][k] = 0
                continue
            else:
                return True        

    return False

Solve(0)
上一篇:HDU - 4722 Good Numbers(数位DP)


下一篇:Java整数划分问题