Script til at løse Soduko

Backtracking kan altid bruges.
1) Opstil de frie felter i en liste
2) Fra en ende af prøver du tallene 1..9
3) hvis et tal ikke giver en modstrid, prøver du 1..9 for det næste i listen
4) hvis det giver en modstrid går du ikke videre
5) Når du er kommet forbi 9 går du tilbage til det forrige felt i listen

Rekursion er en god måde at løse det på ;)

Øhhh, og det fattede jeg så intet af :D

Så er det enten
a) Jeg ikke kan forklare det godt nok, eller
b) Du ikke skal begynde på at løse lige det problem ;)

Men søg du bare efter backtracking på google.

1: Vælg et tilfældigt tomt felt
2: Find et tal der kan passe i feltet, hvis ikke du kan finde et tal, så start forfra
3: Hvis alle felter er fyldt -> done
4: Gå til 1

Det blev det ikke meget nemmere af :S

Kan du læse C++ kode ? Har du et par opgaver ?
Så laver jeg lige koden i C++

Det skal være PHP, derfor jeg har lagt den herinde i Script/PHP/

Du kan få en her: http://www.lovatts.com.au/sudoku/sudoku.htm

Ideen var at jeg skrev det i C++ så du kan se hvordan man gør & du "oversætter" til PHP

ja okay, der er da helt i orden :)

Arbejder på projectet.

Lyder godt :)

Dette ser ud til at virke:

#include <iostream>
#include <algorithm>

int OrgMaze[9][9] = // 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}
};

int Random()
{
  return rand()%9; // Random Number 0..8
}

int main()
{
  int OrgNum, i, j, n, t, Num, NumberArray[9] = {1,2,3,4,5,6,7,8,9};
  srand(time(0));
  for(i = 0, OrgNum = 0; i < 9; i++)
      for(j = 0; j < 9; j++)
        if(OrgMaze[i][j] == 0)
            OrgNum++;

  while(1)
  {  // Start all over
      Num = OrgNum;
      int Maze[9][9];
      memcpy(Maze, OrgMaze, sizeof(Maze)); // Set Maze = OrgMaze
      bool Valid = true;
      while(Valid)
      {
        i = Random(); // Select a random field
        j = Random();
        if(Maze[i][j] == 0)
        {
            std::random_shuffle(NumberArray, &NumberArray[9]);
            bool Done = false;
            int idx;
            for(idx = 0; idx < 9 && !Done; idx++)
            {
              Done = true;
              t = NumberArray[idx];
              for(n = 0; n < 9; n++) // Check one line
                if(Maze[n][j] == t)
                    Done = false;
              for(n = 0; n < 9; n++) // Check the other line
                if(Maze[i][n] == t)
                    Done = false;
              int x = i/3, y = j/3;  // Check the square
              if(Maze[x*3][y*3 + 0] == t || Maze[x*3 + 1][y*3 + 0] == t || Maze[x*3 + 2][y*3 + 0] == t ||
                  Maze[x*3][y*3 + 1] == t || Maze[x*3 + 1][y*3 + 1] == t || Maze[x*3 + 2][y*3 + 1] == t ||
                  Maze[x*3][y*3 + 2] == t || Maze[x*3 + 1][y*3 + 2] == t || Maze[x*3 + 2][y*3 + 2] == t)
              {
                  Done = false;
              }
            }
            if(Done)
            {
              Maze[i][j] = t;
              Num--;
              if(Num == 0)
              {  // We are done
                  for(i = 0; i < 9; i++)
                  {
                    for(j = 0; j < 9; j++)
                      std::cout << Maze[i][j];
                    std::cout << std::endl;
                  }
                  exit(0);
              }
            }
            else
            {
              Valid = false;
            }
        }
      }
  }
}

En lidt simplere version, den virker vist lige så godt:
#include <iostream>

int OrgMaze[9][9] = // 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}
};

int Random()
{
  return rand()%9; // Random Number 0..8
}

