Sudoku i C#

Det eneste "rigtige"(Her mener jeg uden for mange gætterier) måde at løse en Soduku, må efter min mening være at neural netwærk. Et neuralt netværk prøver såvidt muligt at efterligne hjernen, og man kan derfor lave et netværk og derefter træne det op, så det kan løse en soduku selv. Det skal dog siges at neurale netværk er et ret så avanceret emne, og det ville nok være nemmere enten at gribe problemet an med en genetisk algorithme(Som Brian har forslået) eller med en iterativ løsning.

Desuden fandt jeg også lige et forum for soduka programmøre. Kan være det kan bruges: http://www.setbb.com/phpbb/?mforum

MH.

The-Freak

Livet er for kort til at kede sig.
blog: http://laslego.frac.dk

The-Freak: Du har helt ret det er sådan det bedst kan laves.. Det gør også at tiden for at finde løsningen er kort i forhold til gæteri.

Jeg har selv lavet en soduko løser som kan tage en del forskellige sodukoer. Jeg er ikke noget til den kan løse de helt svære.

Men måden man kan efter ligne hjernen på, er at man har f.eks 2 eller flere forskellige faser den skal køre for at kunne finde nogle hele tal som den er sikker på skal stå der.
Når den så har fundet de tal som den er sikker på skal stå der køre man de 2 eller flere faser igennem for at finde flere nye hele tal den er sikker på skal stå der.

Jeg ved at DTU har en matematisk formel for at regne en celle i soduko ud, men jeg har ikke set den.

Med venlig hilsen
Frede_Manden

[Redigeret d. 21/10-05 16:04:49 af Frede_Manden]

[Redigeret d. 21/10-05 16:06:05 af Frede_Manden]

En ren logisk løsning på at løse sudoku må være:

Find et tomt felt, for alle gyldige tal i dette felt prøves med alle gyldige tal i alle andre felter.

Det ses let at dette bliver til et træ, sådanne træer løses lettest med en recursiv algoritme.

Der er en tråd om emnet her:
http://www.eksperten.dk/spm/641545

Jeg har selv lavet en sudoku løser i C++, den bruger ren tilfældig gæt, hvilket er den letteste løsning, men den er lidt langsom.

Hej..

Det er spændende når en tråd giver anledning til at involvere lidt matematik...

Jeg kan ikke tale med om hvad neurale netværk i sandhed er, udover at jeg også har hørt at det er "efterligning af hjernen" - hvis nogen kan forklare yderligere hvad det indebærer er jeg all-ears.

Skulle man også lave neurale netværk til faktorisering af (store) tal, der f.eks. kan hjælpe til at bryde koder?? Man kan jo bruge talteorien i stedet...

Neurale netværk lyder dog for mig som noget overdrevent når spillet nu engang er "logisk". Matematisk er det lidt interessant idet Sudoku er en special tilfælde af det man kalder "Latin Square". www.mathworld.com har uden tvivl noget om latin square...

Det er muligt at gå matematisk/logisk til værks ved løsning af en sudoku. Så vidt jeg kan huske har en af de store hoveder, Donald E. Knuth, en algoritme "Dancing link" som er mulig at overføre til en sudoku.

Men det er jo altid sjovere når man selv finder frem til effektive løsninger, og de mest oplagte metoder at løse en sudoku er jo allerede beskrevet i tråden.

God fornøjelse med Sudoku programmeringen!

Venlig hilsen
MF

Fandt lige følgende som er interessant for dig hvad angår det matematiske: http://www.student.dtu.dk/~s011378/sudoku

[Redigeret d. 21/10-05 18:56:36 af MF]

Jeg lavede en sudoku løser i C++, den bruger recursion, det er næsten så simpelt som det kan blive:

#include <iostream>
#include <vector>

typedef unsigned char uint8_t;
struct SudokuT
{
   uint8_t Maze[9][9];
};

