Sudoku Solver

Sudoku Solver - 消息

#1 已发布: 2019/8/30 08:52:43
overlord

overlord

600个赞,共1,381个帖子。

组: Moderator

I have been trying to make this code work for two days.
Actually it is a C code which I am trying to implicate to SMath. C code is also included and runs perfectly.
In SMath, code works to a point actually. When I debug it I can see it can assign numbers, backtrack if there is no option.
So SMath code also seems legit but eventually the algorithm just stop working. No error no significant reason.
With different puzzles, code terminated at different places at middle of calculation.
I couldn't figure out what is wrong. Is it a bug or my coding is insufficient?
Any help should be appreciated.

Regards.

sudoku.sm (26.74 KiB)已下载 1127 次。
sudoku.7z (38.26 KiB)已下载 553 次。


#2 已发布: 2019/8/30 13:06:01
Arie

Arie

94个赞,共285个帖子。

组: User

I posted something very inaccurate before and have since deleted it. However, in my testing, it seems that it's not dependent on the number of iterations. The function seems to stop when rw,cl get to around 2,4 or 2,5. This is independent of the number of function calls to fillSudoku.
Feel free to join the SMath Studio Users Discord Channel: https://discord.gg/PayZpJW
#3 已发布: 2019/8/30 13:18:25
Arie

Arie

94个赞,共285个帖子。

组: User

Wrote

I posted something very inaccurate before and have since deleted it. However, in my testing, it seems that it's not dependent on the number of iterations. The function seems to stop when rw,cl get to around 2,4 or 2,5. This is independent of the number of function calls to fillSudoku.



This looks to correlate to a depth of ~21 or 22 levels of recursion no matter the starting puzzle.
Feel free to join the SMath Studio Users Discord Channel: https://discord.gg/PayZpJW
#4 已发布: 2019/8/30 13:44:22
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

Wrote

With different puzzles, code terminated at different places at middle of calculation.
I couldn't figure out what is wrong. Is it a bug or my coding is insufficient?


I never heard of Sudoku. As it looks, you first scan for coincidence.
Can it relate to some truth table ? Then else game ... !

Sudoku.PNG
#5 已发布: 2019/8/30 13:47:06
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

... your original creates "critical error", that can be repaired in the first module.
#6 已发布: 2019/8/30 13:51:21
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

Wrote

... your original creates "critical error", that can be repaired in the first module.



Sudoku First Module.sm (17.66 KiB)已下载 1111 次。

#7 已发布: 2019/8/30 14:09:53
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

... make sure you completely understand the Bolean
from the code you imitate. As corrected, red.
Red may mean not winning ?

sudoku Freak.sm (23.07 KiB)已下载 1076 次。

#8 已发布: 2019/8/30 15:25:01
Arie

Arie

94个赞,共285个帖子。

组: User

Wrote

Wrote

I posted something very inaccurate before and have since deleted it. However, in my testing, it seems that it's not dependent on the number of iterations. The function seems to stop when rw,cl get to around 2,4 or 2,5. This is independent of the number of function calls to fillSudoku.



This looks to correlate to a depth of ~21 or 22 levels of recursion no matter the starting puzzle.



To better illustrate what I think is happening I've created the following worksheet. The first function definition is just a simple function that calls itself recursively until its 200th call at which point it exits. However, when run it experiences the same error as we see in the sudoku.sm. I rewrote the function using a try/on error and we see we only get to 50 iterations before it fails.

Untitled.png
recursion.sm (4.13 KiB)已下载 1087 次。
Feel free to join the SMath Studio Users Discord Channel: https://discord.gg/PayZpJW
#9 已发布: 2019/8/30 16:14:24
overlord

overlord

600个赞,共1,381个帖子。

组: Moderator

Wrote

This looks to correlate to a depth of ~21 or 22 levels of recursion no matter the starting puzzle.


Wrote


To better illustrate what I think is happening I've created the following worksheet. The first function definition is just a simple function that calls itself recursively until its 200th call at which point it exits. However, when run it experiences the same error as we see in the sudoku.sm. I rewrote the function using a try/on error and we see we only get to 50 iterations before it fails.

Untitled.png
recursion.sm (4.13 KiB)已下载 1087 次。



What I understood considering your last messages, you think there is nothing significant wrong with the code itself. Problem is SMath handling of recursions.
So, it comes forward that is why I wouldn't be able to make an SMath Sudoku Solver with recursion.

Thank you Alyles.
#10 已发布: 2019/8/30 19:41:02
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

I think it's possible to fill the '0' positions of the 9x9 Sudoku
with random not common to the existing filled position.
Filling one col at time, collect ...

Sudoku in(x,y).PNG
#11 已发布: 2019/8/31 10:50:00
Davide Carpi

Davide Carpi

1,443个赞,共2,936个帖子。

组: Moderator

Wrote

Wrote

This looks to correlate to a depth of ~21 or 22 levels of recursion no matter the starting puzzle.


Wrote


To better illustrate what I think is happening I've created the following worksheet. The first function definition is just a simple function that calls itself recursively until its 200th call at which point it exits. However, when run it experiences the same error as we see in the sudoku.sm. I rewrote the function using a try/on error and we see we only get to 50 iterations before it fails.

Untitled.png
recursion.sm (4.13 KiB)已下载 1087 次。



