µLua DS - Forum officiel | Official forum Index du Forum

µLua DS - Forum officiel | Official forum
Le bon endroit pour en savoir plus sur MicroLua et pour parler de vos projets ! | The right place to learn more about MicroLua and talk about your projects !

 FAQFAQ   RechercherRechercher   MembresMembres   GroupesGroupes   S’enregistrerS’enregistrer   ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

Solveur de sudoku

 
Poster un nouveau sujet   Répondre au sujet    µLua DS - Forum officiel | Official forum Index du Forum -> Section française -> Coin du dév'
Sujet précédent :: Sujet suivant  
Auteur Message
ShiiFu


Hors ligne

Inscrit le: 05 Juil 2012
Messages: 51

MessagePosté le: Jeu 12 Juil 2012 - 21:14    Sujet du message: Solveur de sudoku Répondre en citant

Salut à tous,

je vous présente mon projet qui consiste à faire un solveur de Sudoku.

En effet, je voulais faire un projet qui puisse mettre à l'épreuve mes connaissances en µlua et que se sois un défi algorithmique. J'ai trouvé, un solveur de sudoku! Very Happy
J'ai commencé à coder la base, l'aspect graphique. Le voici en image :


La grille de l'écran du haut est en rouge si non résolu et si le programme a résolu le sudoku elle sera verte.

Pour le moment, je m'attaque à la résolution des singleton pour pouvoir résoudre les grille très facile. Ensuite, je m'attaquerai bien sûr aux grilles plus difficiles.

Dés que le programme sera fonctionnel pour certains sudoku je mettrai le code.


Revenir en haut
Publicité






MessagePosté le: Jeu 12 Juil 2012 - 21:14    Sujet du message: Publicité

PublicitéSupprimer les publicités ?
Revenir en haut
thomh@ck


Hors ligne

Inscrit le: 01 Aoû 2011
Messages: 360
Localisation: Notepad++

MessagePosté le: Jeu 12 Juil 2012 - 21:55    Sujet du message: Solveur de sudoku Répondre en citant

C'est un super projet  Okay
j'avais moi même essayer d'en réaliser un mais l'algo m'avais de suite paru trop élaborer pour mes connaissance et j'ai vite laisser tomber ...
en tout cas je te dis bon courage et aussi bonne chance ;-)


EDIT: ça me rappel un tuto du sdz que j'avais essayer de suivre pour le sujet http://www.siteduzero.com/tutoriel-3-360004-le-backtracking-par-l-exemple-resoudre-un-sudoku.html
c'est en C++ mais ça explique une technique tu pourrai peut-être t'en inspirer ^^
_________________
Vous aimez l'Origami ?


Revenir en haut
Visiter le site web du posteur
Fantasix
Modérateur

Hors ligne

Inscrit le: 26 Avr 2010
Messages: 1 317
Localisation: SCREEN_UP, en -1, -1

MessagePosté le: Jeu 12 Juil 2012 - 22:52    Sujet du message: Solveur de sudoku Répondre en citant

Bonne chance à toi !

Fait gaffe quand même, on aperçoit le chiffre zéro plusieurs fois dans la grille du haut ^.^

Fanta'
_________________


BMA News :

Création du Homebrew Storage en cours ...


Revenir en haut
Visiter le site web du posteur
thermo_nono
Modérateur

Hors ligne

Inscrit le: 31 Déc 2008
Messages: 2 415
Localisation: La Géhenne

MessagePosté le: Ven 13 Juil 2012 - 00:26    Sujet du message: Solveur de sudoku Répondre en citant

Excellent projet !
Okay
_________________
“Qui reçoit une idée de moi reçoit de la connaissance sans diminuer la mienne, comme celui qui allume sa chandelle à la mienne reçoit la lumière sans me plonger dans l’obscurité.” - Thomas Jefferson


Revenir en haut
Visiter le site web du posteur MSN
ShiiFu


Hors ligne

Inscrit le: 05 Juil 2012
Messages: 51

MessagePosté le: Ven 13 Juil 2012 - 11:45    Sujet du message: Solveur de sudoku Répondre en citant

thomh@ck a écrit:
C'est un super projet  Okay
j'avais moi même essayer d'en réaliser un mais l'algo m'avais de suite paru trop élaborer pour mes connaissance et j'ai vite laisser tomber ...
en tout cas je te dis bon courage et aussi bonne chance ;-)


EDIT: ça me rappel un tuto du sdz que j'avais essayer de suivre pour le sujet http://www.siteduzero.com/tutoriel-3-360004-le-backtracking-par-l-exemple-resoudre-un-sudoku.html
c'est en C++ mais ça explique une technique tu pourrai peut-être t'en inspirer ^^

Et bien, pour ma part, je trouve aussi l'algo très difficile, mais il faut bien se lancer des défi. Et pour le tuto je l'ai lu, mais il faut que je le relise pour bien comprendre Mr. Green

