Sudoku Loesung finden

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

Hallo
Hab für Sudoku eine Loesung-Suche geschrieben :)
Sudoku? Infos hier: http://www.tagesschau.de/aktuell/meldun ... 68,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.

Code: Alles auswählen

import permute

Sudoku1 = [
     [0,6,0,1,0,4,0,5,0], # Original
     [0,0,8,3,0,5,6,0,0], # viele Zahlen zu checken
     [2,0,0,0,0,0,0,0,1], 
     [8,0,0,4,0,7,0,0,6],
     [0,0,6,0,0,0,3,0,0],
     [7,0,0,9,0,1,0,0,4],
     [5,0,0,0,0,0,0,0,2],
     [0,0,7,2,0,6,9,0,0],
     [0,4,0,5,0,8,0,7,0]]
     
Sudoku1 = [
     [0,6,0,1,0,4,0,5,0], # schnelle Variante zum Testen
     [0,0,8,3,0,5,6,4,9], # wenige Zahlen zu checken
     [2,0,0,6,8,9,7,3,1],
     [8,2,1,4,0,7,0,9,6],
     [0,0,6,8,5,2,3,0,7],
     [7,0,0,9,6,1,8,2,4],
     [5,8,9,7,1,3,0,0,2],
     [0,0,7,2,0,6,9,8,5],
     [6,4,2,5,0,8,1,7,0]]

# Zahlen 1..9 alle da?
def Reihe(r):
    check = [0,0,0,0,0,0,0,0,0,0]
    for i in range(9):
        if (r[i]>0) and (check[r[i]] == 0):
            check[r[i]] = 1
        else:
            return 0
    for i in range(1,10):
        if check[i] <> 1:
            return 0
    return 1
          
def Zahl_doppelt(r):
    z = []
    for i in r:
        if i in z:
            return 1
        else:
            z.append(i)
    return 0
                
# Zahlen die erraten werden muessen
def Zahlen(r):
    nein = []
    for i in range(len(r)):
        if r[i] > 0:
            nein.append(r[i])
    z = []
    for i in range(1,10):
        if not i in nein:
            z.append(i)
    return z
        
def Zahlen_Vorgabe(r):
    zv = []
    for i in range(len(r)):
        if r[i] > 0:
            zv.append([i,r[i]])
    return zv

# 3 Reihen a 3 Inseln werden gecheckt - 1..9 vorhanden?
def inseln(r):
    for x in [0,3,6]:
        Insel = []
        for y in range(3):
            for x2 in range(3):
                Insel.append(r[y][x+x2])
        if not Reihe(Insel):
            return 0
    return 1
        
# Permutieren der 9 waagerechten Reihen 
print "Schritt 1/5 - Zahlen permutieren"                                                                
s = Sudoku1[:] 
permu_list = []
for i in range(9):
    permu_list.append(permute.permute(Zahlen(s[i])))
    zv = Zahlen_Vorgabe(s[i])
    for x in range(len(permu_list[i])):
        l1 = permu_list[i][x]
        for i2 in range(len(zv)):
            zvx = zv[i2]
            l1.insert(zvx[0],zvx[1])
        permu_list[i][x] = l1

# jeweils 3 uebereinanderliegende Reihen werden gecheckt
def L3Check(Liste1,Liste2,Liste3,OKListe):
    for x0 in range(len(Liste1)):
        for x1 in range(len(Liste2)):
            for x2 in range(len(Liste3)):
                weiter = 1
                for i in range(9):
                    if Zahl_doppelt([Liste1[x0][i],Liste2[x1][i],Liste3[x2][i]]):
                        weiter = 0
                        break
                if not weiter:
                    continue
                if not inseln([Liste1[x0],Liste2[x1],Liste3[x2]]):
                    continue
                OKListe.append([Liste1[x0],Liste2[x1],Liste3[x2]])