What I understood considering your last messages, you think there is nothing significant wrong with the code itself. Problem is SMath handling of recursions.
So, it comes forward that I wouldn't be able to make an SMath Sudoku Solver.

Thank you Alyles.



I remember this limitation was introduced some time ago to avoid unintentional hard crashes on wrong formed algorithms; considering that any recursive algorithm can be made iterative, you probably have to design it in another way or find a different code
If you like my plugins please consider to support the program buying a license; for personal contributions to me: paypal.me/dcprojects
1位用户喜欢此帖子
overlord 2019/8/31 13:08:00
#12 已发布: 2019/8/31 11:33:57
Arie

Arie

94个赞,共285个帖子。

组: User

As Davide said, you don't have to do it recursively.

It may be slow, but it works. Might be able to optimize for better performance.

Untitled.png
sudoku_lyles2.sm (28.25 KiB)已下载 1098 次。
Feel free to join the SMath Studio Users Discord Channel: https://discord.gg/PayZpJW
1位用户喜欢此帖子
sergio 2019/8/31 11:40:00
#13 已发布: 2019/8/31 11:48:48
Arie

Arie

94个赞,共285个帖子。

组: User

Wrote

As Davide said, you don't have to do it recursively.

It may be slow, but it works. Might be able to optimize for better performance.

Untitled.png
sudoku_lyles2.sm (28.25 KiB)已下载 1098 次。



Well it works for the first two puzzles at least. Having issues with the third. Haven't tried the fourth....

It's a start
Feel free to join the SMath Studio Users Discord Channel: https://discord.gg/PayZpJW
#14 已发布: 2019/8/31 12:42:16
NDTM Amarasekera

NDTM Amarasekera

130个赞,共352个帖子。

组: User

Wrote


Well it works for the first two puzzles at least. Having issues with the third. Haven't tried the fourth....



It works for the fourth, but fails for the third puzzle.
Look within!... The secret is inside you. Best Regards Eng. NDTM Amarasekera - Sri Lanka
#15 已发布: 2019/8/31 13:04:33
overlord

overlord

600个赞,共1,381个帖子。

组: Moderator

Wrote

I remember this limitation was introduced some time ago to avoid unintentional hard crashes on wrong formed algorithms; considering that any recursive algorithm can be made iterative, you probably have to design it in another way or find a different code


Wow, I didn't know there is a purposed limitation for recursion. For those who knows what they are doing, I think that limit can be removed by adding an extra code at the beginning like (recurselimit:=0), or re-adding the limit (recurselimit:=1).

Yeah it can be made iterative, alyles already did one as far as I can see. I just wanted you guys to check if I did something wrong about my algorithm. I just love recursing, I always feel like it is magical to me.

Thank you all guys, regards


#16 已发布: 2019/8/31 13:31:14
overlord

overlord

600个赞,共1,381个帖子。

组: Moderator

Wrote

Wrote


Well it works for the first two puzzles at least. Having issues with the third. Haven't tried the fourth....



It works for the fourth, but fails for the third puzzle.



Don't bother about it. I found these sudoku's on internet without checking them.
I checked that puzzle with C code right now and it has no solution.

Regards
#17 已发布: 2019/8/31 18:15:53
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

Confirmed: puzzle 3 fails "Requested matrix does not exist" [q=> 1..99]
#18 已发布: 2019/9/1 01:50:14
Alvaro

Alvaro

1,139个赞,共1,805个帖子。

组: User

Wrote


Wow, I didn't know there is a purposed limitation for recursion. For those who knows what they are doing, I think that limit can be removed by adding an extra code at the beginning like (recurselimit:=0), or re-adding the limit (recurselimit:=1).



Hi. It exists in other languages. For instance, can see it at https://reference.wolfram.com/language/ref/$RecursionLimit.html

Best regards.
Alvaro.
1位用户喜欢此帖子
overlord 2019/9/1 03:43:00
#19 已发布: 2019/9/1 10:15:02
Jean Giraud

Jean Giraud

983个赞,共6,866个帖子。

组: User

Wrote

Don't bother about it. I found these sudoku's on internet without checking them.
I checked that puzzle with C code right now and it has no solution.


You mean puzzle 3 has no solution ?
Solution is => give to champions.
Attached utilities may be useful otherwise.
Mathemtica 4.0 "recursion limit" is pure jargon.
In some program, if/otherwise does not work [if/else = YES].
Is there a catch wrt puzzle 3 ... Watson ?

Utilities Matrix Count in Soduku.sm (22.13 KiB)已下载 1152 次。
#20 已发布: 2019/9/2 23:14:14
Alvaro

Alvaro

1,139个赞,共1,805个帖子。

组: User

Hi. Here, the mathcad 11 version for the recursive method. Notice that mathcad don't pass values by reference, only by value, so the matrix can't be modified inside the fucntion, only 'outside'. Also, mathcad have the return function as keyword but isn't used.

SudokuRec.zip (24.01 KiB)已下载 390 次。
SudokuRec.pdf (285.89 KiB)已下载 745 次。

This other is te recurrent version in SMath: don't works.

SudokuRec.sm (45.18 KiB)已下载 1144 次。

This other is a rewrite of the alyles version.

SudokuBruteForce_lyles.sm (43.51 KiB)已下载 1181 次。

Best regards.
Alvaro.
1位用户喜欢此帖子
sergio 2019/9/3 05:02:00
  • 有新帖
  • 无新帖