5 Temmuz 2008 Cumartesi

Python sudoku solver

An easy solver. It doesn't make brute-force . So it's able to solve only simple sudokus where at least one field has no doubt about matcing only one number at any time.  


#!/usr/bin/python
# -*- coding: cp1254 -*-


#sample board
board=[[0,4,0,0,2,0,0,0,8],
      [0,8,0,0,0,7,4,5,0],
      [1,0,5,3,0,0,7,0,0],
      [9,0,4,0,3,8,1,0,7],
      [0,0,0,0,0,0,0,0,0],
      [5,0,7,4,1,0,2,0,9],
      [0,0,8,0,0,1,9,0,6],
      [0,9,1,8,0,0,0,2,0],
      [3,0,0,0,4,0,0,7,0]]

def get_row_suitables(y):
   lst=range(1,10)
   for x in range(0,9):
       number=board[y][x]
       if number:lst.remove(number)
   return lst
def get_column_suitables(x):
   lst=range(1,10)
   for y in range(0,9):
       number=board[y][x]
       if number:lst.remove(number)
   return lst
def get_square_suitables(y,x):
   ystart=y-(y%3)
   xstart=x-(x%3)
   lst=range(1,10)
   for y in range(ystart,ystart+3):
       for x in range(xstart,xstart+3):
           number=board[y][x]
           if number:lst.remove(number)
   return lst
  
def get_mutuals(a,b,c):
   mutuals=[]
   for i in a:
       if b.count(i) and c.count(i): mutuals.append(i)
   return mutuals
def total_zeros():
   total=0
   for y in range(0,9):
       total+= board[y].count(0)
   return total
def print_board():
   for y in range(0,9):print board[y]

#main loop
while True:
   has_found_any=0
   for y in range(0,9):
       for x in range(0,9):
           if not board[y][x]:
               a=get_row_suitables(y)
               b=get_column_suitables(x)
               c=get_square_suitables(y,x)
               d=get_mutuals(a,b,c)
               if len(d)==1:
                   board[y][x]=d[0]
                   has_found_any=1
               elif len(d)==0:
                   print "Error! This sudoku is wrong."
                   break
               else:
                   pass
   if not total_zeros():
       print "Sudoku solved succesfully"
       print_board()
       break
   if not has_found_any:
       print "Sudoku isn't solved"
       break

0 yorum: