Home > Archive > APL > February 2006 > APL Sudoko Solver
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
|
| It would seem ridiculous to write this myself when someone else has
already done it, so this is to ask for APL code to solve any Sudoko.
Tim
| |
| Don Kelly 2006-02-01, 3:55 am |
| doesn't that take the purpose out of doing sudoku?
--
Don Kelly @shawcross.ca
remove the X to answer
----------------------------
"timb" <bourketim@hotmail.com> wrote in message
news:1138761410.258242.53880@f14g2000cwb.googlegroups.com...
> It would seem ridiculous to write this myself when someone else has
> already done it, so this is to ask for APL code to solve any Sudoko.
>
> Tim
>
| |
| Mike Kent 2006-02-01, 3:55 am |
| Don Kelly wrote:
> doesn't that take the purpose out of doing sudoku?
Getting one from someone else surely does. Writing one yourself ...
| |
| Ellis Morgan 2006-02-01, 3:55 am |
| In article <44b2urF1ab7aU1@individual.net>, Mike Kent <mkent@acm.org>
writes
>Don Kelly wrote:
>
>Getting one from someone else surely does. Writing one yourself ...
There were a couple in vector 21.4 (go to www.vector.org.uk and look for
back issues). One of them was mine, why I wrote it is described in
vector, you are welcome to a copy it runs on Dyalog 10.1.
--
Ellis Morgan
| |
| LanceMD@gmail.com 2006-02-01, 6:55 pm |
| timb wrote:
> It would seem ridiculous to write this myself when someone else has
> already done it, so this is to ask for APL code to solve any Sudoko.
>
> Tim
If any one is interested, I can post my APL solution (APL Win). It's
about a dozen lines and uses recursion to solve the puzzle. It seems
to be able to solve anything sent its way.
Lance
| |
|
| timb wrote:
> It would seem ridiculous to write this myself when someone else has
> already done it, so this is to ask for APL code to solve any Sudoko.
Depends on your APL interpreter - if you have Dyalog, you'd perhaps
interested in the dynamic functions in www.dyalog.com/dfnsdws/index.htm
(scroll down to get the sudoku dfn)
And yes, trying to make the algorithm to solve the sudokus is even more
challenging (if you decide not to look at other people's code), and fun,
than just trying to solve the *&% problems...
Yours
- Veli-Matti
| |
|
| Post it!
LanceMD@gmail.com wrote:
> timb wrote:
>
> If any one is interested, I can post my APL solution (APL Win). It's
> about a dozen lines and uses recursion to solve the puzzle. It seems
> to be able to solve anything sent its way.
>
> Lance
>
| |
| LanceMD@gmail.com 2006-02-01, 6:55 pm |
| [0] Z{<-}SOLVE M;R;C;POSSIBLE;XX
[1] :FOR XX :IN {enclose}[1]1+9
9{representation}{neg}1+(,M=3D0)/{iota}81
[2]
{execute}((M[R;C]=3D0){and}1=3D{rho}POSS
IBLE{<-}({ioto}9)~M[R;],M[;C],,M[{n=
eg}3{take}{ioto}3=D7{ceiling}=F73=F7R{<-}XX[1];{neg}3{take}{iota}3=D7{ceili=
ng}=F73=F7C{<-}XX[2]])/'M[R;C]{<-}POSSIBLE[1]
{diamond} {->}1'
[3] {execute}(0=3D{rho}{rho}POSSIBLE)/'{->}ERROR'
[4] :ENDFOR
[5] {execute}({and}/{and}/0{doesn't equal}Z{<-}M)/'{->}0'
[6] :FOR XX :IN
({iota}9)~M[R;],M[;C],,M[{minus}3{take}{
iota}3=D7{ceiling}R=F73;{minus}3{ta=
ke}{iota}3=D7{ceiling}=F73=F7C{<-}M[R{<-}({floor}/M){iota}0;]{iota}0]
[7] M[R;C]{<-}XX
[8] Z{<-}SOLVE M
[9] {execute}({and}/{and}/Z{doesn't equal}0)/'{->}0'
[10] :ENDFOR
[11] {->}0
[12] ERROR: 'ERROR IN ORIGINAL MATRIX'
I sort of made up the translation, but I believe it's intuitive enough
such that my translation errors won't matter. {representation} is the
little big T (don't recall the name of this. Also it is quadIO{<-}1
I think that should be enough. The input variable M, is a 9 by 9
matrix with 0's placed for the blank squares in the puzzle.
Let me know if it does or does not work for others.
Lance
apl wrote:
> Post it! =20
>
| |
|
| Thanks.
LanceMD@gmail.com wrote:
> [0] Z{<-}SOLVE M;R;C;POSSIBLE;XX
> [1] :FOR XX :IN {enclose}[1]1+9
> 9{representation}{neg}1+(,M=0)/{iota}81
> [2]
> {execute}((M[R;C]=0){and}1={rho}POSSIBLE
{<- }({ioto}9)~M[R;],M[;C],,M[{neg}3{take}{i
oto}3×{ceiling}÷3÷R{<- }XX[1];{neg}3{take}{iota}3×{ceiling}÷3÷C
{<-}XX[2]])/'M[R;C]{<-}POSSIBLE[1]
> {diamond} {->}1'
> [3] {execute}(0={rho}{rho}POSSIBLE)/'{->}ERROR'
> [4] :ENDFOR
> [5] {execute}({and}/{and}/0{doesn't equal}Z{<-}M)/'{->}0'
> [6] :FOR XX :IN
> ({iota}9)~M[R;],M[;C],,M[{minus}3{take}{
iota}3×{ceiling}R÷3;{minus}3{take}{iota}
3×{ceiling}÷3÷C{<-}M[R{<-}({floor}/M){iota}0;]{iota}0]
> [7] M[R;C]{<-}XX
> [8] Z{<-}SOLVE M
> [9] {execute}({and}/{and}/Z{doesn't equal}0)/'{->}0'
> [10] :ENDFOR
> [11] {->}0
> [12] ERROR: 'ERROR IN ORIGINAL MATRIX'
>
> I sort of made up the translation, but I believe it's intuitive enough
> such that my translation errors won't matter. {representation} is the
> little big T (don't recall the name of this. Also it is quadIO{<-}1
>
> I think that should be enough. The input variable M, is a 9 by 9
> matrix with 0's placed for the blank squares in the puzzle.
>
> Let me know if it does or does not work for others.
>
> Lance
>
> apl wrote:
>
| |
|
| Here is your function with minor tweaks by removing the executes.
{del} Z{<-}Soduko M;R;C;POSSIBLE;XX
[1] @ LanceMD{@}gmail.com
[2] :for XX :in {enclose}[1]1+9 9{represent}{neg}1+(,M=0)/{iota}81
[3] i{<-}i+1
[4] :if ((M[R;C]=0)^1={rho}POSSIBLE{<- }({iota}9)~M[R;],M[;C],,M[{neg}3{take}{i
ota}3{times}{ceiling}{divide}3{divide}R{
<- }XX[1];{neg}3{take}{iota}3{times}{ceilin
g}{divide}3{divide}C{<-}XX[2]])
[5] M[R;C]{<-}POSSIBLE[1] & :continue
[6] :end
[7] {->}(0={rho}{rho}POSSIBLE)/ERROR
[8] :end
[9] {->}(^/^/0{/=}Z{<-}M)/0
[10] :for XX :in ({iota}9)~M[R;],M[;C],,M[{neg}3{take}{io
ta}3{times}{ceiling}R{divide}3;{neg}3{ta
ke}{iota}3{times}{ceiling}{divide}3{divi
de}C{<-}M[R{<-}({min}/M){iota}0;]{iota}0]
[11] M[R;C]{<-}XX
[12] Z{<-}Soduko M
[13] {->}(^/^/Z{/=}0)/0
[14] :end
[15] {->}0
[16] ERROR: 'ERROR IN ORIGINAL MATRIX'
{del}
LanceMD@gmail.com wrote:
> [0] Z{<-}SOLVE M;R;C;POSSIBLE;XX
> [1] :FOR XX :IN {enclose}[1]1+9
> 9{representation}{neg}1+(,M=0)/{iota}81
> [2]
> {execute}((M[R;C]=0){and}1={rho}POSSIBLE
{<- }({ioto}9)~M[R;],M[;C],,M[{neg}3{take}{i
oto}3×{ceiling}÷3÷R{<- }XX[1];{neg}3{take}{iota}3×{ceiling}÷3÷C
{<-}XX[2]])/'M[R;C]{<-}POSSIBLE[1]
> {diamond} {->}1'
> [3] {execute}(0={rho}{rho}POSSIBLE)/'{->}ERROR'
> [4] :ENDFOR
> [5] {execute}({and}/{and}/0{doesn't equal}Z{<-}M)/'{->}0'
> [6] :FOR XX :IN
> ({iota}9)~M[R;],M[;C],,M[{minus}3{take}{
iota}3×{ceiling}R÷3;{minus}3{take}{iota}
3×{ceiling}÷3÷C{<-}M[R{<-}({floor}/M){iota}0;]{iota}0]
> [7] M[R;C]{<-}XX
> [8] Z{<-}SOLVE M
> [9] {execute}({and}/{and}/Z{doesn't equal}0)/'{->}0'
> [10] :ENDFOR
> [11] {->}0
> [12] ERROR: 'ERROR IN ORIGINAL MATRIX'
>
> I sort of made up the translation, but I believe it's intuitive enough
> such that my translation errors won't matter. {representation} is the
> little big T (don't recall the name of this. Also it is quadIO{<-}1
>
> I think that should be enough. The input variable M, is a 9 by 9
> matrix with 0's placed for the blank squares in the puzzle.
>
> Let me know if it does or does not work for others.
>
> Lance
>
> apl wrote:
>
| |
| Tracker 2006-02-01, 6:55 pm |
| That post looked awful when I read it back, but not when I posted it. Try this in []cr format:
Z{<-}Soduko M;R;C;POSSIBLE;XX
@ LanceMD{@}gmail.com
:for XX :in {enclose}[1]1+9 9{represent}{neg}1+(,M=0)/{iota}81
i{<-}i+1
:if ((M[R;C]=0)^1={rho}POSSIBLE{<- }({iota}9)~M[R;],M[;C],,M[{neg}3{take}{i
ota}3{times}{ceiling}{divide}3{divide}R{
<- }XX[1];{neg}3{take}{iota}3{times}{ceilin
g}{divide}3{divide}C{<-}XX[2]])
M[R;C]{<-}POSSIBLE[1] & :continue
:end
{->}(0={rho}{rho}POSSIBLE)/ERROR
:end
{->}(^/^/0{/=}Z{<-}M)/0
:for XX :in ({iota}9)~M[R;],M[;C],,M[{neg}3{take}{io
ta}3{times}{ceiling}R{divide}3;{neg}3{ta
ke}{iota}3{times}{ceiling}{divide}3{divi
de}C{<-}M[R{<-}({min}/M){iota}0;]{iota}0]
M[R;C]{<-}XX
Z{<-}Soduko M
{->}(^/^/Z{/=}0)/0
:end
{->}0
ERROR: 'ERROR IN ORIGINAL MATRIX'
apl wrote:[color=darkred]
> Here is your function with minor tweaks by removing the executes.
>
> {del} Z{<-}Soduko
> M;R;C;POSSIBLE;XX
> [1] @ LanceMD{@}gmail.com
> [2] :for XX :in {enclose}[1]1+9 9{represent}{neg}1+(,M=0)/{iota}81
> [3]
> i{<-}i+1
> [4] :if
> ((M[R;C]=0)^1={rho}POSSIBLE{<- }({iota}9)~M[R;],M[;C],,M[{neg}3{take}{i
ota}3{times}{ceiling}{divide}3{divide}R{
<- }XX[1];{neg}3{take}{iota}3{times}{ceilin
g}{divide}3{divide}C{<-}XX[2]])
>
> [5] M[R;C]{<-}POSSIBLE[1] & :continue
> [6] :end
> [7] {->}(0={rho}{rho}POSSIBLE)/ERROR
> [8] :end
> [9] {->}(^/^/0{/=}Z{<-}M)/0
> [10] :for XX :in
> ({iota}9)~M[R;],M[;C],,M[{neg}3{take}{io
ta}3{times}{ceiling}R{divide}3;{neg}3{ta
ke}{iota}3{times}{ceiling}{divide}3{divi
de}C{<-}M[R{<-}({min}/M){iota}0;]{iota}0]
> [11]
> M[R;C]{<-}XX
> [12] Z{<-}Soduko
> M
> [13]
> {->}(^/^/Z{/=}0)/0
> [14] :end
> [15]
> {->}0
> [16] ERROR: 'ERROR IN ORIGINAL
> MATRIX'
> {del}
>
>
> LanceMD@gmail.com wrote:
| |
|
| Your post still looks bad.
Tracker wrote:[color=darkred]
> That post looked awful when I read it back, but not when I posted it.
> Try this in []cr format:
>
>
> Z{<-}Soduko
> M;R;C;POSSIBLE;XX
> @
> LanceMD{@}gmail.com
> :for XX :in {enclose}[1]1+9
> 9{represent}{neg}1+(,M=0)/{iota}81
>
> i{<-}i+1
> :if
> ((M[R;C]=0)^1={rho}POSSIBLE{<- }({iota}9)~M[R;],M[;C],,M[{neg}3{take}{i
ota}3{times}{ceiling}{divide}3{divide}R{
<- }XX[1];{neg}3{take}{iota}3{times}{ceilin
g}{divide}3{divide}C{<-}XX[2]])
>
> M[R;C]{<-}POSSIBLE[1] &
> :continue
>
> :end
>
> {->}(0={rho}{rho}POSSIBLE)/ERROR
> :end
> {->}(^/^/0{/=}Z{<-}M)/0
> :for XX :in
> ({iota}9)~M[R;],M[;C],,M[{neg}3{take}{io
ta}3{times}{ceiling}R{divide}3;{neg}3{ta
ke}{iota}3{times}{ceiling}{divide}3{divi
de}C{<-}M[R{<-}({min}/M){iota}0;]{iota}0]
>
> M[R;C]{<-}XX
> Z{<-}Soduko
> M
>
> {->}(^/^/Z{/=}0)/0
> :end
> {->}0
> ERROR: 'ERROR IN ORIGINAL
> MATRIX'
>
>
>
> apl wrote:
| |
| LanceMD@gmail.com 2006-02-01, 6:55 pm |
| A question, and two comments.
1=2E What is the purpose of the i{<-}i+1?
2=2E In the first loop, I specifically wanted to exit the loop and
restart the same loop if you found a unique solution to a square. This
is because as you fill in the squares, it can create possible solutions
in previous squares of the matrix when earlier they may have had two or
more unique solutions. Therefore I had a {->}1, which is going to act
differently than your :continue, which will just take you to the next
XX value in the loop. Yours may work, but it is my opinion that it
won't be as efficient in the long run.
3=2E I imagine that my code would look nicer if I had used {quad}IO{<-}0
instead of 1. Old habits are hard to change.
Lance
apl wrote:
> Here is your function with minor tweaks by removing the executes.
>
> {del} Z{<-}Soduko M;R;C;POSSIBLE;XX
> [1] @ LanceMD{@}gmail.com
> [2] :for XX :in {enclose}[1]1+9 9{represent}{neg}1+(,M=3D0)/{iota}81
> [3] i{<-}i+1
> [4] :if ((M[R;C]=3D0)^1=3D{rho}POSSIBLE{<-}({iota}9)~M[R;],M[;C],,M=
[{neg}3{take}{iota}3{times}{ceiling}{div
ide}3{divide}R{<-}XX[1];{neg}3{take=
}{iota}3{times}{ceiling}{divide}3{divide
}C{<-}XX[2]])
> [5] M[R;C]{<-}POSSIBLE[1] & :continue
> [6] :end
> [7] {->}(0=3D{rho}{rho}POSSIBLE)/ERROR
> [8] :end
> [9] {->}(^/^/0{/=3D}Z{<-}M)/0
> [10] :for XX :in ({iota}9)~M[R;],M[;C],,M[{neg}3{take}{io
ta}3{times}{cei=
ling}R{divide}3;{neg}3{take}{iota}3{time
s}{ceiling}{divide}3{divide}C{<-}M[=
R{<-}({min}/M){iota}0;]{iota}0][color=darkred]
> [11] M[R;C]{<-}XX
> [12] Z{<-}Soduko M
> [13] {->}(^/^/Z{/=3D}0)/0
> [14] :end
> [15] {->}0
> [16] ERROR: 'ERROR IN ORIGINAL MATRIX'
> {del}
>
>
> LanceMD@gmail.com wrote:
M[{neg}3{take}{ioto}3=D7{ceiling}=F73=F7
R{<-}XX[1];{neg}3{take}{iota}3=D7{c=
eiling}=F73=F7C{<-}XX[2]])/'M[R;C]{<-}POSSIBLE[1][color=darkred]
3{take}{iota}3=D7{ceiling}=F73=F7C{<-}M[R{<-}({floor}/M){iota}0;]{iota}0][color=darkred]
| |
|
| Ah - neglected to remove the i{<->i+1, was testing the number of iterations. I will now test using your {->}1 instead of :continue. Your solution is fast either way.
LanceMD@gmail.com wrote:
> A question, and two comments.
> 1. What is the purpose of the i{<-}i+1?
> 2. In the first loop, I specifically wanted to exit the loop and
> restart the same loop if you found a unique solution to a square. This
> is because as you fill in the squares, it can create possible solutions
> in previous squares of the matrix when earlier they may have had two or
> more unique solutions. Therefore I had a {->}1, which is going to act
> differently than your :continue, which will just take you to the next
> XX value in the loop. Yours may work, but it is my opinion that it
> won't be as efficient in the long run.
> 3. I imagine that my code would look nicer if I had used {quad}IO{<-}0
> instead of 1. Old habits are hard to change.
>
> Lance
>
> apl wrote:
>
| |
| Tracker 2006-02-01, 9:56 pm |
| LanceMD@gmail.com wrote:
> A question, and two comments.
> 1. What is the purpose of the i{<-}i+1?
> 2. In the first loop, I specifically wanted to exit the loop and
> restart the same loop if you found a unique solution to a square. This
> is because as you fill in the squares, it can create possible solutions
> in previous squares of the matrix when earlier they may have had two or
> more unique solutions. Therefore I had a {->}1, which is going to act
> differently than your :continue, which will just take you to the next
> XX value in the loop. Yours may work, but it is my opinion that it
> won't be as efficient in the long run.
> 3. I imagine that my code would look nicer if I had used {quad}IO{<-}0
> instead of 1. Old habits are hard to change.
>
> Lance
Here is the difference - your method is faster. Soduko is your original method. Soduko1 is with :continue.
Games: m mm mmm
0 6 0 1 0 4 0 5 0 0 0 0 0 2 5 0 3 0 7 0 0 8 0 0 0 5 0
0 0 8 3 0 5 6 0 0 0 0 0 4 0 0 0 7 0 0 0 0 6 0 0 0 0 0
2 0 0 0 0 0 0 0 1 6 0 0 9 0 0 0 8 0 9 0 4 0 0 0 0 0 2
8 0 0 4 0 7 0 0 6 0 0 2 0 9 0 5 0 0 0 2 0 0 9 0 0 6 0
0 0 6 0 0 0 3 0 0 0 0 3 0 0 0 1 0 0 0 1 0 0 0 0 0 7 0
7 0 0 9 0 1 0 0 4 0 0 7 0 8 0 2 0 0 0 9 0 0 5 0 0 8 0
5 0 0 0 0 0 0 0 2 0 9 0 0 0 6 0 0 4 5 0 0 0 0 0 6 0 3
0 0 7 2 0 6 9 0 0 0 5 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0
0 4 0 5 0 8 0 7 0 0 2 0 7 4 0 0 0 0 0 7 0 0 0 4 0 0 1
i{<-}0 & Soduko m & i & i{<-}0 & Soduko1 m & i
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
787
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
719
i{<-}0 & Soduko mm & i & i{<-}0 & Soduko1 mm & i
8 7 4 6 2 5 9 3 1
2 3 9 4 1 8 6 7 5
6 1 5 9 7 3 4 8 2
1 4 2 3 9 7 5 6 8
9 8 3 5 6 2 1 4 7
5 6 7 1 8 4 2 9 3
7 9 8 2 5 6 3 1 4
4 5 6 8 3 1 7 2 9
3 2 1 7 4 9 8 5 6
7884
8 7 4 6 2 5 9 3 1
2 3 9 4 1 8 6 7 5
6 1 5 9 7 3 4 8 2
1 4 2 3 9 7 5 6 8
9 8 3 5 6 2 1 4 7
5 6 7 1 8 4 2 9 3
7 9 8 2 5 6 3 1 4
4 5 6 8 3 1 7 2 9
3 2 1 7 4 9 8 5 6
7940
i{<-}0 & Soduko mmm & i & i{<-}0 & Soduko1 mmm & i
7 3 1 8 2 9 4 5 6
2 5 8 6 4 3 9 1 7
9 6 4 7 1 5 8 3 2
4 2 7 1 9 8 3 6 5
8 1 5 4 3 6 2 7 9
3 9 6 2 5 7 1 8 4
5 8 2 9 7 1 6 4 3
1 4 3 5 6 2 7 9 8
6 7 9 3 8 4 5 2 1
2134
7 3 1 8 2 9 4 5 6
2 5 8 6 4 3 9 1 7
9 6 4 7 1 5 8 3 2
4 2 7 1 9 8 3 6 5
8 1 5 4 3 6 2 7 9
3 9 6 2 5 7 1 8 4
5 8 2 9 7 1 6 4 3
1 4 3 5 6 2 7 9 8
6 7 9 3 8 4 5 2 1
2150
| |
| Don Kelly 2006-02-02, 3:55 am |
| ----------------------------
"Mike Kent" <mkent@acm.org> wrote in message
news:44b2urF1ab7aU1@individual.net...
> Don Kelly wrote:
>
> Getting one from someone else surely does. Writing one yourself ...
You have a valid point there. Judging from the responses, several people
have taken up this challenge which may be easier than actually hand solving
some of them.
--
Don Kelly @shawcross.ca
remove the X to answer
| |
| Christopher Browne 2006-02-02, 6:56 pm |
| > ----------------------------
> "Mike Kent" <mkent@acm.org> wrote in message
> news:44b2urF1ab7aU1@individual.net...
>
> You have a valid point there. Judging from the responses, several
> people have taken up this challenge which may be easier than
> actually hand solving some of them.
My implementation of such a solver was in Prolog; it was of about
comparable length to Roger Hui's, and I'll bet the same is true for
pretty well any "pretty high level language." And it'll provide
solutions in a comparable "a few milliseconds on modern hardware."
I wound up validating that a set of sudoku puzzles that I got were
wrongly framed, as they admitted multiple solutions :-(.
Anyone with the mindset where they can write a program to solve the
puzzles is anything but helpless at it.
One of my coworkers found his stepson coming home with sudoku puzzles
from school; he said, "Hey, I'll see about writing a program to solve
these!" (He chose PHP, providing an instant web interface; UI
actually is of some importance...) The stepson's reaction: "That's
impossible! You can't do that!" (At which I just shook my head.
Jan's not someone you should say "impossible" to...) Given the PHP
implementation, the solver was trivially turned into a web application
so that the stepson can solve them any time he likes even though he
doesn't know any programming languages yet...
--
"cbbrowne","@","gmail.com"
http://cbbrowne.com/info/linuxdistributions.html
"Transported to a surreal landscape, a young girl kills the first
woman she meets and then teams up with three complete strangers to
kill again." -- Unknown, Marin County newspaper's TV listing for _The
Wizard of Oz_
|
|
|
|
|