This is a sudoku solving program written in Python.
It uses the brute force method of solving sudokus and employs recursion.
PyStack usage is a limitation of this program. Its limit cannot be increased by editing the parameters of the plot setup menu of the Python app. If the program would not use recursion then PyStack usage limit would not be an issue.
Should the PyStack usage limit be reached halfway through the solving process, then one must press the enter key to solve again. Should this not work, then it is necessary to set a couple of the last modified cells back to zero and start the process again.
It is possible to show the solving process as it happens.
Code:
#PYTHON sudoku
from hpprime import *
from micropython import *
#Set the x coordinate in the sudoku matrix to 0.
x=0
#Set the y coordinate in the sudoku matrix to 0.
y=0
#Set variable matrix to a 9 by 9 matrix filled with zeros representing empty cells.
matrix=[[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]]
#This method checks the validity of the number present at the given coordinates by searching for equal numbers in the same row, column and 3 by 3 square. If an equal number is found, or if the considered cell contains 0, then 0 (false) is returned otherwise 1 (true) is returned.
def test(x,y):
#The variable n is set to the value present in matrix at the given coordinates.
n=matrix[x][y]
#If the cell is empty then 0 is returned.
if n==0:
return 0
#The top-left coordinates of the 3 by 3 square are computed and assigned to variables boxx and boxy.
boxx=x-x%3
boxy=y-y%3
#The variable i is incremented by 1 9 times.
for i in range(9):
#The coordinates of each cell in a 3 by 3 square are not in sequence. The variable x2 is set to the top-left x coordinate plus i modulo 3 (ranging from 0 to 2). The variable y2 is set to the top-left y coordinate plus the integer result of i divided by 3 (ranging from 0 to 2). When a row of the 3 by 3 square ends, x2 is set back to the leftmost x coordinate in the square while y2 is incremented by 1.
x2=boxx+i%3
y2=boxy+int(i/3)
#A cell of the row, the column and the square is checked as long as the dynamic coordinate(s) in each check are not equal to the ones feeded to the method.
if (matrix[i][y]==n and i!=x) or (matrix[x][i]==n and i!=y) or (matrix[x2][y2]==n and x2!=x and y2!=y):
#If an equal number is found return 0.
return 0
#If no equal numbers were found return 1.
return 1
#Set variable d to 0. This is a flag to show the solving process as it happens. The process is slower if shown.
d=0
#The method solve is a recursive method which attempts to solve the sudoku. The arguments x and y are passed during each recursive calling of the method and indicate the current position of the solving process in the matrix.
def solve(x,y):
#PyStack usage is a limitation of this program. Its limit cannot be increased by editing the parameters of the plot setup menu of the Python app. The following check halts the solving process if pystack_use() returns a value larger than 4039. It appears that running the python program embedded in a PPL program from the program library allows for a higher limit for PyStack. The value 4039 was determined by trial and error, and only achieves its goal when the python program is executed within a PPL program from the program library. If the program would not use recursion then PyStack usage limit would not be an issue.
if pystack_use()>4039:
return 1
#The next empty (equal to 0) cell is searched proceding in order from left to right, top to bottom. If no empty cells are found the whole sudoku is checked for validity. If the sudoku results to be valid then 1 is returned, therefore ending the solving process. Otherwise 0 is returned.
while matrix[x][y]!=0:
if x<8:
x+=1
elif y<8:
y+=1
x=0
else:
for i in range(9):
for ii in range(9):
if test(i,ii)==0:
return 0
return 1
#The value in matrix at coordinates x and y is incremented in the following for loop from 1 to 9.
for matrix[x][y] in range(1,10):
#If d is 1 then the sudoku matrix is displayed during the solving process.
if d:
display(x,y,0)
#The validity of the given cell is checked as it is incremented in the for loop. If test(x,y) returns 1 then solve(x,y) is called as well in the process of evaluation of the boolean statement. If test(x,y) returns 0 then solve(x,y) is not called and the for loop continues. The boolean statemnet "test(x,y) and solve(x,y)" will return 1 only if the solving process has completed, that is to say, if the final validity check described above has rerurned 1. Returning 1 from within a recursion level causes each recursion level to return successfully (return 1), therefore ending the solving process.
if test(x,y) and solve(x,y):
return 1
#If the loop ends, then each number ranging from 1 to 9 that has been put in the cell was invalid (or the solving process has failed deeper in the recursion levels). Therefore the cell is set back to 0 and the solve method returns 0, so as to return to the prevoius cell being edited in an upper recursion level. This is done in an attempt to correct a wrong number chosen in an upper recursion level.
matrix[x][y]=0
return 0
#This method displays the sudoku matrix. Arguments x and y indicate the cell that is currently selected and which will be highlighted. Argument flag indicates that the sudoku cannot be solved.
def display(x,y,flag):
#G1 is set to a white background the size of the screen.
dimgrob(1,320,240,0xffffff)
#The sudoku matrix is drawn.
for i in range(9):
x0=i*14+int(i/3)*6+2
for ii in range(9):
y0=ii*14+int(ii/3)*6
if x==i and y==ii:
fillrect(1,x0,y0+3,8,10,0xffff00,0xffff00)
textout(1,x0,y0,str(matrix[i][ii]),0)
#If flag is 1 then a message indicating that the sudoku cannot be solved is displayed.
if flag:
textout(1,180,110,"Impossible",0xff0000)
#If show progress mode is active then variable c is set to the RGB value of the color green, otherwise of the color red.
c=0xff0000
if d:
c=0xff00
#A colored message indicating the presence of show progress mode and its state is drawn.
textout(1,150,220,"Press x to show process",c)
textout(1,150,200,"Press enter to solve",0)
#PyStack usage is shown.
textout(1,150,180,"Pystack use: "+str(pystack_use()),0)
#G1 is copied to G0.
blit(0,0,0,1)
#The variable q is a lock to prevent multiple key presses.
q=1
#The following loop is repeated as long as the escape key is not pressed.
while keyboard()>>4&1<1:
#Whether the down key on the dpad is pressed.
kd0=keyboard()>>12&1
#Whether the up key on the dpad is pressed.
kd1=keyboard()>>2&1
#Whether the right key on the dpad is pressed.
kd2=keyboard()>>8&1
#Whether the left key on the dpad is pressed.
kd3=keyboard()>>7&1
#Whether the x key (multiplication) is pressed.
kx=keyboard()>>40&1
#Whether the current coordinates are in the acceptable range. The coordinates are repositioned on the other edge of the sudoku matrix if a limit is reached.
xmin=x>0
xmax=x<8
ymin=y>0
ymax=y<8
if kd0 or kd1 or kd2 or kd3 or kx:
if kd0 and q:
if ymax:
y+=1
elif xmax:
y=0
x+=1
if kd1 and q:
if ymin:
y-=1
elif xmin:
y=8
x-=1
if kd2 and q:
if xmax:
x+=1
elif ymax:
x=0
y+=1
if kd3 and q:
if xmin:
x-=1
elif ymin:
x=8
y-=1
if kx and q:
if d:
d=0
else:
d=1
q=0
else:
q=1
n=0
#Whether the number keys are pressed.
k7=keyboard()>>32&1
k8=keyboard()>>33&1
k9=keyboard()>>34&1
k4=keyboard()>>37&1
k5=keyboard()>>38&1
k6=keyboard()>>39&1
k1=keyboard()>>42&1
k2=keyboard()>>43&1
k3=keyboard()>>44&1
#The delete key sets the number back to 0.
k0=keyboard()>>47&1 or keyboard()>>19&1
if k7 or k8 or k9 or k4 or k5 or k6 or k1 or k2 or k3 or k0:
if k7:
n=7
if k8:
n=8
if k9:
n=9
if k4:
n=4
if k5:
n=5
if k6:
n=6
if k1:
n=1
if k2:
n=2
if k3:
n=3
if k0:
n=0
matrix[x][y]=n
#The display method is called. Its flag argument is set to a boolean statement where if the enter key is pressed then the solve method is called, therefore starting the solving process. If the solve method returns 0, the flag argument is 1 and the "impossible" message is displayed. If the enter key is not pressed then the solve method is not called.
display(x,y,keyboard()>>30&1 and solve(0,0)==0)
#end
EXPORT SUDOKU()
BEGIN
PYTHON(sudoku)
END;
Search
Member List
Calendar
Help
/
Sudoku solving program written in Python