Fantasix a écrit:


Bonne chance à toi !

Fait gaffe quand même, on aperçoit le chiffre zéro plusieurs fois dans la grille du haut ^.^

Fanta'

Quand le chiffre est égale à zéro cela veut dire que la case est vide. En bas on ne les vois pas car je n'affiche pas les 0.

Mon code n'est vraiment pas propre mais il résout les singleton sur ligne. Je lui fait une manucure et je le post. Okay

Merci pour les encouragements.


Revenir en haut
ShiiFu


Hors ligne

Inscrit le: 05 Juil 2012
Messages: 51

MessagePosté le: Jeu 16 Aoû 2012 - 20:15    Sujet du message: Solveur de sudoku Répondre en citant

Après un long moment de silence, voici la V1-dev :

Elle est fait à l'arrache, très brouillonne, il y a beaucoup d'améliorations à y apporter, le solveur est loin d'être terminer, mais il faut bien un avant goût.

Je l'ai programmer entièrement depuis la DS, l'indentation y est parfois délaissé de ce fait, mais j'ai surtout séparer le projet dans pas mal de fichier pour retrouvé les fonction plus aisément.

Voici les fichier dans l'ordre :

 
Code:
 -- debut

dofile("debut.lua")

-- index
while not Keys.held.Start do
        Controls.read()
      
   if Keys.newPress.Up then
      info.y = info.y - 1
      if info.y == 0 then
         info.y = 9
      end
   elseif Keys.newPress.Down then
      info.y = info.y + 1
      if info.y == 10 then
         info.y = 1
      end
   elseif Keys.newPress.Left then
      info.x = info.x - 1
      if info.x == 0 then
         info.x = 9
      end
   elseif Keys.newPress.Right then
      info.x = info.x + 1
      if info.x == 10 then
         info.x = 1
      end
   end
   infocase(info.x, info.y)
   
   if Keys.newPress.A then
      resolveA()
   elseif Keys.newPress.B then
      resolveB()
   elseif Keys.newPress.Select then
      resolvetotal()
   elseif Keys.newPress.L then
      editL(info.x, info.y)
   elseif Keys.newPress.R then
      editR(info.x, info.y)
   end
   
   
   if not resolu then
      resolu = verify()
   else
      screen.print(1, 0, 160, nbuk.." cases trouvees en "..t.." secondes")
      screen.print(1, 0, 172, u.." milisecondes par case ")
   end

   affiche()
   render()
end

-- fin

dofile("fin.lua")



 
Code:
 -- debut

pausetime = Timer.new()
timeresolve = Timer.new()   
 
-- SUDOKU

dofile("initgrid.lua")

--info = {{}, {}, {}}
single = {{}}
nbuk = 0
for i = 1, 9 do
   for j = 1, 9 do
      if gridwork[j][i] == 0 then
         nbuk = nbuk + 1
      end
   end
end
resolu = false
info = {x = 1, y = 1}

-- Couleur
blanc = Color.new(31, 31, 31)
bleu = Color.new(0, 0, 31)
rouge = Color.new(31, 0, 0)
vert = Color.new(0, 31, 0)
jaune = Color.new(30, 26, 0)

-- function

dofile("function.lua")





 
Code:
 bleu = Color.new(0, 0, 31)

-- menu

array = {}
array[1] = "sudoku edit"
array[2] = "example"
total = 2
choix = 2

--[[while not Keys.newPress.A do
      Controls.read()

   if Keys.newPress.Up then
      choix = choix - 1
   elseif Keys.newPress.Down then
      choix = choix + 1
   end

   screen.print(1, 0, 0, "Menu : ")
   for i = 1, total do
      if choix == i then
         screen.print(1, 0, 12 * i, array[i], bleu)
      else
         screen.print(1, 0, 12 * i, array[i])
      end
   end


   render()
end--]]


if choix == 2 then

array[1] = "debutant"
array[2] = "specialiste 1"
array[3] = "specialuste 2"
array[4] = "exper"
total = 4
--choix = 2

while not Keys.newPress.B do
      Controls.read()

   if Keys.newPress.Up then
      choix = choix - 1
   elseif Keys.newPress.Down then
      choix = choix + 1
   end

   screen.print(1, 0, 0, "Menu : ")
   for i = 1, total do
      if choix == i then
         screen.print(1, 0, 12 * i, array[i], bleu)
      else
         screen.print(1, 0, 12 * i, array[i])
      end
   end


   render()
end


if choix == 1 then