int main()
{
  int OrgNum, i, j, n, t, Num;
  srand(time(0));
  for(i = 0, OrgNum = 0; i < 9; i++) // Count number of "holes"
      for(j = 0; j < 9; j++)
        if(OrgMaze[i][j] == 0)
            OrgNum++;

  while(1)
  {  // Start all over
      Num = OrgNum;
      int Maze[9][9];
      memcpy(Maze, OrgMaze, sizeof(Maze)); // Set Maze = OrgMaze
      bool Valid = true;
      while(Valid)
      {
        i = Random(); // Select a random field
        j = Random();
        if(Maze[i][j] == 0)
        {
            bool Done = false;
            int idx;
            for(idx = 1; idx <= 9 && !Done; idx++)
            {
              t = idx;
              Done = true;
              for(n = 0; n < 9; n++) // Check one line
                if(Maze[n][j] == t)
                    Done = false;
              for(n = 0; n < 9; n++) // Check the other line
                if(Maze[i][n] == t)
                    Done = false;
              int x = i/3, y = j/3;  // Check the square
              if(Maze[x*3][y*3 + 0] == t || Maze[x*3 + 1][y*3 + 0] == t || Maze[x*3 + 2][y*3 + 0] == t ||
                  Maze[x*3][y*3 + 1] == t || Maze[x*3 + 1][y*3 + 1] == t || Maze[x*3 + 2][y*3 + 1] == t ||
                  Maze[x*3][y*3 + 2] == t || Maze[x*3 + 1][y*3 + 2] == t || Maze[x*3 + 2][y*3 + 2] == t)
              {
                  Done = false;
              }
            }
            if(Done)
            {
              Maze[i][j] = t;
              Num--;
              if(Num == 0)
              {  // We are done
                  for(i = 0; i < 9; i++)
                  {
                    for(j = 0; j < 9; j++)
                      std::cout << Maze[i][j];
                    std::cout << std::endl;
                  }
                  exit(0);
              }
            }
            else
            {
              Valid = false;
            }
        }
      }
  }
}

Lækker, prøver at oversætte den...

Det tror jeg ikke du skal gøre - så vidt jeg kan se virker den ikke.

Det som bertelbrander gør, er at vælge et felt, og vælge et tal i det felt, som ikke
giver konflikt med sodukos regler. Hvis det lykkes kan tallet i det pågældende felt ikke
siden ændres, men det er ikke nødvendigvis er korrekt. Der kan jo sagtens være
flere muligheder, og et forkert valg kan blokere for en korrekt løsning et andet
sted på pladen.

Så vidt jeg kan se. Skal vi ikke lige se om bertelbrander er enig?

Æv, sad lige og håbede...

>>erik, det ser jeg også i koden, så som du snakkede om, noget rekursivt, som sætter et tal ind i puslespillet ad gangen og så kalder sig selv til en ny tur ...

Enig, og så vil jeg da godt påpege at en strategi baseret på et random-nummer ikke ligefrem er specielt effektiv. Det ender meget hurtigt med at man prøver det samme tal flere gange (specielt når der som her er ganske få muligheder). Der er i stedet brug for en algoritme, som systematisk gennemprøver de mulige værdier et af gangen.

Hmmm... Er det noget en af jer kan lave, eller forklare hvordan man laver? :)

Altså, forklare sådan så jeg forstår der :P

Egentlig tror jeg at random-number strategien har en anelse bedre chance end den med at tage den fra en ende af, for jeg vil tro, at løsninger har det med at have en spredning, som ligger langt fra en regularitet !-)

-- men det er vigtigt at man tager de tomme felter en for en og får dem udfyldt med noget gyldigt, prøver det næste, evt. går tilbage og prøver et nyt tal ...

-- hrm, php kan jeg ikke, men jeg kan da prøve at kigge på en algoritme, som virker, hrm, hrm ...

Algoritmen virker men er ikke ret effiktiv, der skal et stem mellem 10000 og 100000 forsøg til at finde den rigtige løsning.

Hvis jeg får sat et tal et forkert sted, vil jeg senere få et felt hvor jeg ikke kan finde noget nummer der passer. I så fald starter man helt forfra.

Så skal random-strategien da i hvert fald kombineres med en mekanisme som sikre at man ikke forsøger sig med det samme tal flere gange ... samt at man er klar ov er hvornår at man har været alle mulighederne igennem.

Det skal bare kunne køre på en Apache med PHP og MySQL... Så er jeg egentlig ligeglad med hvordan det er lavet... Men hvis jeg selv skal lave det, så skal det være i PHP :)

Man kan naturligvis lave en mere intelligent løsning, men det bliver let meget kompliceret.

Programmet fra før løser let opgaven på under et sekund.

>nielle, hvordan ved man om man har forsøgt sig med det samme tal? Og hvordan ved man at man har prøvet alle muligheder?
Der bør nok laves et check for om Soduko'en er valid, ellers kunne programmet ende i en uendelig løkke. I praksis kunne man sætte et loft over hvor mange gange man ville forsøge.

Algoritmen kunne udvides til at starte med at finde de huller hvor der kun kan stå et bestemt tal, og sætte dette, og derpå undersøge om der er flere steder hvor det kun et bestemt tal, osv. Det ville gøre processen hurtigere i de trivielle tilfælde.

bertelbrander> Det er også kun muligt, hvis man starter systematisk fra den ene ende, og at man vel at mærke basere sig på en rekursiv algoritme.

Så har man for hver plads i soduku'en et boolsk-array af 9 pladser. Disse starter med at være initialiseret til false alle sammen. Når man har afprøvet tallet 1, så sættes plads nr. 1 (eller indeks 0) til true. Hvis man bruger random-metoden og f.eks. starter med at prøve med tallet 7 så er det selvfølgelig denne plads man sætter til true.

