[Vari] Contest 15

[ally]

...qui viene proposta una applet con diversi sistemi di solver...l'algoritmo proposto risolve il caso richiesto dal thread in una manciata di secondi...volevo chiedere all'autore del thread se la difficoltà di risoluzione di questo sudoku sta solo nella scelta di usare una scala di valori decrescente per la prima riga (un brute force incrementando il valore per ogni riquadro arriverà a ricostruire la sequenza 9-8-7... nel maggior tempo possibile) o ci sono altri giochini dietro?...

...ciao Andrea...

[!k-0t1c!]

Ok, dai, posto la mia: il codice è per lo più una traduzione di un post che ho trovato, ma solo per una questione di eleganza. Infatti ho sempre reputato l'uso di un po' di constraint programming la via più comoda e dunque appoggiarsi a un solver era secondo me naturale
Il codice è come al solito in F# (4.0), ed in questo caso è richiesta la presenza di Microsoft Solver Foundation (l'express edition gratuita basta).
Il tempo impiegato sul mio misero T7700 @ 2.4ghz è 500ms e gran parte del tempo è spesa per il caricamento/inizializzazione del solver e non per la ricerca della soluzione.

open System
open System.IO
open Microsoft.SolverFoundation.Common
open Microsoft.SolverFoundation.Services

module Sudoku =
    type SudokuCell(row, col, value) =
        let mutable _value = value
        member x.Row = row
        member x.Col = col
        member x.Value with get() = _value and set(v) = _value <- v
        member x.FloatValue with get() = float _value and set(v:float) = _value <- int v
    
    type Block = { KeyRow : int; KeyCol : int; IsIn : Rational }
                
    let Solve(src:int array array) =
        let rational (i:int) = Rational.op_Implicit i
        let ctx = SolverContext.GetContext()
        let model = ctx.CreateModel()
        let line = Set(Domain.IntegerRange(rational 0, rational 9), "line")
        let board = Array2D.init 9 9 (fun r c -> SudokuCell(r, c, src.[r].[c]))
        let boardDec = Decision(Domain.IntegerRange(rational 1, rational 9), "board", line, line)
        boardDec.SetBinding(board |> Seq.cast<SudokuCell>, "FloatValue", "Row", "Col")
        let presetBoard = Parameter(Domain.IntegerRange(rational 0, rational 9), "presetBoard", line, line)
        presetBoard.SetBinding(board |> Seq.cast<SudokuCell>, "Value", "Row", "Col")
        model.AddDecision boardDec
        model.AddParameter presetBoard
        model.AddConstraint(null,  Model.ForEach(line, fun i -> Model.ForEachWhere(line, (fun j -> Term.op_Equality(boardDec.[i,j],presetBoard.[i, j])), fun j -> Term.op_GreaterThan(presetBoard.[i, j], 0 |> rational |> Term.op_Implicit)))) |> ignore
        model.AddConstraint(null, Model.ForEach(line, fun j -> Model.AllDifferent (Model.ForEach(line, fun i -> boardDec.[i,j])))) |> ignore
        model.AddConstraint(null, Model.ForEach(line, fun i -> Model.AllDifferent (Model.ForEach(line, fun j -> boardDec.[i,j])))) |> ignore
        let isInBlock i j row col = if i * 3 <= row && row <= i * 3 + 2 && j * 3 <= col && col <= j * 3 + 2 then rational 1 else rational 0
        for i in 0..2 do 
            for j in 0..2 do
                let boardBlock = Parameter(Domain.IntegerNonnegative, "boardBlock", line, line)
                model.AddParameters boardBlock
                boardBlock.SetBinding(board |> Seq.cast<SudokuCell> |> Seq.map(fun c -> { KeyRow = c.Row; KeyCol = c.Col; IsIn = isInBlock i j c.Row c.Col }), "IsIn", "KeyRow", "KeyCol")
                model.AddConstraint(null, Model.AllDifferent(Model.ForEach(line, fun keyi -> Model.ForEachWhere(line, (fun keyj -> boardDec.[keyi, keyj]), fun keyj -> boardBlock.[keyi,keyj])))) |> ignore
        let solution = ctx.Solve()
        if solution.Quality = SolverQuality.Feasible then
            ctx.PropagateDecisions()
            Some [| for i in 0..8 -> [| for j in 0..8 -> board.[i,j].Value |] |]
        else None
        
