Condividi:        

Sudoku: Perl to C to Java

Problemi di HTML? Di PHP, ASP, .NET, JSP, Perl, SQL, JavaScript, Visual Basic..?
Vuoi realizzare programmi in C, C++, Java, Ruby o Smalltalk, e non sai da che parte cominciare?
Entra qui e troverai le risposte!

Moderatori: Anthony47, Triumph Of Steel, archimede

Sudoku: Perl to C to Java

Postdi infinito1971 » 10/10/05 18:14

Ciao a tutti,
ho trovato su Internet un interessante programmino in perl di soli tre righi che riesce a risolvere qualsiasi schema di Sudoku 9x9 con solo tre righe di codice! (in realtà il codice funziona scrivendolo anche tutto su una sola riga!!!).
La spiegazione del programma col relativo codice la si può trovare qui.
Per comodità riporto di seguito il codice:
Codice: Seleziona tutto
use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

Sto cercando di tradurre in C tale codice senza perderne, però, al tempo stesso, la bellezza intrinseca dello stesso.
La cosa mi sembra piuttosto complicata (almeno per me) e cerco qualche volenteroso che voglia collaborare nella stesura...
Per il momento non ho ancora iniziato la conversione vera e propria ma mi sono limitato a studiarne il funzionamento.
Ho pensato che dovendo essere tale codice gioco-forza piuttosto breve, si possa utilizzare questo topic per qualsiasi contributo al codice.
Grazie per l'attenzione.

Un saluto,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Sponsor
 

Postdi zello » 10/10/05 21:39

obfuscated perl? No, grazie, faccio fatica a leggere il perl quando è scritto normale...
Il faut être toujours ivre. Tout est là : c'est l'unique question. Pour ne pas sentir l'horrible fardeau du Temps qui brise vos épaules et vous penche vers la terre,il faut vous enivrer sans trêve...
Avatar utente
zello
Moderatore
 
Post: 2351
Iscritto il: 06/05/02 13:44

Sviluppi 1

Postdi infinito1971 » 17/10/05 10:21

Ho riscrito il codice come segue:
Codice: Seleziona tutto
use integer;
@A = split //, <>;

sub R {
    for $i ( 0 .. 80 )
       {
           if ($A[$i]==0)
              {
                 my %t = map
                       {
                          $_ / 9 == $i / 9
                       || $_ % 9 == $i % 9
                       || $_ / 27 == $i / 27 && $_ % 9 / 3 == $i % 9 / 3
                        ? $A[$_]
                        : 0 => 1
                       } 0 .. 80;
                 R( $A[$i] = $_ ) for grep { !$t{$_} } 1 .. 9;
                 return $A[$i] = 0;
              }
       }
    die @A;
      }
R
Ho notato che sostituendo:
Codice: Seleziona tutto
for $i ( 0 .. 80 )
con:
Codice: Seleziona tutto
for ($i=0; $i<81; $i++)
Il risultato cambia e non è più corretto... come mai?!? :eeh:
E' qualcosa che ha a che fare con la variabile predefinita $_ ?? :roll:
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Postdi klizya » 17/10/05 11:14

i miei ricordi di C sono datati ma dovrebbe essere così:
int i (dichiarazione)
e il ciclo:
for %i=0; %i=80; %i++

prendilo col beneficio del dubbio ma provare non costa nulla :)
klizya
Utente Senior
 
Post: 901
Iscritto il: 09/06/05 12:03
Località: Grosseto

Postdi klizya » 17/10/05 11:17

ho dimenticato le parentesi dopo il for :P
klizya
Utente Senior
 
Post: 901
Iscritto il: 09/06/05 12:03
Località: Grosseto

Codice Perl

Postdi infinito1971 » 17/10/05 11:49

Ciao klizya,
ti ringrazio per la buona volontà di collaborare ma forse hai fatto un pò di confusione con i linguaggi di programmazione...
Il codice riportato su è scritto in perl e la sintassi del ciclo è corretta in entrambi i casi... in c sarebbe apparso come segue:
Codice: Seleziona tutto
for (i=0; i<81; i++)

