Sudoku Loesung finden

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Gast

Sudoku Loesung finden

Beitragvon Gast » Montag 6. Juni 2005, 23:26

Hallo
Hab für Sudoku eine Loesung-Suche geschrieben :)
Sudoku? Infos hier: http://www.tagesschau.de/aktuell/meldungen/0,1185,OID4387268,00.html

Hierzu musste ich Zahlen permutieren. Da ich für Python kein Code gefunden hatte, aber dafür für Pascal, hab ich es "übersetzt". Der Code stammt von hier: http://www.schoenleber.org/pascal/pascal2-03.html. Ich weiss bloß nicht ob ich den so veröffentlichen darf..., deshalb lasse ich es.
  1. import permute
  2.  
  3. Sudoku1 = [
  4.      [0,6,0,1,0,4,0,5,0], # Original
  5.      [0,0,8,3,0,5,6,0,0], # viele Zahlen zu checken
  6.      [2,0,0,0,0,0,0,0,1],
  7.      [8,0,0,4,0,7,0,0,6],
  8.      [0,0,6,0,0,0,3,0,0],
  9.      [7,0,0,9,0,1,0,0,4],
  10.      [5,0,0,0,0,0,0,0,2],
  11.      [0,0,7,2,0,6,9,0,0],
  12.      [0,4,0,5,0,8,0,7,0]]
  13.      
  14. Sudoku1 = [
  15.      [0,6,0,1,0,4,0,5,0], # schnelle Variante zum Testen
  16.      [0,0,8,3,0,5,6,4,9], # wenige Zahlen zu checken
  17.      [2,0,0,6,8,9,7,3,1],
  18.      [8,2,1,4,0,7,0,9,6],
  19.      [0,0,6,8,5,2,3,0,7],
  20.      [7,0,0,9,6,1,8,2,4],
  21.      [5,8,9,7,1,3,0,0,2],
  22.      [0,0,7,2,0,6,9,8,5],
  23.      [6,4,2,5,0,8,1,7,0]]
  24.  
  25. # Zahlen 1..9 alle da?
  26. def Reihe(r):
  27.     check = [0,0,0,0,0,0,0,0,0,0]
  28.     for i in range(9):
  29.         if (r[i]>0) and (check[r[i]] == 0):
  30.             check[r[i]] = 1
  31.         else:
  32.             return 0
  33.     for i in range(1,10):
  34.         if check[i] <> 1:
  35.             return 0
  36.     return 1
  37.          
  38. def Zahl_doppelt(r):
  39.     z = []
  40.     for i in r:
  41.         if i in z:
  42.             return 1
  43.         else:
  44.             z.append(i)
  45.     return 0
  46.                
  47. # Zahlen die erraten werden muessen
  48. def Zahlen(r):
  49.     nein = []
  50.     for i in range(len(r)):
  51.         if r[i] > 0:
  52.             nein.append(r[i])
  53.     z = []
  54.     for i in range(1,10):
  55.         if not i in nein:
  56.             z.append(i)
  57.     return z
  58.        
  59. def Zahlen_Vorgabe(r):
  60.     zv = []
  61.     for i in range(len(r)):
  62.         if r[i] > 0:
  63.             zv.append([i,r[i]])
  64.     return zv
  65.  
  66. # 3 Reihen a 3 Inseln werden gecheckt - 1..9 vorhanden?
  67. def inseln(r):
  68.     for x in [0,3,6]:
  69.         Insel = []
  70.         for y in range(3):
  71.             for x2 in range(3):
  72.                 Insel.append(r[y][x+x2])
  73.         if not Reihe(Insel):
  74.             return 0
  75.     return 1
  76.        
  77. # Permutieren der 9 waagerechten Reihen
  78. print "Schritt 1/5 - Zahlen permutieren"                                                                
  79. s = Sudoku1[:]
  80. permu_list = []
  81. for i in range(9):
  82.     permu_list.append(permute.permute(Zahlen(s[i])))
  83.     zv = Zahlen_Vorgabe(s[i])
  84.     for x in range(len(permu_list[i])):
  85.         l1 = permu_list[i][x]
  86.         for i2 in range(len(zv)):
  87.             zvx = zv[i2]
  88.             l1.insert(zvx[0],zvx[1])
  89.         permu_list[i][x] = l1
  90.  
  91. # jeweils 3 uebereinanderliegende Reihen werden gecheckt
  92. def L3Check(Liste1,Liste2,Liste3,OKListe):
  93.     for x0 in range(len(Liste1)):
  94.         for x1 in range(len(Liste2)):
  95.             for x2 in range(len(Liste3)):
  96.                 weiter = 1
  97.                 for i in range(9):
  98.                     if Zahl_doppelt([Liste1[x0][i],Liste2[x1][i],Liste3[x2][i]]):
  99.                         weiter = 0
  100.                         break
  101.                 if not weiter:
  102.                     continue
  103.                 if not inseln([Liste1[x0],Liste2[x1],Liste3[x2]]):
  104.                     continue
  105.                 OKListe.append([Liste1[x0],Liste2[x1],Liste3[x2]])
  106.  
  107. OK012Listen = []            
  108. OK345Listen = []
  109. OK678Listen = []
  110. print "Schritt 2/5 - Zeilen 1-3 checken"
  111. L3Check(permu_list[0],permu_list[1],permu_list[2],OK012Listen)
  112. print "Schritt 3/5 - Zeilen 4-6 checken"
  113. L3Check(permu_list[3],permu_list[4],permu_list[5],OK345Listen)
  114. print "Schritt 4/5 - Zeilen 7-9 checken"
  115. L3Check(permu_list[6],permu_list[7],permu_list[8],OK678Listen)
  116.  
  117. BingoListe = []
  118.  
  119. # gefundene 3er-Linien werden gecheckt ob sie zusammenpassen
  120. print "Schritt 5/5 - Zeilen 1-9 zusammensetzen"
  121. for L1 in range(len(OK012Listen)):
  122.     l1 = []
  123.     for i in range(3): l1.append(OK012Listen[L1][i])
  124.     for L2 in range(len(OK345Listen)):
  125.         l2 = l1[:]
  126.         for i in range(3): l2.append(OK345Listen[L2][i])
  127.         for L3 in range(len(OK678Listen)):
  128.             l3 = l2[:]
  129.             for i in range(3): l3.append(OK678Listen[L3][i])
  130.             OK = 1
  131.             for x in range(9):
  132.                 l = []
  133.                 for i in range(9):
  134.                     l.append(l3[i][x])
  135.                 if not Reihe(l):
  136.                     OK = 0
  137.                     break
  138.             if OK:
  139.                 BingoListe.append(l3)
  140.  
  141. # Ergebnis zeigen
  142. for BL in range(len(BingoListe)):
  143.     print
  144.     print    
  145.     print "Sudoku - Loesung", BL+1
  146.     for i in range(len(BingoListe[BL])):
  147.         print BingoListe[BL][i]


Edit (Leonidas): Code in Python-Tags gesetzt.
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Dienstag 7. Juni 2005, 09:26

Sieht ziemlich aufwendig aus für eine "einfache" mathematische Zielstellung, aber Interessant auch die Seiten :).
Ich kenne das Spiel zwar nicht aber könnte mir vorstellen das es mit einer Funktion zu lösen ist. :o
Was is permute für ein Modul?
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
Gast

Beitragvon Gast » Dienstag 7. Juni 2005, 10:19

@Olliminatore
Ich kenne das Spiel zwar nicht aber könnte mir vorstellen das es mit einer Funktion zu lösen ist. :o
Auf geht's, zeig's mir, mach mich fertig :) :wink:
Was is permute für ein Modul?
permute = permutieren, das was ich von Pascal übernommen habe.
Um alle Lösungsmöglichkeiten zu testen mußte ich alle generieren.
Beispiel: Die Zahlen 1,2,3
1,2,3 + 2,3,1 + 1,3,2 + 1,3,2 usw.
Dem Modul «permut» übergibt man eine Liste, zurückgegeben wird eine permutierte Liste.
Der Sudoku-Haken ist, das einige Zahlen bereits vorgegeben sind, z.B. 0,0,3,0,8,0,5,0,0 - an 3.Position muß immer eine 3 Stehen, an 5. eine 8 usw.(wo eine 0 steht sind die Flächen die berechnet werden). Anzahl/Wert/Position dieser Vorgabezahlen sind variabel, umso mehr Vorgabezahlen desto leichter ist das Spiel(auch zu berechnen).
Wenn man keine Vorgabezahlen machen würde, dann würde das Programm alle Spiel-Möglichkeiten berechnen, das dauert aber auch ganz schön lange :shock:


