Backtracking si partitionarea unui numar in Python

nsol = 0.
nz = 0.
nr = []
N = 0.

def construct(nr_partitii, numar):
    global N, nr
    N = numar
    for i in range(nr_partitii):
        nr.append(0)

def is_zero():
    for i in range (len(nr)):
        if nr[i] == 0:
            return True
    return False

def init (k):
    nr[k] = -1

def succesor (k):
    if nr[k] < N:
        nr[k] += 1
        return True
    nr[k] -= 1
    return False

def valid (k):
    suma = 0.
    for i in range (k):
        suma += nr[i]
    if suma+nr[k] <= N:
        return True
    return False

def solutie (k):
    return k == len(nr)-1 and sum(nr)==N

def bt (k):
    init(k)
    global nsol, nz
    while succesor(k):
        if valid(k):
            if solutie(k):
                #print nr
                nsol += 1
                if is_zero():
                    #print nr
                    nz += 1
            elif k<len(nr)-1:
                bt(k+1)

print "Partitionarea unui numar"

construct(4,12)
bt(0)

print "Solutii: ",nsol
print nsol-nz,"combinatii de termeni nenuli"

Problema reginelor

Pe o tablă NxN trebuie așezate N regine astfel încât să nu existe conflicte între oricare 2 piese (o regină poate elimina altă regină dacă segmentul determinat de cele două piese este paralel cu oricare din axele sau diagonalele tablei de joc).

In program, *s este vectorul care retine pe ce linie se afla fiecare regina pusa pe o singura coloana. Ex. s[1]=3 inseamna `regina de pe coloana 1 se afla pe linia 3`.

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int n , *s;
int vf;

void avans () {

vf++;
s[vf]=-1;

}

int succesor () {

s[vf]++;
return s[vf] < n;

}

int valid () {

int ok = 1;
int i;
for (i=0; i < vf; i++)
if(s[i]==s[vf] || abs(s[vf]-s[i])==vf-i)
ok=0;
return ok;
}

int sol () {

return vf==n-1;
}

void tipar () {

int i,j;
printf("solutie\n");
for(i=0; i < n; i++) {
for(j=0; j < n; j++) {
if(s[i]==j) printf("Q");
else printf("#"); }
printf("\n"); }
printf("\n");
}

void back() {

vf = -1;
avans ();
while(vf > -1) {
if(succesor()) {
if(valid()) { if(sol()) tipar();
else avans(); }
else ; }
else vf--; }
}

int main() {

printf("\n");
printf("n= ");
scanf("%d", &n);
s = (int *) malloc (n*sizeof(int));
back();
return 0;

}