Il codice da te riportato sarebbe comunque errato; ricorda in C il confronto di un uguaglianza va effettuata con == e non con = che coincide ad un'assegnazione!
Inoltre, il secondo parametro del for indica la condizione per cui il ciclo va eseguito e quindi è corretto scrivere i<81.
Grazie comunque.

Un saluto,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Postdi klizya » 17/10/05 12:00

non guardare le sottigliezze quali il == o l'impostazione del ciclo iterativo ma vedi piuttosto se è una questione di dichiarazione e di contenuto delle variabili.
Scrivi la sintassi corretta e prova
klizya
Utente Senior
 
Post: 901
Iscritto il: 09/06/05 12:03
Località: Grosseto

Postdi GAD » 17/10/05 12:24

infinito, hai letto hacker journal anche tu in settimana?? :D
Per seguire meglio la logica scrivi prima la forma estesa e poi quando funge passa a quella ristretta, conviene sempre.
Mi pare che in ci ansi i caratteri @ $ non possano essere usati come nell'esempio che hai postato
Quando l'ultimo albero sarà abbattuto,l'ultimo pesce catturato,l'ultimo fiume avvelenato,
soltanto allora gli uomini si accorgeranno chei soldi non possono essere mangiati
GAD
Moderatore
 
Post: 2184
Iscritto il: 22/09/02 14:36
Località: Nebbiosa

Postdi infinito1971 » 17/10/05 16:38

GAD, quello che ho postato è ancora codice perl... la mia domanda, per il momento, era sul fatto che modificando semplicemente il ciclo come detto, il risultato cambia in modo che non riesco a spiegarmi...
Per quanto riguarda hackers journal, ebbene si, lo leggo abitualmente (è tra le mie insane letture...) in quanto è economico e spesso fonte di spunti (come in questo caso) anche se lo trovo un pò sempliciotto e spesso gli articoli sono delle semplici traduzioni di articoli presenti in rete... (d'altra parte, però, cos'è che non si trova su Internet?!?).
Comunque se vuoi ti consiglio questa rivista che a mio avviso è il top per questo genere di riviste!

Ciao,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Postdi GAD » 17/10/05 16:53

deheh l'ho letto giusto l'altra sera e mi e' rimasto in mente l'articolo sul sudoku col perl offuscato. Anche io lo prendo perche' costa poco ed e' pieno di spunti... kryptos l'ho conosciuto li' per la prima volta, mi e' piaciuta un tot come info per approfondire.
Non l'ho mai vista quella rivista, grazie per il link. Rimpiango i vecchi netrunner, quelli hanno fatto storia e molti articoli sono ancora validissimi per capire come funzionano hardware\software e la logica.

Ma sei sicuro che devi usare 81 come limite? il for e il contenuto dell'array non va da 0 a n-1?
Quando l'ultimo albero sarà abbattuto,l'ultimo pesce catturato,l'ultimo fiume avvelenato,
soltanto allora gli uomini si accorgeranno chei soldi non possono essere mangiati
GAD
Moderatore
 
Post: 2184
Iscritto il: 22/09/02 14:36
Località: Nebbiosa

Ciclo corretto!

Postdi infinito1971 » 18/10/05 10:03

GAD, il problema non è quello. L'array è costituito da tutti gli elementi da 0 a 80, per cui il ciclo è corretto; d'altra parte puoi rendertene conto lanciando il seguente codice scritto in perl:
Codice: Seleziona tutto
for $i ( 0 .. 9)
{
   print "\$i= $i\n";
}
print "\n";
for ($i=0; $i<10; $i++)
{
   print "\$i= $i\n";
}
Ciao,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Sviluppi 2

Postdi infinito1971 » 19/10/05 10:31

Ciao a tutti,
ho riscritto il codice Perl in una forma molto più leggibile e simile al C; l'unico problema rimasto che non so spiegarmi è quello legato ai cicli presenti nel codice che, se scritti in forma diversa, portano a risultati errati.
Qualcuno ha qualche idea in merito?!? Io penso che in qualche modo ciò sia legato alla ricorsione utilizzata nel programma ma ancora non so spiegarmi il motivo di questo "strano" comportamento... :eeh:
Comunque, riporto di seguito il codice ed attendo fiducioso qualche contributo...
Codice: Seleziona tutto
use integer;
@A = split //, <>;

