473,769 Members | 2,090 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

line print out for sudoku solver

Thekid
145 New Member
Hi, I found this sudoku solver online and it works good but I was wondering how I could get the answer that's in matrix form, to also print out in a single comma-delimited line, instead of 9 rows of 9?

Expand|Select|Wrap|Line Numbers
  1. from copy import deepcopy
  2. class DeadEnd(Exception): pass
  3.  
  4.  
  5. class Matrix:
  6.     def __init__(self, input):
  7.         self.rows = [[] for i in range(9)]
  8.         self.cols  = [[] for i in range(9)]
  9.         self.submatrices = [[] for i in range(9)]
  10.         self.cells = [Cell(i,self) for i in range(81)]
  11.         self.subdiagonals = [self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
  12.         input = [s not in '-*' and int(s) or 0 for s in input if s in '0123456789-*']
  13.         for cell,val in zip(self.cells, input): 
  14.             if val: cell.setSolution(val)
  15.  
  16.     def solve(self): #Brute-force solver
  17.         self.solveByReduction()
  18.         lensols=[(len(c.solutions),c.index) for c in self.cells if not c.solved]
  19.         if not lensols: return True
  20.         unsolved = min(lensols)[1]
  21.         solutions = list(self.cells[unsolved].solutions)
  22.         for s in solutions:
  23.             tmpmatrix = deepcopy(self)
  24.             try:
  25.                 tmpmatrix.cells[unsolved].setSolution(s)
  26.                 if tmpmatrix.solve():
  27.                     self.update(tmpmatrix)
  28.                     return True
  29.             except DeadEnd: pass
  30.  
  31.     def solveByReduction(self):
  32.         while True:
  33.             self.changed = False
  34.             for c in self.cells: c.solve()
  35.             for c in self.subdiagonals: c.skim()
  36.             if not self.changed: break
  37.  
  38.     def update(self, m):
  39.         self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\
  40.             m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals
  41.  
  42.     def __str__(self):
  43.         return "\n".join(str([c for c in row ])[1:-1] for row in self.rows)
  44.  
  45.  
  46. class Cell:
  47.     def __init__(self, index, matrix):
  48.         self.solved = False
  49.         self.matrix = matrix
  50.         self.index = index
  51.         self.row = matrix.rows[index/9]
  52.         self.col = matrix.cols[index%9]
  53.         self.submatrix = matrix.submatrices[((index/9)/3)*3+(index%9)/3]
  54.         self.row.append(self)
  55.         self.col.append(self)
  56.         self.submatrix.append(self)
  57.         self.solutions = set(range(1,10))
  58.  
  59.     def solve(self):
  60.         if self.solved: return
  61.         if len(self.solutions) == 1:
  62.             self.setSolution(self.solutions.pop())
  63.         else:
  64.             sol = set()
  65.             for cells in [self.row, self.col, self.submatrix]:
  66.                 otherSolutions = self.cells2sols(cells, self)
  67.                 sol |= (self.solutions - otherSolutions)
  68.             if len(sol) > 1: raise DeadEnd()
  69.             if sol: self.setSolution(sol.pop())
  70.  
  71.     def skim(self):
  72.         submatrix = set(self.submatrix)
  73.         for r in  (set(self.row), set(self.col)):
  74.             subset1 = submatrix - r
  75.             subset2 = r - submatrix
  76.             solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2)
  77.             solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1)
  78.             for c in subset1: c.delSolutions(solsNotIn1)
  79.             for c in subset2: c.delSolutions(solsNotIn2)
  80.  
  81.     def setSolution(self, val):
  82.         self.solved = True
  83.         self.solutions = set((val,))
  84.         self.matrix.changed = True
  85.         for other in self.row+self.col+self.submatrix:
  86.             if other is self: continue
  87.             if other.solutions == self.solutions: raise DeadEnd()
  88.             other.delSolutions(self.solutions)
  89.  
  90.     def delSolutions(self, val):
  91.         if not self.solved and val & self.solutions:
  92.             self.solutions -= val
  93.             self.matrix.changed = True
  94.             if not self.solutions: raise DeadEnd()
  95.  
  96.     def __repr__(self):
  97.         return str(self.solved and list(self.solutions)[0] or list(self.solutions))
  98.  
  99.     @staticmethod
  100.     def cells2sols(cells, exclude=None):
  101.         return set(s for c in cells for s in c.solutions if c is not exclude)
  102.  
  103.  
  104. if __name__ == "__main__":
  105.     input = '''5,6,7,2,3,0,0,0,1,2,0,0,0,9,1,5,6,7,8,0,1,0,0,0,2,0,4,0,5,0,1,2,0,7,8,9,0,2,3,0,0,0,0,5,0,0,8,9,0,5,6,0,2,3,0,7,0,3,4,5,0,1,2,3,0,5,9,1,2,0,7,8,9,0,2,6,7,8,3,4,5'''
  106.     matrix = Matrix(input)
  107.     matrix.solve()
  108.     print matrix
  109.  
  110.  