OK012Listen = []            
OK345Listen = []
OK678Listen = []
print "Schritt 2/5 - Zeilen 1-3 checken"
L3Check(permu_list[0],permu_list[1],permu_list[2],OK012Listen)
print "Schritt 3/5 - Zeilen 4-6 checken"
L3Check(permu_list[3],permu_list[4],permu_list[5],OK345Listen)
print "Schritt 4/5 - Zeilen 7-9 checken"
L3Check(permu_list[6],permu_list[7],permu_list[8],OK678Listen)

BingoListe = []

# gefundene 3er-Linien werden gecheckt ob sie zusammenpassen
print "Schritt 5/5 - Zeilen 1-9 zusammensetzen"
for L1 in range(len(OK012Listen)):
    l1 = []
    for i in range(3): l1.append(OK012Listen[L1][i])
    for L2 in range(len(OK345Listen)):
        l2 = l1[:]
        for i in range(3): l2.append(OK345Listen[L2][i])
        for L3 in range(len(OK678Listen)):
            l3 = l2[:]
            for i in range(3): l3.append(OK678Listen[L3][i])
            OK = 1
            for x in range(9):
                l = []
                for i in range(9):
                    l.append(l3[i][x])
                if not Reihe(l):
                    OK = 0
                    break
            if OK:
                BingoListe.append(l3)

# Ergebnis zeigen
for BL in range(len(BingoListe)): 
    print
    print     
    print "Sudoku - Loesung", BL+1
    for i in range(len(BingoListe[BL])):
        print BingoListe[BL][i]
Edit (Leonidas): Code in Python-Tags gesetzt.
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

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?
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
Gast

@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
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

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.

Code: Alles auswählen

Sudoku1 = [
     [0,6,0,1,0,4,0,5,0], # schnelle Variante zum Testen
     [0,0,8,3,0,5,6,4,9], # wenige Zahlen zu checken
     [2,0,0,6,8,9,7,3,1],
     [8,2,1,4,0,7,0,9,6],
     [0,0,6,8,5,2,3,0,7],
     [7,0,0,9,6,1,8,2,4],
     [5,8,9,7,1,3,0,0,2],
     [0,0,7,2,0,6,9,8,5],
     [6,4,2,5,0,8,1,7,0]]

#for x in Sudoku1: print x

so_len=len(Sudoku1)

for x in xrange(so_len):
    for y in xrange(so_len):
        if Sudoku1[x][y] == 0:
            Sudoku1[x][y]=range(1,so_len+1)
        else:
            Sudoku1[x][y]=[Sudoku1[x][y]]

def countSo(Sudoku1):
    printli=[]
    for x in xrange(so_len):
        printl=[]
        printtlist=[]
        for y in xrange(so_len):
            printl.append(len(Sudoku1[x][y]))
            printtlist.append((y+1,Sudoku1[x][y]))
        printli.append(sum(printl)-so_len)
        #print printtlist
    #print sum(printli),printli   
    return sum(printli)

def reduceSo(c,Sudoku1):
    for x in xrange(so_len):
        for y in xrange(so_len):
            if len(Sudoku1[x][y])==1:
                for i in xrange(so_len):
                    try:
                        if i != x: Sudoku1[i][y].remove(Sudoku1[x][y][0])
                    except ValueError: pass
                    try:
                        if i != y: Sudoku1[x][i].remove(Sudoku1[x][y][0])
                    except ValueError: pass
    cs=countSo(Sudoku1)
    if c!=cs:
        c=cs
        return reduceSo(c,Sudoku1)
    return Sudoku1

print 
for x in reduceSo(0,Sudoku1): print x
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@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?
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

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]:
[/size]
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
BlackJack

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.

Code: Alles auswählen