let main() =
    let puzzle = "sudoku.csv" |> File.ReadAllLines |> Array.Parallel.map(fun ln -> ln.Split([|','|], StringSplitOptions.RemoveEmptyEntries) |> Array.Parallel.map(int))
    let sw = System.Diagnostics.Stopwatch.StartNew()
    match Sudoku.Solve puzzle with
    | Some b -> sw.Stop()
                let lines = b |> Array.Parallel.map(fun r -> (r |> Array.fold(fun acc b -> sprintf "%s,%i" acc b) String.Empty).Substring 1)
                File.WriteAllLines("solved.csv", lines)
                lines |> Seq.iter(fun ln -> printfn "%s" ln)
                printfn "Parsed and solved in %ims" sw.ElapsedMilliseconds
    | None -> printfn "failed"
    Console.ReadKey() |> ignore
    
do main();;

[!k-0t1c!]

@ally: Il puzzle proposto è preso da QUI e l'ho scelto apposta perché ero curioso di vedere quanto avrebbe stimolato la gente ad andare 1po' oltre il mero brute force

[ally]

Originariamente inviato da !k-0t1c!

1,4,5,7,8,2,6,3,9
3,7,9,1,6,4,5,2,8
2,6,8,3,9,5,4,1,7
5,2,1,4,7,8,3,9,6
4,3,7,6,1,9,2,8,5
8,9,6,2,5,3,1,7,4
7,8,4,5,2,1,9,6,3
6,1,3,9,4,7,8,5,2
9,5,2,8,3,6,7,4,1

0,0,0,0,0,0,0,0,0
0,0,0,0,0,3,0,8,5
0,0,1,0,2,0,0,0,0
0,0,0,5,0,7,0,0,0
0,0,4,0,0,0,1,0,0
0,9,0,0,0,0,0,0,0
5,0,0,0,0,0,0,7,3
0,0,2,0,1,0,0,0,0
0,0,0,0,4,0,0,0,9

...le grigle sembrano diverse...prendo come riferimento la posizione del numero uno sul primo quadrante...

...ciao Andrea...

[!k-0t1c!]

http://tbn3.google.com/images?q=tbn:...y-facepalm.jpg
Mi ero dimenticato una riga, quella che impone che i valori iniziali diversi da 0 ed i valori finali nelle stesse posizioni coincidano...Fixed, il tempo è salito di qualche millisecondo ma siamo sempre li

[Tommo]

Originariamente inviato da !k-0t1c!

Applicando solo le regole, senza "indovinare" mai, la cosa è fattibile in 15righe Tutto sta nel saper usare le regole inizialmente e poi "indovinare" intelligentemente. Se comunque hai la parte di verifica delle regole e di riempimento secondo le regole implementare la parte che "indovina" ed eventualmente fa backtracking non dovrebbe essere traumatico

Vero.
Un'altro conto è invece fare che ci mette 13 ms a risolverlo

Ora provo a metterci il "guessing" spero che non faccia aumentare assurdamente i tempi...

[rеpne scasb]

■

[d_traveler]

Originariamente inviato da rеpne scasb

Linguaggio: C
Algoritmo: Non utilizza la forza bruta.
Tempo: Il tempo impiegato e molto minore di 1 millesimo di secondo

#include <stdio.h>
#include <time.h>

#define N_CLK 10
#define INPUT_FILE_NAME "SUDOKU.DAT"
#define SIZE 9
#define CELL (SIZE/3)

int main(void)