grid = {{0, 0, 0, 0, 4, 0, 8, 9, 0},
       {2, 4, 0, 0, 9, 0, 7, 0, 0},
       {8, 7, 0, 1, 0, 0, 0, 0, 0},
       {0, 9, 1, 2, 0, 4, 3, 0, 0},
       {0, 3, 0, 0, 0, 7, 0, 0, 6},
       {4, 0, 8, 9, 5, 0, 0, 1, 7},
       {1, 8, 4, 0, 0, 0, 5, 0, 0},
       {0, 2, 0, 0, 0, 1, 0, 0, 3},
       {3, 0, 0, 4, 0, 6, 0, 8, 9}}
 
gridwork = {{0, 0, 0, 0, 4, 0, 8, 9, 0},
       {2, 4, 0, 0, 9, 0, 7, 0, 0},
       {8, 7, 0, 1, 0, 0, 0, 0, 0},
       {0, 9, 1, 2, 0, 4, 3, 0, 0},
       {0, 3, 0, 0, 0, 7, 0, 0, 6},
       {4, 0, 8, 9, 5, 0, 0, 1, 7},
       {1, 8, 4, 0, 0, 0, 5, 0, 0},
       {0, 2, 0, 0, 0, 1, 0, 0, 3},
       {3, 0, 0, 4, 0, 6, 0, 8, 9}}

elseif choix == 2 then

grid = {{5, 0, 4, 0, 0, 0, 0, 0, 0},
       {0, 7, 0, 4, 5, 0, 0, 0, 0},
       {0, 0, 3, 0, 0, 1, 0, 6, 0},
       {6, 0, 1, 0, 0, 0, 0, 0, 5},
       {0, 0, 0, 0, 0, 3, 0, 2, 0},
       {0, 0, 0, 0, 8, 0, 0, 0, 1},
       {2, 8, 0, 5, 0, 9, 0, 0, 0},
       {0, 4, 0, 0, 1, 0, 3, 0, 0},
       {0, 0, 6, 0, 0, 4, 0, 0, 0}}
 
gridwork = {{5, 0, 4, 0, 0, 0, 0, 0, 0},
       {0, 7, 0, 4, 5, 0, 0, 0, 0},
       {0, 0, 3, 0, 0, 1, 0, 6, 0},
       {6, 0, 1, 0, 0, 0, 0, 0, 5},
       {0, 0, 0, 0, 0, 3, 0, 2, 0},
       {0, 0, 0, 0, 8, 0, 0, 0, 1},
       {2, 8, 0, 5, 0, 9, 0, 0, 0},
       {0, 4, 0, 0, 1, 0, 3, 0, 0},
       {0, 0, 6, 0, 0, 4, 0, 0, 0}}

elseif choix == 3 then

grid = {{9, 0, 0, 0, 0, 0, 0, 0, 0},
       {5, 0, 0, 0, 3, 0, 0, 0, 2},
       {3, 0, 0, 5, 0, 0, 7, 0, 6},
       {0, 0, 8, 0, 0, 0, 0, 0, 0},
       {0, 9, 0, 0, 0, 6, 5, 4, 0},
       {1, 4, 0, 7, 0, 0, 0, 0, 0},
       {0, 5, 0, 4, 0, 2, 0, 7, 9},
       {0, 0, 0, 0, 0, 0, 0, 0, 5},
       {0, 0, 3, 0, 7, 0, 1, 0, 0}}
 
gridwork = {{9, 0, 0, 0, 0, 0, 0, 0, 0},
         {5, 0, 0, 0, 3, 0, 0, 0, 2},
         {3, 0, 0, 5, 0, 0, 7, 0, 6},
         {0, 0, 8, 0, 0, 0, 0, 0, 0},
         {0, 9, 0, 0, 0, 6, 5, 4, 0},
         {1, 4, 0, 7, 0, 0, 0, 0, 0},
         {0, 5, 0, 4, 0, 2, 0, 7, 9},
         {0, 0, 0, 0, 0, 0, 0, 0, 5},
         {0, 0, 3, 0, 7, 0, 1, 0, 0}}

else

grid = {{1, 6, 8, 0, 0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, 6, 0},
       {5, 0, 7, 0, 0, 0, 0, 0, 0},
       {0, 0, 6, 2, 0, 7, 1, 0, 0},
       {4, 0, 1, 0, 3, 0, 0, 8, 0},
       {0, 0, 0, 0, 0, 4, 0, 0, 7},
       {0, 8, 0, 1, 4, 0, 0, 0, 0},
       {0, 2, 0, 9, 0, 6, 5, 0, 0},
       {0, 0, 4, 3, 0, 0, 0, 0, 0}}
 
gridwork = {{1, 6, 8, 0, 0, 0, 0, 0, 0},
         {0, 0, 0, 0, 0, 0, 0, 6, 0},
         {5, 0, 7, 0, 0, 0, 0, 0, 0},
         {0, 0, 6, 2, 0, 7, 1, 0, 0},
         {4, 0, 1, 0, 3, 0, 0, 8, 0},
         {0, 0, 0, 0, 0, 4, 0, 0, 7},
         {0, 8, 0, 1, 4, 0, 0, 0, 0},
         {0, 2, 0, 9, 0, 6, 5, 0, 0},
         {0, 0, 4, 3, 0, 0, 0, 0, 0}}

