Omnimaga
Calculator Community => TI Calculators => Axe => Topic started by: Jsec42 on September 15, 2014, 06:11:42 pm
-
I couldn't find anything good along these lines on ticalc.org, so I have been attempting to make it myself. It is a sudoku solver, in case you didn't already know. [-.-]~ However, for whatever reason it is getting into an infinite recursion :banghead: , though I am not entirely sure why. <_<
.SDKUSVZ
#Realloc(L1)
0->X
0->Y
0->A
0->B
[0042241818244200]->Pic2
[0000000000000000007E6E4E6E467E0000423C724E3E000000427C427C7C4200005A5A407A7A7A0000003E027C7C020000403E3E023C420000007872664E1E0000423C423C3C420000403C3C407C7C00]->Pic1
Buff(81)->G
Goto MAIN
prgmSTACKLIB
Lbl DISP
ClrDraw^^r^^r
For(A,0,9
Line(0,7*A,63,7*A)
Line(7*A,0,7*A,63)
End
For(A,0,8
For(B,0,8
If {9*B+G+A}
Pt-On(7*A,7*B,{9*B+G+A}*8+Pic1)^^r
End
End
End
Pt-On(7*X,7*Y,Pic2)
DispGraph^^r
Return
Lbl MAIN
Repeat getKey(9)
DISP()
If getKey(4)?Y!=0
Y-1->Y
End
If getKey(1)?Y!=8
Y+1->Y
End
If getKey(2)?X!=0
X-1->X
End
If getKey(3)?X!=8
X+1->X
End
If getKey(33)
0->{9*Y+X+G}
End
If getKey(34)
1->{9*Y+X+G}
End
If getKey(35)
4->{9*Y+X+G}
End
If getKey(36)
7->{9*Y+X+G}
End
If getKey(26)
2->{9*Y+X+G}
End
If getKey(27)
5->{9*Y+X+G}
End
If getKey(28)
8->{9*Y+X+G}
End
If getKey(18)
3->{9*Y+X+G}
End
If getKey(19)
6->{9*Y+X+G}
End
If getKey(20)
9->{9*Y+X+G}
End
If getKey(15)
For(N,0,80)
0->{G+N}
End
End
If getKey(55)
Return^^r
End
End
0->L
0->M
sub(BACKTRACK)
Disp "Solve complete!",[i]
Disp T>Dec
Goto MAIN
Lbl ISFULL
For(X,0,8
For(Y,0,8
If {9*Y+X+G}=0
0->T
Return
End
End
End
1->T
Return
Lbl GETNEXT
While {9*M+L+G}!=0?M!=9
L++
If L=9
0->L
M++
End
End
Return
Lbl COLLISION
If L<3
0->A
ElseIf L<6
3->A
Else
6->A
End
If M<3
0->B
ElseIf M<6
3->B
Else
6->B
End
For(X,0,8)
If {9*M+X+G}!=0
If X!=L
If {9*M+X+G}={9*M+L+G}
1->T
Return
End
End
End
If {9*X+L+G}!=0
If X!=M
If {9*X+L+G}={9*M+L+G}
1->T
Return
End
End
End
End
A+2->C
B+2->D
For(X,A,C)
For(Y,B,D)
If {9*Y+X+G}!=0
If L!=X??M!=Y
If {9*Y+X+G}={9*M+L+G}
1->T
Return
End
End
End
End
End
0->T
Return
Lbl BACKTRACK
If {9*M+L+G}!=0
sub(GETNEXT)
End
1->N
While N!=10
N->{9*M+L+G}
sub(COLLISION)
If T=0
sub(ISFULL)
If T=1
Return
End
L++
If L=9
M++
0->L
End
sub(PUSH,L1,L)
sub(PUSH,L1,M)
sub(PUSH,L1,N)
sub(BACKTRACK)
sub(POP,L1,N)
sub(POP,L1,M)
sub(POP,L1,L)
If T=1
Return
End
L--
If L=65535
8->L
M--
End
If L=0
8->L
M--
Else
L--
End
End
N++
End
0->{9*M+L+G}
0->T
Return
It also uses a stack library of my own creation to keep from overflowing the tiny 300 byte stack on the ti-83. ;)
..STACKLIB
Lbl PUSH
{[r1]}^^r+1->{[r1]}^^r
{[r2]}^^r->{{[r1]}^^r+1+[r1]}
Return
Lbl POP
If {[r1]}^^r>=>=0
{{[r1]}^^r+1+[r1]}->{[r2]}^^r
{[r1]}^^r-1->{[r1]}^^r
Else
0->{[r2]}
End
Return
It is rather minimal, but I don't think the stacklib is the problem. Any assistance?
-
I made some changes to the code, but it still isn't working. I will post the files here. I have also attached some screenshots. As you can see, when I input a blank sudoku it does not solve completely. <_< I would appreciate some help here, as I am at a standstill. :banghead:
-
One potential issue I see is that it looks like your stack functions expect the second argument, the variable to save/restore, to be passed by reference. But your uses of the functions pass the values of the variables, not references. You could fix this by changing the uses of L, M, and N in the push/pop function calls to °L, °M, and °N. Alternatively, a solution that would probably result in slightly simpler code is to not pass these by reference, and instead have the push function accept a value and have the pop function return a value.
Also, it looks like you're trying to use L1 as your stack space and your variable space simultaneously (seeing the #Realloc(L1) at the top of your code), which probably also doesn't help, unless I'm misunderstanding that. Unless you have a strong reason to, I'd recommend not using the #Realloc() directive at all anyways, since recent versions of Axe put the variables in a fairly isolated location in memory by default.
-
I noticed that removing #realloc() made the stacklib stop reading in garbage data (This is what caused issues with some of my early pre-alphas). Truthfully though, stacklib doesn't care whether or not the majority of the stack is filled with garbage data, as long as the first two bytes are initially zero. And yes, I am trying to tie in stack space with variables, since I couldn't reliably get the r1-r6 variables to host locally. But getting rid of that line did fix it, along with some recoding of stacklib(just for optimization).
-
This is the fixed source code. I am still considering it pre-alpha since it has a couple of dealbreaking bugs <_< . But this is the first version where the solver is actually functional. I have some screenshots as well. One of them is of what I call the Out-of-bounds glitch. It is caused by solving immediately after solving a sudoku :P . It also needs to be optimized. ;)
-
More optimizations :) . I finally learned the art of abusing HL, so I applied it to my program. I hope you don't mind that I copied your loop structure :P , but it shaved about 15% of the time off. I do admit though that because your loop is a decrementing loop, it changed the algorithm a little, but it was worth the speed gain ;) . Nice job finding that loop :thumbsup: .
-
This looks pretty nice :). As a future suggestion, though, when you have several updates to post in less than 24 hours you should probably edit your last post if nobody else replied to avoid double-posting. ;)
-
I will remember that next time ;D . I'm thinking about starting a new thread for the alpha, now that it works :thumbsup: . Thanks to Runner112 for his advice on fixing this solver ;) .
-
Hold on........AXE question
Does the codeX?GoTo nTranslate told [address of x],HL
cp HL
nz jp [address of n]? If so there might be an even more optimized loop up the sleeve of AXE :o !
-
More optimizations :) . I finally learned the art of abusing HL, so I applied it to my program. I hope you don't mind that I copied your loop structure :P , but it shaved about 15% of the time off. I do admit though that because your loop is a decrementing loop, it changed the algorithm a little, but it was worth the speed gain ;) . Nice job finding that loop :thumbsup: .
Shhh!!!! Don't give him so much praise, he already is cocky enough as is `>..<"
Though I guess being the best optimizer around /does/ give you some bragging rights.
-
Unless of course that optimization I came up with works even faster ;D . It goes something like this.
lbl something
..code goes here
conditional
asm(3E00BEC2(L(list token)something))
It effectively emulates a do...while loop, so it is probably faster, if the ? short circuit operates like I think it does ;) .
Some HL abuse could probably be applied to the conditional as well, but that is program-dependent :) . The for variant would work like this
n
lbl something
-1->X
..code goes here
X
asm(3E00BEC2(L(list token)something))
It would start from n-1 and go until it hits 0
I know it's cheating to use an asm statement for a conditional jump, but oh well :P .
EDIT: Conditional?goto something didn't work, so I made an assembly command.