{
    clock_t clk[N_CLK];
    FILE *input_file_handle;
    int b,i,j,k,l,m,n,o,s,sp,sv=SIZE*SIZE,sk[SIZE][SIZE],ts[SIZE][SIZE];

    if((input_file_handle=fopen(INPUT_FILE_NAME,"rt"))==NULL)
    {
	fprintf(stderr,"Non trovo il file " INPUT_FILE_NAME "\n");
	return 1;
    }

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	{
	    fscanf(input_file_handle,"%d,",&sk[i][j]);
	    if(sk[i][j])
		sv--;
	}
    }

    if(fclose(input_file_handle))
    {
	fprintf(stderr,"Errore durante fclose\n");
	return 1;
    }

    printf("*** Input ***\n\n");

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	    printf("%d ",sk[i][j]);
	printf("\n");
    }

    clk[0]=clock();

    do
    {
	for(i=0;i<SIZE;i++)
	{
	    for(j=0;j<SIZE;j++)
	    	ts[i][j]=0;
	}
	for(i=0;i<SIZE;i++)
	{
	    for(j=0;j<SIZE;j++)
	    {
		if(sk[i][j])
		{
		    for(k=0;k<SIZE;k++)
			ts[k][j]|=1<<(sk[i][j]-1);
		    for(k=0;k<SIZE;k++)
			ts[i][k]|=1<<(sk[i][j]-1);
		    for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		    {
		        for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		            ts[k][l]|=1<<(sk[i][j]-1);
		    }
		}
	    }
	}
	for(b=0;b<SIZE;b++)
	{
	    for(i=0;i<SIZE;i++)
	    {
	        for(l=j=0;j<SIZE;j++)
		{
		    if(sk[i][j]==0)
		    {
		        if((ts[i][j]&(1<<b))==0)
			{
			    l++;
			    m=j;
			}
		    }
		}
		if(l==1)
		{
		    sk[i][m]=b+1;
		    sv--;
		    for(k=0;k<SIZE;k++)
			ts[k][m]|=1<<b;
		    for(k=0;k<SIZE;k++)
			ts[i][k]|=1<<b;
		    for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		    {
		        for(l=(m/CELL)*CELL;l<((m/CELL)*CELL+CELL);l++)
		            ts[k][l]|=1<<b;
		    }
		}
	    }
	    for(j=0;j<SIZE;j++)
	    {
	        for(l=i=0;i<SIZE;i++)
	        {
	    	    if(sk[i][j]==0)
		    {
		        if((ts[i][j]&(1<<b))==0)
			{
			    l++;
			    m=i;
			}
		    }
		}
	        if(l==1)
		{
		    sk[m][j]=b+1;
		    sv--;
		    for(k=0;k<SIZE;k++)
			ts[k][j]|=1<<b;
		    for(k=0;k<SIZE;k++)
			ts[m][k]|=1<<b;
		    for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
		    {
		        for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		            ts[k][l]|=1<<b;
		    }
		}
	    }
	    for(i=0;i<SIZE;i+=CELL)
	    {
		for(j=0;j<SIZE;j+=CELL)
		{
		    for(n=0,k=i;k<(i+CELL);k++)
		    {
			for(l=j;l<(j+CELL);l++)
			{
	    	    	    if(sk[k][l]==0)
		    	    {
		                if((ts[k][l]&(1<<b))==0)
			        {
			    	    n++;
			    	    m=k;
				    o=l;
			  	}
			    }
			}
		    }			
	            if(n==1)
		    {
		        sk[m][o]=b+1;
		        sv--;
		        for(k=0;k<SIZE;k++)
			    ts[k][o]|=1<<b;
		        for(k=0;k<SIZE;k++)
			    ts[m][k]|=1<<b;
		        for(k=(m/CELL)*CELL;k<((m/CELL)*CELL+CELL);k++)
		        {
		            for(l=(o/CELL)*CELL;l<((o/CELL)*CELL+CELL);l++)
		                ts[k][l]|=1<<b;
		        }
		    }
		}
	    }
	}

        for(sp=i=0;i<SIZE;i++)
        {
	    for(j=0;j<SIZE;j++)
	    {
	        if(sk[i][j]==0)
	        {
		    for(s=k=0;k<SIZE;k++)
		        s|=1<<sk[k][j];
		    for(k=0;k<SIZE;k++)
		        s|=1<<sk[i][k];
		    for(k=(i/CELL)*CELL;k<((i/CELL)*CELL+CELL);k++)
		    {
		        for(l=(j/CELL)*CELL;l<((j/CELL)*CELL+CELL);l++)
		            s|=1<<sk[k][l];
		    }
		    for(s>>=1,l=k=0;k<SIZE;k++)
		    {
			if(s&(1<<k))
			    l++;
			else
			    m=k;
		    }
		    if(l==(SIZE-1))
		    {
		        sk[i][j]=m+1;
			sv--;
			sp=1;
			break;
		    }		
	        }	    
	        if(sp)
		    break;
	    }
	    if(sp)
	        break;
        }

    } while (sv);

    clk[1]=clock();

    printf("\n*** Soluzione ***\n\n");

    for(i=0;i<SIZE;i++)
    {
	for(j=0;j<SIZE;j++)
	    printf("%d ",sk[i][j]);
	printf("\n");
    }

    printf("\nTempo per ricercare la soluzione: %7.3f secondi\n",(double)(clk[1]-clk[0])/CLK_TCK);

    return 0;
}

