[algogeeks] Sudoku problem

[Wladimir Tavares]

Hi Guys,

I try to solve this problem:
http://br.spoj.pl/problems/BSUDO/

Using backtracking + bit representation but my solution get TLE

Some idea??

My backtracking function is here:

int linha[N]; //line
int coluna[N]; //column
int box[N];
char A[N+1][N+1];

int mask [] = {
#define B(i) 1<<i
B(0),B(1),B(2),B(3),B(4),B(5),B(6),B(7),B(8)
};
int backtrack(int i, int j) {
    int c;
    if (i == N) {
        return 1;
    }
    int in = i, jn = j+1;
    if (jn == N) {
        in++;
        jn = 0;
    }

  if (A[i][j] != '0') {
        return backtrack(in, jn);
    }

    int ii = i / 3;
  int jj = j / 3;

  c = linha[i] | coluna[j] | box[3*ii+jj];
  c = ~c;
    for (int k = 0; k < N; k++) {
if( (c&mask[k]) !=0 ){
 A[i][j] = '0'+k+1;
linha[i]     |=  mask[k];
coluna[j]    |=  mask[k];
 box[3*ii+jj] |=  mask[k];
if( backtrack(in, jn) )
return 1;
 A[i][j] = '0';
linha[i]     &=  ~mask[k];
coluna[j]    &=  ~mask[k];
 box[3*ii+jj] &=  ~mask[k];
}
    }
    return 0;
}






Wladimir Araujo Tavares
*Federal University of Ceará <http://lia.ufc.br/%7Ewladimir/>
Homepage <http://lia.ufc.br/%7Ewladimir/> |
Maratona<https://sites.google.com/site/quixadamaratona/>|
*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.


#include <stdio.h>
#include <stdlib.h>
#include <map>
#define N 9

using namespace std;

int t;
int linha[N];
int coluna[N];
int box[N];
char A[N+1][N+1];

int mask [] = {
#define B(i) 1<<i
B(0),B(1),B(2),B(3),B(4),B(5),B(6),B(7),B(8)
};

//FILE *fp;
//
//
//void imprime(){
//	
//	fprintf(fp,"Tabuleiro\n");
//	for (int i = 0; i < N; i++) {
//        fprintf(fp,"%d ", A[i][0]);
//        for (int j = 1; j < N; j++) {
//            fprintf(fp,"%d ", A[i][j]);
//        }
//        fprintf(fp,"\n");
//  }
//  fprintf(fp,"-----------------------------\n");
//  
//
//}

int backtrack(int i, int j) {
    
    int c;
		
		if (i == N) {
        return 1;
    }
    int in = i, jn = j+1;
    if (jn == N) {
        in++;
        jn = 0;
    }
    
		if (A[i][j] != '0') {
        return backtrack(in, jn);
    }
    
    int ii = i / 3;
		int jj = j / 3;
    
		c = linha[i] | coluna[j] | box[3*ii+jj];
		c = ~c;
		
    for (int k = 0; k < N; k++) {
				if( (c&mask[k]) !=0 ){
					A[i][j] = '0'+k+1;
					linha[i]     |=  mask[k];
					coluna[j]    |=  mask[k];
					box[3*ii+jj] |=  mask[k]; 
					if( backtrack(in, jn) )
						return 1;
					A[i][j] = '0';
				  linha[i]     &=  ~mask[k];
					coluna[j]    &=  ~mask[k];
					box[3*ii+jj] &=  ~mask[k]; 
				}
    }
    return 0;
}



int main(){

		char str[1024];

		//fp = fopen("sudoku2.out","wt");

		int k;

		
		scanf("%d\n", &t); 
    while (t--) {
        
        for(int i=0; i < N; i++){
					linha[i] = coluna[i] = box[i] = 0;
				}
				
				for (int i = 0; i < N; i++) {
            scanf("%s",A[i]);
            for (int j = 0; j < N; j++) {		
								if(A[i][j] != '0'){
						      int k = A[i][j]-'0';
									int ii = i / 3;
									int jj = j / 3;
									linha[i]     |=  mask[k-1];
									coluna[j]    |=  mask[k-1];						
									box[3*ii+jj] |=  mask[k-1];
						    }	
            }
				}
				
				
				
				if (backtrack(0, 0)) {
            for (int i = 0; i < N; i++) {
                printf("%s\n", A[i]);
            }
        } else {
            printf("NO SOLUTION\n");
        }
        
	  }
	  //fclose(fp);
	  //system("PAUSE");
		return 0;
}