Når man skal trække et nyt tal så trækker man til til at man får et tal man ikke har prøvet før.

Og man kan konstatere at man har afprøvet alle tallene når der står lutter true i arrayet.

Men det dur som sagt kun hvis man bruger en rekursiv algoritme, ikke til tilfældet man starter helt forfra hver gang.

Tjah, jeg fandt jo ud af, at den viste Soduko kunne løses med ren logik, den vil jeg lige prøve at forfølge, i stedet for at forsøge med en brute force-agtig løsning !-)

-- men der skal sikkert tilføjes noget try and error, når logikken hører op !o]

Et af problemerne med at huske på hvad man har prøvet er:
Hvis man prøver sig frem indtil man når en blind ende, hvordan ved man så hvor meget af det man har lavet der er forkert? I mit eksempel går jeg ud fra at det er det hele og prøver forfra.
Selv med en recursiv metode vil der (så vidt jeg kan se) opstå problemer; at man én gang har fundet ud af at der ikke kan stå 7 i 0,0 betyder ikke at der ikke kan stå 7 der, hvis man ændrer et tal et andet sted.

Hver gang at algoritmen backtracker, og prøver ud af en ny vej, så bliver det gamle array automatisk smidt ud idet det så ryger ud af scope.

Man må da på en eller anden måde få den til at regne ud hvilke tal der kan stå i hvert felt, og i mindst 1 af den, kan der kun stå 1 tal, og det skal den så skrive, når den har skrevet det, skal den prøve igen, og sådan bliver den ved.
Det vil så kun virke hvis det f.eks er en af dem der er på denne side: http://aftenbladet.no/quiz/sudoku/

Skal bare lige finde ud af hvordan den skal regne ud hvilke tal der kan stå i hvert felt, uden at skulle skrive 50.000 linier :P

Tjah, den javascript-ting, jeg har lavet ud fra ovennævnte logik og eksempel virker bare, så den logik kan altså virke !-)

-- nu skal jeg så bare have den til at virke med et indtastet Soduko-problem, dvs. lave en fornuftig html-tabel med felter i !o]

Hvis alle opgaver kan løses på den måde som lallalej beskriver "15:28:50" er det næsten for let. Men jeg tvivler på at det er tilfældet med alle, der må være nogen hvor man skal prøve sig frem.

Tjah, nu kan vi jo prøve og se, om der altid er præcis een løsning !-)

-- hvis der er, så virker denne javascript-baserede ting:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
    "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<script type="text/javascript">
var talt = 0;
function solve(){
/*  var maze = [
    [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]
  ];
 
  txt = maze.toString();*/
 
  var maze = new Array();
  for(i=0;9>i;i++){
    maze[i] = new Array();
    for(j=0;9>j;j++){
      maze[i][j] = +document.getElementById("celle_" + i + "_" + j).value;
    }
  }
 
  var p = new Array(),used;
  for(i=0;9>i;i++){
    p[i] = new Array();
    for(j=0;9>j;j++){
      used = maze[i][j];
      p[i][j] = new Array();
      p[i][j][0] = used==0?9:1;
      for(k=1;10>k;k++){
        p[i][j][k] = used==0 || used==k;
      }
    }
  }
 
  for(i=0;9>i;i++){
    for(j=0;9>j;j++){
      if(maze[i][j]>0)
        p = updatePossibilities(i,j,p,maze);
    }
  }
  var tim = new Date();
  var changed = true;
  while(changed){
    changed = false;
    document.getElementById('minSpan').innerHTML = ++talt;
   
    for(i=0;9>i;i++){
      for(j=0;9>j;j++){
        if(maze[i][j] == 0 && p[i][j][0] == 1){
          num = 0;
          for(k=1;10>k;k++){
            if(num == 0 && p[i][j][k]){
              maze[i][j] = k;
              changed = true;
            }
            num += p[i][j][k]?1:0;
          }
          if(num>1){
            //rebuild if errors
            alert("Der er fundet fejl i possibilities !-)");
            return;
          }else
            p = updatePossibilities(i,j,p,maze);
        }
      }
    }
  }
 
  //alert(maze +"\n"+ txt);
 
  document.getElementById('minSpan').innerHTML = "Løsningstid: " + (new Date().getTime()-tim.getTime()) + " msek.";
 
  for(i=0;9>i;i++){
    for(j=0;9>j;j++){
      document.getElementById("Tcelle_" + i + "_" + j).innerHTML = maze[i][j];
    }
  }
}