Oct 1 '08 #1
1 2040
kaarthikeyapreyan
107 New Member
Hey use the numarray or numpy to print the output in an array form
Oct 3 '08 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

23
2643
by: Mark Dickinson | last post by:
I have a simple 192-line Python script that begins with the line: dummy0 = 47 The script runs in less than 2.5 seconds. The variable dummy0 is never referenced again, directly or indirectly, by the rest of the script. Here's the surprise: if I remove or comment out this first line, the script takes more than 15 seconds to run. So it appears that adding a redundant line produces a spectacular six-fold increase in speed!
11
4140
by: ago | last post by:
Inspired by some recent readings on LinuxJournal and an ASPN recipe, I decided to revamp my old python hack... The new code is a combination of (2) reduction methods and brute force and it is quite faster than the ASPN program. If anyone is interested I attached the code in http://agolb.blogspot.com/2006/01/sudoku-solver-in-python.html
12
6347
by: kalinga1234 | last post by:
hy guys i am having a problem with my sudoku program which i coded using c++.; currently in my program if a duplicate number exist in either row/column/block i would make the particualr square 0. but thats not i want to do. I want to recurse back until until it find a correct number. i will post the function which i need the help; ---coding----------------------------------------------------------
4
11448
by: flplini | last post by:
Nowhere in the web have i been able to find a perfect program in c++. Does any computer buff know it out there?
2
2205
by: avinash1990 | last post by:
hi can you tell me how to make a sudoku solver program ..i really need it for my project
6
11883
by: blux | last post by:
I am working on a function to check the validity of a sudoku puzzle. It must check the 9x9 matrix to make sure it follows the rules and is a valid sudoku puzzle. this is what I have come up with so far: However I have found that it does not check it correctly. I just need to check the 9x9 array, which I am passing to this function against the classic sudoku rules and then return true for
2
1382
by: Derek Marshall | last post by:
This is just for fun, in case someone would be interested and because I haven't had the pleasure of posting anything here in many years ... http://derek.marshall.googlepages.com/pythonsudokusolver Appreciate any feedback anyone who takes the time to have a look would want to give ... Yours with-too-much-time-to-kill-on-the-train'ly, Derek
38
6395
by: Boon | last post by:
Hello group, I've been toying with a simple sudoku solver. I meant for the code to be short and easy to understand. I figured "brute force is simple" -- who needs finesse, when you've got muscle, right? :-) http://en.wikipedia.org/wiki/Sudoku Thus, the strategy is to test every legal "move" and to backtrack when stuck. A recursive function seemed appropriate. I'd like to hear
62
12258
jkmyoung
by: jkmyoung | last post by:
Does anyone have some super, super hard Sudoku puzzles? Back in February this year, I had enough time to finally program a Sudoku solver in Java. Right now, I'm looking for solvable puzzles, but ones that my program cannot solve. However, most hard puzzles in the newspapers are solved within 2-3 cycles so far. The ones I've found on google which are said to be hard, get solved in 3 cycles. Any help would be very much appreciated!...
0
9422
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
9987
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9857
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
8867
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7404
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6662
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5294
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5444
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3952
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.