Re: sudoku solver
- To: mathgroup at smc.vnet.net
- Subject: [mg128215] Re: sudoku solver
- From: Fred Simons <f.h.simons at tue.nl>
- Date: Wed, 26 Sep 2012 04:11:46 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Delivered-to: l-mathgroup@wolfram.com
- Delivered-to: mathgroup-newout@smc.vnet.net
- Delivered-to: mathgroup-newsend@smc.vnet.net
- References: <20120925083815.DE57C6843@smc.vnet.net>
Sudoku puzzles can be solved with a computer, and therefore with
Mathematica, in a lot of ways. Your code is not very readable, but,
given the message on $RecursionLimit, it seems that you are using some
or other form of backtracking. My experience is that for 9 x 9 puzzles,
it is usually faster first to apply some simple logical rules before
switching to backtracking. Your second puzzle can be solved without any
backtracking by only using the logical rule hiddensingles.
Regards,
Fred Simons
Eindhoven University of Technology
Op 25-9-2012 10:38, lapajne.jure at gmail.com schreef:
> Hello, I'm trying to solve euler problem 96 - solve 50 sudokus. I have already written a solution in phyton and it works, but I have a problem in Mathematica.
> The code works for some sudokus while for others it gives me an error just before it finishes.The error message is:
> $RecursionLimit::reclim: Recursion depth of 256 exceeded. >>
> General::stop: Further output of $RecursionLimit::reclim will be suppressed during this calculation. >>
>
> examples:
> \left(
> \begin{array}{ccccccccc}
> 0 & 0 & 3 & 0 & 2 & 0 & 6 & 0 & 0 \\
> 9 & 0 & 0 & 3 & 0 & 5 & 0 & 0 & 1 \\
> 0 & 0 & 1 & 8 & 0 & 6 & 4 & 0 & 0 \\
> 0 & 0 & 8 & 1 & 0 & 2 & 9 & 0 & 0 \\
> 7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8 \\
> 0 & 0 & 6 & 7 & 0 & 8 & 2 & 0 & 0 \\
> 0 & 0 & 2 & 6 & 0 & 9 & 5 & 0 & 0 \\
> 8 & 0 & 0 & 2 & 0 & 3 & 0 & 0 & 9 \\
> 0 & 0 & 5 & 0 & 1 & 0 & 3 & 0 & 0
> \end{array}
> \right)
>
> but the next one doesn't finish:
> \left(
> \begin{array}{ccccccccc}
> 2 & 0 & 0 & 0 & 8 & 0 & 3 & 0 & 0 \\
> 0 & 6 & 0 & 0 & 7 & 0 & 0 & 8 & 4 \\
> 0 & 3 & 0 & 5 & 0 & 0 & 2 & 0 & 9 \\
> 0 & 0 & 0 & 1 & 0 & 5 & 4 & 0 & 8 \\
> 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
> 4 & 0 & 2 & 7 & 0 & 6 & 0 & 0 & 0 \\
> 3 & 0 & 1 & 0 & 0 & 7 & 0 & 4 & 0 \\
> 7 & 2 & 0 & 0 & 4 & 0 & 0 & 6 & 0 \\
> 0 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 3
> \end{array}
> \right)
>
> This one gives an error when it tries to solve the last zero (position {9,8}). The weird thing is that if I try to solve position {9,8} first and then everything else in normal order, it just stops one earlier (position {9,7}.
>
> My code is written below. I checked where it stops and it stops before the two for loops in sestopaj[..] module.
> code:
> main function:
>
> \text{sestopaj}[\text{delno0$\_$}]\text{:=}\text{Module}[\{\text{deln=
o}=\text{delno0},i=1,j=1,\text{k1},\text{z1},\text{mozne},d=0,\te=
xt{i1}=0,\text{j1}=0,a=0\},\{\text{i1}=0;\text{j1}=0;\text{If}[=
\text{resen}[\text{delno}],a=2;\text{Return}[]];\text{For}[i=1,i\leq =
9,i\text{++},\text{For}[j=1,j\leq 9,j\text{++},\text{If}[\text{delno}[[=
i,j]]==0,\text{i1}=i;\text{j1}=j;\text{Break}[]];];\text{If}[\tex=
t{i1}\neq 0 \&\&\text{j1}\neq 0,\text{Break}[]];];\text{mozne}=\text{mo=
znecifre}[\text{i1},\text{j1},\text{delno}];d=\text{Length}[\text{mozne=
}];\text{For}[\text{k1}=1,\text{k1}\leq 1d,\text{k1}\text{++},\text{del=
no}[[\text{i1},\text{j1}]]=\text{mozne}[[\text{k1}]];\text{Print}[\text=
{delno}];\text{z1}=\text{sestopaj}[\text{delno}];\text{If} [\text{z1}\n=
eq \text{None},a=1;\text{Return}[] ]; ];\text{delno}[[\text{i1},\text{j=
1}]]=0;\};\text{If}[a==2,\text{Return}[\text{delno}]];\text{If}[a==
=1,\text{Return}[\text{z1}],\text{Return}[\text{None}]];]
>
> auxiliary functions:
>
> \text{cifre}[\text{a0$\_$},\text{b0$\_$},\text{delno3$\_$}]\text{:=}\=
text{Module}[\{a=\text{a0},b=\text{b0},\text{vse},c,e,l,o\},\{c=1;e=
=1;\text{If}[a>10 \|b>10,\text{Print}[a,b]];\text{vse}=\{1,2,3,4,5,6,=
7,8,9\};\text{For}[c=1,c<10,c\text{++},\text{If}[\text{delno3}[[c,b]]\n=
eq 0 ,\text{vse}=\text{Complement}[\text{vse},\{\text{delno3}[[c,b]] \}=
] ];\text{If}[\text{delno3}[[a,c]]\neq 0, \text{vse}=\text{Complement}[=
\text{vse},\{\text{delno3}[[a,c]]\} ] ];];e=\text{IntegerPart}[(a-1)/3]=
*3+1;o=\text{IntegerPart}[(b-1)/3]*3+1;\text{For}[c=e,c<e+3,c\text{++=
},\text{For}[l=o,l<o+3,l\text{++},\text{vse}=\text{Complement}[\text{=
vse},\{\text{delno3}[[c,l]]\} ] ;]]\};\text{vse}]\text{moznecifre}[\text{=
f0$\_$},\text{g0$\_$},\text{delno1$\_$}]\text{:=}\text{Which}[\text{del=
no1}[[\text{f0},\text{g0}]]\neq 0,\{\},\text{delno1}[[\text{f0},\text{g0}=
]]==0, \text{cifre}[\text{f0},\text{g0},\text{delno1}]]\text{resen}[\=
text{delno2$\_$}]\text{:=}\text{Which}[\text{MemberQ}[\text{Flatten}[\t=
ext{d!
> elno2}],0
> ],\text{False},\text{MemberQ}[\text{Flatten}[\text{delno2}],0]==\=
text{False},\text{True}];
>
> I have tried changing a lot of things with no success. I'll appreciate =
any help. Thank you.
>
>
>
> -----
> Geen virus gevonden in dit bericht.
> Gecontroleerd door AVG - www.avg.com
> Versie: 2012.0.2221 / Virusdatabase: 2441/5290 - datum van uitgifte: 09=
/24/12
>
>
> .
>
- References:
- sudoku solver
- From: lapajne.jure@gmail.com
- sudoku solver