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? -
from copy import deepcopy
-
class DeadEnd(Exception): pass
-
-
-
class Matrix:
-
def __init__(self, input):
-
self.rows = [[] for i in range(9)]
-
self.cols = [[] for i in range(9)]
-
self.submatrices = [[] for i in range(9)]
-
self.cells = [Cell(i,self) for i in range(81)]
-
self.subdiagonals = [self.rows[i][j+i%3] for i in range(9) for j in [0,3,6]]
-
input = [s not in '-*' and int(s) or 0 for s in input if s in '0123456789-*']
-
for cell,val in zip(self.cells, input):
-
if val: cell.setSolution(val)
-
-
def solve(self): #Brute-force solver
-
self.solveByReduction()
-
lensols=[(len(c.solutions),c.index) for c in self.cells if not c.solved]
-
if not lensols: return True
-
unsolved = min(lensols)[1]
-
solutions = list(self.cells[unsolved].solutions)
-
for s in solutions:
-
tmpmatrix = deepcopy(self)
-
try:
-
tmpmatrix.cells[unsolved].setSolution(s)
-
if tmpmatrix.solve():
-
self.update(tmpmatrix)
-
return True
-
except DeadEnd: pass
-
-
def solveByReduction(self):
-
while True:
-
self.changed = False
-
for c in self.cells: c.solve()
-
for c in self.subdiagonals: c.skim()
-
if not self.changed: break
-
-
def update(self, m):
-
self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\
-
m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals
-
-
def __str__(self):
-
return "\n".join(str([c for c in row ])[1:-1] for row in self.rows)
-
-
-
class Cell:
-
def __init__(self, index, matrix):
-
self.solved = False
-
self.matrix = matrix
-
self.index = index
-
self.row = matrix.rows[index/9]
-
self.col = matrix.cols[index%9]
-
self.submatrix = matrix.submatrices[((index/9)/3)*3+(index%9)/3]
-
self.row.append(self)
-
self.col.append(self)
-
self.submatrix.append(self)
-
self.solutions = set(range(1,10))
-
-
def solve(self):
-
if self.solved: return
-
if len(self.solutions) == 1:
-
self.setSolution(self.solutions.pop())
-
else:
-
sol = set()
-
for cells in [self.row, self.col, self.submatrix]:
-
otherSolutions = self.cells2sols(cells, self)
-
sol |= (self.solutions - otherSolutions)
-
if len(sol) > 1: raise DeadEnd()
-
if sol: self.setSolution(sol.pop())
-
-
def skim(self):
-
submatrix = set(self.submatrix)
-
for r in (set(self.row), set(self.col)):
-
subset1 = submatrix - r
-
subset2 = r - submatrix
-
solsNotIn1 = set(range(1,10)) - self.cells2sols(subset2)
-
solsNotIn2 = set(range(1,10)) - self.cells2sols(subset1)
-
for c in subset1: c.delSolutions(solsNotIn1)
-
for c in subset2: c.delSolutions(solsNotIn2)
-
-
def setSolution(self, val):
-
self.solved = True
-
self.solutions = set((val,))
-
self.matrix.changed = True
-
for other in self.row+self.col+self.submatrix:
-
if other is self: continue
-
if other.solutions == self.solutions: raise DeadEnd()
-
other.delSolutions(self.solutions)
-
-
def delSolutions(self, val):
-
if not self.solved and val & self.solutions:
-
self.solutions -= val
-
self.matrix.changed = True
-
if not self.solutions: raise DeadEnd()
-
-
def __repr__(self):
-
return str(self.solved and list(self.solutions)[0] or list(self.solutions))
-
-
@staticmethod
-
def cells2sols(cells, exclude=None):
-
return set(s for c in cells for s in c.solutions if c is not exclude)
-
-
-
if __name__ == "__main__":
-
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'''
-
matrix = Matrix(input)
-
matrix.solve()
-
print matrix
-
-
1 2040
Hey use the numarray or numpy to print the output in an array form
Sign in to post your reply or Sign up for a free account.
Similar topics |
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!
|
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
|
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----------------------------------------------------------
|
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?
|
by: avinash1990 |
last post by:
hi
can you tell me how to make a sudoku solver program ..i really need it for my project
| |
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
|
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
|
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
|
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!...
|
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,...
|
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,...
| |
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...
|
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...
|
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...
|
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();...
|
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...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
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
| |