function updatePossibilities(x,y,p,m){
  var boxX = x - x%3;
  var boxY = y - y%3;
  var num = m[x][y];
  for(var i=0; 9>i; i++){
    if(p[x][i][num])
      p[x][i][0]--;
    p[x][i][num] = false;
    if(p[i][y][num])
      p[i][y][0]--;
    p[i][y][num] = false;
  }
  for(i=0;3>i;i++){
    for(var j=0; 3>j; j++){
      actX = boxX + i;
      actY = boxY + j;
      if(actX!=x || actY!=y){
        if(p[actX][actY][num])
          p[actX][actY][0]--;
        p[actX][actY][num] = false;
      }
    }
  }
  p[x][y][0] = 1;
  return p;
}
</script>
<style type="text/css">
td{text-align:center;width:4em;}
input{text-align:center;}
</style>
<title>Løs Soduko</title>
</head>
<body>

<table border="1">
  <tr>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_0_0" maxlength="1" size="1" value="7"></td>
    <td><input type="text" id="celle_0_1" maxlength="1" size="1" value="8"></td>
    <td><input type="text" id="celle_0_2" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_0_3" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_0_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_0_5" maxlength="1" size="1" value="5"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_0_6" maxlength="1" size="1" value="9"></td>
    <td><input type="text" id="celle_0_7" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_0_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_1_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_1_1" maxlength="1" size="1" value="4"></td>
    <td><input type="text" id="celle_1_2" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_1_3" maxlength="1" size="1" value="2"></td>
    <td><input type="text" id="celle_1_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_1_5" maxlength="1" size="1" value="7"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_1_6" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_1_7" maxlength="1" size="1" value="3"></td>
    <td><input type="text" id="celle_1_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_2_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_2_1" maxlength="1" size="1" value="5"></td>
    <td><input type="text" id="celle_2_2" maxlength="1" size="1" value="9"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_2_3" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_2_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_2_5" maxlength="1" size="1" value="8"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_2_6" maxlength="1" size="1" value="2"></td>
    <td><input type="text" id="celle_2_7" maxlength="1" size="1" value="4"></td>
    <td><input type="text" id="celle_2_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
  </tr>
  <tr>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_3_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_3_1" maxlength="1" size="1" value="2"></td>
    <td><input type="text" id="celle_3_2" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_3_3" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_3_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_3_5" maxlength="1" size="1" value="9"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_3_6" maxlength="1" size="1" value="3"></td>
    <td><input type="text" id="celle_3_7" maxlength="1" size="1" value="1"></td>
    <td><input type="text" id="celle_3_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_4_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_4_1" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_4_2" maxlength="1" size="1" value="7"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_4_3" maxlength="1" size="1" value="3"></td>
    <td><input type="text" id="celle_4_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_4_5" maxlength="1" size="1" value="4"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_4_6" maxlength="1" size="1" value="6"></td>
    <td><input type="text" id="celle_4_7" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_4_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_5_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_5_1" maxlength="1" size="1" value="3"></td>
    <td><input type="text" id="celle_5_2" maxlength="1" size="1" value="4"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_5_3" maxlength="1" size="1" value="1"></td>
    <td><input type="text" id="celle_5_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_5_5" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_5_6" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_5_7" maxlength="1" size="1" value="9"></td>
    <td><input type="text" id="celle_5_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
  </tr>
  <tr>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_6_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_6_1" maxlength="1" size="1" value="6"></td>
    <td><input type="text" id="celle_6_2" maxlength="1" size="1" value="5"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_6_3" maxlength="1" size="1" value="7"></td>
    <td><input type="text" id="celle_6_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_6_5" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_6_6" maxlength="1" size="1" value="8"></td>
    <td><input type="text" id="celle_6_7" maxlength="1" size="1" value="2"></td>
    <td><input type="text" id="celle_6_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_7_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_7_1" maxlength="1" size="1" value="7"></td>
    <td><input type="text" id="celle_7_2" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_7_3" maxlength="1" size="1" value="9"></td>
    <td><input type="text" id="celle_7_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_7_5" maxlength="1" size="1" value="6"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_7_6" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_7_7" maxlength="1" size="1" value="5"></td>
    <td><input type="text" id="celle_7_8" maxlength="1" size="1" value="0"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td><input type="text" id="celle_8_0" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_8_1" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_8_2" maxlength="1" size="1" value="3"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_8_3" maxlength="1" size="1" value="5"></td>
    <td><input type="text" id="celle_8_4" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_8_5" maxlength="1" size="1" value="0"></td>
  </tr>
  <tr>
    <td><input type="text" id="celle_8_6" maxlength="1" size="1" value="0"></td>
    <td><input type="text" id="celle_8_7" maxlength="1" size="1" value="7"></td>
    <td><input type="text" id="celle_8_8" maxlength="1" size="1" value="6"></td>
  </tr>
</table></td>
  </tr>
</table>

<button onclick="solve();return false;">Løs Soduko</button>
<span id="minSpan"></span>