end

else

--editor here   

end

bleu = nil
array = nil
total = nil
choix = nil



 
Code:
 -- function

dofile("verify.lua")

dofile("info.lua")

dofile("resolve.lua")

function unepause(temps)
   pausetime:start()   
   quitter = false   
   while not quitter do
      Controls.read()
      if pausetime:time() > temps then
         pausetime:reset()
         quitter = true
      end
   end   
end

function affiche()
    
   screen.print(1, 0, 184, "FPS: "..NB_FPS)
   --screen.print(1, 0, 172, "test: "..grid[2][3])
   for i = 1, 9 do
      for j = 1, 9 do
         if gridwork[j][i] > 0 then
            screen.print(1, -10+16*i, -10+16*j, gridwork[j][i])
         end
      end
   end
   for l = 0, 1 do
      for i = 1, 9 do
        for j = 1, 9 do
          if grid[j][i] > 0 then
            screen.print(l, -10+16*i, -10+16*j, grid[j][i], vert)
          end
        end
      end
   end
   local temp
   for j = 0, 1 do
       -- Affichage des lignes verticales
      for i = 0, 9 do
         temp = i * 16 + 2
         if i == 0 or i == 3 or i == 6 or i == 9 then
            if j == 1 then
               if resolu then
                  screen.drawLine(j, temp, 2, temp, 146, vert)
               else
                  screen.drawLine(j, temp, 2, temp, 146, rouge)
               end
            else   
               screen.drawLine(j, temp, 2, temp, 146, bleu)
            end
         else
            screen.drawLine(j, temp, 2, temp, 146, blanc)
         end
      end
       -- Affichage des lignes horizontales
      for i = 0, 9 do
         temp = i * 16 + 2
         if i == 0 or i == 3 or i == 6 or i == 9 then
            if j == 1 then
               if resolu then
                  screen.drawLine(j, 2, temp, 146, temp, vert)
               else
                  screen.drawLine(j, 2, temp, 146, temp, rouge)
               end
            else
               screen.drawLine(j, 2, temp, 146, temp, bleu)
            end
         else
            screen.drawLine(j, 2, temp, 146, temp, blanc)
         end
      end
   end
   --screen.print(1, 0, 148, "apres")
   screen.print(0, 0, 148, "avant")
   
end

function editL(x, y)
   if gridwork[y][x] == 0 then
      gridwork[y][x] = 9
   else
      gridwork[y][x] = gridwork[y][x] - 1
   end
end

function editR(x, y)
   if gridwork[y][x] == 9 then
      gridwork[y][x] = 0
   else
      gridwork[y][x] = gridwork[y][x] + 1
   end
end





 
Code:
 function verifyligne()
   resultat = 0
   for i = 1, 9 do
      resultat = resultat + gridwork[1][i]
   end
   if resultat == 45 then
      resultat = 0
      for i = 1, 9 do
         resultat = resultat + gridwork[2][i]
      end
      if resultat == 45 then
         resultat = 0
         for i = 1, 9 do
            resultat = resultat + gridwork[3][i]
         end
         if resultat == 45 then
            resultat = 0
            for i = 1, 9 do
               resultat = resultat + gridwork[4][i]
            end
            if resultat == 45 then
               resultat = 0
               for i = 1, 9 do
                  resultat = resultat + gridwork[5][i]
               end
               if resultat == 45 then
                  resultat = 0
                  for i = 1, 9 do
                     resultat = resultat + gridwork[6][i]
                  end
                  if resultat == 45 then
                     resultat = 0
                     for i = 1, 9 do
                        resultat = resultat + gridwork[7][i]
                     end
                     if resultat == 45 then
                        resultat = 0
                        for i = 1, 9 do
                           resultat = resultat + gridwork[8][i]
                        end
                        if resultat == 45 then
                           resultat = 0
                           for i = 1, 9 do
                              resultat = resultat + gridwork[9][i]
                           end
                           if resultat == 45 then
                              return true
                           else
                              return false
                           end
                        else
                           return false
                        end
                     else
                        return false
                     end
                  else
                     return false
                  end
               else
                  return false
               end
            else
               return false
            end
         else
            return false
         end
      else
         return false
      end
   else
      return false
   end
end