ciao
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Dienstag 7. Juni 2005, 13:54

Auf geht's, zeig's mir, mach mich fertig
Ja mein Name ist Programm, ich muss zwanghaft alles optimieren/eliminieren :mrgreen:(=olliminieren)

Ist komplexer als ich dachte, muss es wohl wenn es ein Mathematiker herraus gebracht hat :P. Ich denke du kannst das permut Modul ruhig posten.
Kann es sein das für das erste Gitterfeld mehrere Lösungen in Frage kommen? Für das zweite Gitterfeld habe ich eine Lösung geschafft(weiter komm ich erstmal nicht). Wobei die countSo Funktion nur prüft ob die reduceSo Funktion
fertig ist.

  1. Sudoku1 = [
  2.      [0,6,0,1,0,4,0,5,0], # schnelle Variante zum Testen
  3.      [0,0,8,3,0,5,6,4,9], # wenige Zahlen zu checken
  4.      [2,0,0,6,8,9,7,3,1],
  5.      [8,2,1,4,0,7,0,9,6],
  6.      [0,0,6,8,5,2,3,0,7],
  7.      [7,0,0,9,6,1,8,2,4],
  8.      [5,8,9,7,1,3,0,0,2],
  9.      [0,0,7,2,0,6,9,8,5],
  10.      [6,4,2,5,0,8,1,7,0]]
  11.  
  12. #for x in Sudoku1: print x
  13.  
  14. so_len=len(Sudoku1)
  15.  
  16. for x in xrange(so_len):
  17.     for y in xrange(so_len):
  18.         if Sudoku1[x][y] == 0:
  19.             Sudoku1[x][y]=range(1,so_len+1)
  20.         else:
  21.             Sudoku1[x][y]=[Sudoku1[x][y]]
  22.  
  23. def countSo(Sudoku1):
  24.     printli=[]
  25.     for x in xrange(so_len):
  26.         printl=[]
  27.         printtlist=[]
  28.         for y in xrange(so_len):
  29.             printl.append(len(Sudoku1[x][y]))
  30.             printtlist.append((y+1,Sudoku1[x][y]))
  31.         printli.append(sum(printl)-so_len)
  32.         #print printtlist
  33.     #print sum(printli),printli  
  34.     return sum(printli)
  35.  
  36. def reduceSo(c,Sudoku1):
  37.     for x in xrange(so_len):
  38.         for y in xrange(so_len):
  39.             if len(Sudoku1[x][y])==1:
  40.                 for i in xrange(so_len):
  41.                     try:
  42.                         if i != x: Sudoku1[i][y].remove(Sudoku1[x][y][0])
  43.                     except ValueError: pass
  44.                     try:
  45.                         if i != y: Sudoku1[x][i].remove(Sudoku1[x][y][0])
  46.                     except ValueError: pass
  47.     cs=countSo(Sudoku1)
  48.     if c!=cs:
  49.         c=cs
  50.         return reduceSo(c,Sudoku1)
  51.     return Sudoku1
  52.  
  53. print
  54. for x in reduceSo(0,Sudoku1): print x
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Beitragvon salznase » Dienstag 7. Juni 2005, 15:34

@Olliminatore

Wau, das Feld2 ist richtig berechnet...
Wieso dein Programm das erste Feld nicht schafft ähhh muß ich checken, du gehst ja einen ganz anderen Weg wie ich.
Das erste Feld ist aber dasselbe Feld wie Feld2, in Feld2 habe ich von der Lösung nur ein paar Zahlen reingesetzt damit die Berechnung schneller geht(zum Testen). Ich hab hier nur einen 400MHz, der brauch so lange das ich das Feld1 noch nie durchlaufen liess.

