[Tutor] The Python way and two dimensional lists
Dennis Lee Bieber
wlfraed at ix.netcom.com
Wed Dec 8 00:56:38 EST 2021
On Wed, 8 Dec 2021 12:06:51 +1100, Phil <phillor9 at gmail.com> declaimed the
following:
>This is a rather easy puzzle to solve, my programme solved it in 3
>passes. I'm not skiting, just pointing out that I have achieved something.
>
How do you define "passes"?
Just for giggles I took an old, unfinished solver I'd started over a
decade ago, and modified it for Python3.x (I think I'd already 2to3 over it
as the "print" statements were up-to-date -- but the change of "int / int
=> float" killed it. Had to change the "/" to "//".
I'm going to put it as text attachments to avoiding spamming too many
-- as I recall the group does allow plain text as an attachment. I'll also
include a run of the program with your data set. As you'll see, I only
manage to solve the simpler levels and reach deadlock for some cases.
This code does NOT use the class I illustrated earlier. 1) Python2.x
hadn't introduced "sets" at the time I wrote it, so everything is lists; 2)
it uses three classes: Cell (one cell with flags for locked [provided start
value, and maybe solved value] along with a list of candidates); Grid (a
3x3 set of Cell -- your box/region); Table (a 3x3 set of Grid).
--
Wulfraed Dennis Lee Bieber AF6VN
wlfraed at ix.netcom.com http://wlfraed.microdiversity.freeddns.org/
-------------- next part --------------
# Dec 8 2021 -- update to Python 3.x
import time
class Cell(object):
def __init__(self):
self.locked = False # final value found
self.value = None
self.candidates = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def set(self, value):
self.locked = True
self.value = value
self.candidates = None
def eliminate(self, value):
if not self.locked:
if value in self.candidates:
self.candidates.remove(value)
return True
return False
class Grid(object):
def __init__(self):
self.cells = [ [Cell(), Cell(), Cell()],
[Cell(), Cell(), Cell()],
[Cell(), Cell(), Cell()] ]
def completed(self):
for r in range(3):
for c in range(3):
if not self.cells[r][c].locked:
return False
return True
class Table(object):
def __init__(self):
self.grids = [ [Grid(), Grid(), Grid()],
[Grid(), Grid(), Grid()],
[Grid(), Grid(), Grid()] ]
self.rows = [None] * 9
for r in range(9):
row = [None] * 9
for c in range(9):
row[c] = self.grids[r // 3][c // 3].cells[r % 3][c % 3]
def set(self, row, col, value):
self.grids[row // 3][col // 3].cells[row % 3][col % 3].set(value)
def get(self, row, col):
return self.grids[row // 3][col // 3].cells[row % 3][col % 3]
def eliminate(self, row, col, value):
changed = False
for c in range(9):
changed = (self.grids[row // 3][c // 3].cells[row % 3][c % 3].eliminate(value)
or changed)
for r in range(9):
changed = (self.grids[r // 3][col // 3].cells[r % 3][col % 3].eliminate(value)
or changed)
grid = self.grids[row // 3][col // 3]
for c in range(3):
for r in range(3):
changed = (grid.cells[r][c].eliminate(value) or changed)
return changed
def display(self):
print("\n\n0 1 2 3 4 5 6 7 8\n==================")
for r in range(9):
for c in range(9):
if self.get(r, c).value:
print("%s" % (self.get(r, c).value), end=' ')
else:
print(" ", end=' ')
print("|%s" % r)
def completed(self):
for r in range(3):
for c in range(3):
if not self.grids[r][c].completed():
return False
return True
if __name__ == "__main__":
myTable = Table()
print("\n\nEnter a value of 0 to exit setup")
print("\tRow and Column range 0..8")
while True:
cin = input("Enter the cell Value Row Column (space separated): ")
try:
cv, cr, cc = cin.split()
value = int(cv)
if value == 0: break
row = int(cr)
col = int(cc)
myTable.set(row, col, value)
myTable.display()
print()
except:
print("Error processing input: try again")
pass
print("\n\nBuilding table ", end=' ')
for r in range(9):
for c in range(9):
if myTable.get(r, c).locked:
myTable.eliminate(r, c, myTable.get(r, c).value)
myTable.display()
while True:
print("Evaluating ")
change = False
done = True
for r in range(9):
for c in range(9):
print(".", end=' ')
time.sleep(0.01)
if not myTable.get(r, c).locked:
if len(myTable.get(r, c).candidates) == 1:
myTable.set(r, c, myTable.get(r, c).candidates[0])
change = myTable.eliminate(r, c,
myTable.get(r, c).value)
myTable.display()
if change: break
if change: break
print()
# check for completion
if myTable.completed():
print("Completed")
break
if not change:
deadlock = True
print("Resolving initial deadlock")
for gr in range(3):
for gc in range(3):
myGrid = myTable.grids[gr][gc]
count = [0] * 9
if deadlock:
for r in range(3):
for c in range(3):
if deadlock and myGrid.cells[r][c].candidates:
for n in myGrid.cells[r][c].candidates:
count[n-1] += 1
try:
n = count.index(1) + 1
deadlock = False
for r in range(3):
for c in range(3):
if (myGrid.cells[r][c].candidates
and n in myGrid.cells[r][c].candidates):
myGrid.cells[r][c].set(n)
myTable.eliminate(gr * 3 + r, gc * 3 + c, n)
myTable.display()
except:
pass
if deadlock:
print("Deadlocked; must be resolved manually")
cin = input("Enter value row column: ")
cv, cr, cc = cin.split()
value = int(cv)
row = int(cr)
col = int(cc)
myTable.set(row, col, value)
myTable.eliminate(row, col, value)
myTable.display()
cv, cr, cc = cin.split()
value = int(cv)
row = int(cr)
col = int(cc)
myTable.set(row, col, value)
myTable.eliminate(row, col, value)
-------------- next part --------------
C:\Users\Wulfraed\Documents\_Hg-Repositories\Python Progs>sudoku.py
Enter a value of 0 to exit setup
Row and Column range 0..8
Enter the cell Value Row Column (space separated): 2 0 1
0 1 2 3 4 5 6 7 8
==================
2 |0
|1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 7 0 2
0 1 2 3 4 5 6 7 8
==================
2 7 |0
|1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 8 0 4
0 1 2 3 4 5 6 7 8
==================
2 7 8 |0
|1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 9 0 5
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 |0
|1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 6 0 6
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
|1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 1 1 5
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 |1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 7 1 6
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 |1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 2 1 8
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
|2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 9 2 0
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
|3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 5 3 4
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 |3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 7 3 8
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
|4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 1 4 0
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 |4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 7 4 1
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 |4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 2 4 7
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 |4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 6 4 8
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
|5
|6
|7
|8
Enter the cell Value Row Column (space separated): 8 5 0
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 |5
|6
|7
|8
Enter the cell Value Row Column (space separated): 4 5 4
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
|6
|7
|8
Enter the cell Value Row Column (space separated): 4 6 8
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
|7
|8
Enter the cell Value Row Column (space separated): 2 7 0
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 |7
|8
Enter the cell Value Row Column (space separated): 8 7 2
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 |7
|8
Enter the cell Value Row Column (space separated): 5 7 3
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
|8
Enter the cell Value Row Column (space separated): 1 8 2
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 |8
Enter the cell Value Row Column (space separated): 8 8 3
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 |8
Enter the cell Value Row Column (space separated): 6 8 4
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 |8
Enter the cell Value Row Column (space separated): 2 8 6
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 |8
Enter the cell Value Row Column (space separated): 3 8 7
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Enter the cell Value Row Column (space separated): 0 0 0
Building table
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . .
0 1 2 3 4 5 6 7 8
==================
2 7 8 9 6 |0
3 1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . .
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
3 1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . .
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 |2
5 7 |3
1 7 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 |2
5 7 |3
1 7 9 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 |2
5 7 |3
1 7 3 9 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 1 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 1 6 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
3 2 7 4 8 9 6 |0
6 3 1 7 2 |1
9 1 6 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
3 2 7 4 8 9 6 |0
8 6 3 1 7 2 |1
9 1 6 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
3 2 7 4 8 9 6 |0
8 6 3 1 7 2 |1
9 1 6 5 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
3 2 7 4 8 9 6 |0
8 6 3 1 7 9 2 |1
9 1 6 5 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
0 1 2 3 4 5 6 7 8
==================
3 2 7 4 8 9 6 |0
8 6 3 1 7 9 2 |1
9 1 6 5 |2
5 7 |3
1 7 3 9 8 2 6 |4
8 4 |5
9 4 |6
2 8 5 |7
1 8 6 2 3 |8
Evaluating
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Resolving initial deadlock
Deadlocked; must be resolved manually
Enter value row column:
More information about the Tutor
mailing list