function verifycolonne()
   resultat = 0
   for i = 1, 9 do
      resultat = resultat + gridwork[i][1]
   end
   if resultat == 45 then
      resultat = 0
      for i = 1, 9 do
         resultat = resultat + gridwork[i][2]
      end
      if resultat == 45 then
         resultat = 0
         for i = 1, 9 do
            resultat = resultat + gridwork[i][3]
         end
         if resultat == 45 then
            resultat = 0
            for i = 1, 9 do
               resultat = resultat + gridwork[i][4]
            end
            if resultat == 45 then
               resultat = 0
               for i = 1, 9 do
                  resultat = resultat + gridwork[i][5]
               end
               if resultat == 45 then
                  resultat = 0
                  for i = 1, 9 do
                     resultat = resultat + gridwork[i][6]
                  end
                  if resultat == 45 then
                     resultat = 0
                     for i = 1, 9 do
                        resultat = resultat + gridwork[i][7]
                     end
                     if resultat == 45 then
                        resultat = 0
                        for i = 1, 9 do
                           resultat = resultat + gridwork[i][8]
                        end
                        if resultat == 45 then
                           resultat = 0
                           for i = 1, 9 do
                              resultat = resultat + gridwork[i][9]
                           end
                           if resultat == 45 then
                              return true
                           else
                              return false
                           end
                        else
                           return false
                        end
                     else
                        return false
                     end
                  else
                     return false
                  end
               else
                  return false
               end
            else
               return false
            end
         else
            return false
         end
      else
         return false
      end
   else
      return false
   end
end

function verifycarre(ci, cj)
   resultat = 0
   for i = ci, ci + 2 do
      for j = cj, cj + 2 do
         resultat = resultat + gridwork[i][j]
         --screen.print(1, 0, 160, i..", "..j)
         --affiche()
         --unepause(2000)
      end
   end
   --screen.print(1, 0, 160, ci..", "..cj)
   --affiche()
   --unepause(2000)
   if resultat == 45 then
      if ci == 1 then
         if cj == 1 then
            if not verifycarre(1, 4) then
               return false
            end
         elseif cj == 4 then
            if not verifycarre(1, 7) then
               return false
            end
         elseif cj == 7 then
            if not verifycarre(4, 1) then
               return false
            end
         end
      elseif ci == 4 then
         if cj == 1 then
            if not verifycarre(4, 4) then
               return false
            end
         elseif cj == 4 then
            if not verifycarre(4, 7) then
               return false
            end
         elseif cj == 7 then
            if not verifycarre(7, 1) then
               return false
            end
         end
      elseif ci == 7 then
         if cj == 1 then
            if not verifycarre(7, 4) then
               return false
            end
         elseif cj == 4 then
            if not verifycarre(7, 7) then
               return false
            end
         elseif cj == 7 then
            --screen.print(1, 0, 160, "true?")
            --affiche()
            --unepause(2000)
            return true
         end
      end
      return true
   else
      return false
   end
end

function verify()
   local line = verifyligne()
   if line then
      local colonne = verifycolonne()
      if colonne then
         carre = verifycarre(1, 1)
         --carre = true
         if carre then
            return true
         else
            return false
         end
      else
         return false
      end
   else
      return false
   end
end



 
Code:
 -- info

function surligne(x, y)

   local tx = x - 1
   local ty = y - 1
   screen.drawFillRect(1, 3 + 16 * tx, 2 + 16 * ty, 3 + 16 * x, 2 + 16 * y, jaune)

end

function infocase(x, y)

   screen.print(1, 6 + 9 * 16, 3, "INFO : ")
   
   local case = 0
   local p = 1
   local q = 1
   if y <= 3 then
      if x <= 3 then
         case = 1
      elseif x >= 7 then
         case = 3
         p = 7
      else
         case = 2
         p = 4
      end
   elseif y >= 7 then
      if x <= 3 then
         case = 7
         q = 7
      elseif x >= 7 then
         case = 9
         p = 7
         q = 7
      else
         case = 8
         p = 4
         q = 7
      end
   else
      if x <= 3 then
         case = 4
         q = 4
      elseif x >= 7 then
         case = 6
         p = 7
         q = 4
      else
         case = 5
         p = 4
         q = 4
      end
   end
   screen.print(1, 0, 148, x..", "..y.." / case "..case)
   
   if gridwork[y][x] == 0 then
      screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], rouge)
      screen.print(1, 6 + 9 * 16, 30, "valeur possible: ", blanc)
      --code de recherche
      
      local test = {{}, {}}
      local possibilite = 0
      for l = 1, 9 do
         test[l] = false
         for i = 1, 9 do
            if l == gridwork[y][i] then
               test[l] = true
            end
         end
         for i = 1, 9 do
            if l == gridwork[i][x] then
               test[l] = true
            end
         end
         
         for i = q, q + 2 do
            for j = p, p + 2 do
               if l == gridwork[i][j] then
                  test[l] = true
               end
            end
         end
         
         if not test[l] then
            possibilite = possibilite + 1
            screen.print(1, 6 + 9 * 16, 30 + 12 * possibilite, l, blanc)
         end
      end
            
      --fin de code de recherche
   else
      screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], vert)
   end
   
   surligne(x, y)

