r4520 - in developers/erin_yueh/pythonEFL-sudoku: data data/image data/puzzle src/sudoku
erin_yueh at docs.openmoko.org
erin_yueh at docs.openmoko.org
Wed Jul 9 18:45:19 CEST 2008
Author: erin_yueh
Date: 2008-07-09 18:45:19 +0200 (Wed, 09 Jul 2008)
New Revision: 4520
Added:
developers/erin_yueh/pythonEFL-sudoku/data/image/dummy.png
developers/erin_yueh/pythonEFL-sudoku/data/pythonEFL-sudoku.desktop
developers/erin_yueh/pythonEFL-sudoku/src/sudoku/generator.py
Removed:
developers/erin_yueh/pythonEFL-sudoku/data/puzzle/solver.py
developers/erin_yueh/pythonEFL-sudoku/data/puzzle/sudoku.py
Log:
update sudoku.desktop and add generotor, solver script (Erin Yueh)
Added: developers/erin_yueh/pythonEFL-sudoku/data/image/dummy.png
===================================================================
(Binary files differ)
Property changes on: developers/erin_yueh/pythonEFL-sudoku/data/image/dummy.png
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Deleted: developers/erin_yueh/pythonEFL-sudoku/data/puzzle/solver.py
===================================================================
--- developers/erin_yueh/pythonEFL-sudoku/data/puzzle/solver.py 2008-07-09 16:13:51 UTC (rev 4519)
+++ developers/erin_yueh/pythonEFL-sudoku/data/puzzle/solver.py 2008-07-09 16:45:19 UTC (rev 4520)
@@ -1,252 +0,0 @@
-#!/usr/bin/python
-
-import sys
-
-class SudokuSolver:
- def __init__(self):
- self.puzzle = None
-
- self.row = [False] * 90
- self.col = [False] * 90
- self.grp = [False] * 90
-
- self.steps = []
- for i in xrange(9):
- self.steps.append([])
-
- self.scores = [-1] * 81
-
- self.tries = []
- for i in xrange(81):
- self.tries.append([])
-
- self.relatives = []
- for r in xrange(9):
- for c in xrange(9):
- tmp = []
- for x in xrange(9):
- if x != c:
- tmp.append(r * 9 + x)
- for y in xrange(9):
- if y != r:
- tmp.append(y * 9 + c)
- gr = (r / 3) * 3
- gc = (c / 3) * 3
- for y in xrange(gr, gr + 3):
- for x in xrange(gc, gc + 3):
- if y != r and x != c:
- tmp.append(y * 9 + x)
-
- self.relatives.append(tmp)
-
- def _verify(self):
- print "verify"
- for r in xrange(9):
- for c in xrange(9):
- s = self.scores[r * 9 + c]
- if s == -1:
- continue
-
- tmp = []
- for n in xrange(1, 10):
- if not (self.row[r * 10 + n] or self.col[c * 10 + n] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + n]):
- tmp.append(n)
-
- if len(tmp) - 1 != s:
- print "(%d, %d) has score %d, instead of %d" % (r, c, len(tmp) - 1, s)
- return False
-
-
- old = self.tries[r * 9 + c][:]
- old.sort()
- if old != tmp:
- print "(%d, %d) has tries", tmp, "instead of", old
-
- try:
- self.steps[s].index(r * 9 + c)
- except:
- print "(%d, %d) @ %d is not a step" % (r, c, s)
- return False
-
- return True
-
- def _try(self, pos, n):
- positions = []
- for p in self.relatives[pos]:
- if self.scores[p] >= 0 and n in self.tries[p]:
- if len(self.tries[p]) == 1:
- return False
-
- positions.append(p)
-
- r = pos / 9
- c = pos % 9
- self.row[r * 10 + n] = True
- self.col[c * 10 + n] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + n] = True
-
- self.puzzle[r][c] = n
-
- for p in positions:
- self.tries[p].remove(n)
- s = self.scores[p]
- self.scores[p] -= 1
- self.steps[s - 1][:0] = [p]
- self.steps[s].remove(p)
-
- return True
-
- def _undo(self, pos, n):
- r = pos / 9
- c = pos % 9
- self.row[r * 10 + n] = False
- self.col[c * 10 + n] = False
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + n] = False
-
- self.puzzle[r][c] = 0
-
- for p in self.relatives[pos]:
- old_score = self.scores[p]
- if old_score == -1:
- continue
-
- if n not in self.tries[p]:
- y = p / 9
- x = p % 9
- if not (self.row[y * 10 + n] or self.col[x * 10 + n] or self.grp[((y / 3) * 3 + (x / 3)) * 10 + n]):
- self.tries[p][:0] = [n]
- self.scores[p] += 1
- self.steps[old_score + 1][:0] = [p]
- self.steps[old_score].remove(p)
-
- def _solve(self):
- pos = 81
- for score in xrange(9):
- if self.steps[score]:
- pos = self.steps[score].pop()
- break
- if pos >= 81:
- return True
-
- self.scores[pos] = -1
-
- for n in self.tries[pos]:
- if self._try(pos, n):
- if self._solve():
- return True
- self._undo(pos, n)
-
- self.scores[pos] = score
- self.steps[score].append(pos)
-
- return False
-
- def _analyze(self):
- for i in xrange(90):
- self.row[i] = False
- self.col[i] = False
- self.grp[i] = False
-
- for r in xrange(9):
- for c in xrange(9):
- pos = r * 9 + c
- v = self.puzzle[r][c]
- if v:
- if self.row[r * 10 + v] or self.col[c * 10 + v] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + v]:
- return False
-
- self.row[r * 10 + v] = True
- self.col[c * 10 + v] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + v] = True
-
- self.scores[pos] = -1
-
- for i in xrange(9):
- self.steps[i] = []
-
- for r in xrange(9):
- for c in xrange(9):
- pos = r * 9 + c
- v = self.puzzle[r][c]
- if not v:
- tries = []
- for n in xrange(1, 10):
- if not (self.row[r * 10 + n] or self.col[c * 10 + n] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + n]):
- tries.append(n)
-
- if not tries:
- return False
-
- score = len(tries) - 1
-
- self.tries[pos] = tries
- self.scores[pos] = score
- self.steps[score].append(pos)
-
- while (self.steps[0]):
- pos = self.steps[0].pop()
- r = pos / 9
- c = pos % 9
-
- v = self.tries[pos].pop()
-
- self.row[r * 10 + v] = True
- self.col[c * 10 + v] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + v] = True
- self.puzzle[r][c] = v
-
- self.scores[pos] = -1
-
- for p in self.relatives[pos]:
- s = self.scores[p]
- if s > 0 and v in self.tries[p]:
- self.tries[p].remove(v)
- self.scores[p] -= 1
- self.steps[s - 1][:0] = [p]
- self.steps[s].remove(p)
-
- return True
-
- def solve(self, puzzle):
- self.puzzle = puzzle
-
- if not self._analyze():
- return False
-
- return self._solve()
-
-def parse_file():
- lines = sys.stdin.readlines()
-
- puzzles = []
- for l in lines:
- if (len(l) != 82):
- print "xxx"
- continue
-
- p = []
- for i in xrange(9):
- t = []
- for j in xrange(9):
- t.append(int(l[i * 9 + j]))
- p.append(t)
- puzzles.append(p)
-
- return puzzles
-
-def main():
- solver = SudokuSolver()
- puzzles = parse_file()
-
- for p in puzzles:
- if (solver.solve(p)):
- pass
- for i in xrange(9):
- print p[i]
- print
- else:
- print "no solution"
-
-
-if __name__ == "__main__":
- main()
Deleted: developers/erin_yueh/pythonEFL-sudoku/data/puzzle/sudoku.py
===================================================================
--- developers/erin_yueh/pythonEFL-sudoku/data/puzzle/sudoku.py 2008-07-09 16:13:51 UTC (rev 4519)
+++ developers/erin_yueh/pythonEFL-sudoku/data/puzzle/sudoku.py 2008-07-09 16:45:19 UTC (rev 4520)
@@ -1,252 +0,0 @@
-#!/usr/bin/python
-
-import sys
-
-class SudokuSolver:
- def __init__(self):
- self.puzzle = None
-
- self.row = [False] * 90
- self.col = [False] * 90
- self.grp = [False] * 90
-
- self.steps = []
- for i in xrange(9):
- self.steps.append([])
-
- self.scores = [-1] * 81
-
- self.tries = []
- for i in xrange(81):
- self.tries.append([])
-
- self.relatives = []
- for r in xrange(9):
- for c in xrange(9):
- tmp = []
- for x in xrange(9):
- if x != c:
- tmp.append(r * 9 + x)
- for y in xrange(9):
- if y != r:
- tmp.append(y * 9 + c)
- gr = (r / 3) * 3
- gc = (c / 3) * 3
- for y in xrange(gr, gr + 3):
- for x in xrange(gc, gc + 3):
- if y != r and x != c:
- tmp.append(y * 9 + x)
-
- self.relatives.append(tmp)
-
- def _verify(self):
- print "verify"
- for r in xrange(9):
- for c in xrange(9):
- s = self.scores[r * 9 + c]
- if s == -1:
- continue
-
- tmp = []
- for n in xrange(1, 10):
- if not (self.row[r * 10 + n] or self.col[c * 10 + n] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + n]):
- tmp.append(n)
-
- if len(tmp) - 1 != s:
- print "(%d, %d) has score %d, instead of %d" % (r, c, len(tmp) - 1, s)
- return False
-
-
- old = self.tries[r * 9 + c][:]
- old.sort()
- if old != tmp:
- print "(%d, %d) has tries", tmp, "instead of", old
-
- try:
- self.steps[s].index(r * 9 + c)
- except:
- print "(%d, %d) @ %d is not a step" % (r, c, s)
- return False
-
- return True
-
- def _try(self, pos, n):
- positions = []
- for p in self.relatives[pos]:
- if self.scores[p] >= 0 and n in self.tries[p]:
- if len(self.tries[p]) == 1:
- return False
-
- positions.append(p)
-
- r = pos / 9
- c = pos % 9
- self.row[r * 10 + n] = True
- self.col[c * 10 + n] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + n] = True
-
- self.puzzle[r][c] = n
-
- for p in positions:
- self.tries[p].remove(n)
- s = self.scores[p]
- self.scores[p] -= 1
- self.steps[s - 1][:0] = [p]
- self.steps[s].remove(p)
-
- return True
-
- def _undo(self, pos, n):
- r = pos / 9
- c = pos % 9
- self.row[r * 10 + n] = False
- self.col[c * 10 + n] = False
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + n] = False
-
- self.puzzle[r][c] = 0
-
- for p in self.relatives[pos]:
- old_score = self.scores[p]
- if old_score == -1:
- continue
-
- if n not in self.tries[p]:
- y = p / 9
- x = p % 9
- if not (self.row[y * 10 + n] or self.col[x * 10 + n] or self.grp[((y / 3) * 3 + (x / 3)) * 10 + n]):
- self.tries[p][:0] = [n]
- self.scores[p] += 1
- self.steps[old_score + 1][:0] = [p]
- self.steps[old_score].remove(p)
-
- def _solve(self):
- pos = 81
- for score in xrange(9):
- if self.steps[score]:
- pos = self.steps[score].pop()
- break
- if pos >= 81:
- return True
-
- self.scores[pos] = -1
-
- for n in self.tries[pos]:
- if self._try(pos, n):
- if self._solve():
- return True
- self._undo(pos, n)
-
- self.scores[pos] = score
- self.steps[score].append(pos)
-
- return False
-
- def _analyze(self):
- for i in xrange(90):
- self.row[i] = False
- self.col[i] = False
- self.grp[i] = False
-
- for r in xrange(9):
- for c in xrange(9):
- pos = r * 9 + c
- v = self.puzzle[r][c]
- if v:
- if self.row[r * 10 + v] or self.col[c * 10 + v] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + v]:
- return False
-
- self.row[r * 10 + v] = True
- self.col[c * 10 + v] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + v] = True
-
- self.scores[pos] = -1
-
- for i in xrange(9):
- self.steps[i] = []
-
- for r in xrange(9):
- for c in xrange(9):
- pos = r * 9 + c
- v = self.puzzle[r][c]
- if not v:
- tries = []
- for n in xrange(1, 10):
- if not (self.row[r * 10 + n] or self.col[c * 10 + n] or self.grp[((r / 3) * 3 + (c / 3)) * 10 + n]):
- tries.append(n)
-
- if not tries:
- return False
-
- score = len(tries) - 1
-
- self.tries[pos] = tries
- self.scores[pos] = score
- self.steps[score].append(pos)
-
- while (self.steps[0]):
- pos = self.steps[0].pop()
- r = pos / 9
- c = pos % 9
-
- v = self.tries[pos].pop()
-
- self.row[r * 10 + v] = True
- self.col[c * 10 + v] = True
- self.grp[((r / 3) * 3 + (c / 3)) * 10 + v] = True
- self.puzzle[r][c] = v
-
- self.scores[pos] = -1
-
- for p in self.relatives[pos]:
- s = self.scores[p]
- if s > 0 and v in self.tries[p]:
- self.tries[p].remove(v)
- self.scores[p] -= 1
- self.steps[s - 1][:0] = [p]
- self.steps[s].remove(p)
-
- return True
-
- def solve(self, puzzle):
- self.puzzle = puzzle
-
- if not self._analyze():
- return False
-
- return self._solve()
-
-def parse_file():
- lines = sys.stdin.readlines()
-
- puzzles = []
- for l in lines:
- if (len(l) != 82):
- print "xxx"
- continue
-
- p = []
- for i in xrange(9):
- t = []
- for j in xrange(9):
- t.append(int(l[i * 9 + j]))
- p.append(t)
- puzzles.append(p)
-
- return puzzles
-
-def main():
- solver = SudokuSolver()
- puzzles = parse_file()
-
- for p in puzzles:
- if (solver.solve(p)):
- pass
- for i in xrange(9):
- print p[i]
- print
- else:
- print "no solution"
-
-
-if __name__ == "__main__":
- main()
Added: developers/erin_yueh/pythonEFL-sudoku/data/pythonEFL-sudoku.desktop
===================================================================
--- developers/erin_yueh/pythonEFL-sudoku/data/pythonEFL-sudoku.desktop (rev 0)
+++ developers/erin_yueh/pythonEFL-sudoku/data/pythonEFL-sudoku.desktop 2008-07-09 16:45:19 UTC (rev 4520)
@@ -0,0 +1,12 @@
+[Desktop Entry]
+Encoding=UTF-8
+Name=pythonEFL-sudoku
+TryExec=sudoku_ui.py
+GenericName=pythonEFL-sudoku
+Comment=Sudoku game
+StartupNotify=false
+Exec=sudoku_ui.py
+Icon=pythonEFL-sudoku
+Terminal=false
+Type=Application
+Categories=Games;
Added: developers/erin_yueh/pythonEFL-sudoku/src/sudoku/generator.py
===================================================================
--- developers/erin_yueh/pythonEFL-sudoku/src/sudoku/generator.py (rev 0)
+++ developers/erin_yueh/pythonEFL-sudoku/src/sudoku/generator.py 2008-07-09 16:45:19 UTC (rev 4520)
@@ -0,0 +1,199 @@
+#!/usr/bin/python
+
+import ecore.evas
+import ecore
+import math
+import random
+
+def generateDummyGroup(ee,number):
+ group = ee.data['group_list']
+ (g,start_row,start_line) = group[str(number)]
+ items = [1,2,3,4,5,6,7,8,9]
+ random.shuffle(items)
+ for i in range (start_row, start_row+3):
+ for j in range(start_line, start_line+3):
+ key = (i,j)
+ obj = ee.data[key]
+ obj.color_set(0,255,0,255)
+ value = items.pop()
+ obj.text_set(str(value))
+ obj.data['value'] = value
+ return True
+
+def checkGroupRule(ee,number):
+ group = ee.data['group_list']
+ (g,start_row,start_line) = group[str(number)]
+ used_items = [0]
+
+ for i in range (start_row,start_row+3):
+ for j in range(start_line,start_line+3):
+ key = (i,j)
+ obj = ee.data[key]
+ value = int(obj.data['value'])
+ if(value>0):
+ used_items.append(value)
+ #print 'check group:',number,'used_items =',used_items
+ return used_items
+
+def checkRowRule(ee,number):
+ used_items = [0]
+ for i in range(1,10):
+ key = (number,i) # row
+ obj = ee.data[key]
+ value = int(obj.data['value'])
+ if(value>0):
+ used_items.append(value)
+ #print 'check row:', number, 'used_items = ',used_items
+ return used_items
+
+def checkLineRule(ee,number):
+ used_items = [0]
+ for i in range(1,10):
+ key = (i,number) # line
+ obj = ee.data[key]
+ value = int(obj.data['value'])
+ if(value>0):
+ used_items.append(value)
+ #print 'check line:', number, 'used_items = ',used_items
+ return used_items
+
+def CheckAndMergeUsed(group_used,row_used,line_used):
+ items = [1,2,3,4,5,6,7,8,9]
+ for k in range(len(group_used)):
+ if(group_used[k] in items):
+ items.remove(group_used[k])
+ for i in range(len(row_used)):
+ if(row_used[i] in items):
+ items.remove(row_used[i])
+ for j in range(len(line_used)):
+ if(line_used[j] in items):
+ items.remove(line_used[j])
+
+ if(len(items)==0):
+ return False
+ else:
+ return True
+
+def fillinByGroup(ee,number):
+ group = ee.data['group_list']
+ (g,start_row,start_line) = group[str(number)]
+ items = [1,2,3,4,5,6,7,8,9]
+ random.shuffle(items)
+
+ group_used = checkGroupRule(ee,number)
+ needed = len(items) - len(group_used) + 1
+ bingo = 0
+
+ for i in range (start_row,start_row+3):
+ for j in range(start_line,start_line+3):
+ key = (i,j)
+ obj = ee.data[key]
+ value = int(obj.data['value'])
+ if(value==0):
+ group_used = checkGroupRule(ee,number)
+ row_used = checkRowRule(ee,i)
+ line_used = checkLineRule(ee,j)
+ if(CheckAndMergeUsed(group_used,row_used,line_used) == False):
+ return 1
+ for v in range(len(items)):
+ ball = items[v]
+ if(ball not in group_used and
+ ball not in row_used and ball not in line_used):
+ obj.data['value'] = ball
+ obj.text_set(str(ball))
+ obj.color_set(255,0,0,255)
+ bingo+=1
+ break
+ if(bingo==needed):
+ return 0
+ else:
+ return 1
+
+def refreshByGroup(ee,number):
+ group = ee.data['group_list']
+ (g,start_row,start_line) = group[str(number)]
+
+ for i in range (start_row,start_row+3):
+ for j in range(start_line,start_line+3):
+ key = (i,j)
+ obj = ee.data[key]
+ obj.text_set('0')
+ obj.data['value'] = 0
+
+ return True
+
+
+def main():
+ ee = ecore.evas.SoftwareX11(w=360, h=360)
+ canvas = ee.evas
+ group = {
+ '1': (1,1,1), '2':(2,1,4), '3':(3,1,7),
+ '4': (4,4,1), '5':(5,4,4), '6':(6,4,7),
+ '7': (7,7,1), '8':(8,7,4), '9':(9,7,7),
+ }
+
+ ee.data['group_list'] = group
+
+ # create a black backgound
+ bg = canvas.Rectangle(color=(0, 0, 0, 255))
+ bg.size = canvas.size
+ bg.show()
+
+ element_w = 360 / 9
+ element_h = 360 / 9
+
+ # put all elements to Text objects
+ for i in range (1,10):
+ for j in range(1,10):
+ x = 5 + (element_w * (i-1))
+ y = 5 + (element_h * (j-1))
+ value = 0
+ display = str(value)
+ text = canvas.Text(text=display, font=("sans serif", 12), color=(0,255,255,255))
+ text.pos_set(x,y)
+ text.data['row'] = j
+ text.data['line'] = i
+ text.data['value'] = value
+ text.show()
+ addr = (text.data['row'],text.data['line'])
+ ee.data[addr] = text
+ text.text_set(str(addr))
+
+ dummy_group = (9,5,1)
+ #not_dummy_group = (2,8,7,4,6,1,5,9,3)
+ not_dummy_group = (2,8,3,4,6,7)
+ flag = False
+ times = 0
+ counter = 0
+ curr_time = ecore.time_get()
+ print 'start to run:', times, curr_time
+ while(flag == False):
+ counter = 1
+ # generate three dummy group
+ for i in range(len(dummy_group)):
+ #print 'generateDummyGroup', dummy_group[i]
+ generateDummyGroup(ee,dummy_group[i])
+ # clean up other groups
+ for j in range(len(not_dummy_group)):
+ #print 'refreshByGroup', not_dummy_group[j]
+ refreshByGroup(ee,not_dummy_group[j])
+ # fill in by group
+ for k in range(len(not_dummy_group)):
+ #print 'fillinByGroup', not_dummy_group[k]
+ counter = fillinByGroup(ee,not_dummy_group[k])
+ if(counter==1):
+ break
+ if(counter ==1):
+ flag = False
+ elif(counter ==0):
+ flag = True
+ times += 1
+
+ print 'times = ', times, 'running time = ',(ecore.time_get() - curr_time)
+
+ ee.show()
+ ecore.animator_frametime_set(1.0 / 10.0)
+ ecore.main_loop_begin()
+
+if __name__ == "__main__":
+ main()
\ No newline at end of file
More information about the commitlog
mailing list