<table border="1">
  <tr>
    <td><table border="0">
  <tr>
    <td id="Tcelle_0_0"></td>
    <td id="Tcelle_0_1"></td>
    <td id="Tcelle_0_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_0_3"></td>
    <td id="Tcelle_0_4"></td>
    <td id="Tcelle_0_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_0_6"></td>
    <td id="Tcelle_0_7"></td>
    <td id="Tcelle_0_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_1_0"></td>
    <td id="Tcelle_1_1"></td>
    <td id="Tcelle_1_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_1_3"></td>
    <td id="Tcelle_1_4"></td>
    <td id="Tcelle_1_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_1_6"></td>
    <td id="Tcelle_1_7"></td>
    <td id="Tcelle_1_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_2_0"></td>
    <td id="Tcelle_2_1"></td>
    <td id="Tcelle_2_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_2_3"></td>
    <td id="Tcelle_2_4"></td>
    <td id="Tcelle_2_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_2_6"></td>
    <td id="Tcelle_2_7"></td>
    <td id="Tcelle_2_8"></td>
  </tr>
</table></td>
  </tr>
  <tr>
    <td><table border="0">
  <tr>
    <td id="Tcelle_3_0"></td>
    <td id="Tcelle_3_1"></td>
    <td id="Tcelle_3_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_3_3"></td>
    <td id="Tcelle_3_4"></td>
    <td id="Tcelle_3_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_3_6"></td>
    <td id="Tcelle_3_7"></td>
    <td id="Tcelle_3_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_4_0"></td>
    <td id="Tcelle_4_1"></td>
    <td id="Tcelle_4_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_4_3"></td>
    <td id="Tcelle_4_4"></td>
    <td id="Tcelle_4_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_4_6"></td>
    <td id="Tcelle_4_7"></td>
    <td id="Tcelle_4_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_5_0"></td>
    <td id="Tcelle_5_1"></td>
    <td id="Tcelle_5_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_5_3"></td>
    <td id="Tcelle_5_4"></td>
    <td id="Tcelle_5_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_5_6"></td>
    <td id="Tcelle_5_7"></td>
    <td id="Tcelle_5_8"></td>
  </tr>
</table></td>
  </tr>
  <tr>
    <td><table border="0">
  <tr>
    <td id="Tcelle_6_0"></td>
    <td id="Tcelle_6_1"></td>
    <td id="Tcelle_6_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_6_3"></td>
    <td id="Tcelle_6_4"></td>
    <td id="Tcelle_6_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_6_6"></td>
    <td id="Tcelle_6_7"></td>
    <td id="Tcelle_6_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_7_0"></td>
    <td id="Tcelle_7_1"></td>
    <td id="Tcelle_7_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_7_3"></td>
    <td id="Tcelle_7_4"></td>
    <td id="Tcelle_7_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_7_6"></td>
    <td id="Tcelle_7_7"></td>
    <td id="Tcelle_7_8"></td>
  </tr>
</table></td>
    <td><table border="0">
  <tr>
    <td id="Tcelle_8_0"></td>
    <td id="Tcelle_8_1"></td>
    <td id="Tcelle_8_2"></td>
  </tr>
  <tr>
    <td id="Tcelle_8_3"></td>
    <td id="Tcelle_8_4"></td>
    <td id="Tcelle_8_5"></td>
  </tr>
  <tr>
    <td id="Tcelle_8_6"></td>
    <td id="Tcelle_8_7"></td>
    <td id="Tcelle_8_8"></td>
  </tr>
</table></td>
  </tr>
</table>

</body>
</html>

Det virker ikke med den der står på forsiden af www.sudoku.com

Tjah, det tænkte jeg nok, den kigger jeg da lige på !-)

Sikke da en diskussion ;) Sudoku er dybt kedelig at løse med et program, men det kan jo gøres, og en gang skulle jeg lige se at
der var præcis een løsning til et eller andet sudoku-brædt. Så jeg skrev et Perl-script. Hvis jeg tager input:

780 005 900
040 207 030
059 008 240

020 009 310
007 304 600
034 100 090

065 700 820
070 906 050
003 500 076

udskriver det


782 435 961
641 297 538
359 618 247

526 879 314
917 354 682
834 162 795

165 743 829
478 926 153
293 581 476

Princippet er backtracking med rekursion, og det ikke specielt kønne, men vistnok fungerende script er her (lettere forbedret i forhold til min gamle original *g*):

#!/usr/bin/perl

$line="";
while (<>) {
  chomp;
  $line.=" $_";
}

while ($line=~/([0-9])/g) {
  $b[$i++]=int($1);
}

sub printb {
  my($i,$j);
  for ($i=0;$i<=8;$i++) {
    if ($i%3==0) { print "\n"; }
    for ($j=0;$j<=8;$j++) {
      if ($j%3==0) { print " "; }
      print $b[$i*9+$j];
    }
    print "\n";
  }
  print "\n";
}