end





 
Code:
 function resolveA2(x, y)

   screen.print(1, 6 + 9 * 16, 3, "INFO : ")
   
   
   local lastpossibi = 0
   local case = 0
   local p = 1
   local q = 1
   if y <= 3 then
      if x <= 3 then
         case = 1
      elseif x >= 7 then
         case = 3
         p = 7
      else
         case = 2
         p = 4
      end
   elseif y >= 7 then
      if x <= 3 then
         case = 7
         q = 7
      elseif x >= 7 then
         case = 9
         p = 7
         q = 7
      else
         case = 8
         p = 4
         q = 7
      end
   else
      if x <= 3 then
         case = 4
         q = 4
      elseif x >= 7 then
         case = 6
         p = 7
         q = 4
      else
         case = 5
         p = 4
         q = 4
      end
   end
   
   if gridwork[y][x] == 0 then
      screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], rouge)
      screen.print(1, 6 + 9 * 16, 30, "valeur possible: ", blanc)
      --code de recherche
      
      -- 1
      local test = {{}, {}}
      local possibilite = 0
      for l = 1, 9 do
         test[l] = false
         for i = 1, 9 do
            if l == gridwork[y][i] then
               test[l] = true
            end
         end
         for i = 1, 9 do
            if l == gridwork[i][x] then
               test[l] = true
            end
         end
         
         for i = q, q + 2 do
            for j = p, p + 2 do
               if l == gridwork[i][j] then
                  test[l] = true
               end
            end
         end
         
         if not test[l] then
            possibilite = possibilite + 1
            lastpossibi = l
            screen.print(1, 6 + 9 * 16, 30 + 12 * possibilite, l, blanc)
         end
      end
      
      if possibilite == 1 then
         gridwork[y][x] = lastpossibi
      end
      
      --fin de code de recherche
   else
      screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], vert)
   end
   
   surligne(x, y)
end

function resolveBligne (x, y)
   
   screen.print(1, 6 + 9 * 16, 3, "INFO : ")
   
   local possibiliteArray1 = {}
   local case = 0
   local possibilite = 0
   local test = {}
   local t = 0
   
   local p = 1
   local q = 1
   if y <= 3 then
      if x <= 3 then
         case = 1
      elseif x >= 7 then
         case = 3
         p = 7
      else
         case = 2
         p = 4
      end
   elseif y >= 7 then
      if x <= 3 then
         case = 7
         q = 7
      elseif x >= 7 then
         case = 9
         p = 7
         q = 7
      else
         case = 8
         p = 4
         q = 7
      end
   else
      if x <= 3 then
         case = 4
         q = 4
      elseif x >= 7 then
         case = 6
         p = 7
         q = 4
      else
         case = 5
         p = 4
         q = 4
      end
   end
   
      
   for k = 1, 9 do
   
      if k <= 3 then
         p = 1
      elseif k >= 7 then
         p = 7
      else
         p = 4
      end
      
      if gridwork[y][k] == 0 then
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], rouge)
        --screen.print(1, 6 + 9 * 16, 30, "valeur possible: ", blanc)
        --code de recherche
        
        for l = 1, 9 do
          test[l] = false
          for i = 1, 9 do
            if l == gridwork[y][i] then
               test[l] = true
            end
          end
          for i = 1, 9 do
            if l == gridwork[i][k] then
               test[l] = true
            end
          end
          
          for i = q, q + 2 do
            for j = p, p + 2 do
               if l == gridwork[i][j] then
                 test[l] = true
               end
            end
          end
          
          if not test[l] then
            possibilite = possibilite + 1
            possibiliteArray1[possibilite] = {}
            possibiliteArray1[possibilite][1] = l
            possibiliteArray1[possibilite][2] = k
            possibiliteArray1[possibilite][3] = y
          end
                 
        end            
        --fin de code de recherche
      else
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], vert)
      end
   
   end
   
   for l = 1, 9 do
      test[l] = 0
      for i = 1, possibilite do
         if l == possibiliteArray1[i][1] then
            test[l] = test[l] + 1
         end
      end
   end
   for i = 1, 9 do
      if test[i] == 1 then
         for j = 1, possibilite do
            if i == possibiliteArray1[j][1] then
               gridwork[possibiliteArray1[j][3]][possibiliteArray1[j][2]] = possibiliteArray1[j][1]
            end
         end
      end
      
   end
   
   for i = 1, 9 do
      surligne(i, y)
   end
end

