Author Topic: Troublesome Sudoku Solver  (Read 6998 times)

0 Members and 1 Guest are viewing this topic.

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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 :banghead: , though I am not entirely sure why. <_<
Code: [Select]
.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. ;)
Code: [Select]
..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?


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

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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. :banghead:


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

Offline Runer112

  • Project Author
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
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.

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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.

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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 :P . It also needs to be optimized. ;)


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

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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 :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: .


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

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
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. ;)

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
Re: Troublesome Sudoku Solver
« Reply #7 on: September 19, 2014, 08:45:08 am »
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 ;) .


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

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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],HL
cp HL
nz jp [address of n]
? If so there might be an even more optimized loop up the sleeve of AXE :o !


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

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
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 :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.
I'm not a nerd but I pretend:

Offline Jsec42

  • LV2 Member (Next: 40)
  • **
  • Posts: 20
  • Rating: +0/-0
    • View Profile
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 ;D . It goes something like this.
Code: [Select]
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
Code: [Select]
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.
« 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.