sub okrow {
  my($row,$val) = @_;
  my($i);
  for ($i=0;$i<=8;$i++) {
    if ($b[$row*9+$i]==$val) {
      return 0;
    }
  }
  return 1;
}

sub okcol {
  my($col,$val) = @_;
  my($i);
  for ($i=0;$i<=8;$i++) {
    if ($b[$col+$i*9]==$val) {
      return 0;
    }
  }
  return 1;
}

sub oksquare {
  my($top,$left,$val) = @_;
  my($i,$j);
  for ($i=$left;$i<$left+3;$i++) {
    for ($j=$top;$j<$top+3;$j++) {
      if ($b[$i+$j*9]==$val) {
        return 0;
      }
    }
  }
  return 1;
}

sub tryit {
  my($n) = @_;
  my($i,$row,$col,$top,$left);
  if ($n>$#b) {
    print "Solution:\n";
    printb();
    print "\n";
} elsif ($b[$n]==0) {
    ($row,$col)=(int($n/9),$n%9);
    ($top,$left)=(3*int($row/3),3*int($col/3));
    for ($i=1;$i<=9;$i++) {
      if (okrow($row,$i) && okcol($col,$i) && oksquare($top,$left,$i)) {
      $b[$n]="$i";
      tryit($n+1);
      $b[$n]='-';
      }
     
    }
  } else {
    tryit($n+1);
  }
}

tryit(0);

Det indlæser en fil, og kan kaldes med fx

  perl soduko.pl soduko.txt

Det var da ikke den sidste version?? Ret

      $b[$n]="$i";
      tryit($n+1);
      $b[$n]='-';

til

      $b[$n]=$i;
      tryit($n+1);
      $b[$n]=0;

Hmm jeg har ikke Perl på min server :(

Perl kører på alt, så du kan få Perl til din maskine derhjemme, uanset hvad det er.
Og så kan du jo lave det om til PHP - ideen skulle være til at se.

Jeg kan da i hvertfald prøve... Men sidst jeg prøvede at smide noget Perl på den, virkede det ikke...

Jeg går i gang med at oversætte den i morgen aften, skal alligevel sidde og stene 3 timer i toget :S

Skulle du køre Windows, burde Perl fra activestate.com være problemløst at installere.

Men bemærk at det kan tage tid. Den linux-server mit kører på nu er vist omkring 450 MHz.
Simple baner koster måske 40 ms. Mere komplicerede kan tage over 1 sekund. Kører du på et webhotel, kan du godt regne med at de kigger efter scripts, der belaster serveren. Der kunne være raison i at lave det i JavaScript, hvor det så er brugerens maskine, der belastes.

Har lavet et site med en soduko-solver (og dynamisk soduko-opgave generator), men i java. Kører ganske hurtigt på min egen maskine, så java er også en mulighed. Check det ud:

Frederik's Soduko:
http://soduko.netgubbi.dk
(kræver java plugin)

-> bertelbrander: Sværheden af sodukoer varierer fra indlysende til uigennemskueligt. Derfor kan den samme metode ikke bruges til at løse alle sodukoer. En skudsikker soduko-solver bør rumme alle de løsningsteknikker, der er opregnet på nedenstående side, selv om den kun yderst sjældent (ved de rigtig svære opgaver) vil få brug for at benytte dem alle sammen. Solveren på mit eget site rummer kun de første par teknikker, og kan derfor kun løse opgaver op til en vis sværhedsgrad. Resten af teknikkerne kan selvfølgelig også omsættes til algoritmer, men mange af dem er ret beregningstunge, så indtil videre har jeg ikke taget mig tid til det. Men vil gerne høre fra nogen der har ;-)

Sodukoløsnings-teknikker:
http://www.simes.clara.co.uk/programs/sudokutechniques.htm

Frederik21, en random brute force metode som min vil vel altid kunne finde løsningen? De vanskelige opgaver vil dog tage mere tid at løse.

Mere generelt: enhver rigtig metode til at løse sudoko kan vel løse alle sudoko?

Ja, random brute force kan løse alle sudokuer. Men en ægte sudoku skal kunne løses vha logik alene, altså uden tilfældige gæt, og derfor vil der altid være en "sikker" kandidat et sted på brættet, hvis ellers man kender de rette logiske regler for udelukkelse af kandidater. Med den viden synes jeg det giver mere mening at implementere de logiske udelukkelsesregler end en brute-force løsning.

Desuden er det langt nemmere at konstruere en sudoku som er beviseligt løsbar uden gætteri, hvis man har en solver der kun anvender de logiske regler. Så kan man generere et fyldt sudoku-bræt (en gyldig løsning) og fjerne tal fra felterne, der hvor solveren beslutter at der logisk set ikke kan stå andet (ligesom et menneske vil kunne slutte), indtil der ikke kan fjernes flere. Så har man en sudoku-opgave.