#!/usr/bin/env python
"""A Sudoku solver.

Sudoku is a number game similar to magic squares.  There is a 9x9 matrix with
some pre-filled fields and it has to be completed by filling all fields with
single digits from 1 to 9.  The filled matrix must satisfy these rules:

1. Every row must contain all digits from 1 to 9,
2. every column must contain all digits from 1 to 9,
3. and the matrix is evenly divided into nine 3x3 matrices that must contain
   all digits from 1 to 9.

:var example_sudoku: Test sudoku.
"""
from __future__ import division
import copy

__author__ = "Marc 'BlackJack' Rintsch"
__version__ = '0.1.0'
__date__ = '$Date: 2005-06-08 21:29:06 +0200 (Wed, 08 Jun 2005) $'
__revision__ = '$Rev: 696 $'

__docformat__ = 'reStructuredText'


example_sudoku = [[0, 6, 0,  1, 0, 4,  0, 5, 0],
                  [0, 0, 8,  3, 0, 5,  6, 0, 0],
                  [2, 0, 0,  0, 0, 0,  0, 0, 1],
                  
                  [8, 0, 0,  4, 0, 7,  0, 0, 6],
                  [0, 0, 6,  0, 0, 0,  3, 0, 0],
                  [7, 0, 0,  9, 0, 1,  0, 0, 4],
                  
                  [5, 0, 0,  0, 0, 0,  0, 0, 2],
                  [0, 0, 7,  2, 0, 6,  9, 0, 0],
                  [0, 4, 0,  5, 0, 8,  0, 7, 0]]