Dein Programm scheint zu funktionieren solange es nur eine Lösung gibt, oder?
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Mittwoch 8. Juni 2005, 12:23

Hi salznase,

willkommen als ForumsMember, irgendwoher kenne ich deinen Nick!?
Jetzt kannst du das permute Modul nicht mehr posten. :o
salznase hat geschrieben:du gehst ja einen ganz anderen Weg wie ich

Ja du nimmst den mehr rekursiven, ich den iterativen Weg. :-P
Dein Programm scheint zu funktionieren solange es nur eine Lösung gibt, oder?

Ja, es wird nur Lösung herausgegeben oder hält eben bei den verbleibenden Zahlen/Möglichkeiten an,
weiter habe ich noch nicht getestet.

Kann dein Script den letzten Punkt vor der Lösungsgabelung ermitteln?
Hmm das wäre ja schon eine Art Umkehrfunktion.
Der Herausgeber hat ja einen Code geschrieben um Gitterfeld-Aufgaben zu generieren.

Du/Wir könnten ja vielleicht ein Spiel mit GUI daraus machen!?

Edit: man könnte mein "try: if i !=x:" noch ersetzen durch(k.A ob das schneller ist):

Code: Alles auswählen

    if i != x and len(Sudoku1[i][y])-1 and Sudoku1[x][y][0] in Sudoku1[i][y]:
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
BlackJack

Beitragvon BlackJack » Mittwoch 8. Juni 2005, 20:55

Noch'n Versuch. Alle Möglichkeiten durchprobieren ist wohl nicht drin; das sind nämlich 4638397686588101979328150167890591454318967698009 für das Beispiel von der Webseite.

Aber $GOTT sei Dank sind die Möglichkeiten für jedes Feld durch die schon vorhandenen Zahlen eingeschränkt. Für diese Einschränkungen habe ich eine Klasse erstellt, die sich in Mengen (`set`) merkt, welche Zahlen in jeder Zeile, Spalte und jedem 3x3 Quadrat noch nicht verwendet wurden. Zu jedem Feld gibt es also drei Mengen, die der Zeile, der Spalte und des Quadrats in der es liegt. Die Schnittmenge der drei Mengen ergibt die noch möglichen Belegungen für das Feld.

Beispiel für Feld (0,0):

Zeile: { 2, 3, 7, 8, 9 }

Spalte: { 1, 3, 4, 6, 9 }

Quadrat: { 1, 3, 4, 5, 7, 9 }

Wie man sieht sind nur die 3 und die 9 in allen drei Mengen enthalten, also kann man auch nur diese beiden in Feld (0,0) eintragen.