function resolveBcolonne (x, y)

   screen.print(1, 6 + 9 * 16, 3, "INFO : ")
   
   local possibiliteArray1 = {}
   local case = 0
   local possibilite = 0
   local test = {}
   local t = 0
   
   local p = 1
   local q = 1
   if y <= 3 then
      if x <= 3 then
         case = 1
      elseif x >= 7 then
         case = 3
         p = 7
      else
         case = 2
         p = 4
      end
   elseif y >= 7 then
      if x <= 3 then
         case = 7
         q = 7
      elseif x >= 7 then
         case = 9
         p = 7
         q = 7
      else
         case = 8
         p = 4
         q = 7
      end
   else
      if x <= 3 then
         case = 4
         q = 4
      elseif x >= 7 then
         case = 6
         p = 7
         q = 4
      else
         case = 5
         p = 4
         q = 4
      end
   end
   
      
   for k = 1, 9 do
   
      if k <= 3 then
         q = 1
      elseif k >= 7 then
         q = 7
      else
         q = 4
      end
      
      if gridwork[k][x] == 0 then
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], rouge)
        --screen.print(1, 6 + 9 * 16, 30, "valeur possible: ", blanc)
        --code de recherche
        
        for l = 1, 9 do
          test[l] = false
          for i = 1, 9 do
            if l == gridwork[i][x] then
               test[l] = true
            end
          end
          for i = 1, 9 do
            if l == gridwork[k][i] then
               test[l] = true
            end
          end
          
          for i = q, q + 2 do
            for j = p, p + 2 do
               if l == gridwork[i][j] then
                 test[l] = true
               end
            end
          end
          
          if not test[l] then
            possibilite = possibilite + 1
            possibiliteArray1[possibilite] = {}
            possibiliteArray1[possibilite][1] = l
            possibiliteArray1[possibilite][2] = x
            possibiliteArray1[possibilite][3] = k
            --screen.print(1, 6 + 9 * 16, 30 + 12 * possibilite, l, blanc)
          end
                 
        end            
        --fin de code de recherche
      else
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], vert)
      end
   
   end
   
   for l = 1, 9 do
      test[l] = 0
      for i = 1, possibilite do
         if l == possibiliteArray1[i][1] then
            test[l] = test[l] + 1
         end
      end
   end
   for i = 1, 9 do
      if test[i] == 1 then
         for j = 1, possibilite do
            if i == possibiliteArray1[j][1] then
               gridwork[possibiliteArray1[j][3]][possibiliteArray1[j][2]] = possibiliteArray1[j][1]
            end
         end
      end
      
   end
   
   for i = 1, 9 do
      surligne(x, i)
   end
end

function resolveBcarre (x, y)
   
   screen.print(1, 6 + 9 * 16, 3, "INFO : ")
   
   local possibiliteArray1 = {}
   local case = 0
   local possibilite = 0
   local test = {}
   local t = 0
   
   local p = 1
   local q = 1
   if y <= 3 then
      if x <= 3 then
         case = 1
      elseif x >= 7 then
         case = 3
         p = 7
      else
         case = 2
         p = 4
      end
   elseif y >= 7 then
      if x <= 3 then
         case = 7
         q = 7
      elseif x >= 7 then
         case = 9
         p = 7
         q = 7
      else
         case = 8
         p = 4
         q = 7
      end
   else
      if x <= 3 then
         case = 4
         q = 4
      elseif x >= 7 then
         case = 6
         p = 7
         q = 4
      else
         case = 5
         p = 4
         q = 4
      end
   end
   
      
   for k = p, p + 2 do
   for h = q, q + 2 do
   
   surligne(k, h)
      
      if gridwork[h][k] == 0 then
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], rouge)
        --screen.print(1, 6 + 9 * 16, 30, "valeur possible: ", blanc)
        --code de recherche
        
        for l = 1, 9 do
          test[l] = false
          for i = 1, 9 do
            if l == gridwork[h][i] then
               test[l] = true
            end
          end
          for i = 1, 9 do
            if l == gridwork[i][k] then
               test[l] = true
            end
          end
          
          for i = q, q + 2 do
            for j = p, p + 2 do
               if l == gridwork[i][j] then
                 test[l] = true
               end
            end
          end
          
          if not test[l] then
            possibilite = possibilite + 1
            possibiliteArray1[possibilite] = {}
            possibiliteArray1[possibilite][1] = l
            possibiliteArray1[possibilite][2] = k
            possibiliteArray1[possibilite][3] = h
            --screen.print(1, 6 + 9 * 16, 30 + 12 * possibilite, l, blanc)
          end
                 
        end            
        --fin de code de recherche
      else
        screen.print(1, 6 + 9 * 16, 18, "valeur: "..gridwork[y][x], vert)
      end
     
     
   end
   end
   
   for l = 1, 9 do
      test[l] = 0
      for i = 1, possibilite do
         if l == possibiliteArray1[i][1] then
            test[l] = test[l] + 1
         end
      end
   end
   for i = 1, 9 do
      if test[i] == 1 then
         for j = 1, possibilite do
            if i == possibiliteArray1[j][1] then
               gridwork[possibiliteArray1[j][3]][possibiliteArray1[j][2]] = possibiliteArray1[j][1]
            end
         end
      end
      
   end
end