sub R {
    for $i ( 0 .. 80 )
       {
           if ($A[$i]==0)
              {
                 my %t = ();
                 for $j ( 0 .. 80 )
       {
          $t{
                          $j / 9 == $i / 9
                       || $j % 9 == $i % 9
                       || $j / 27 == $i / 27 && $j % 9 / 3 == $i % 9 / 3
                        ? $A[$j]
                        : 0} = 1;
                 }
       for $j ( 1 .. 9 )
                 {
                     if ($t{$j}==0)
         {
            R( $A[$i] = $j );
         }
                 }
                 return $A[$i] = 0;
              }
       }
   die @A;
      }
R
Saluti,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Ci sono!!!

Postdi infinito1971 » 19/10/05 11:25

Finalmente sono venuto a capo del problema relativo ai cicli... :!:
L'errore era nel mancato utilizzo dell'operatore my... :evil:
Riporto di seguito il codice... ora non dovrebbe essere molto difficile convertirlo in C.. :)

Saluti,
infinito1971
Codice: Seleziona tutto
use integer;
@A = split //, <>;

sub R {
    for (my $i=0; $i<81; $i++)
       {
           if ($A[$i]==0)
              {
                 my %t = ();
                 for (my $j=0; $j<81; $j++)
       {
          $t{
                          $j / 9 == $i / 9
                       || $j % 9 == $i % 9
                       || $j / 27 == $i / 27 && $j % 9 / 3 == $i % 9 / 3
                        ? $A[$j]
                        : 0} = 1;
                 }
       for (my $j=1; $j<10; $j++)
                 {
                     if ($t{$j}==0)
         {
            R( $A[$i] = $j );
         }
                 }
                 return $A[$i] = 0;
              }
       }
   die @A;
      }
R
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Sviluppi 3

Postdi infinito1971 » 20/10/05 10:55

Ciao a tutti,
ho modificato il codice precedente in modo tale da evitare l'uso degli hash e di utilizzare soltanto gli array; riporto di seguito il nuovo codice Perl:
Codice: Seleziona tutto
use integer;
@A = split //, <>;

sub R {
    for (my $i=0; $i<81; $i++)
       {
           if ($A[$i]==0)
              {
                 my @t = ();
                 for (my $j=0; $j<81; $j++)
       {
          $t[
                          $j / 9 == $i / 9
                       || $j % 9 == $i % 9
                       || $j / 27 == $i / 27 && $j % 9 / 3 == $i % 9 / 3
                        ? $A[$j]
                        : 0] = 1;
                 }
       for (my $j=1; $j<10; $j++)
                 {
                     if ($t[$j]==0)
         {
            R( $A[$i] = $j );
         }
                 }
                 return $A[$i] = 0;
              }
       }
   die @A;
      }
R

Saluti,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Prima stesura in C

Postdi infinito1971 » 20/10/05 11:10

Ciao a tutti,
riporto di seguito una primissima stesura in C del programma; ancora non funziona e dev'essere corretto... chi mi da una mano?!?
Grazie in anticipo,
infinito1971

Codice: Seleziona tutto
// Sudoku.cpp : Defines the entry point for the console application.
//

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

char A[]="012504870040000000750016423504108730020050040003409500480005017000000000235701690";

int R(int n)
{
   for (int i=0; i<81; i++)
      {
         if (A[i]=='0')
         {
            int t[9];
            for (int j=0; j<81; j++)
            {
               t[
                     int(j / 9) == int(i / 9)
                  || j % 9 == i % 9
                  || int(j / 27) == int(i / 27) && int(j % 9 / 3) == int(i % 9 / 3)
                   ? A[j] - 48
                   : 0] = 1;
            }
            for (int k=1; k<10; k++)
            {
               if (t[k]==0)
                  {
                     A[i] = 48 + k;
                     R(k);
                  }
            }
            A[i] = '0';
            return 0;
         }
      }
//   die @A;
//   return A;
}

int main(int argc, char* argv[])
{
//   gets(A);
   R(0);
   printf("%s\n", A);

   return 0;
}
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Sviluppi 4