Hvis du omskriver dit program (ovenstående) til at indgå i en sudoku-generator vil du se at de genererede sudokuer allesammen får den samme sværhedsgrad (let), fordi kun de simpleste udelukkelsesregler anvendes (tjek på kolonner, rækker og blokke). Implementerer du de mere sofistikerede kandidat-udelukkelsesregler, vil du kunne få sudokuer der også er sværere at løse.

Det er noget værre noget jeg har fået rodet med ud i...

Jeg har prøvet på at oversætte de scripts ^^ til PHP, men kan ikke få det til at virke... Bagefter har jeg prøvet på at lave et i PHP/MySQL der gemmer tallene fra 1-9 i en tabel som hedder "muligheder" og de forud fastsatte tal i en tabel der hedder løsning, så tjekker det med de simple regler, og fjerner fra tabellen "muligheder" hvis de ikke kan lade sig gøre, og hvis der så kun er 1 mulighed tilbage, så sætter den ind i "løsning" og så starter den forfra, den kører indtil alt er udfyldt, men jeg blev nød til at sætte en max 500 gange på, for ellers blev den ved med at køre i ring ved nogle af sodukoerne...

Jeg fik lige lyst til at lave en udgave i java script:
http://erikjacobsen.info/sudoku/
Det er gemen backtracking - intet fancy ;)

Hej frederik21 og alle andre... og selvfølgelig hej lullalej

Matematik er tydeligvis ikke en gren frederik21 og nogle andre i tråden er bekendt med som et effektivt redskab. Læste også en tråd på et andet site hvor folk foreslog neurale netværk...
Sudoku er en special tilfælde af det såkaldte Latin Square. DET ER MULIGT AT GÅ MATEMATISK TIL VÆRKS...

Man vil heller ikke bruge diverse fancy metoder til faktorisering af (evt. store) tal... Man vil i stedet angribe det matematisk og finde effektive metoder! Jeg vil også gerne diskutere dette med folk der evt. vil hævde at faktorisering af tal ikke kan foregå effektivt i stedet for at være baseret på metoder der efterligner der menneskelige måde at gøre dette på...

IMM ved DTU, har lavet en ganske fin lille side der netop beskriver dette fra matematisk synspunkt. Og ganske som de beskriver er løsningsmodellen ikke enestående genial idet mange andre ville kunne finde frem til samme metode.

http://www.student.dtu.dk/~s011378/sudoku

Til dig lullalej.. jeg kan ikke programmere i scriptsprog så derfor kan jeg ikke hjælpe dig der, men det er der helt sikkert andre herinde der kan...

Hej mafics

Spændende og velskrevet artikel du henviser til - tak for det. Jeg bliver nødt til at sige at jeg udmærket ved, at matematik er et yderst effektivt redskab - jeg har bare ikke selv studeret det :) Selv om løsningmodellen i artiklen er skarp, er det nok ikke tilfældigt at den stopper hvor den gør - ved spørgsmålet om konstruktion af sudoku-opgaver. Hvis det tager den præsenterede algoritme 1 sekund at løse en opgave, hvor længe vil det så tage den at konstruere et fyldt bræt, plus at regne sig tilbage til den medfølgende opgave? Opgaven skal være menneskeligt løsbar, det vil sige at der på et givent tidspunkt undervejs i løsningen skal være mindst et tomt felt på brættet, hvor alle andre end et tal med sikkerhed kan udelukkes som kandidater. Dette kan selvfølgelig tilføjes algoritmen som en matematisk formuleret "begrænsing", men vil opgave-konstruktions-algoritmen så ikke komme til at iterere en algoritme der svarer til den præsenterede (blot med denne ekstra begrænsning) for hvert skridt af opgave-konstruktionen, altså for hvert felt i løsningen, der slettes for at generere den løsbare opgave? Og hvor mange sekunder kommer det til at tage? Antal tomme felter * 1 sek?

Desuden skal man kunne angive opgavens sværhedsgrad, som jo er et udtryk for hvilke  løsningsmetoder et menneske skal bruge for at finde løsningen (naked pairs, subsets, X-wing, swordfish etc). Hvis programmet der genererer opgaven ikke har noget begreb om disse metoder, hvordan skal den så kunne angive en passende sværhedsgrad?

Det er af disse grunde, at jeg har baseret min kombinerede solver og opgave-generator på de konkrete, logiske løsnings-metoder. Lige nu genererer den nye, unikke opgaver på ca 1 sekund, men det er så heller ikke i scriptsprog. Og nogle af de mere avancerede løsningsmetoder er særdeles beregningstunge, så vi må vel se hvordan de påvirker hastigheden, når jeg får dem implementeret ;)