function resolveB()
   local quitter = false
   local count = 0
   while not quitter do
   
      for i = 1, 9 do
         for j = 1, 9 do
            resolveBligne(j, i)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         end
      end
      
      for i = 1, 9 do
         for j = 1, 9 do
            resolveBcolonne(i, j)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         end
      end
     
     for i = 1, 9 do
         for j = 1, 9 do
            resolveBcarre(i, j)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         end
      end
      
   
        Controls.read()
      if Keys.newPress.Select then
         quitter = true
      end
      count = count + 1
      if count == 12 then      
         quitter = true
      end
      if verify() then
         quitter = true
      end

      screen.print(1, 0, 148, "En cours de traitement...", jaune)
      affiche()
      render()
   end

end

function resolveA()
   local quitter = false
   local count = 0
   while not quitter do
   
      for i = 1, 9 do   
         for j = 1, 9 do   
            resolveA2(j, i)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         end
      end
   
        Controls.read()
      if Keys.newPress.Select then
         quitter = true
      end
      count = count + 1
      if count == 12 then      
         quitter = true
      end
      if verify() then
         quitter = true
      end

      screen.print(1, 0, 148, "en cours...", jaune)
      affiche()
      render()
   end

end

function resolvetotal()

   local quitter = false
   local resolveA = true
   timeresolve:start()   
   
   while not quitter do
         
      if resolveA then
         for i = 1, 9 do   
            for j = 1, 9 do   
               resolveA2(j, i)
               screen.print(1, 0, 148, "En cours de traitement...", jaune)
               affiche()
               render()
            end
         end
         resolveA = false
      else
         resolveA = true
      end
      
      for i = 1, 9 do
         --for j = 1, 9 do
            resolveBligne(1, i)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         --end
      end
      
      for i = 1, 9 do
         --for j = 1, 9 do
            resolveBcolonne(i, 1)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         --end
      end
     
     for i = 1, 3 do
         for j = 1, 3 do
            v = -2 + i * 3
            w = -2 + j * 3
            resolveBcarre(v, w)
            screen.print(1, 0, 148, "En cours de traitement...", jaune)
            affiche()
            render()
         end
      end
      
      Controls.read()
      if Keys.newPress.Select then
         quitter = true
      end
      if verify() then
         quitter = true
         timeresolve:stop()
         t = timeresolve:time() / 1000
         u = timeresolve:time() / nbuk
      end      
      
   end
end


Si vous n'avez pas envie de vous prendre la tête à regarder le code très long et incomplet. Voici le récapitulatif de ses fonctions actuelles : Le solveur de sudoku résout les sudoku de façon intelligente. Cependant, il bloque sur les sudoku où il faut faire un choix. C'est pourquoi il manque l'ajout du backtracking dans ce cas. Il manque aussi la possibilité d'y mettre son propre sudoku et non un donné en exemple(les sudokus d'exemples sont tirés d'un cahier été je crois). Il manque aussi la destruction de toutes les variables à la fin du programme.


Revenir en haut
thermo_nono
Modérateur

Hors ligne

Inscrit le: 31 Déc 2008
Messages: 2 415
Localisation: La Géhenne

MessagePosté le: Jeu 16 Aoû 2012 - 23:56    Sujet du message: Solveur de sudoku Répondre en citant

Okay
_________________
“Qui reçoit une idée de moi reçoit de la connaissance sans diminuer la mienne, comme celui qui allume sa chandelle à la mienne reçoit la lumière sans me plonger dans l’obscurité.” - Thomas Jefferson


Revenir en haut
Visiter le site web du posteur MSN
Fantasix
Modérateur

Hors ligne

Inscrit le: 26 Avr 2010
Messages: 1 317
Localisation: SCREEN_UP, en -1, -1

MessagePosté le: Ven 17 Aoû 2012 - 00:11    Sujet du message: Solveur de sudoku Répondre en citant

Serait-ce possible d'avoir une archive s'il te plait ?

Disons que, j'ai un peu la flemme de faire du copier-coller ... :p

Fanta'
_________________


BMA News :

Création du Homebrew Storage en cours ...


Revenir en haut
Visiter le site web du posteur
ShiiFu


Hors ligne

Inscrit le: 05 Juil 2012
Messages: 51

MessagePosté le: Ven 17 Aoû 2012 - 08:15    Sujet du message: Solveur de sudoku Répondre en citant

Sans problème je te fait ça Wink

EDIT : Download Link


Revenir en haut
Contenu Sponsorisé






MessagePosté le: Aujourd’hui à 10:27    Sujet du message: Solveur de sudoku

Revenir en haut
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    µLua DS - Forum officiel | Official forum Index du Forum -> Section française -> Coin du dév' Toutes les heures sont au format GMT + 1 Heure
Page 1 sur 1

 
Sauter vers:  

Index | Creer un forum | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation
Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com