Postdi infinito1971 » 20/10/05 16:07

Per rendere ancor meglio leggibile il programma in Perl, ho apportato alcune modifiche; quello che segue è il codice definitivo (in Perl) da convertire in C:
Codice: Seleziona tutto
use integer;
@A = split //, <>;

sub R {
    for (my $i=0; $i<81; $i++)
       {
           if ($A[$i]==0)
              {
                 my @t = ();
                 for (my $j=0; $j<81; $j++)
       {
          $t[
                          $j / 9 == $i / 9
                       || $j % 9 == $i % 9
                       || $j / 27 == $i / 27 && $j % 9 / 3 == $i % 9 / 3
                        ? $A[$j]
                        : 0] = 1;
                 }
       for (my $j=1; $j<10; $j++)
                 {
                     if ($t[$j]==0)
         {
            $A[$i] = $j;
            R();
         }
                 }
                 $A[$i] = 0;
                 return;
              }
       }
   die @A;
      }
R

Un saluto,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Seconda stesura

Postdi infinito1971 » 20/10/05 16:45

Alla luce della precedente implementazione, riporto di seguito le modifiche apportate al programma in C che, però, al momento, ancora non funge... :roll:
Codice: Seleziona tutto
// Sudoku.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>

char A[]="012504870040000000750016423504108730020050040003409500480005017000000000235701690";

void R()
{
   int t[9];
   int i,j;

   for (i=0; i<81; i++)
      {
         if (A[i]=='0')
         {
            for (i=0; i<10; i++)
               t[i]=0;
            for (j=0; j<81; j++)
            {
               t[
                     int(j / 9) == int(i / 9)
                  || j % 9 == i % 9
                  || int(j / 27) == int(i / 27) && int(j % 9 / 3) == int(i % 9 / 3)
                   ? A[j] - 48
                   : 0] = 1;
            }
            for (j=1; j<10; j++)
            {
               if (t[j]==0)
                  {
                     A[i] = 48 + j;
                     R();
                  }
            }
            A[i] = '0';
            return;
         }
      }
//   die @A;
}

int main(int argc, char* argv[])
{
//   gets(A);
   R();
   printf("%s\n", A);

   return 0;
}

bye,
infinito1971
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Postdi disgrazia » 20/10/05 23:51

Ho fatto una miriade di modifiche, un po' a naso, un po' a caso... però alla fine funziona! 8)

Codice: Seleziona tutto
/* sudoku.c
 * Original by infinito1971
 * Modified by disgrazia
 */


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

char A[81]="000010000301400860900500200700160000020805010000097004003004006048006907000080000";


void R()
 {
    int t[10];
    int i,j;
 
    for (i=0; i<81; i++)
       {
    if (A[i]!='0') continue;
    
    for (j=0; j<10; j++)
      t[j]=0;

    for (j=0; j<81; j++)
      {         
        if ( ((j / 9) == (i / 9))\
        || ((j % 9) == (i % 9) ) \
        || ( (j / 27 == i / 27) && ((j % 9) / 3) == ((i % 9) / 3) ) )
          t[A[j] - 48] = 1;
      }

    for (j=1; j<10; j++)
      {
        if (t[j]==0)
          {
       A[i] =  j + 48;
       R();
          }
      }

    A[i] = '0';
    return;
         
       }

   /* If we get here, we have the solution.
    * We have to print it and exit, otherwise if we let the function return
    * all open pending recursive calls will try new values for each position!
    */   


   for(i=0; i<81; i++)
     {
       putc(A[i],stdout);
       if (!((i+1)%9)) putc('\n',stdout);
     }


   putc('\n',stdout);
   exit(0);

 }
 
 int main(int argc, char* argv[])
 {
   int c;
   R();   
   return 0;
 }



In realtà le modifiche da fare al tuo codice sono poche, se non ricordo male gli errori principali erano:
  • non bisogna utilizzare la variabile i nel ciclo for che inizializza il vettore t, altrimenti si modifica l'indice di posizione corrente del ciclo for più esterno
  • una volta trovata la soluzione bisogna evitare che tutte le chiamate ricorsive aperte ritornino, sennò la ricerca continua.
  • ma che cavolo era quella funzione/macro int() che chiamavi? ma int non è una parola riservata in C? Poi non serve convertire ad interi, in C la divisione fra interi ha risultato intero.

