[Python-de] Sudoku mit Python

Mathias Uebel mathias.uebel at meeloon.de
Fre Aug 4 00:30:59 CEST 2006


grassi schrieb:
> Hallole,
> 
> Mathias Uebel schrieb:
> 
>>wenn ich Langeweile habe, übe ich mich in Python.
> 
> löblich ;-)
> 
> 
>>Ich habe jetzt mal so etwas gemacht:
>>http://www.meeloon.de/sudoku/index.cgi
>>Hat jemand mal Lust den Code zu prüfen?
> 
> Ich würde ihn mir gern mal anschauen, ob ich zu kommentieren in der
> Lage bin sei dahin gestellt.

[...]

> Sieht auf den ersten Blick so aus, als ob der Server 50 Sekunden
> "rödelt", wenn ich auf Submit drücke, ohne was einzugeben. 

[...]
Ja, es rödelt ganz schön. Man kann die Schleifen begrenzen. Meine 
Versuche haben gezeigt, dass es mit ca. 10-15 Durchläufe erledigt ist. 
Darum habe ich eine Max von 50 eingegeben.
Jetzt habe ich ein Demo eingerichtet (Zahlenvorgabe).

Ich weiss, dass html als Interface nicht geeignet ist. Ein GUI kommt noch.

Hier die Klasse:

#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-
#
# copyright mathias.uebel at meeloon.de
#

"""
	Sudoku
	--------------------------------------------------------------
	|  x  |  6  |  4  |  5  |  x  |  9  |  2  |  3  |  x  |
	--------------------------------------------------------------
	|  8  |  x  |  3  |  x  |  4  |  x  |  6  |  x  |  1  |
	--------------------------------------------------------------
	|  1  |  2  |  x  |  3  |  x  |  6  |  x  |  4  |  5  |
	--------------------------------------------------------------
	|  5  |  x  |  7  |  x  |  2  |  x  |  8  |  x  |   4  |
	--------------------------------------------------------------
	|  x  |  1  |  x  |  8  |  x  |  5  |  x  |  6  |   x  |
	--------------------------------------------------------------
	|  6  |  x  |  8  |  x  |  7  |  x  |  5  |   x  |  9  |
	--------------------------------------------------------------
	|  9  |  8  |  x  |  7  |  x  |  2  |  x  |  5  |   6  |
	--------------------------------------------------------------
	|  2  |  x  |  6  |  x  |  5  |  x  |  1  |  x  |   3  |
	--------------------------------------------------------------
	|  x  |  4  |  5  |  1  |   x  |  8  |  9    7  |  x  |
	--------------------------------------------------------------


"""

import sys