Tipico Output:

*** Input ***

0 0 0 0 0 0 0 0 0 
0 0 0 0 0 3 0 8 5 
0 0 1 0 2 0 0 0 0 
0 0 0 5 0 7 0 0 0 
0 0 4 0 0 0 1 0 0 
0 9 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 7 3 
0 0 2 0 1 0 0 0 0 
0 0 0 0 4 0 0 0 9 

*** Soluzione ***

9 8 7 6 5 4 3 2 1 
2 4 6 1 7 3 9 8 5 
3 5 1 9 2 8 7 4 6 
1 2 8 5 3 7 6 9 4 
6 3 4 8 9 2 1 5 7 
7 9 5 4 6 1 8 3 2 
5 1 9 2 8 6 4 7 3 
4 7 2 3 1 9 5 6 8 
8 6 3 7 4 5 2 1 9 

Tempo per ricercare la soluzione:   0.000 secondi

P.S. Se riscontrare errori avvertitemi.
P.P.S. Se c'e' un numero sufficiente di persone interessare a sapere come funziona, saro' lieta di spiegarlo.

in c, difficilissimo.

[Tommo]

Originariamente inviato da rеpne scasb

P.S. Se riscontrare errori avvertitemi.
P.P.S. Se c'e' un numero sufficiente di persone interessare a sapere come funziona, saro' lieta di spiegarlo.

Per me o hai un pc sperimentale oppure usi magia nera
Mi interesserebbe capire da dove iniziare per leggerlo più che altro

Ma c'è qualche "guideline" per avere dei risultati prestazionali eccellenti come fai sempre oppure serve solamente un'esperienza eccessiva?

[rеpne scasb]

■

[rеpne scasb]

■

[d_traveler]

Originariamente inviato da rеpne scasb

Affatto, il tempo stimato per scrivere il sorgente e' stato di circa 30 minuti (non ti fare impressionare c'e' un sacco di copia&incolla).

in poco tempo anche. mi sembra difficilissimo il c, io non riesco a farlo neanche in java o in python che conosco un pò meglio.

[!k-0t1c!]

Bene bene, festa delle bitmasks
Codice illeggibile, specie senza commenti, ma è comunque comprensibile il principio, complimenti

Direi che questo contest è stato risolto interessantemente, il prossimo lo penserò per qualcosa di molto parallelizzabile

P.S.: "lieta" <- donna in questo campo? doppi complimenti. Anche se qualcuno potrebbe fare la classica battuta "ecco perché scrive codice così contorto"

[rеpne scasb]

■

[wingman87]

@rеpne scasb: Una domanda: gli or + shift servono a segnare in una casella che il numero corrente non può starci? Molto interessante, io nel risolvere i sudoku a mano ho sempre fatto il contrario invece con questo metodo una volta segnata la casella non devi più cancellare il segno che fai. Anche se in effetti facendolo a mano quando i segni diventano tanti diventa un po' un pasticcio...
E un'altra cosa: pensavo che senza il bruteforce non si potesse risolvere qualsiasi schema. Sbaglio?

[rеpne scasb]

■

[banryu79]

Bravissima, repne

[rеpne scasb]

■

[VICIUS]

Originariamente inviato da banryu79

Bravissima, repne

Vero. Non possiamo che inchinarci.

[rеpne scasb]

■