### Author Topic: Troublesome Sudoku Solver  (Read 7358 times)

0 Members and 1 Guest are viewing this topic.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Troublesome Sudoku Solver
« 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 , though I am not entirely sure why.
Code: [Select]
.SDKUSVZ#Realloc(L1)0->X0->Y0->A0->B[0042241818244200]->Pic2[0000000000000000007E6E4E6E467E0000423C724E3E000000427C427C7C4200005A5A407A7A7A0000003E027C7C020000403E3E023C420000007872664E1E0000423C423C3C420000403C3C407C7C00]->Pic1Buff(81)->GGoto MAINprgmSTACKLIBLbl DISPClrDraw^^r^^rFor(A,0,9Line(0,7*A,63,7*A)Line(7*A,0,7*A,63)EndFor(A,0,8For(B,0,8If {9*B+G+A}Pt-On(7*A,7*B,{9*B+G+A}*8+Pic1)^^rEndEndEndPt-On(7*X,7*Y,Pic2)DispGraph^^rReturnLbl MAINRepeat getKey(9)DISP()If getKey(4)?Y!=0Y-1->YEndIf getKey(1)?Y!=8Y+1->YEndIf getKey(2)?X!=0X-1->XEndIf getKey(3)?X!=8X+1->XEndIf getKey(33)0->{9*Y+X+G}EndIf getKey(34)1->{9*Y+X+G}EndIf getKey(35)4->{9*Y+X+G}EndIf getKey(36)7->{9*Y+X+G}EndIf getKey(26)2->{9*Y+X+G}EndIf getKey(27)5->{9*Y+X+G}EndIf getKey(28)8->{9*Y+X+G}EndIf getKey(18)3->{9*Y+X+G}EndIf getKey(19)6->{9*Y+X+G}EndIf getKey(20)9->{9*Y+X+G}EndIf getKey(15)For(N,0,80)0->{G+N}EndEndIf getKey(55)Return^^rEndEnd0->L0->Msub(BACKTRACK)Disp "Solve complete!",[i]Disp T>DecGoto MAINLbl ISFULLFor(X,0,8For(Y,0,8If {9*Y+X+G}=00->TReturnEndEndEnd1->TReturnLbl GETNEXTWhile {9*M+L+G}!=0?M!=9L++If L=90->LM++EndEndReturnLbl COLLISIONIf L<30->AElseIf L<63->AElse6->AEndIf M<30->BElseIf M<63->BElse6->BEndFor(X,0,8)If {9*M+X+G}!=0If X!=LIf {9*M+X+G}={9*M+L+G}1->TReturnEndEndEndIf {9*X+L+G}!=0If X!=MIf {9*X+L+G}={9*M+L+G}1->TReturnEndEndEndEndA+2->CB+2->DFor(X,A,C)For(Y,B,D)If {9*Y+X+G}!=0If L!=X??M!=YIf {9*Y+X+G}={9*M+L+G}1->TReturnEndEndEndEndEnd0->TReturnLbl BACKTRACKIf {9*M+L+G}!=0sub(GETNEXT)End1->NWhile N!=10N->{9*M+L+G}sub(COLLISION)If T=0sub(ISFULL)If T=1ReturnEndL++If L=9M++0->LEndsub(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=1ReturnEndL--If L=655358->LM--EndIf L=08->LM--ElseL--EndEndN++End0->{9*M+L+G}0->TReturnIt also uses a stack library of my own creation to keep from overflowing the tiny 300 byte stack on the ti-83.
Code: [Select]
..STACKLIBLbl PUSH{[r1]}^^r+1->{[r1]}^^r{[r2]}^^r->{{[r1]}^^r+1+[r1]}ReturnLbl POPIf {[r1]}^^r>=>=0{{[r1]}^^r+1+[r1]}->{[r2]}^^r{[r1]}^^r-1->{[r1]}^^rElse0->{[r2]}EndReturnIt is rather minimal, but I don't think the stacklib is the problem. Any assistance?

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #1 on: September 17, 2014, 06:32:47 pm »
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.

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### Runer112

• Project Author
• LV11 Super Veteran (Next: 3000)
• Posts: 2289
• Rating: +639/-31
##### Re: Troublesome Sudoku Solver
« Reply #2 on: September 17, 2014, 10:27:48 pm »
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.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #3 on: September 18, 2014, 04:45:59 pm »
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).

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #4 on: September 18, 2014, 05:06:15 pm »
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 . It also needs to be optimized.

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #5 on: September 18, 2014, 10:27:42 pm »
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 , 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 .

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55942
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: Troublesome Sudoku Solver
« Reply #6 on: September 18, 2014, 11:54:10 pm »
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.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #7 on: September 19, 2014, 08:45:08 am »
I will remember that next time . I'm thinking about starting a new thread for the alpha, now that it works . Thanks to Runner112 for his advice on fixing this solver .

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #8 on: September 22, 2014, 07:35:02 am »
Hold on........AXE question
Does the code
Code: [Select]
X?GoTo nTranslate to
Code: [Select]
ld [address of x],HLcp HLnz jp [address of n]? If so there might be an even more optimized loop up the sleeve of AXE !

Computer Science is not the only science that matters, but it's definitely the most interesting.

#### aeTIos

• Nonbinary computing specialist
• LV12 Extreme Poster (Next: 5000)
• Posts: 3915
• Rating: +184/-32
##### Re: Troublesome Sudoku Solver
« Reply #9 on: September 22, 2014, 07:51:33 am »
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 , 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 .
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.
I'm not a nerd but I pretend:

#### Jsec42

• LV2 Member (Next: 40)
• Posts: 20
• Rating: +0/-0
##### Re: Troublesome Sudoku Solver
« Reply #10 on: September 22, 2014, 10:11:05 am »
Unless of course that optimization I came up with works even faster . It goes something like this.
Code: [Select]
lbl something..code goes hereconditionalasm(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
Code: [Select]
nlbl something-1->X..code goes hereXasm(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  .

EDIT: Conditional?goto something didn't work, so I made an assembly command.
« Last Edit: September 25, 2014, 07:45:00 am by Jsec42 »

Computer Science is not the only science that matters, but it's definitely the most interesting.