class sudoku:
	"""
Diese Klasse nimmt ein Dictionary mit 81 Wertepaaren((int,int):int) auf, 
z.B.{(0,0):3,(1,1):5,...}
Die Schluessel sind die Sudoku-Koordinaten, die Values sind die 
vorhandenen Werte.
Die Methode 'Scan' scannt dann die Matrix und gibt ein Dictionary mit 
den moeglichen Treffern zurueck.
Treffer sind die Werte-Paare, welche fuer jede gegebene Ziffer einer 
Zelle nur eine Moeglichkeit ergibt (ScanLevel, default = 1).
Die Methode 'Result' gibt des Ergebnis von 'MaxTries' Versuche aus 
(default sind 100 Versuche).


table
           col0  col1  col2    col3  col4  col5    col6  col7  col8
          -----------------------------------------------------------
row0     ||field|field|field||       ----       |       ----       |
row1     ||field|field|field||       cell       |       cell       |
row2     ||field|field|field||       ----       |       ----       |
          -----------------------------------------------------------
row3     |       ----       |        ----       |       ----       |
row4     |       cell       |        cell       |       cell       |
row5     |       ----       |        ----       |       ----       |
          -----------------------------------------------------------
row6     |       ----       |        ----       |       ----       |
row7     |       cell       |        cell       |       cell       |
row8     |       ----       |        ----       |       ----       |
          -----------------------------------------------------------


	def __init__(self, TableDict):
		""" Initialisierung """
		self.table = TableDict or list
		# Abbruch, wenn das Dictionary nicht genug Daten hat
		if len(self.table) is not 81:
			sys.exit('zu wenig oder zu viel daten an "class table" uebergeben')

	def _Zero(self):
		""" Koordinaten fuer Nullen feststellen """
		list = []
		Keys = self.table.keys()
		Keys.sort()
		for a in Keys:
			if self.table[a] == 0:
				list.append(a)
				#print self.table[a][b]
		return list

	def _RangeRow(self, n):
		""" die Zeilen der Zelle 'n' """
		if n in [0,1,2]:
			Range = [0,1,2]
		if n in [3,4,5]:
			Range = [3,4,5]
		if n in [6,7,8]:
			Range = [6,7,8]
		return Range

	def _RangeCol(self, n):
		""" die Spalten der Zelle 'n' """
		if n in [0,3,6]:
			Range = [0,1,2]
		if n in [1,4,7]:
			Range = [3,4,5]
		if n in [2,5,8]:
			Range = [6,7,8]
		return Range

	def Cell(self,n=0):
		"""Ermittelt die Werte einer Zelle 'n=0' """
		list = []
		for a in self._RangeRow(n):
			for b in self._RangeCol(n):
				list.append(self.table[(a,b)])
		return list

	def Row(self,n=0):
		"""Ermittelt die Werte einer Reihe 'n=0' """
		list = []
		for a in range(9):
			list.append(self.table[(n,a)])
		return list

	def Col(self,n=0):
		"""Ermittelt die Werte einer Spalte 'n=0' """
		list = []
		for a in range(9):
			list.append(self.table[(a,n)])
		return list

	def ValueFailt(self,n):
		"""print Liste: Welche Werte fehlen?"""
		list = []
		for a in range(1,10):
			if a not in self.Cell(n):
				list.append(a)			
		return list

	def Scan(self,ScanLevel = 1):		
		""" Scannt alle Reihen und Spalten """
		out = []
		for n in range(9):									# alle Zellen werden gescannt
			dict = {}
			for a in self.ValueFailt(n):						# Die Liste der fehlenden Felder 
abarbeiten
				z = 0
				list = []
				for b in self._RangeRow(n):					# Tabelle nach Reihen einlesen
					if a not in self.Row(b):					# Reihe auf fehlende Werte scannen
						for c in self._RangeCol(n):			# Tabelle nach Spalten einlesen
							if a not in self.Col(c):			# Spalte auf fehlende Werte scannen
								if (b,c) in self._Zero():		# nur gueltig, wenn es eine leere 
0-Stelle ist
									#list.append(("%s" % (b+1, 
['A','B','C','D','E','F','G','H','I'][c])))
									list.append((b,c))		# die Koordinaten in eine Liste geben
									z = z + 1				# Anzahl der moeglichen Treffer zaehlen								z = 
z + 1					# Anzahl der moeglichen Treffer zaehlen
				if len(list) <= ScanLevel:						# ScanLevel='1': nur die die Felder 
mit einer x,y Uebereinstimmung
					dict[a]=list
			out.append(dict)								# gibt Dictionary mit x,y Uebereinstimmungen 
zurueck
		return out

	def Result(self, MaxTries = 100):
		"""Arbeitet die Scanvorgaenge bis maximal 'MaxTries' durch.
		    Gibt die Anzahl der Versuche zurueck."""
		z = 0
		while z < MaxTries:									# maximale Schleifen
			for a in self.Scan():
				for b in a.keys():
					d = a[b]
					#dict = {a[b] : b}
					for w in d:
						Dict = {w:b}
						#print Dict
						self.table.update(Dict)
			if len(self._Zero()) == 0:
				break
			z = z + 1
		return z

	def __str__(self):
		str = ""
		z = 0
		Keys = self.table.keys()
		Keys.sort()
		for a in Keys:
			if z%9 == 0:	str = str + "\n"
			str = str + "  %s " % self.table[a]
			z = z + 1
		return str



More information about the python-de mailing list