SuDoKu Solver

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • SuDoKu Solver

    Ich hatte das Problem mal in (prozeduralem) C++ (oder ist das doch eher C?) rekursiv gelöst (sollte Backtracking sein ;) ) (christoph.sf-ogame.de/Entwicklung/sudoku.cpp

    Jetzt wollte ich das ohne rekursion in Python angehen, das ganze funktioniert erst fast ;) ich poste mal trotzdem den Code, morgen kommt dann hoffentlich eine funktionierende Version wenn ich den Fehler finde ...

    sudoku.py

    Quellcode

    1. #!/usr/bin/python
    2. # -*- coding: utf-8 -*-
    3. #Backtracking Algorithmus zum Lösen von SuDoKus
    4. #© Christoph Egger
    6. def print_actual(feld):
    7. for line in feld:
    8. for col in line:
    9. print col,
    10. print ""
    12. def read_sudoku(filename):
    13. feld = []
    14. f = file(filename, "r")
    15. data = f.read()
    16. tmp1 = data.splitlines()
    17. for a in tmp1:
    18. feld.append(a.split())
    19. return feld
    21. def test_colum(no, feld):
    22. found = []
    23. for n in feld:
    24. if n[no] != "0":
    25. if n[no] not in found:
    26. found.append(n[no])
    27. else:
    28. return False
    29. return True
    31. def test_row(no, feld):
    32. found = []
    33. for n in feld[no]:
    34. if n != "0":
    35. if n not in found:
    36. found.append(n)
    37. else:
    38. return False
    39. return True
    41. def test_quad(qcol, qrow, feld):
    42. found = []
    43. for trow in feld[(qrow*3):((qrow*3)+3)]:
    44. for tcol in trow[(qcol*3):((qcol*3)+3)]:
    45. if tcol != "0":
    46. if tcol not in found:
    47. found.append(tcol)
    48. else:
    49. return False
    50. return True
    52. def find_next_empty(feld):
    53. for a in feld:
    54. for b in a:
    55. if b == "0":
    56. return (feld.index(a), a.index(b))
    57. return (-1, -1)
    59. def solve_sudoku(feld):
    60. stack = []
    61. solutions = []
    62. start = 1
    63. while True:
    65. pos = find_next_empty(feld)
    66. if pos[0] == -1:
    67. solutions.append(feld)
    68. print "Lösung gefunden: "
    69. print_actual(feld)
    70. print " "
    71. if len(stack):
    72. tmp = stack.pop()
    73. feld[tmp[0][0]][tmp[0][1]] = "0"
    74. start = tmp[1] + 1
    75. else:
    76. return solutions
    77. else:
    78. for num in range(start, 10):
    79. feld[pos[0]][pos[1]] = str(num)
    80. if not test_colum(pos[1], feld):
    81. feld[pos[0]][pos[1]] = "0"
    82. continue
    83. if not test_row(pos[0], feld):
    84. feld[pos[0]][pos[1]] = "0"
    85. continue
    86. if not test_quad(pos[1]/3, pos[0]/3, feld):
    87. feld[pos[0]][pos[1]] = "0"
    88. continue
    89. stack.append((pos, num))
    90. start = 1
    91. break
    92. else:
    93. if len(stack):
    94. tmp = stack.pop()
    95. feld[tmp[0][0]][tmp[0][1]] = "0"
    96. start = tmp[1] + 1
    97. else:
    98. return solutions
    Alles anzeigen

    start_sudoku.py

    Quellcode

    1. #!/usr/bin/python
    2. # -*- coding: utf-8 -*-
    3. #Startet den Backtracker zum Lösen des Sudokus
    4. #© Christoph Egger
    6. import sudoku
    7. import sys
    9. if len(sys.argv) == 1:
    10. print "Der Script erwartet den Dateinamen des zu lösenden SuDoKus als Argument"
    11. else:
    12. feld = sudoku.read_sudoku(sys.argv[1])
    13. sudoku.print_actual(feld)
    14. print type(feld[0][0])
    15. print ""
    16. res = sudoku.solve_sudoku(feld)
    17. if len(res) > 1:
    18. print "Das SuSoKu ist mehrdeutig!"
    19. print "es existieren", len(res), "Lösungen!"
    20. elif len(res) == 0:
    21. print "Das SuDoKu besitzt keine Lösung!"
    22. else:
    23. print "Das SuDoKu ist eindeutig lösbar!"
    Alles anzeigen


    Die SuDoKus haben folgende Form:
    test.sudoku

    Quellcode

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


    EDIT://
    Fehler behoben

    EDIT://
    Einrückung wiederhergestellt, scheint bei Editieren nicht erhalten zu bleiben ...
    There are only 10 types of people in the world: Those who understand binary, and those who don't.

    Download meines ersten Spiels:HIER
    Über Feedback würde ich mich freuen ;)

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von darthdespotism ()

  • Auf irgendeine Weise findet es die erste (und wohl einzigste Lösung) aber versucht danach nicht, weitere Lösungen zu finden und beendet sich auch nicht am Ende ...

    Hat jemand eine Idee?

    Um genau zu sein unterscheiden sich die Lösungen sogar ...

    EDIT://
    Ich bekomme 600 Lösungen für ein normales SuDoKu gemeldet. Das kann eigentlich nicht sein oder?
    There are only 10 types of people in the world: Those who understand binary, and those who don't.

    Download meines ersten Spiels:HIER
    Über Feedback würde ich mich freuen ;)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von darthdespotism ()

  • Hm ja ein gutes SuDoKu sollte nur eine Lösung haben.

    Mein Programm liefert mir für SuDoKus aus der Zeitung und aus diversen Heften 400 - 600 Lösungen. Ich denke mal da muss ich noch auf Fehlersuche gehen?

    Der nächste Schritt wird es sein, SuDoKus zu erstellen, ich hab da schon so eine Idee ;) aber jetzt muss erstmal der Fehler gefunden werden. (Werd ich selber angehen und mir hier keine Vorschläge holen, in der Hoffnung dabei noch was zu lernen)

    EDIT://
    Das von dir verlinkte Programm schau' ich mir trotzdem gleich mal an

    EDIT:///
    Scheint ein Fehler in der Regel für die Quads zu sein

    EDIT:////
    Fehler gefunden: wenn ich teile eines Array mit [:] wähle muss der 2. Wert eines hinter das letzte erwünschte Item verweisen.
    There are only 10 types of people in the world: Those who understand binary, and those who don't.

    Download meines ersten Spiels:HIER
    Über Feedback würde ich mich freuen ;)

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von darthdespotism ()