Men indtil videre vil jeg påstå, at hvor solving er en matematisk udfordring, hvor metoden er usynlig/ligegyldig for brugeren, så er opgave-konstruktionen nødt til at forholde sig til den begrænsning der hedder at opgaverne skal være logisk løsbare, og at der skal være en bevidsthed om "hvilken" logik der anvendes (for at kunne vurdere sværhedsgraden af opgaven).

Hvis det kan lade sig gøre vha. matematisk operatonsanalyse, skal jeg være den første til at klappe i mine hænder :)

Hej ericjacobsen!
Jeg synes det er en smadderfin kode du har lavet.
http://erikjacobsen.info/sudoku/
Den vil jeg gerne stjæle. Ved ikke om det er tilladt, men der sker tilsyneladende ikke mere her.
Jeg opretter lige et spørgsmål.

Jo, det er så simpelt så jeg ikke synes det er rimeligt at holde for mig selv ;)
Så det er fri software, men det må ikke bruges til fremstilling af atombomber og tobak - strengt forbudt!

>ericjacobsen, det SKAL BRUGES til pibetobak, såh, men du bedes oprette et svar på det spørgsmål jeg har stillet om dette emne et eller andet sted. Der er jo 200 points som tak fordi jeg har hugget koden!

>ericjacobsen: det er vist her: http://exp.dk/spm/667709. Lav lige et svar, pleace!

Så må du ikke bruge det, skam.
Men jeg samler slet ikke på point, tak.

>ericjacobsen, Ahhhhhh!!! Nu husker jeg det. Jeg har før lukreret på dig - ganske gratis.
Jeg synes, du skal begynde at samle på poins! Jeg synes det meget!!!!
Jeg har oprettet et spørgsmål om et program, der kan generere sudokuer..
Du skulle vel ikke ligge inde med noget kode til sådan noget?

Lige et link mere på falderebet:
http://www.246.dk/sudoku.html

Nå alle sammen, tak for hjælpen, jeg har egentlig opgivet det, men kan være jeg prøver igen en anden gang, og nu ved jeg da hvordan det skal laves (måske)...

Hvis i lige opretter nogle svar (erikjacobsen, roenving og bertelbrander) så fordeler jeg lige de 200 point mellem jer :)

Jeg samler ikke på point.

Men jeg samler slet ikke på point, tak.

Okay, men mange tak for hjælpen alligevel :)

Faldt lige over denne tråd. Jeg har lige skrevet et Perl-script der løser en sudoku med logik, altså uden backtracking/rekursion. Jeg ved ikke om der findes sudokuer der kræver det, men i givet fald kan scriptet modificeres til at bruge rekursion.

Scriptet er en  implementation af den manuelle løsningsmetode jeg har fundet frem til, og som er lidt kedelig at udføre selv:

• Notér for hvert tomt felt alle de mulige værdier det kan have
• For hvert felt med kun en mulig værdi: indskriv værdien og eliminer den fra mulighederne i de felter den er i konflikt med. Herved kan der opstå nye felter med kun en mulighed. Gentag indtil der ikke er flere.
• Hvis sudokuen ikke er løst: Søg felter der har en mulig værdi som ingen andre felter i samme 3x3-gruppe har. Indskriv denne værdi og eliminer den blandt konfliktende muligheder ligesom ovenfor. Gentag indtil denne metode ikke finder flere entydige felter.
• Gentag ovenstående to metoder indtil de ikke finder flere løsninger.
•Sudokuen er nu sandsynligvis løst. Hvis ikke, skal der bruges backtracking.

Hvor mange sudokuer har du prøvet din løsning på?  Er der nogen, hvor den ikke kommer hele vejen?

Jeg mener at have læst, at der findes sudoku-purister, der ikke mener at en sodoku er orn'li' hvis den ikke kan løses med logik, men kræver brutal backtracking.

Efter 2005, som spørgsmålet her er stillet i, har jeg fået for vane at bruge backtracking-sudoku-løsning som mit første programmeringseksempel når jeg skal lære lidt om et nyt programmeringssprog (efter "Hello world").

Sjov tur ned af memory lane. Jeg har ikke været logget ind på eksperten i mange år. Jeg har heller ikke løst sudoku i mange år.

Men jeg programmerer stadig C++

Jeg har kun prøvet den på tre-fire stykker. Den ene var jeg manuelt gået i stå med og troede at backtracking var nødvendig, men scriptet løste den uden, så jeg må have overset noget. Til gengæld har jeg prøvet den på en ny efter jeg skrev kommentaren, og med den når scriptet ikke i mål, så nu forsøger jeg at få styr på hvordan man jonglerer korrekt med referencer til arrays af arrays, så jeg kan gøre den rekursiv. Jeg programmerer ikke til daglig, så opgaver af denne kompleksitet kræver lidt rustafbankning.

Det vil stadig ikke være brute-force, da den kun skal arbejde rekursivt med de felter der endte med at være 'kampvalg' til, og igen med samme logiske fremgangsmåde.