class Sudoku:
    """A `Sudoku` instance knows the matrix and keeps track of constraints
    for all fields.
    
    :ivar rows: constraints for rows.
    :ivar columns: constraints for columns.
    :ivar fields: constraints for 3x3 sub-matrices.
    :ivar numbers: the matrix.
    :type rows columns: [set]
    :type fields: [[set]]
    :type numbers: [[int]]
    """
    def __init__(self, values=None):
        """Creates a Sudoku matrix.
        
        If no value matrix is passed in, an empty matrix is created.
        
        :param values: value matrix.
        :type values: [[int]]
        """
        numbers = xrange(1, 10)     # 1-9
        self.rows = [set(numbers) for dummy in numbers]
        self.columns = [set(numbers) for dummy in numbers]
        self.fields = [[set(numbers) for dummy in xrange(3)]
                       for dummy in xrange(3)]
        self.numbers = copy.deepcopy(values)
        if self.numbers is None:
            self.numbers = [[0] * 9 for dummy in numbers]
        self._prepare()
    
    def _prepare(self):
        """Sets constraints for the values of `self.numbers`."""
        for row_nr, row in enumerate(self.numbers):
            for column_nr, value in enumerate(row):
                coordinate = (row_nr, column_nr)
                if value != 0:
                    self[coordinate] = value

    def __setitem__(self, (row, column), value):
        # 
        # Update constraints and set value.
        # 
        self.rows[row].remove(value)
        self.columns[column].remove(value)
        self.fields[row // 3][column // 3].remove(value)
        self.numbers[row][column] = value
    
    def __delitem__(self, (row, column)):
        # 
        # Update constraints and delete value.
        # 
        value = self.numbers[row][column]
        assert value != 0
        self.rows[row].add(value)
        self.columns[column].add(value)
        self.fields[row // 3][column // 3].add(value)
        self.numbers[row][column] = 0
    
    def iter_empty_fields(self):
        """Iterates over the empty fields.
        
        :rtype: iterable of (row, column)
        """
        for row_nr, row in enumerate(self.numbers):
            for column_nr, value in enumerate(row):
                if value == 0:
                    yield (row_nr, column_nr)
    
    def get_candidates(self, (row, column)):
        """Gets all possible values for given `row` and `column`.
        
        :returns: the intersection of unused values in the row, in the column,
            and the 3x3 field that contains the field (`row`, `column`).
        :rtype: iterable
        """
        return (self.rows[row] &
                self.columns[column] &
                self.fields[row // 3][column // 3])


def solve(values):
    """Finds all solutions for the given `values` matrix.
    
    :param values: a sudoku matrix with some pre-filled values.
    :type values: [[int]]
    
    :returns: all solutions.
    :rtype: [[int]]
    """
    results = list()
    constraints = Sudoku(values)
    empty_fields = list(constraints.iter_empty_fields())
    
    def solve_recursive(current_field=0):
        """Finds all solutions recursivly."""
        # 
        # If all fields are filled, add the solution to `results`.
        # 
        if current_field == len(empty_fields):
            results.append(copy.deepcopy(constraints.numbers))
            return
        # 
        # Test all possible values for the `current_field` and recurse.
        # 
        coordinate = empty_fields[current_field]
        for value in constraints.get_candidates(coordinate):
            constraints[coordinate] = value
            solve_recursive(current_field + 1)
            del constraints[coordinate]
    
    solve_recursive()
    return results


def main():
    """Test."""
    print solve(example_sudoku)


if __name__ == '__main__':
    main()
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@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

@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
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

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 (former) Modvoice
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@Leonidas

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

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.

Code: Alles auswählen

def reduceSu(c,Sudoku1):
    for x in xrange(su_len):
        xq=(x/3)*3
        for y in xrange(su_len):
            yq=(y/3)*3
            if not len(Sudoku1[x][y])-1:
                xy=Sudoku1[x][y][0]
                for i in xrange(su_len):
                    try:    ## clear vertical 
                        if i != x: Sudoku1[i][y].remove(xy)
                    except ValueError: pass    
                    try:    ## clear horizontal
                        if i != y: Sudoku1[x][i].remove(xy)
                    except ValueError: pass
                    
                    qx,qy=divmod(i,3)
                    xx,yy = xq+qx,yq+qy
                    try:    ## clear square
                        if (xx,yy) != (x,y): Sudoku1[xx][yy].remove(xy)
                    except ValueError: pass    

    cs=countSu(Sudoku1)
    if c!=cs:
        c=cs
        return reduceSu(c,Sudoku1)
    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.
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

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!

Code: Alles auswählen

su_len=len(Sudoku1)
## convert all values to list
for x in xrange(su_len):
    for y in xrange(su_len):
        if Sudoku1[x][y] == 0: Sudoku1[x][y]=range(1,su_len+1)
        else: Sudoku1[x][y]=[Sudoku1[x][y]]
            
def countSu(Sudoku1):
    "sum all possible values for check"
    printxl=[]
    printyl=[]
    for x in xrange(su_len):
        printlx=[]
        printly=[]
        printtlist=[]
        for y in xrange(su_len):
            printlx.append(len(Sudoku1[x][y]))
            #printly.append(len(Sudoku1[y][x]))
            #printtlist.append((y+1,Sudoku1[x][y]))
        printxl.append(sum(printlx)-su_len)
        #printyl.append(sum(printly)-su_len)
        #print printtlist
    #print "horizontal sum",sum(printxl),printxl  
    #print "vertical sum",sum(printyl),printyl  
    return sum(printxl)

def reduceSu(c,Sudoku1):
    "iter over all fields"
    for x in xrange(su_len):
        xq=(x/3)*3
        contain=[[i] for i in xrange(1,su_len+1)]    ## clear container
        for y in xrange(su_len):
            yq=(y/3)*3
            if not len(Sudoku1[x][y])-1:
                xy=Sudoku1[x][y][0]
                contain[xy-1].extend([xy]*2)   ## mark container 
                for i in xrange(su_len):
                    try:    ## clear vertical 
                        if i != x: Sudoku1[i][y].remove(xy)
                    except ValueError: pass    
                    try:    ## clear horizontal
                        if i != y: Sudoku1[x][i].remove(xy)
                    except ValueError: pass
                    qx,qy=divmod(i,3)
                    xx,yy = xq+qx,yq+qy
                    try:    ## clear square
                        if (xx,yy) != (x,y): Sudoku1[xx][yy].remove(xy)
                    except ValueError: pass    
            else:  ## fill container with possible values
                for i in Sudoku1[x][y]:
                    contain[i-1].append(y)
        for i in contain:   ## check container for a single value
            if len(i)==2: Sudoku1[x][i[1]]=[i[0]]
    cs=countSu(Sudoku1)
    if c!=cs:
        c=cs
        return reduceSu(c,Sudoku1)
    return Sudoku1
             
print
for x in reduceSu(0,Sudoku1): print x
Schönes Spiel , danke salznase.
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
BlackJack

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

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 ....

Code: Alles auswählen

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

Code: Alles auswählen

Sudoku1 = [
     [7,5,6,1,8,4,3,2,9],
     [1,9,4,6,2,3,7,5,8],
     [3,8,2,9,7,5,4,1,6],
     [9,3,1,7,5,6,2,8,4],
     [8,6,7,4,1,2,9,3,5],
     [2,4,5,8,3,9,6,7,1],
     [5,7,9,2,6,1,8,4,3],
     [4,1,8,3,9,7,5,6,2],
     [6,2,3,5,4,8,1,9,7]]
BlackJack

Und was genau willst Du damit jetzt sagen!?

Zumal da gestern noch ein etwas anderes Sudoku stand was nicht lösbar war weil die Ausgangssituation schon die Regeln verletzte.
ramin
User
Beiträge: 8
Registriert: Sonntag 15. Mai 2005, 15:07

Naja, was ich sagen will: dieses Script scheint nur einfache Sudokus zu lösen - falls ich es unverständlich ausgedrückt haben sollte. Deshalb al Beispiel ein Sudoku, welches ein Mensch lösen kann (siehe Lösung) allerdings dieses Script nicht - weshalb ich meinte, dass da wohl noch etwas fehlt.

Sorry, dass ich mich beim Abtippen des Beispiel-Sudoku einmal verschrieben habe, ist aber mittlerweile wie festgestellt korrigiert.
BlackJack hat geschrieben:Und was genau willst Du damit jetzt sagen!?

Zumal da gestern noch ein etwas anderes Sudoku stand was nicht lösbar war weil die Ausgangssituation schon die Regeln verletzte.
BlackJack

Mein Skript löst das Sudoku. Und muss wohl auch nicht weiter optimiert werden bei ca. 0.2 Sekunden auf einem "lahmen" Athlon mit 1 Ghz.

Code: Alles auswählen

bj@s8n:~/src/cvs/sandbox> time ./sudoku.py
[[[7, 5, 6, 1, 8, 4, 3, 2, 9],
 [1, 9, 4, 6, 2, 3, 7, 5, 8],
 [3, 8, 2, 9, 7, 5, 4, 1, 6],
 [9, 3, 1, 7, 5, 6, 2, 8, 4],
 [8, 6, 7, 4, 1, 2, 9, 3, 5],
 [2, 4, 5, 8, 3, 9, 6, 7, 1],
 [5, 7, 9, 2, 6, 1, 8, 4, 3],
 [4, 1, 8, 3, 9, 7, 5, 6, 2],
 [6, 2, 3, 5, 4, 8, 1, 9, 7]]]

real    0m0.197s
user    0m0.167s
sys     0m0.021s
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Tatsächlich bin ich auch fehlerhaft.
Du/Ihr habt vollkommen Recht.
Ich hatte mir damals schon fast gedacht, dass es nicht vollständig ist.
Ich bin mir ziemlich sicher dass der Artikel über Sudoku damals in Wikipedia nicht so ausführlich war. Demnach habe ich die Schnittmengen-Methode angewandt.
Glücklicher weise ist auch das letzte schwere(eindeutige) Sudokurätsel(von ramin) nach dieser Methode(ohne würfeln u Backtracking-Methode) lösbar, nachdem ich einen weiteren Kombinations-Schritt meinem Script hinzugefügt habe.
Mein Script darf natürlich nach belieben verwendet werden(zB als Referenz mehrerer Lösungswege).
[edit]
Leider kann es (immer noch) nicht die ganz schweren Sudokus lösen.
[/edit]
Noch eine Erklärung zu dem letzten Kombinationsschritt; Nachdem der Iterationsschritt keine einelementigen Kandidaten mehr erbrachte, habe ich eine Kandidatenmenge aus noch möglichen Zweierpaaren gesammelt und überprüft ob sie sich in x und y Reihe überschneiden(Quadrat wäre auch noch möglich). Dies war einzig in dem Feld 7,7 der Fall womit ich wieder ein einelementiges Feld[8] hatte, usw.
(Die container Variable wird praktisch erst nach dem 2. Funktionsdurchlauf nützlich.)

Nochmal das komplette Script; (falls es fehlerhaft ist werde ich es löschen :? und durch ein besseres ersetzen :P)

Code: Alles auswählen

from copy import deepcopy

Sudoku2="""
4.6.5.12.
...4....8
.92....7.
.2..8....
7..1.3..6
....9..4.
.1....56.
2....5...
.45.1.3.2
""" #4_6_5_12_+___4____8+_92____7_+_2__8____+7__1_3__6+____9__4_+_1____56_+2____5___+_45_1_3_2

numbers=[]
for data in Sudoku2.splitlines(9):
    row=[]
    if len(data)>8:
        for value in data: 
            if value.isdigit(): row.append(int(value))
            elif value=="." or value=="x": row.append(0)
        numbers.append(row)
Sudoku1=numbers    
su_len=len(Sudoku1)

class Sudoku:

    def __init__(self, values=None):
        self.Sudoku1=values
        for x in self.Sudoku1: print x
        givenValues=0
        self.contain=[[i] for i in xrange(1,su_len+1)] ## make empty container
        for x in xrange(su_len):    ## convert all values to list
            for y in xrange(su_len):
                if not self.Sudoku1[x][y]: self.Sudoku1[x][y]=range(1,su_len+1)
                else:
                    self.Sudoku1[x][y]=[self.Sudoku1[x][y]]
                    givenValues+=1
        print "given values =",givenValues
        self.reduceSu(0)

    def countSu(self):
        " sum all possible values for check "
        printxl,printyl=[],[]
        for x in xrange(su_len):
            printlx,printly,printtlist=[],[],[]
            for y in xrange(su_len):
                printlx.append(len(self.Sudoku1[x][y]))
                printly.append(len(self.Sudoku1[y][x]))
                printtlist.append((y+1,self.Sudoku1[x][y]))
            printxl.append(sum(printlx)-su_len)
            printyl.append(sum(printly)-su_len)
            print printtlist
        print "horizontal sum",sum(printxl),printxl  
        print "vertical sum",sum(printyl),printyl
        return sum(printxl)

    def NakedSingle(self,x,y,xq,xy,yq):
        """Method-A For Sole Candidate"""
        for i in xrange(su_len):
            if i!=x: self._remove(xy,i,y)    ## clear vertical
            if i!=y: self._remove(xy,x,i)    ## clear horizontal
            qx,qy=divmod(i,3)
            xx,yy=xq+qx,yq+qy
            if (xx,yy)!=(x,y): self._remove(xy,xx,yy)  ## clear square
    
    def reduceSu(self,c):
        """ Iter over all fields and search single values """
        for x in xrange(su_len):
            xq,xqr=divmod(x,3)
            xq,xqr=xq*3,xqr*3
            h_xcontain=deepcopy(self.contain)   ## reset the 3 containers
            h_ycontain=deepcopy(self.contain)   ## for Hidden Single/Subsets
            h_qcontain=deepcopy(self.contain)
            h2_xSubset,h2_ySubset,h2_qSubset,h_qpair=[],[],[],[]  ## Method C2(Hidden Subset)
            for y in xrange(su_len):
                xy,yx,yq=self.Sudoku1[x][y],self.Sudoku1[y][x],(y/3)*3
                if not len(xy)-1:    ## Method-A1 Naked Single Number
                    h_xcontain[xy[0]-1].extend(xy*3)   ## mark container
                    self.NakedSingle(x,y,xq,xy[0],yq)
                else:   ## fill container with possible values
                    for i in xy: h_xcontain[i-1].append(y)
                if not len(yx)-1: h_ycontain[yx[0]-1].extend([yx[0]]*3)   ## mark
                else:
                    for i in yx: h_ycontain[i-1].append(y)
                qx,qy=divmod(y,3)
                xx,yy=xq+qx,xqr+qy
                xxyy=self.Sudoku1[xx][yy]
                if not len(xxyy)-1: h_qcontain[xxyy[0]-1].extend([xxyy[0]]*3)   ## mark
                else:
                    for i in xxyy: h_qcontain[i-1].append((xx,yy))  ## end A1      
            for i in xrange(su_len):   ## check containers for sole/double values
                ## Solve Method A2 (Hidden Single)
                if len(h_xcontain[i])==2: self.Sudoku1[x][h_xcontain[i][1]]=[i+1]
                elif len(h_xcontain[i])==3: ## hidden double value
                    h2_xSubset+=[(h_xcontain[i][1],h_xcontain[i][2],i+1)]
                if len(h_ycontain[i])==2: self.Sudoku1[h_ycontain[i][1]][x]=[i+1]
                elif len(h_ycontain[i])==3:
                    h2_ySubset+=[(h_ycontain[i][1],h_ycontain[i][2],i+1)]
                if len(h_qcontain[i])==2:    ## hidden single square-value
                    self.Sudoku1[h_qcontain[i][1][0]][h_qcontain[i][1][1]]=[i+1]
                ## End /Method-A /
                elif len(h_qcontain[i])==3:   ## double possible values
                    (x1,y1),(x2,y2)=h_qcontain[i][1],h_qcontain[i][2]
                    h2_qSubset+=[(h_qcontain[i][0],x1,y1,x2,y2)]
           ## Solve Method-B1 FIXME - Block/Block and Column/Row Interactions        
            for xy,x1,y1,x2,y2 in h2_qSubset:
                if x1==x2:  ## clear horizontal
                    for j in xrange(su_len): 
                        if y1>j or j>y2: self._remove(xy,x1,j)
                elif y1==y2: ## clear vertical
                    for j in xrange(su_len):
                        if x1>j or j>x2: self._remove(xy,j,y1)
            ## End/B Begin Solve Method-C2 - Hidden Subset
            ## If two cells in the same row/column/block have only the same two candidates,
                else: h_qpair+=[(x1,y1,x2,y2,xy)]
            for i in xrange(len(h_qpair)-1):
                h2=[j for j in h_qpair[i+1:] if h_qpair[i][:-1]==j[:-1]]
                if h2:
                    for x1,y1 in (h_qpair[i][:2],h_qpair[i][2:4]): self.Sudoku1[x1][y1]=[h_qpair[i][-1],h2[0][-1]]
            for i in xrange(len(h2_xSubset)-1):
                h2=[j for j in h2_xSubset[i+1:] if h2_xSubset[i][:2]==j[:2]]
                if h2:
                    for h2_y in h2[0][:2]: self.Sudoku1[x][h2_y]=[h2_xSubset[i][2],h2[0][-1]]
            for i in xrange(len(h2_ySubset)-1):
                h2=[j for j in h2_ySubset[i+1:] if h2_ySubset[i][:2]==j[:2]]
                if h2:
                    for h2_x in h2[0][:2]: self.Sudoku1[h2_x][x]=[h2_ySubset[i][2],h2[0][-1]]
            ## End/ Method-C2
        cs=self.countSu()
        if c!=cs: return self.reduceSu(cs)
        ## FIXME Method-D? 
        for x in  xrange(su_len): ## remove low candidates from 3*square
            xq=x/3*3
            for x3 in  xrange(0,su_len,3):
                qx3_ls,qy3_ls=[],[]
                for y3 in  xrange(x3,3+x3):

                    if 1<len(self.Sudoku1[x][y3])<4: qx3_ls+=self.Sudoku1[x][y3]
                    if 1<len(self.Sudoku1[y3][x])<4: qy3_ls+=self.Sudoku1[y3][x]
                qx3_ls=self._comSquare(qx3_ls,x,xq,x3)
                qy3_ls=self._comSquare(qy3_ls,x,xq,x3)
                for xy,xx,yy in qx3_ls: self._remove(xy,xx,yy)
                for xy,xx,yy in qy3_ls: self._remove(xy,yy,xx)
        cs=self.countSu()
        if c!=cs: return self.reduceSu(cs)
        return

    def _comSquare(self,qx3_ls,x,xq,x3):
        qx3set,qxy3=set(qx3_ls),[]
        if len(qx3_ls)>6 and len(qx3set)==3 or len(qx3_ls)==4 and len(qx3set)==2:
            for r in xrange(su_len):
                r1,r2=divmod(r,3)
                if r1+xq!=x: qxy3+=[[v,r1+xq,r2+x3] for v in qx3set]
        return qxy3

    def _remove(self,nr,xr,yr):
        try: self.Sudoku1[xr][yr].remove(nr) #;print nr,"removed from ",xr,yr
        except ValueError: return

print   ## solution
for x in Sudoku(Sudoku1).Sudoku1:
    c=[]
    for y in x:
        if len(y)-1: c.append(y)
        else: c+=y
    print c
[edit]
Einen anderen Datentyp als "list" zu nehmen, lohnt sich glaube ich nicht bei der Kurze der Listen. Ich wüsste jetzt auch nicht, wo ich "yield" verwenden könnte.
Zuletzt geändert von Olliminatore am Dienstag 1. November 2005, 18:45, insgesamt 1-mal geändert.
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
Olliminatore
User
Beiträge: 55
Registriert: Montag 30. Mai 2005, 16:03
Wohnort: schönsten Stadt Deutschlands
Kontaktdaten:

Ich hätte nie gedacht, dass Sudoku so komplex wird wenn man es logisch lösen will. So viele Techniken/Methoden sind notwendig um schwere Sudokus (logical no"guess") zu lösen. Auf englischen Seiten stößt man auf Begriffe wie Seafood, X-Wing, Swordfish, Jellyfish, Squirmbag...
(Die eben genannten Techniken sind nicht in meinem Script implementiert, nur die Einfachsten.)
Es hat auch noch niemand alle Methoden gefunden(um alle zu lösen). Hier ein Paar Links die sich damit beschäftigen:

Sudoku Solver Group by logic
Technik Erläuterungen
Sudoku Programmers Forum
(Dort im Forum ist auch der deutsche Autor des auf Wikipedia verlinkten Sudoku-Solvers.)

Mein obiges Script ist auch in soweit noch nicht fertig, dass es "Dreier Paare" in der Methode-B/C erkennt. Ich bin auch bloß ein Hobby Programmierer und habe mein PythonWissen von hier, es war faszinierend, man hat nachgedacht, dazu gelernt, es hat Spaß gemacht. (Würde mich freuen wenn jemand drauf aufbaut oder weiter führt und zeigt wie gut Python ist.) Meine Freunde haben mir leider verboten weiter zu machen.
Ende
[size=84][url=http://de.wikipedia.org/wiki/Jamba]Love Jamba[/url] <!--Olliminatore-->input<?/> [url=http://www.spreeblick.com/blog/index.php?p=324]Boycott Jamba[/url][code]def olliminiert(optimiert, eliminiert, terminiert):[/code][/size]
Antworten