Beh, ci ho perso un paio d'orette però e stato divertente! E dire che non ho mai giocato una volta a sudoku :lol:
disgrazia
Download Admin
 
Post: 708
Iscritto il: 08/07/02 22:16

Versione Finale

Postdi infinito1971 » 21/10/05 10:38

Ciao disgrazia,
innanzitutto grazie per il prezioso contributo!
Ho letto con attenzione le indicazioni che mi hai dato ed ho realizzato un codice leggermente più "pulito" e che riporto di seguito.

Grazie mille,
infinito1971
Codice: Seleziona tutto
// Sudoku.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>

/*
use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
$i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R
*/

char A[80];

void R()
{
   int t[10];
   int i,j;

   for (i=0; i<81; i++)
      {
         if (A[i]=='0')
         {
            for (j=0; j<10; j++)
               t[j]=0;
            for (j=0; j<81; j++)
            {
               t[
                     j / 9 == i / 9
                  || j % 9 == i % 9
                  || j / 27 == i / 27 && j % 9 / 3 == i % 9 / 3
                   ? A[j] - 48
                   : 0] = 1;
            }
            for (j=1; j<10; j++)
            {
               if (t[j]==0)
                  {
                     A[i] = 48 + j;
                     R();
                  }
            }
            A[i] = '0';
            return;
         }
      }
   printf("%s\n", A);
}

int main(int argc, char* argv[])
{
   gets(A);
   R();
   return 0;
}
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Versione in VB - Sviluppo 1

Postdi infinito1971 » 17/11/05 10:13

Ciao a tutti,
torno sull'argomento perchè stavo cercando di convertire il codice C realizzato in precedenza in codice Visual Basic.
Il codice che ho realizzato ancora non funzia e cerco qualche volenteroso che mi aiuti nel debug... ;) disgraziaaa... dove sei?!?? :)

Un saluto,
infinito1971

Codice: Seleziona tutto
' use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
' ==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
' $i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

Dim A As String
   
Private Sub Command1_Click()
    Text1.Text = "012504870040000000750016423504108730020050040003409500480005017000000000235701690"
    A = Text1.Text
    Call R
End Sub

Private Sub R()
    Dim t(10) As Integer
    Dim i As Integer, j As Integer
   
    For i = 0 To 80
        If Mid(A, i + 1, 1) = "0" Then
            For j = 0 To 9
                t(j) = 0
            Next
            For j = 0 To 80
                t(IIf(Int(j / 9) = Int(i / 9) Or Int(j Mod 9) = Int(i Mod 9) Or Int(j / 27) = Int(i / 27) And Int(j Mod 9 / 3) = Int(i Mod 9 / 3), Asc(Mid(A, j + 1, 1)) - 48, 0)) = 1
            Next
            For j = 1 To 9
                If t(j) = 0 Then
                    If i = 0 Then
                        A = Trim(Str(j)) & Right(A, 80)
                    ElseIf i = 80 Then
                        A = Left(A, 80) & Trim(Str(j))
                    Else
                        A = Left(A, i) & Trim(Str(j)) & Right(A, 80 - i)
                    End If
                    Call R
                End If
            Next
            If i = 0 Then
                A = "0" & Right(A, 80)
            ElseIf i = 80 Then
                A = Left(A, 80) & "0"
            Else
                A = Left(A, i) & "0" & Right(A, 80 - i)
            End If
            Exit Sub
        End If
    Next
    Text1.Text = A
End Sub
Questo business è binario: o sei 1 o sei 0, vivo o morto, non esistono secondi classificati!
Avatar utente
infinito1971
Utente Senior
 
Post: 532
Iscritto il: 01/08/02 21:22
Località: Napoli

Prossimo

Torna a Programmazione


Topic correlati a "Sudoku: Perl to C to Java":

[Java] Stampare a video
Autore: karug64
Forum: Programmazione
Risposte: 1

Chi c’è in linea

Visitano il forum: Nessuno e 6 ospiti