Das Programm testet auf diese Art rekursiv alle leeren Felder durch. Das passiert für das Beispiel von der Webseite in nur 2266 rekursiven Aufrufen die auf einem 1Ghz Athlon schlappe 0.34 Sekunden CPU-Zeit beanspruchen. Sollte also auch auf einem 400Mhz Rechner in unter zwei Sekunde ablaufen. Und das Programm findet alle Lösungen. Das ist in diesem Fall übrigens nur eine.

  1. #!/usr/bin/env python
  2. """A Sudoku solver.
  3.  
  4. Sudoku is a number game similar to magic squares.  There is a 9x9 matrix with
  5. some pre-filled fields and it has to be completed by filling all fields with
  6. single digits from 1 to 9.  The filled matrix must satisfy these rules:
  7.  
  8. 1. Every row must contain all digits from 1 to 9,
  9. 2. every column must contain all digits from 1 to 9,
  10. 3. and the matrix is evenly divided into nine 3x3 matrices that must contain
  11.   all digits from 1 to 9.
  12.  
  13. :var example_sudoku: Test sudoku.
  14. """
  15. from __future__ import division
  16. import copy
  17.  
  18. __author__ = "Marc 'BlackJack' Rintsch"
  19. __version__ = '0.1.0'
  20. __date__ = '$Date: 2005-06-08 21:29:06 +0200 (Wed, 08 Jun 2005) $'
  21. __revision__ = '$Rev: 696 $'
  22.  
  23. __docformat__ = 'reStructuredText'
  24.  
  25.  
  26. example_sudoku = [[0, 6, 0,  1, 0, 4,  0, 5, 0],
  27.                   [0, 0, 8,  3, 0, 5,  6, 0, 0],
  28.                   [2, 0, 0,  0, 0, 0,  0, 0, 1],
  29.                  
  30.                   [8, 0, 0,  4, 0, 7,  0, 0, 6],
  31.                   [0, 0, 6,  0, 0, 0,  3, 0, 0],
  32.                   [7, 0, 0,  9, 0, 1,  0, 0, 4],
  33.                  
  34.                   [5, 0, 0,  0, 0, 0,  0, 0, 2],
  35.                   [0, 0, 7,  2, 0, 6,  9, 0, 0],
  36.                   [0, 4, 0,  5, 0, 8,  0, 7, 0]]
  37.  
  38.  
  39. class Sudoku:
  40.     """A `Sudoku` instance knows the matrix and keeps track of constraints
  41.    for all fields.
  42.    
  43.    :ivar rows: constraints for rows.
  44.    :ivar columns: constraints for columns.
  45.    :ivar fields: constraints for 3x3 sub-matrices.
  46.    :ivar numbers: the matrix.
  47.    :type rows columns: [set]
  48.    :type fields: [[set]]
  49.    :type numbers: [[int]]
  50.    """
  51.     def __init__(self, values=None):
  52.         """Creates a Sudoku matrix.
  53.        
  54.        If no value matrix is passed in, an empty matrix is created.
  55.        
  56.        :param values: value matrix.
  57.        :type values: [[int]]
  58.        """
  59.         numbers = xrange(1, 10)     # 1-9
  60.         self.rows = [set(numbers) for dummy in numbers]
  61.         self.columns = [set(numbers) for dummy in numbers]
  62.         self.fields = [[set(numbers) for dummy in xrange(3)]
  63.                        for dummy in xrange(3)]
  64.         self.numbers = copy.deepcopy(values)
  65.         if self.numbers is None:
  66.             self.numbers = [[0] * 9 for dummy in numbers]
  67.         self._prepare()
  68.    
  69.     def _prepare(self):
  70.         """Sets constraints for the values of `self.numbers`."""
  71.         for row_nr, row in enumerate(self.numbers):
  72.             for column_nr, value in enumerate(row):
  73.                 coordinate = (row_nr, column_nr)
  74.                 if value != 0:
  75.                     self[coordinate] = value
  76.  
  77.     def __setitem__(self, (row, column), value):
  78.         #
  79.         # Update constraints and set value.
  80.         #
  81.         self.rows[row].remove(value)
  82.         self.columns[column].remove(value)
  83.         self.fields[row // 3][column // 3].remove(value)
  84.         self.numbers[row][column] = value
  85.    
  86.     def __delitem__(self, (row, column)):
  87.         #
  88.         # Update constraints and delete value.
  89.         #
  90.         value = self.numbers[row][column]
  91.         assert value != 0
  92.         self.rows[row].add(value)
  93.         self.columns[column].add(value)
  94.         self.fields[row // 3][column // 3].add(value)
  95.         self.numbers[row][column] = 0
  96.    
  97.     def iter_empty_fields(self):
  98.         """Iterates over the empty fields.
  99.        
  100.        :rtype: iterable of (row, column)
  101.        """
  102.         for row_nr, row in enumerate(self.numbers):
  103.             for column_nr, value in enumerate(row):
  104.                 if value == 0:
  105.                     yield (row_nr, column_nr)
  106.    
  107.     def get_candidates(self, (row, column)):
  108.         """Gets all possible values for given `row` and `column`.
  109.        
  110.        :returns: the intersection of unused values in the row, in the column,
  111.            and the 3x3 field that contains the field (`row`, `column`).
  112.        :rtype: iterable
  113.        """
  114.         return (self.rows[row] &
  115.                 self.columns[column] &
  116.                 self.fields[row // 3][column // 3])
  117.  
  118.  
  119. def solve(values):
  120.     """Finds all solutions for the given `values` matrix.
  121.    
  122.    :param values: a sudoku matrix with some pre-filled values.
  123.    :type values: [[int]]
  124.    
  125.    :returns: all solutions.
  126.    :rtype: [[int]]
  127.    """
  128.     results = list()
  129.     constraints = Sudoku(values)
  130.     empty_fields = list(constraints.iter_empty_fields())
  131.    
  132.     def solve_recursive(current_field=0):
  133.         """Finds all solutions recursivly."""
  134.         #
  135.         # If all fields are filled, add the solution to `results`.
  136.         #
  137.         if current_field == len(empty_fields):
  138.             results.append(copy.deepcopy(constraints.numbers))
  139.             return
  140.         #
  141.         # Test all possible values for the `current_field` and recurse.
  142.         #
  143.         coordinate = empty_fields[current_field]
  144.         for value in constraints.get_candidates(coordinate):
  145.             constraints[coordinate] = value
  146.             solve_recursive(current_field + 1)
  147.             del constraints[coordinate]
  148.    
  149.     solve_recursive()
  150.     return results
  151.  
  152.  
  153. def main():
  154.     """Test."""
  155.     print solve(example_sudoku)
  156.  
  157.  
  158. if __name__ == '__main__':
  159.     main()
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Beitragvon salznase » Mittwoch 8. Juni 2005, 21:40

@Olliminatore - Hi
du nimmst den mehr rekursiven, ich den iterativen Weg.
Eher umgedreht, oder?
Dein «return reduceSo(c,Sudoku1)» ist doch rekursiv...(wo nutze ich Rekursion?)
Der Herausgeber hat ja einen Code geschrieben um Gitterfeld-Aufgaben zu generieren.
Jo, in GB ist Sudoku schon fast ne Sucht, da gibts alles mögliche.
Du/Wir könnten ja vielleicht ein Spiel mit GUI daraus machen!?
Hatte ich auch schon dran gedacht. Aber hab kaum Zeit und Nerven zum coden wenn ich wieder arbeiten muß(hab noch Urlaub) :)
Also so schnell wie du da ein Programm hervorgeholt hast ähhh ich glaub da würde ich dich bloß aufhalten.
Außerdem finde ich das Python-GUI-coden nicht so anregend(wenn man Delphi/Lazarus gewöhnt ist) :wink: Womit erstellst du denn Python-GUIs? Welches BS?
Kann dein Script den letzten Punkt vor der Lösungsgabelung ermitteln?
Du meinst wenn es mehrere Lösungen gibt, oder?

ciao
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Beitragvon salznase » Mittwoch 8. Juni 2005, 22:08

@BlackJack

Grade erst dein Posting gesehen...
Scheinst ja echt schon länger Python zu coden.

Deinen Code schluckt Python bei mir(2.3.4/Linux) nicht.
NameError: global name 'set' is not defined (Zeile60)

ciao
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 9. Juni 2005, 12:57

Das ist erst seit Python 2.4 als set bekannt, für Python 2.3 musst du davor noch folgendes importieren:

Code: Alles auswählen

from sets import Set as set
dann sollte es gehen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Beitragvon salznase » Donnerstag 9. Juni 2005, 14:29

@Leonidas

Danke, jetzt klappts.
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Donnerstag 9. Juni 2005, 16:49

Beeindruckend, da können wir noch was lernen. :)

Die Bedingung mit dem 3*3Quadrat habe ich völlig übersehen. :x
Habe sie jetzt meiner Funktion hinzugefügt.
Demnach schließt meine Funktion (erstmal einfach nur) nach den vorgegebenen Bedingungen alle Möglichkeiten aus (,ohne weitere logische Verknüpfung, Vergleiche oder Versuche).
Aber kommt wieder nicht zu einer Lösung (wenn ich ins 1. leere Feld die 9 einsetze schon, nach 10 Durchläufen).
Was könnte da noch fehlen?
Werde das Skript von BlackJack nachher mal genauer analysieren.
  1. def reduceSu(c,Sudoku1):
  2.     for x in xrange(su_len):
  3.         xq=(x/3)*3
  4.         for y in xrange(su_len):
  5.             yq=(y/3)*3
  6.             if not len(Sudoku1[x][y])-1:
  7.                 xy=Sudoku1[x][y][0]
  8.                 for i in xrange(su_len):
  9.                     try:    ## clear vertical
  10.                         if i != x: Sudoku1[i][y].remove(xy)
  11.                     except ValueError: pass    
  12.                     try:    ## clear horizontal
  13.                         if i != y: Sudoku1[x][i].remove(xy)
  14.                     except ValueError: pass
  15.                    
  16.                     qx,qy=divmod(i,3)
  17.                     xx,yy = xq+qx,yq+qy
  18.                     try:    ## clear square
  19.                         if (xx,yy) != (x,y): Sudoku1[xx][yy].remove(xy)
  20.                     except ValueError: pass    
  21.  
  22.     cs=countSu(Sudoku1)
  23.     if c!=cs:
  24.         c=cs
  25.         return reduceSu(c,Sudoku1)
  26.     return Sudoku1
Eher umgedreht, oder? [...] Womit erstellst du denn Python-GUIs? Welches BS?
Oh ja. Also soviel Erfahrung mit GUIs habe ich auch nicht, bis jetzt nur wxPython und wenn dann sollte es schon auf mehreren BS laufen. Ich würde eher Tkinter oder PyGame bevorzugen.
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
Benutzeravatar
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Beitragvon Olliminatore » Donnerstag 9. Juni 2005, 22:08

Ich habe es gefunden und meiner Funktion "noch" eine Abfrage hinzugerfügt.
Finde jetzt auch die Lösung. :) (in 7 Durchläufen)
Auf zum 16er Hexgitterfeld. :mrgreen:
@BlackJack
Jetzt brauchen wir den Generator noch.:wink:
Kann sein das ich die letzte Abfrage ein bisschen umständlich realisiert habe, mit einer "container" Liste.
Die class Methode (von BlackJack) ist dann wohl die bessere(obwohl ich kein 'set' verwende).
Mir ist noch ein Phänomen aufgefallen. list[:] kopiert nicht Unterlisten!

  1. su_len=len(Sudoku1)
  2. ## convert all values to list
  3. for x in xrange(su_len):
  4.     for y in xrange(su_len):
  5.         if Sudoku1[x][y] == 0: Sudoku1[x][y]=range(1,su_len+1)
  6.         else: Sudoku1[x][y]=[Sudoku1[x][y]]
  7.            
  8. def countSu(Sudoku1):
  9.     "sum all possible values for check"
  10.     printxl=[]
  11.     printyl=[]
  12.     for x in xrange(su_len):
  13.         printlx=[]
  14.         printly=[]
  15.         printtlist=[]
  16.         for y in xrange(su_len):
  17.             printlx.append(len(Sudoku1[x][y]))
  18.             #printly.append(len(Sudoku1[y][x]))
  19.             #printtlist.append((y+1,Sudoku1[x][y]))
  20.         printxl.append(sum(printlx)-su_len)
  21.         #printyl.append(sum(printly)-su_len)
  22.         #print printtlist
  23.     #print "horizontal sum",sum(printxl),printxl  
  24.     #print "vertical sum",sum(printyl),printyl  
  25.     return sum(printxl)
  26.  
  27. def reduceSu(c,Sudoku1):
  28.     "iter over all fields"
  29.     for x in xrange(su_len):
  30.         xq=(x/3)*3
  31.         contain=[[i] for i in xrange(1,su_len+1)]    ## clear container
  32.         for y in xrange(su_len):
  33.             yq=(y/3)*3
  34.             if not len(Sudoku1[x][y])-1:
  35.                 xy=Sudoku1[x][y][0]
  36.                 contain[xy-1].extend([xy]*2)   ## mark container
  37.                 for i in xrange(su_len):
  38.                     try:    ## clear vertical
  39.                         if i != x: Sudoku1[i][y].remove(xy)
  40.                     except ValueError: pass    
  41.                     try:    ## clear horizontal
  42.                         if i != y: Sudoku1[x][i].remove(xy)
  43.                     except ValueError: pass
  44.                     qx,qy=divmod(i,3)
  45.                     xx,yy = xq+qx,yq+qy
  46.                     try:    ## clear square
  47.                         if (xx,yy) != (x,y): Sudoku1[xx][yy].remove(xy)
  48.                     except ValueError: pass    
  49.             else:  ## fill container with possible values
  50.                 for i in Sudoku1[x][y]:
  51.                     contain[i-1].append(y)
  52.         for i in contain:   ## check container for a single value
  53.             if len(i)==2: Sudoku1[x][i[1]]=[i[0]]
  54.     cs=countSu(Sudoku1)
  55.     if c!=cs:
  56.         c=cs
  57.         return reduceSu(c,Sudoku1)
  58.     return Sudoku1
  59.              
  60. print
  61. for x in reduceSu(0,Sudoku1): print x
Schönes Spiel , danke salznase.
Love Jamba <!--Olliminatore-->input<?/> Boycott Jamba

Code: Alles auswählen

def olliminiert(optimiert, eliminiert, terminiert):
BlackJack

Beitragvon BlackJack » Freitag 10. Juni 2005, 00:42

Olliminatore hat geschrieben:Die class Methode (von BlackJack) ist dann wohl die bessere(obwohl ich kein 'set' verwende).


Ich hatte kurz überlegt, ob ich die `set`\s durch `int`\s ersetze und mit den Bits 0-8 arbeite, also Bit 0 gesetzt == 1 ist enthalten, sonst nicht und so weiter. Die '&'-Verknüpfung ist dann ja das gleiche wie die Schnittmenge aus den Mengen zu bilden. Das ist den Aufwand bei der geringen Laufzeit aber wohl nicht wert. Wäre aber eine Optimierung, die für eine Portierung nach C ein guter Weg wäre ohne `set` auszukommen.

Mir ist noch ein Phänomen aufgefallen. list[:] kopiert nicht Unterlisten!


Ja, das kopiert nur die Elemente, die in der Liste stehen -- also in dem Fall die Referenzen auf die enthaltenen Listen. Deshalb auch `copy.deepcopy()` um ein gefundenes Ergebnis zu "sichern".
ramin
User
Beiträge: 8
Registriert: Sonntag 15. Mai 2005, 15:07

da fehlt aber noch einiges

Beitragvon ramin » Samstag 8. Oktober 2005, 19:01

Gut dass mit dem Script bereits einfache Sudokus gelöstwerden können, aber damit ist es noch nicht getan! Da ist noch viel zu eliminieren und optimieren, um Deinem Namen alle Ehren zu machen.


probiere mal folgendes Sudoku ....

  1. Sudoku1 = [
  2.      [0,5,0,0,8,0,0,2,0],
  3.      [0,0,0,6,0,0,7,0,0],
  4.      [3,0,0,9,0,0,4,0,0],
  5.      [0,0,1,0,5,0,0,8,0],
  6.      [0,0,7,0,0,2,9,0,0],
  7.      [0,4,0,0,0,0,6,0,0],
  8.      [0,0,9,0,0,1,0,0,3],
  9.      [0,0,8,0,0,7,0,0,0],
  10.      [0,2,0,0,4,0,0,9,0]]

Lösung:
  1. Sudoku1 = [
  2.      [7,5,6,1,8,4,3,2,9],
  3.      [1,9,4,6,2,3,7,5,8],
  4.      [3,8,2,9,7,5,4,1,6],
  5.      [9,3,1,7,5,6,2,8,4],
  6.      [8,6,7,4,1,2,9,3,5],
  7.      [2,4,5,8,3,9,6,7,1],
  8.      [5,7,9,2,6,1,8,4,3],
  9.      [4,1,8,3,9,7,5,6,2],
  10.      [6,2,3,5,4,8,1,9,7]]

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder