[Vari] Contest 15

[Vincenzo1968]

Io ho trovato codesto codice in C:

http://pubpages.unh.edu/~pas/hacks/sudoku/

#define GRIDSIZE 9
#define MAXLINE GRIDSIZE+2

unsigned int grid[GRIDSIZE][GRIDSIZE];
unsigned int col[GRIDSIZE];
unsigned int row[GRIDSIZE];
unsigned int region[GRIDSIZE];
unsigned int istack[GRIDSIZE*GRIDSIZE];
unsigned int jstack[GRIDSIZE*GRIDSIZE];
unsigned int stackp;

void grid_input(char *filename);
void grid_display();
void placenum(unsigned n, unsigned i, unsigned j);
void removenum(unsigned n, unsigned i, unsigned j);
unsigned solve();
unsigned legal(unsigned n, unsigned i, unsigned j);

int main(int argc, char **argv)
{
	clock_t c_start, c_end;

	c_start = clock();

    grid_input(argv[1]);

    grid_display();

    if (solve())
	{
		printf("Solution found!\n");
		grid_display();
    }
    else
	{
		printf("No solution found\n");
    }

	c_end = clock();

	printf("\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

/* read initial grid from specified file */
void grid_input(char *filename) {

    FILE *fp;
    char line[MAXLINE];
    unsigned i,j;

    if ((fp = fopen(filename, "r")) == NULL)
	{
		fprintf(stderr, "Couldn't open input file\n");
		exit(1);
    }

    stackp = 0;
    for (i = 0; i < GRIDSIZE; i++)
	{
		if (fgets(line, MAXLINE, fp))
		{
			for (j = 0; j < GRIDSIZE; j++)
			{
				if (line[j] >= '1' && line[j] <= '9')
				{
					placenum(line[j] - '0', i, j);
				}
				else /* assume empty */
				{ 
					istack[stackp] = i;
					jstack[stackp] = j;
					stackp++;
				}
			}
		}
		else
		{
			fprintf(stderr, "Unexpected input error\n");
			exit(1);
		}
    }
}

/* solve grid with current stack of empty squares */
unsigned solve()
{
    int n;
    int i, j;

    if (stackp <= 0) { /* no empty squares so */
        return 1; /* solved */
    }
    stackp--;
    i = istack[stackp];
    j = jstack[stackp];

    for (n = 1; n <= 9; n++)
	{
		if (legal(n, i, j))
		{
			placenum(n, i, j);
			if (solve())
			{
				return 1;
			}
			removenum(n, i, j);
		}
    }

    /* no solution at all from this point */
    stackp++;

    return 0;
}


/* is it legal to put value n at row i, column j? */
unsigned legal(unsigned n, unsigned i, unsigned j) {
    return (grid[i][j] == 0) &&
        ((row[i] & (1 << (n-1))) == 0) &&
        ((col[j] & (1 << (n-1))) == 0) &&
	((region[3 * (i/3) + (j/3)] & (1 << (n-1))) == 0);
}

/* place number n at row i, column j */
void placenum(unsigned n, unsigned i, unsigned j) {
    unsigned r;

    grid[i][j] = n;
    row[i] ^= (1 << (n-1));
    col[j] ^= (1 << (n-1));
    region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}

/* remove number n at row i, column j */
void removenum(unsigned n, unsigned i, unsigned j) {
    unsigned r;

    grid[i][j] = 0;
    row[i] ^= (1 << (n-1));
    col[j] ^= (1 << (n-1));
    region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}



/* display current grid */
void grid_display()
{
    unsigned i, j;

    for (i = 0; i < GRIDSIZE; i++) {
	for (j = 0; j < GRIDSIZE; j++) {
	    printf("+---");
	}
	printf("+\n");
	for (j = 0; j < GRIDSIZE; j++) {
	    if (grid[i][j] == 0) {
	        printf("|   ");
	    }
	    else {
		printf("| %d ", grid[i][j]);
	    }
	}
	printf("|\n");
    }
    for (j = 0; j < GRIDSIZE; j++) {
	printf("+---");
    }
    printf("+\n");
}

Questo è il risultato per il sudoku del primo post


Questo è il risultato per il sudoku proposto da DanieleC88:

[malocchio]

Originariamente inviato da rеpne scasb

Scusa se insisto: hai disponibili un sudoku a soluzione univoca, che sia risolvibile soltanto tramite brute-force?

No, io conosco solo la teoria, non c'ho mai sbattuto la testa

Ciao

[gugoXX]

Originariamente inviato da rеpne scasb

Io non ho capito, mi fai un esempio completo 9x9 di un tale tipo di sudoku?

Pensavo che il problema fosse integrare anche sudoku a soluzione non unica, invece pare non sia cosi'.

[!k-0t1c!]

Originariamente inviato da gugoXX

Pensavo che il problema fosse integrare anche sudoku a soluzione non unica, invece pare non sia cosi'.

Infatti in teoria sarebbe così, per quelli a soluzione multipla basta una soluzione qualunque (e questo si può fare sicuramente senza brute force).

[gugoXX]

Originariamente inviato da !k-0t1c!

Infatti in teoria sarebbe così, per quelli a soluzione multipla basta una soluzione qualunque (e questo si può fare sicuramente senza brute force).

Il mio problema sarebbe in questo caso quello di trovare quali sono le caselle implicate che possono avre piu' soluzioni plausibili, senza usare il backtracking, parente della forza bruta.

[rеpne scasb]

■

[!k-0t1c!]

repne, spero che se lavori in questo campo non programmi così perché nonostante la qualità indiscussa dell'algoritmo il codice è a dir poco illeggibile

[marco.r]

Versione prolog con risolutore per domini finiti.
Sulla mia macchina ci mette circa 0.01-0.015 secondi per gli esempi visti prima, a prescindere dalle soluzioni (e.g. togliendo valori).
Nell'esempio hard invece ci mette un bel po' di piu'
La maggior parte del codice e' per l'input-output

charSymbol( '1', 1 ).
charSymbol( '2', 2 ).
charSymbol( '3', 3 ).
charSymbol( '4', 4 ).
charSymbol( '5', 5 ).
charSymbol( '6', 6 ).
charSymbol( '7', 7 ).
charSymbol( '8', 8 ).
charSymbol( '9', 9 ).
charSymbol( '0', N ):-
	N #>= 1,
	N #=< 9.

readSymbol( Stream, S ):-
	get_char( Stream, C ),
	charSymbol( C, S ),
	get_char( Stream, _ ).

readSymbols( _ , [], 0 ).
readSymbols( Stream, [H|T], N ):-
	readSymbol( Stream, H ),
	M is N - 1,
	readSymbols( Stream, T, M ).
	

readLine( Stream, Line ):-
	readSymbols( Stream, Line, 9 ).

readLines( _ , [] , 0 ).
readLines( Stream, [H|T], N ):-
	M is N-1,
	readLine( Stream, H ),
	readLines( Stream, T, M ).

readBoard( Filename, Board ):-
	open( Filename, read, Stream ),
	readLines( Stream, Board, 9 ),
	close(Stream),	
	!.

printLine( [] ):-
	write('\n').

printLine( [H|T] ):-
	write(H),
	write(' '),
	printLine(T).

printBoard( [] ).
printBoard( [H|T] ):-
	printLine(H),
	printBoard(T).

	

columns( [], [], [] ).
columns( [[Cii|Cin] | C], [Cii|X],[Cin|Y]) :-
	columns(C,X,Y).

transpose( [[]|_] , [] ).
transpose( M, [Ci|Cn] ):-
	columns(M,Ci,R),
	transpose( R, Cn ).

sum( [], 0 ).
sum( [H|T], N ):-
	sum( T, M ),
	N #= M + H.



rowsConstraints([]).
rowsConstraints([H|T]):-
	fd_all_different(H),
	sum( H, 45 ),
	rowsConstraints(T).

colsConstraints(Board):-
	transpose(Board,Columns),
	rowsConstraints( Columns ).

dropRows( Matrix, Matrix, 0 ).
dropRows( Matrix, SubM, N ):-
	M is N-1,
	Matrix = [_|T],
	dropRows( T, SubM, M ).

takeRows( _, [], 0 ).
takeRows( Matrix, SubM, N ):-
	M is N-1,
	Matrix = [H|MatrixT],
	SubM = [H|SubMT],
	takeRows( MatrixT, SubMT, M ).

flatten( [], [] ).
flatten( [H|T], Result ):-
	flatten(T,X),
	append(H,X,Result).

subMatrix( Matrix, SubM, RowBegin, ColBegin, RowLength, ColLength ):-
	dropRows( Matrix, SM1, RowBegin ),
	takeRows( SM1, SM2, RowLength ),
	transpose(SM2,SM3),
	dropRows( SM3, SM4, ColBegin ),
	takeRows( SM4, SM5, ColLength ),
%	transpose( SM5, SubM ).
	flatten( SM5, SubM).

blocks(Board,Blocks):-
	Blocks = [B1,B2,B3,B4,B5,B6,B7,B8,B9],

	subMatrix(Board,B1,0,0,3,3),
	subMatrix(Board,B2,0,3,3,3),
	subMatrix(Board,B3,0,6,3,3),
	subMatrix(Board,B4,3,0,3,3),
	subMatrix(Board,B5,3,3,3,3),
	subMatrix(Board,B6,3,6,3,3),
	subMatrix(Board,B7,6,0,3,3),
	subMatrix(Board,B8,6,3,3,3),
	subMatrix(Board,B9,6,6,3,3).
	
	
blockConstraints(Board):-
	blocks(Board,Blocks),
	rowsConstraints( Blocks ).


constraints( Board ):-	
	rowsConstraints( Board ),
	colsConstraints( Board ),
	blockConstraints( Board ).

	
solve( Filename, Board ):-
	readBoard( Filename, Board ),
	constraints( Board ),
	flatten(Board,Values),
	fd_labeling( Values, [variable_method(first_fail)] ).

main:-
	argument_value(1,Filename),
	cpu_time(Begin),
	solve(Filename,Solution),
	cpu_time(End),
	Time is End - Begin,
	printBoard(Solution),
%	write('Time needed:'),
%	write(Time),
%	write('\n').

	
:- initialization(main).

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[!k-0t1c!]

Originariamente inviato da rеpne scasb

Mi pare utilizzi la "forza bruta" per cercare la soluzione o sbaglio?

Non sbagli, e rischia allegramente lo stack overflow
Comunque buffa quella funzione CRC separata per formare CRC in ASCII art, ma trovo una cosa malsana scrivere codice in un certo modo...ghgh

[malocchio]

Originariamente inviato da rеpne scasb

Mi sto allenando per questo http://www.ioccc.org/

Mi piacciono cose di questo tipo:

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

int main(int a,char     **A){FILE*B;typedef     unsigned long C;C b
[8]; if(!(a==7&&(B=     fopen(1[A],"rb"))))     return 1;for(7[b]=0
;7[b]<5;7[b]++)b[7[     b]]=strtoul(A[2+7[b     ]],0,16-!7[b]*6);5[
b]=3[b]                 ; while     ((6[b]=     getc(B)
)!=(C)-                 1){if(2     [b])for     (7[b]=0
;7[b]<4                 ;7[b]++     )if(((6     [b]>>7[
b])^(6[                 b]>>(7-7[b])))&1)6[     b] ^=(1
<<7[b])                 ^(1<<(7-7[b]));5[b]     ^= 6[b]
<<(0[b]                 -8);for(7[b]=0;7[b]     <8;7[b]
++)if((                 5[b]>>(0[b]-            1))&1)5
[b]=(5[                 b]<<1)^ 1[b];           else 5[
b]<<=1;                 }5[b]&=((((C)1          <<(0[b]
-1))-1)                 <<1)|1; if(2[b]         )for(7[
b]=0;7[                 b]<(0[b  ]>>1);7        [b] ++)
if(((5[b]>>7[b])^(5     [b]>>(0   [b]-1-7       [b])))&1)5[b]^=((C)
1<<7[b])^((C)1<<(0[     b]-1-7[    b]));5[      b]^=4[b];fclose(B);
printf("%0*lX\n", (     int)(0[     b]+3)>>     2,5[b]); return 0;}

Ora si spiega tutto. Ma l'assembly inline non è previsto?

Scusa ma che sono ste cose: 1[A] 7[b] eccetera? Un'oscura opzione del C ?!?!?

[rеpne scasb]

■

[Tommo]

in pratica ptr[i] fa *(i + ptr)... quindi funziona anche il contrario. Non ci avevo mai pensato prima.
certo davvero che brutto

[~FullSyst3m~]

Originariamente inviato da rеpne scasb

Mi sto allenando per questo http://www.ioccc.org/

Mi piacciono cose di questo tipo:

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

int main(int a,char     **A){FILE*B;typedef     unsigned long C;C b
[8]; if(!(a==7&&(B=     fopen(1[A],"rb"))))     return 1;for(7[b]=0
;7[b]<5;7[b]++)b[7[     b]]=strtoul(A[2+7[b     ]],0,16-!7[b]*6);5[
b]=3[b]                 ; while     ((6[b]=     getc(B)
)!=(C)-                 1){if(2     [b])for     (7[b]=0
;7[b]<4                 ;7[b]++     )if(((6     [b]>>7[
b])^(6[                 b]>>(7-7[b])))&1)6[     b] ^=(1
<<7[b])                 ^(1<<(7-7[b]));5[b]     ^= 6[b]
<<(0[b]                 -8);for(7[b]=0;7[b]     <8;7[b]
++)if((                 5[b]>>(0[b]-            1))&1)5
[b]=(5[                 b]<<1)^ 1[b];           else 5[
b]<<=1;                 }5[b]&=((((C)1          <<(0[b]
-1))-1)                 <<1)|1; if(2[b]         )for(7[
b]=0;7[                 b]<(0[b  ]>>1);7        [b] ++)
if(((5[b]>>7[b])^(5     [b]>>(0   [b]-1-7       [b])))&1)5[b]^=((C)
1<<7[b])^((C)1<<(0[     b]-1-7[    b]));5[      b]^=4[b];fclose(B);
printf("%0*lX\n", (     int)(0[     b]+3)>>     2,5[b]); return 0;}

Bellissimo questo codice usato per l'ASCII art.
Ma in quale direzione si dovrebbe leggere il codice?
Comunque credo che sia molto più difficile scrivere codice in modo da formare un'ASCII art. E bisogna essere anche davvero bravi.

[||ElChE||88]

Originariamente inviato da Tommo

certo davvero che brutto

Io lo trovo quasi elegante, nella sua semplicità (certo che se uno lo usa al di fuori di un contest simile a quello sopra mi viene qualche dubbio che sia un po' sadico ).

Originariamente inviato da ~FullSyst3m~

Ma in quale direzione si dovrebbe leggere il codice?
Comunque credo che sia molto più difficile scrivere codice in modo da formare un'ASCII art. E bisogna essere anche davvero bravi.

Si legge normalmente (int main(int a,char **A) { FILE*B; typedef unsigned long C; C b[8]; if(!(a==... etc).
Comunque ce ne sono altri anche più impressionanti (il simulatore di volo...).

[~FullSyst3m~]

Originariamente inviato da ||ElChE||88

Comunque ce ne sono altri anche più impressionanti (il simulatore di volo...).

Si deve essere davvero bravi per fare cose del genere.

[malocchio]

Originariamente inviato da Tommo

in pratica ptr[i] fa *(i + ptr)... quindi funziona anche il contrario. Non ci avevo mai pensato prima.
certo davvero che brutto

Ecco spiegata la mia bassa considerazione del C...

[rеpne scasb]

■