SudokuT Maze = // This is the sudoko to solve
{
   {
      {7,8,0,0,0,5,9,0,0},
      {0,4,0,2,0,7,0,3,0},
      {0,5,9,0,0,8,2,4,0},
      {0,2,0,0,0,9,3,1,0},
      {0,0,7,3,0,4,6,0,0},
      {0,3,4,1,0,0,0,9,0},
      {0,6,5,7,0,0,8,2,0},
      {0,7,0,9,0,6,0,5,0},
      {0,0,3,5,0,0,0,7,6}
   }
};

bool IsValid(const SudokuT &aSudoko, int aX, int aY, uint8_t aVal)
{  // Will the sudoko be valid if we put aVal into [aX][aY]
   int a;
   for(a = 0; a < 9; a++)
      if(aSudoko.Maze[aX][a] == aVal)
         return false;
   for(a = 0; a < 9; a++)
      if(aSudoko.Maze[a][aY] == aVal)
         return false;
   int y = aY/3;
   int x = aX/3;
   if(aSudoko.Maze[x*3][y*3 + 0] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 0] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 0] == aVal ||
      aSudoko.Maze[x*3][y*3 + 1] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 1] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 1] == aVal ||
      aSudoko.Maze[x*3][y*3 + 2] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 2] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 2] == aVal)
   {
      return false;
   }
   return true;
}

bool Solve(SudokuT &aSudoko)
{
   int x, y;
   uint8_t Val;
   for(y = 0; y < 9; y++)
   {
      for(x = 0; x < 9; x++)
      {
         if(aSudoko.Maze[x][y] == 0)
         {  // Have found a empty index, check all values
            for(Val = 1; Val <= 9; Val++)
            {
               if(IsValid(aSudoko, x, y, Val))
               {
                  aSudoko.Maze[x][y] = Val;
                  if(Solve(aSudoko))
                     return true;
               }
            }
            aSudoko.Maze[x][y] = 0;
            return false;
         }
      }
   }
   return true;
}

int main()
{
   if(Solve(Maze))
   {
      std::cout << "Success" << std::endl;
      int x, y;
      for(y = 0; y < 9; y++)
      {
         for(x = 0; x < 9; x++)
            std::cout << int(Maze.Maze[y][x]);
         std::cout << std::endl;
      }
   }
   else
   {
      std::cout << "Failed" << std::endl;
   }
}

Man kunne optimere på to punkter:
1: Når man skal finde en tom plads startes der altid forfra.
2: Måden man finder ud af hvilke tal der kan bruges på en plads, kunne optimeres ved at starte med at lave en liste over mulige tal, så skulle man kun søge gennem én gang.

Jeg lavede en sudoku løser i C++, den bruger recursion, det er næsten så simpelt som det kan blive:

Hej igen...

Dog kan jeg ikke understrege nok den vigtighed og kraftfuldhed som matematikken har i optimeringsopgaver, bl.a. Sudoku.

DTU artiklen kan måske virke skræmmende på grund af matematikken, men den viser hvor simpelt det kan være at udvikle en algoritme der fungerer. Og ganske som de skriver er løsningsmodellen ikke et genialt påfund idet mange andre kan komme frem til samme model.

Venlig hilsen
MF

Jeg er ikke matematikker, og forstår ikke koden i artiklen.
Jeg er programmør, og løser problemet med en logisk løsning.

Sidst jeg var i København skrev jeg en sudoku solver i toget, den kan sagtens opmiteres lidt men det kommer vi til. Og så kom jeg jo lige i tanker om denne tråd (jeg skrev godt nok min i c)

Algoritmen benytter den strategi der hedder Backtracking.

først skal vi have styr på pladen, vi opretter en datatype, jeg kaldte min felt, den består en integer der angiver værdien i feltet (0 hvis værdien ikke er sat) og et array af integers der repræsenterer samtlige mulige tal, husk at 0 er i c false og alt andet er sandt, det er det vi skal misbruge her.

selve spillepladen er to-dimentinelt array af felt (gæt selv dimentionerne)

vi skal nu bruge et par hjælpefunktioner, setvalue og unsetvalue, de kaldes med samme parametre og er egentlig blot hinandens omvendte.

så jeg nøjes med at beskrive setvalue.
setvalue skal sætte værdien af et felt (x,y) til værdien v og markere i relevante felter at de ikke kan antage værdien v. sidst nævnte gøremål er det sværeste her, men løses med lidt for knepperi og pladen[x,y].array[v]++; det er ikke væsentlig at integeren kun incrementeres 1, det vigtige er at unsetvalue ophæver det.

og nu løsningsfidusen, vi starter bare med det første og bedste felt og for hver permutation vi endnu ikke har markeret som ulovlig siger vi:
setvalue(x,y,v);
solve(nextX, nextY);
unsetvalue(x,y,v);

succes kriteriet er at y opnår værdien 9;

nå men kode siger mere end 1000 ord

#include <stdio.h>

typedef struct{
        char potentielle[10];
        char value;} felt;

felt plade[9][9];

int solved = 0;

void setvalue(int x, int y, int v){
     int i,j;
     
     plade[x][y].value = v;
     
     for(i = 0; i < 9; i++) plade[ i ][y].potentielle[v]++;
             
     for(i = 0; i < 9; i++) plade[x][ i ].potentielle[v]++;

     for(i = (x / 3) * 3; i <(x / 3) * 3 +3; i++)
           for(j = (y / 3) * 3; j <(y / 3) * 3 +3; j++)
                 plade[ i ][j].potentielle[v]++;                
}

void unsetvalue(int x, int y, int v){
     int i,j;
     
     plade[x][y].value = 0;
     
     for(i = 0; i < 9; i++) plade[ i ][y].potentielle[v]--;
             
     for(i = 0; i < 9; i++) plade[x][ i ].potentielle[v]--;

     for(i = (x / 3) * 3; i <(x / 3) * 3 +3; i++)
           for(j = (y / 3) * 3; j <(y / 3) * 3 +3; j++)
                 plade[ i ][j].potentielle[v]--;
}     

void printres(){
     int i,j;
     for( i = 0; i < 9; i++){
            for(j = 0; j < 9; j++) printf("%d ", plade[j][ i ].value);
            printf("\\n");
          }
          solved = 1;
          }

void solve(int x, int y){
     int nx, ny;
     int i;
     if(solved) return;

     if(y == 9) {
          printres();
          return;
          }
     
     nx = x +1;
     ny= y;
     if ( nx == 9){ nx = 0; ny++;}
     
     if(!plade[x][y].value){ for(i = 1; i < 10; i++){
            if(!plade[x][y].potentielle[ i ]){ 
            setvalue(x,y,i);
            solve(nx, ny);
            unsetvalue(x,y,i);}
            }}else solve(nx,ny);
}
          
int main(){
    int tal;
    int i,j,k;
    FILE * f = fopen("sudokuin.txt", "r");
    for( i = 0; i < 9; i++) for(j = 0; j < 9; j++) {
         fscanf(f,"%u", &tal);
         setvalue(j,i,tal);
         }
     fclose(f);
     solve(0,0);
    
     return 0;     
}

og den indlæser en sudoku fra filen sudokuin.txt der f.eks. kan være formatteret således:

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

af optimeringer kan jeg nævne at det ikke nødvendigvis er det mest effektive at starte fra en ende til en anden, der er det bedre hele tiden at tage det delt med færrest mulige permutationer. succes kriteriet skal dog ændres lidt (setvalue kørt 81 gange mere end unsetvalue);

håber der er nogen der kan bruge det til noget.

//TROELS

ps. koden kan hurtigt omskrives så den istedet om en sudoku har en entydig løsning.

EDIT: Traditionen tro fucker ehtml ens kode op


[Redigeret d. 14/11-05 12:22:41 af Troels]