Message-ID:

Progress means replacing a theory that is wrong with one more subtly wrong.

devel / comp.lang.forth / Sudoku revisited

Sudoku revisited

<ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>

https://news.novabbs.org/devel/article-flat.php?id=24946&group=comp.lang.forth#24946

X-Received: by 2002:a05:6214:4b0b:b0:66a:d295:960c with SMTP id pj11-20020a0562144b0b00b0066ad295960cmr488636qvb.3.1697444415232;
Mon, 16 Oct 2023 01:20:15 -0700 (PDT)
X-Received: by 2002:a05:6830:33e1:b0:6c7:aab5:6b60 with SMTP id
i1-20020a05683033e100b006c7aab56b60mr2451733otu.2.1697444415026; Mon, 16 Oct
2023 01:20:15 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 01:20:14 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:4163:48df:51b:ab6a:d84f;
posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:4163:48df:51b:ab6a:d84f
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
Subject: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Mon, 16 Oct 2023 08:20:15 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2072

by: minforth - Mon, 16 Oct 2023 08:20 UTC

For the rainy autumn days to come ;-)

A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve performance.

Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?

The puzzle is:
_,_,_, _,_,_, _,_,_,
_,_,_, _,_,3, _,8,5,
_,_,1, _,2,_, _,_,_,

_,_,_, 5,_,7, _,_,_,
_,_,4, _,_,_, 1,_,_,
_,9,_, _,_,_, _,_,_,

5,_,_, _,_,_, _,7,3,
_,_,2, _,1,_, _,_,_,
_,_,_, _,4,_, _,_,9

Another hard one:
8,_,_, _,_,_, _,_,_,
_,_,3, 6,_,_, _,_,_,
_,7,_, _,9,_, 2,_,_,

_,5,_, _,_,7, _,_,_,
_,_,_, _,4,5, 7,_,_,
_,_,_, 1,_,_, _,3,_,

_,_,1, _,_,_, _,6,8,
_,_,8, 5,_,_, _,1,_,
_,9,_, _,_,_, 4,_,_

Re: Sudoku revisited

<e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24948&group=comp.lang.forth#24948

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:620a:49d:b0:775:7523:b690 with SMTP id 29-20020a05620a049d00b007757523b690mr583867qkr.4.1697446885721;
Mon, 16 Oct 2023 02:01:25 -0700 (PDT)
X-Received: by 2002:a05:6871:6a99:b0:1dc:34ea:1a6a with SMTP id
zf25-20020a0568716a9900b001dc34ea1a6amr11775565oab.6.1697446885397; Mon, 16
Oct 2023 02:01:25 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 02:01:24 -0700 (PDT)
In-Reply-To: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=79.45.240.13; posting-account=ryzhhAoAAAAIqf1uqmG9E4uP1Bagd-k2
NNTP-Posting-Host: 79.45.240.13
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com>
Subject: Re: Sudoku revisited
From: peter.m.falth@gmail.com (P Falth)
Injection-Date: Mon, 16 Oct 2023 09:01:25 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

by: P Falth - Mon, 16 Oct 2023 09:01 UTC

On Monday, 16 October 2023 at 10:20:16 UTC+2, minforth wrote:
> For the rainy autumn days to come ;-)
>
> A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve performance.
>
> Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?
>
It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

Peter

> The puzzle is:
> _,_,_, _,_,_, _,_,_,
> _,_,_, _,_,3, _,8,5,
> _,_,1, _,2,_, _,_,_,
>
> _,_,_, 5,_,7, _,_,_,
> _,_,4, _,_,_, 1,_,_,
> _,9,_, _,_,_, _,_,_,
>
> 5,_,_, _,_,_, _,7,3,
> _,_,2, _,1,_, _,_,_,
> _,_,_, _,4,_, _,_,9
>
> Another hard one:
> 8,_,_, _,_,_, _,_,_,
> _,_,3, 6,_,_, _,_,_,
> _,7,_, _,9,_, 2,_,_,
>
> _,5,_, _,_,7, _,_,_,
> _,_,_, _,4,5, 7,_,_,
> _,_,_, 1,_,_, _,3,_,
>
> _,_,1, _,_,_, _,6,8,
> _,_,8, 5,_,_, _,1,_,
> _,9,_, _,_,_, 4,_,_

Re: Sudoku revisited

<ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24949&group=comp.lang.forth#24949

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a0c:eb8b:0:b0:66c:fadf:b7ab with SMTP id x11-20020a0ceb8b000000b0066cfadfb7abmr310963qvo.3.1697448814977;
Mon, 16 Oct 2023 02:33:34 -0700 (PDT)
X-Received: by 2002:a05:6808:10d5:b0:3af:8f64:1810 with SMTP id
s21-20020a05680810d500b003af8f641810mr2734697ois.2.1697448814806; Mon, 16 Oct
2023 02:33:34 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 02:33:34 -0700 (PDT)
In-Reply-To: <e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:4163:48df:51b:ab6a:d84f;
posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:4163:48df:51b:ab6a:d84f
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com> <e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>
Subject: Re: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Mon, 16 Oct 2023 09:33:34 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2412

by: minforth - Mon, 16 Oct 2023 09:33 UTC

P Falth schrieb am Montag, 16. Oktober 2023 um 11:01:27 UTC+2:
> On Monday, 16 October 2023 at 10:20:16 UTC+2, minforth wrote:
> > For the rainy autumn days to come ;-)
> >
> > A few years ago there were some discussions and somewhat complicated program concepts here on c.l.f for solving Sudoku puzzles. I wondered if the Forth CLP methods developed for the Hexagon puzzle could be applied to Sudokus as well to improve performance.
> >
> > Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop, which is quite slow indeed. Can Forth do better?
> >
> It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)

:-) Congratulations!

I read that the first puzzle had been designed to stress simple backtracking solvers.
Concerning the second puzzle it was said that it is hard for humans.

Personally, I would probably throw my pencil out of the window after some minutes. ;-)

Re: Sudoku revisited

<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24950&group=comp.lang.forth#24950

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:620a:10b4:b0:76d:be21:5074 with SMTP id h20-20020a05620a10b400b0076dbe215074mr523089qkk.7.1697465792121;
Mon, 16 Oct 2023 07:16:32 -0700 (PDT)
X-Received: by 2002:a9d:7988:0:b0:6bd:c80d:2b65 with SMTP id
h8-20020a9d7988000000b006bdc80d2b65mr10429113otm.6.1697465791834; Mon, 16 Oct
2023 07:16:31 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 07:16:31 -0700 (PDT)
In-Reply-To: <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=77.174.47.232; posting-account=Ebqe4AoAAABfjCRL4ZqOHWv4jv5ZU4Cs
NNTP-Posting-Host: 77.174.47.232
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com> <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com>
Subject: Re: Sudoku revisited
From: the.beez.speaks@gmail.com (Hans Bezemer)
Injection-Date: Mon, 16 Oct 2023 14:16:32 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2537

by: Hans Bezemer - Mon, 16 Oct 2023 14:16 UTC

On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:
> > It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)
> :-) Congratulations!
>
> I read that the first puzzle had been designed to stress simple backtracking solvers.
> Concerning the second puzzle it was said that it is hard for humans.
I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th

It solved the second one in 0s flat:
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

The first one - a tiny delay (let's say a second):

9 8 7 | 6 5 4 | 3 2 1
2 4 6 | 1 7 3 | 9 8 5
3 5 1 | 9 2 8 | 7 4 6
------+-------+------
1 2 8 | 5 3 7 | 6 9 4
6 3 4 | 8 9 2 | 1 5 7
7 9 5 | 4 6 1 | 8 3 2
------+-------+------
5 1 9 | 2 8 6 | 4 7 3
4 7 2 | 3 1 9 | 5 6 8
8 6 3 | 7 4 5 | 2 1 9

Hans Bezemer

Re: Sudoku revisited

<255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24951&group=comp.lang.forth#24951

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:6214:19e8:b0:66d:28ec:8c12 with SMTP id q8-20020a05621419e800b0066d28ec8c12mr275855qvc.0.1697466934294;
Mon, 16 Oct 2023 07:35:34 -0700 (PDT)
X-Received: by 2002:a05:6808:30a7:b0:3af:6c87:144c with SMTP id
bl39-20020a05680830a700b003af6c87144cmr16638318oib.2.1697466934061; Mon, 16
Oct 2023 07:35:34 -0700 (PDT)
Path: i2pn2.org!i2pn.org!news.1d4.us!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 07:35:33 -0700 (PDT)
In-Reply-To: <cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:410d:c76:7149:4e17:8658;
posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:410d:c76:7149:4e17:8658
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com> <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>
<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
Subject: Re: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Mon, 16 Oct 2023 14:35:34 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3221

by: minforth - Mon, 16 Oct 2023 14:35 UTC

Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:
> On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:
> > > It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)
> > :-) Congratulations!
> >
> > I read that the first puzzle had been designed to stress simple backtracking solvers.
> > Concerning the second puzzle it was said that it is hard for humans.
> I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
> https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th
>
> It solved the second one in 0s flat:
> 8 1 2 | 7 5 3 | 6 4 9
> 9 4 3 | 6 8 2 | 1 7 5
> 6 7 5 | 4 9 1 | 2 8 3
> ------+-------+------
> 1 5 4 | 2 3 7 | 8 9 6
> 3 6 9 | 8 4 5 | 7 2 1
> 2 8 7 | 1 6 9 | 5 3 4
> ------+-------+------
> 5 2 1 | 9 7 4 | 3 6 8
> 4 3 8 | 5 2 6 | 9 1 7
> 7 9 6 | 3 1 8 | 4 5 2
>
> The first one - a tiny delay (let's say a second):
>
> 9 8 7 | 6 5 4 | 3 2 1
> 2 4 6 | 1 7 3 | 9 8 5
> 3 5 1 | 9 2 8 | 7 4 6
> ------+-------+------
> 1 2 8 | 5 3 7 | 6 9 4
> 6 3 4 | 8 9 2 | 1 5 7
> 7 9 5 | 4 6 1 | 8 3 2
> ------+-------+------
> 5 1 9 | 2 8 6 | 4 7 3
> 4 7 2 | 3 1 9 | 5 6 8
> 8 6 3 | 7 4 5 | 2 1 9
>

The first one looks like a synthetic exercise made up only as backtracking benchmark.
Look at the first row. So it is perhaps easier to solve with non-backtracking methods.

The second one perhaps just demonstrates that a computer can hold more variables
in his memory than most human beings in their mind. See
https://abcnews.go.com/blogs/headlines/2012/06/can-you-solve-the-hardest-ever-sudoku

Re: Sudoku revisited

<2810effb-c229-45d2-851e-5dd7aa23394bn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24952&group=comp.lang.forth#24952

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:6214:328a:b0:66d:25d6:4021 with SMTP id mu10-20020a056214328a00b0066d25d64021mr200572qvb.3.1697471276430;
Mon, 16 Oct 2023 08:47:56 -0700 (PDT)
X-Received: by 2002:a05:6870:988c:b0:1dd:1837:c704 with SMTP id
eg12-20020a056870988c00b001dd1837c704mr12823894oab.2.1697471276227; Mon, 16
Oct 2023 08:47:56 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 08:47:55 -0700 (PDT)
In-Reply-To: <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=77.174.47.232; posting-account=Ebqe4AoAAABfjCRL4ZqOHWv4jv5ZU4Cs
NNTP-Posting-Host: 77.174.47.232
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com> <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com>
<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <2810effb-c229-45d2-851e-5dd7aa23394bn@googlegroups.com>
Subject: Re: Sudoku revisited
From: the.beez.speaks@gmail.com (Hans Bezemer)
Injection-Date: Mon, 16 Oct 2023 15:47:56 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 2238

by: Hans Bezemer - Mon, 16 Oct 2023 15:47 UTC

On Monday, October 16, 2023 at 4:35:36 PM UTC+2, minforth wrote:
> The second one perhaps just demonstrates that a computer can hold more variables
> in his memory than most human beings in their mind. See
> https://abcnews.go.com/blogs/headlines/2012/06/can-you-solve-the-hardest-ever-sudoku

The solvers behavior on that one was more like the second one - instantaneous. But it's an
interesting exercise - as a person you have almost zero "sure" digits. But like I said - not a
challenge for the algorithm.

8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2

Hans Bezemer

Re: Sudoku revisited

<230d7996-ca88-45a3-84aa-509c0cfdf2adn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24957&group=comp.lang.forth#24957

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:6214:4a8a:b0:66d:b89:4f0d with SMTP id pi10-20020a0562144a8a00b0066d0b894f0dmr7922qvb.1.1697484533432;
Mon, 16 Oct 2023 12:28:53 -0700 (PDT)
X-Received: by 2002:a05:6871:686:b0:1e9:f600:53d with SMTP id
l6-20020a056871068600b001e9f600053dmr12977oao.10.1697484533257; Mon, 16 Oct
2023 12:28:53 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Mon, 16 Oct 2023 12:28:52 -0700 (PDT)
In-Reply-To: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f18:6d00:9d62:85d6:2c25:4389;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f18:6d00:9d62:85d6:2c25:4389
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <230d7996-ca88-45a3-84aa-509c0cfdf2adn@googlegroups.com>
Subject: Re: Sudoku revisited
From: mhx@iae.nl (Marcel Hendrix)
Injection-Date: Mon, 16 Oct 2023 19:28:53 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

by: Marcel Hendrix - Mon, 16 Oct 2023 19:28 UTC

On Monday, October 16, 2023 at 10:20:16 AM UTC+2, minforth wrote:
> For the rainy autumn days to come ;-)
> Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking
> methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop,
> which is quite slow indeed. Can Forth do better?

One second? How old is that laptop?

AMD Ryzen 7 5800X 8-Core Processor
TICKS-GET uses os time & PROCESSOR-CLOCK 4192MHz

I do not use parallel tricks here (on my Z840 a speedup of 88 times would be expected)

FORTH> speedthem
0.032 milliseconds (originally 4.36 ms for the computer)
0.028 milliseconds (45 minutes human)
0.140 milliseconds (2 hours human)
0.029 milliseconds (2 hours for a human, maybe impossible)
0.003 milliseconds (unknown source)
0.004 milliseconds (Paul Hsieh's example #1)
0.003 milliseconds (Paul Hsieh's example #2)
0.003 milliseconds (Paul Hsieh's example #3)
0.302 milliseconds (A `minimal' Sudoku (thought impossible for humans))
0.006 milliseconds (Ertl #1)
0.014 milliseconds (Ertl #2)
0.432 milliseconds (Ertl #3)
0.002 milliseconds (Ertl #4)
0.004 milliseconds (Ertl #5)
0.015 milliseconds (Ertl #6)
0.002 milliseconds (Ertl #7)
0.009 milliseconds (Ertl #8)
0.006 milliseconds (Rickman ExtraHard)
0.029 milliseconds (Albert van der Horst's Python example)
112.000 milliseconds (Sudoku17.txt line 527)
348.000 milliseconds (Sudoku17.txt line 6361)
0.993 milliseconds (Arto Inkala, unsolvable to all but the sharpest minds)
5.345 milliseconds (David Filmer, rated above extreme)
16.000 milliseconds (W_a_x_man's challenge)
3.857 milliseconds (minforth's challenge #1)
0.993 milliseconds (minforth's challenge #2) ok

Re: Sudoku revisited

<433fd9b8-2d91-4b63-89d2-1d01135627can@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24958&group=comp.lang.forth#24958

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:622a:6f0c:b0:41b:aeda:d186 with SMTP id iv12-20020a05622a6f0c00b0041baedad186mr31835qtb.4.1697557879418;
Tue, 17 Oct 2023 08:51:19 -0700 (PDT)
X-Received: by 2002:a05:6870:1782:b0:1e9:9b32:3e7c with SMTP id
r2-20020a056870178200b001e99b323e7cmr900575oae.4.1697557879249; Tue, 17 Oct
2023 08:51:19 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Tue, 17 Oct 2023 08:51:18 -0700 (PDT)
In-Reply-To: <230d7996-ca88-45a3-84aa-509c0cfdf2adn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:410c:54c6:8db7:b540:bb21;
posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:410c:54c6:8db7:b540:bb21
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com> <230d7996-ca88-45a3-84aa-509c0cfdf2adn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <433fd9b8-2d91-4b63-89d2-1d01135627can@googlegroups.com>
Subject: Re: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Tue, 17 Oct 2023 15:51:19 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 1806

by: minforth - Tue, 17 Oct 2023 15:51 UTC

Marcel Hendrix schrieb am Montag, 16. Oktober 2023 um 21:28:54 UTC+2:
> On Monday, October 16, 2023 at 10:20:16 AM UTC+2, minforth wrote:
> > For the rainy autumn days to come ;-)
> > Recently I came across a puzzle that claimed to be particularly difficult to solve using backtracking
> > methods. So it can be used as benchmark. It took about 1s to solve with Prolog on my old laptop,
> > which is quite slow indeed. Can Forth do better?
> One second? How old is that laptop?

Old ?? 22y isn't old here !! ;-)

Re: Sudoku revisited

<e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24959&group=comp.lang.forth#24959

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:620a:2415:b0:774:143e:f96a with SMTP id d21-20020a05620a241500b00774143ef96amr91603qkn.12.1697626665363; Wed, 18 Oct 2023 03:57:45 -0700 (PDT)
X-Received: by 2002:a05:6808:2190:b0:3a8:45f0:b83a with SMTP id be16-20020a056808219000b003a845f0b83amr1442670oib.5.1697626665083; Wed, 18 Oct 2023 03:57:45 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!69.80.99.15.MISMATCH!border-1.nntp.ord.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Wed, 18 Oct 2023 03:57:44 -0700 (PDT)
In-Reply-To: <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:410c:54c6:8db7:b540:bb21; posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:410c:54c6:8db7:b540:bb21
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com> <e1115f65-59de-4eba-8f06-8e857644f21en@googlegroups.com> <ec0045da-68d7-447b-bbf6-5a1e5e8ef0f0n@googlegroups.com> <cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com>
Subject: Re: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Wed, 18 Oct 2023 10:57:45 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 56

by: minforth - Wed, 18 Oct 2023 10:57 UTC

minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:
> Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:
> > On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:
> > > > It took me 11min 26sec to solve it with my head!, without using backtracking. So Prolog is almost 700 times faster then me ;-)
> > > :-) Congratulations!
> > >
> > > I read that the first puzzle had been designed to stress simple backtracking solvers.
> > > Concerning the second puzzle it was said that it is hard for humans.
> > I've had a sudoku solver in my repository since 2005 (Version: 1900 01092005 - Robert Spykerman)
> > https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku..4th
> >
> > It solved the second one in 0s flat:
> > 8 1 2 | 7 5 3 | 6 4 9
> > 9 4 3 | 6 8 2 | 1 7 5
> > 6 7 5 | 4 9 1 | 2 8 3
> > ------+-------+------
> > 1 5 4 | 2 3 7 | 8 9 6
> > 3 6 9 | 8 4 5 | 7 2 1
> > 2 8 7 | 1 6 9 | 5 3 4
> > ------+-------+------
> > 5 2 1 | 9 7 4 | 3 6 8
> > 4 3 8 | 5 2 6 | 9 1 7
> > 7 9 6 | 3 1 8 | 4 5 2
> >
> > The first one - a tiny delay (let's say a second):
> >
> > 9 8 7 | 6 5 4 | 3 2 1
> > 2 4 6 | 1 7 3 | 9 8 5
> > 3 5 1 | 9 2 8 | 7 4 6
> > ------+-------+------
> > 1 2 8 | 5 3 7 | 6 9 4
> > 6 3 4 | 8 9 2 | 1 5 7
> > 7 9 5 | 4 6 1 | 8 3 2
> > ------+-------+------
> > 5 1 9 | 2 8 6 | 4 7 3
> > 4 7 2 | 3 1 9 | 5 6 8
> > 8 6 3 | 7 4 5 | 2 1 9
> >
> The first one looks like a synthetic exercise made up only as backtracking benchmark.
> Look at the first row. So it is perhaps easier to solve with non-backtracking methods.

Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be
swapped, without destroying solvability.

Such symmetries could be used to precondition the matrix for a speedier solver (less backtracking).
Don't ask if it is worth it. ;-) It is only a game.

Re: Sudoku revisited

<nnd$6d0069ac$7fb26984@efebf0675e8eb255>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24960&group=comp.lang.forth#24960

copy link Newsgroups: comp.lang.forth

Newsgroups: comp.lang.forth
Subject: Re: Sudoku revisited
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com> <cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com> <e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com>
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
From: albert@cherry (none)
Originator: albert@cherry.(none) (albert)
Message-ID: <nnd$6d0069ac$7fb26984@efebf0675e8eb255>
Organization: KPN B.V.
Date: Wed, 18 Oct 2023 14:37:29 +0200
Path: i2pn2.org!i2pn.org!news.swapon.de!news.in-chemnitz.de!2.eu.feeder.erje.net!feeder.erje.net!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!feed.abavia.com!abe004.abavia.com!abp002.abavia.com!news.kpn.nl!not-for-mail
Lines: 73
Injection-Date: Wed, 18 Oct 2023 14:37:29 +0200
Injection-Info: news.kpn.nl; mail-complaints-to="abuse@kpn.com"
X-Received-Bytes: 3598

by: none - Wed, 18 Oct 2023 12:37 UTC

In article <e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com>,
minforth <minforth@arcor.de> wrote:
>minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:
>> Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:
>> > On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:
>> > > > It took me 11min 26sec to solve it with my head!, without using
>backtracking. So Prolog is almost 700 times faster then me ;-)
>> > > :-) Congratulations!
>> > >
>> > > I read that the first puzzle had been designed to stress simple
>backtracking solvers.
>> > > Concerning the second puzzle it was said that it is hard for humans.
>> > I've had a sudoku solver in my repository since 2005 (Version: 1900
>01092005 - Robert Spykerman)
>> > https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th
>> >
>> > It solved the second one in 0s flat:
>> > 8 1 2 | 7 5 3 | 6 4 9
>> > 9 4 3 | 6 8 2 | 1 7 5
>> > 6 7 5 | 4 9 1 | 2 8 3
>> > ------+-------+------
>> > 1 5 4 | 2 3 7 | 8 9 6
>> > 3 6 9 | 8 4 5 | 7 2 1
>> > 2 8 7 | 1 6 9 | 5 3 4
>> > ------+-------+------
>> > 5 2 1 | 9 7 4 | 3 6 8
>> > 4 3 8 | 5 2 6 | 9 1 7
>> > 7 9 6 | 3 1 8 | 4 5 2
>> >
>> > The first one - a tiny delay (let's say a second):
>> >
>> > 9 8 7 | 6 5 4 | 3 2 1
>> > 2 4 6 | 1 7 3 | 9 8 5
>> > 3 5 1 | 9 2 8 | 7 4 6
>> > ------+-------+------
>> > 1 2 8 | 5 3 7 | 6 9 4
>> > 6 3 4 | 8 9 2 | 1 5 7
>> > 7 9 5 | 4 6 1 | 8 3 2
>> > ------+-------+------
>> > 5 1 9 | 2 8 6 | 4 7 3
>> > 4 7 2 | 3 1 9 | 5 6 8
>> > 8 6 3 | 7 4 5 | 2 1 9
>> >
>> The first one looks like a synthetic exercise made up only as
>backtracking benchmark.
>> Look at the first row. So it is perhaps easier to solve with
>non-backtracking methods.
>
>Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be
>swapped, without destroying solvability.
>
>Such symmetries could be used to precondition the matrix for a speedier
>solver (less backtracking).
>Don't ask if it is worth it. ;-) It is only a game.
>

I sort the fields to be probed once in the beginning, on the
remaining possibilities of the content. This order is relevant
throughout.
It is remarkable that the second sudoku is much harder in my book also.
28 ms versus 180 ms on my 4 Ghz AMD system.
(11 versus 75 if I kill mprime that is running on 8 cores.).

It is remarkable that Marcel Hendrix solved the second soduku
substantially faster than the first. Is that an error?

Groetjes Albert
--
Don't praise the day before the evening. One swallow doesn't make spring.
You must not say "hey" before you have crossed the bridge. Don't sell the
hide of the bear until you shot it. Better one bird in the hand than ten in
the air. First gain is a cat spinning. - the Wise from Antrim -

Re: Sudoku revisited

<cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24962&group=comp.lang.forth#24962

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:ad4:4b62:0:b0:66d:12f9:9635 with SMTP id m2-20020ad44b62000000b0066d12f99635mr105733qvx.4.1697635634436;
Wed, 18 Oct 2023 06:27:14 -0700 (PDT)
X-Received: by 2002:a05:6870:9555:b0:1e1:15ca:2aa1 with SMTP id
v21-20020a056870955500b001e115ca2aa1mr1709481oal.11.1697635633752; Wed, 18
Oct 2023 06:27:13 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Wed, 18 Oct 2023 06:27:13 -0700 (PDT)
In-Reply-To: <nnd$6d0069ac$7fb26984@efebf0675e8eb255>
Injection-Info: google-groups.googlegroups.com; posting-host=2003:f7:1f3d:410c:54c6:8db7:b540:bb21;
posting-account=AqNUYgoAAADmkK2pN-RKms8sww57W0Iw
NNTP-Posting-Host: 2003:f7:1f3d:410c:54c6:8db7:b540:bb21
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
<e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com> <nnd$6d0069ac$7fb26984@efebf0675e8eb255>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>
Subject: Re: Sudoku revisited
From: minforth@arcor.de (minforth)
Injection-Date: Wed, 18 Oct 2023 13:27:14 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 4519

by: minforth - Wed, 18 Oct 2023 13:27 UTC

none albert schrieb am Mittwoch, 18. Oktober 2023 um 14:37:34 UTC+2:
> In article <e1bb7bd8-2195-4cea...@googlegroups.com>,
> minforth <minf...@arcor.de> wrote:
> >minforth schrieb am Montag, 16. Oktober 2023 um 16:35:36 UTC+2:
> >> Hans Bezemer schrieb am Montag, 16. Oktober 2023 um 16:16:33 UTC+2:
> >> > On Monday, October 16, 2023 at 11:33:36 AM UTC+2, minforth wrote:
> >> > > > It took me 11min 26sec to solve it with my head!, without using
> >backtracking. So Prolog is almost 700 times faster then me ;-)
> >> > > :-) Congratulations!
> >> > >
> >> > > I read that the first puzzle had been designed to stress simple
> >backtracking solvers.
> >> > > Concerning the second puzzle it was said that it is hard for humans.
> >> > I've had a sudoku solver in my repository since 2005 (Version: 1900
> >01092005 - Robert Spykerman)
> >> > https://sourceforge.net/p/forth-4th/code/HEAD/tree/trunk/4th.src/sudoku.4th
> >> >
> >> > It solved the second one in 0s flat:
> >> > 8 1 2 | 7 5 3 | 6 4 9
> >> > 9 4 3 | 6 8 2 | 1 7 5
> >> > 6 7 5 | 4 9 1 | 2 8 3
> >> > ------+-------+------
> >> > 1 5 4 | 2 3 7 | 8 9 6
> >> > 3 6 9 | 8 4 5 | 7 2 1
> >> > 2 8 7 | 1 6 9 | 5 3 4
> >> > ------+-------+------
> >> > 5 2 1 | 9 7 4 | 3 6 8
> >> > 4 3 8 | 5 2 6 | 9 1 7
> >> > 7 9 6 | 3 1 8 | 4 5 2
> >> >
> >> > The first one - a tiny delay (let's say a second):
> >> >
> >> > 9 8 7 | 6 5 4 | 3 2 1
> >> > 2 4 6 | 1 7 3 | 9 8 5
> >> > 3 5 1 | 9 2 8 | 7 4 6
> >> > ------+-------+------
> >> > 1 2 8 | 5 3 7 | 6 9 4
> >> > 6 3 4 | 8 9 2 | 1 5 7
> >> > 7 9 5 | 4 6 1 | 8 3 2
> >> > ------+-------+------
> >> > 5 1 9 | 2 8 6 | 4 7 3
> >> > 4 7 2 | 3 1 9 | 5 6 8
> >> > 8 6 3 | 7 4 5 | 2 1 9
> >> >
> >> The first one looks like a synthetic exercise made up only as
> >backtracking benchmark.
> >> Look at the first row. So it is perhaps easier to solve with
> >non-backtracking methods.
> >
> >Sudokus can be rotated by n x 90 degrees, rows/columns 1-3 or 4-6 or 7-9 can be
> >swapped, without destroying solvability.
> >
> >Such symmetries could be used to precondition the matrix for a speedier
> >solver (less backtracking).
> >Don't ask if it is worth it. ;-) It is only a game.
> >
> I sort the fields to be probed once in the beginning, on the
> remaining possibilities of the content. This order is relevant
> throughout.
> It is remarkable that the second sudoku is much harder in my book also.
> 28 ms versus 180 ms on my 4 Ghz AMD system.
> (11 versus 75 if I kill mprime that is running on 8 cores.).
>
> It is remarkable that Marcel Hendrix solved the second soduku
> substantially faster than the first. Is that an error?

The majority of Marcel's timings were in the sub-milliseconds range,
while some puzzles took substantially longer. I wondered if this
"discrepancy" was caused by where in the matrix the algorithm started.

Re: Sudoku revisited

<315b96b8-aef7-4411-b4fe-774841d8c2ebn@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24973&group=comp.lang.forth#24973

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:ac8:6044:0:b0:412:1a03:ba55 with SMTP id k4-20020ac86044000000b004121a03ba55mr3182qtm.9.1697656217266;
Wed, 18 Oct 2023 12:10:17 -0700 (PDT)
X-Received: by 2002:a05:6870:c10c:b0:1e9:df55:aed6 with SMTP id
f12-20020a056870c10c00b001e9df55aed6mr132360oad.7.1697656217044; Wed, 18 Oct
2023 12:10:17 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Wed, 18 Oct 2023 12:10:16 -0700 (PDT)
In-Reply-To: <cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f18:6d00:8465:5624:d989:34a4;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f18:6d00:8465:5624:d989:34a4
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
<e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com> <nnd$6d0069ac$7fb26984@efebf0675e8eb255>
<cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <315b96b8-aef7-4411-b4fe-774841d8c2ebn@googlegroups.com>
Subject: Re: Sudoku revisited
From: mhx@iae.nl (Marcel Hendrix)
Injection-Date: Wed, 18 Oct 2023 19:10:17 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

by: Marcel Hendrix - Wed, 18 Oct 2023 19:10 UTC

On Wednesday, October 18, 2023 at 3:27:16 PM UTC+2, minforth wrote:
[..]
> The majority of Marcel's timings were in the sub-milliseconds range,
> while some puzzles took substantially longer. I wondered if this
> "discrepancy" was caused by where in the matrix the algorithm started.

A really good deduction.

I changed SOLVER to test for 9 to 1 instead of from 1 to 9 in sudoku_fast

: solver ( -- bool )
findnextmove dup 0< IF DROP morespaces? 0= EXIT THEN
\ #10 1
1 9 DO I OVER try
IF I OVER addnumber
recurse IF DROP TRUE UNLOOP EXIT
ELSE DUP removenumber
ENDIF
ENDIF
\ LOOP
-1 +LOOP DROP FALSE ; PRIVATE

This gave the following substantial differences:

FORTH> speedthem
0.170 milliseconds (originally 4.36 ms for the computer)
0.014 milliseconds (45 minutes human)
0.016 milliseconds (2 hours human)
0.017 milliseconds (2 hours for a human, maybe impossible)
0.002 milliseconds (unknown source)
0.005 milliseconds (Paul Hsieh's example #1)
0.003 milliseconds (Paul Hsieh's example #2)
0.002 milliseconds (Paul Hsieh's example #3)
0.023 milliseconds (A `minimal' Sudoku (thought impossible for humans))
0.003 milliseconds (Ertl #1)
0.002 milliseconds (Ertl #2)
0.289 milliseconds (Ertl #3)
0.002 milliseconds (Ertl #4)
0.007 milliseconds (Ertl #5)
0.020 milliseconds (Ertl #6)
0.003 milliseconds (Ertl #7)
0.009 milliseconds (Ertl #8)
0.006 milliseconds (Rickman ExtraHard)
0.013 milliseconds (Albert van der Horst's Python example)
1.000 milliseconds (Sudoku17.txt line 527)
72.000 milliseconds (Sudoku17.txt line 6361)
0.689 milliseconds (Arto Inkala, unsolvable to all but the sharpest minds)
7.418 milliseconds (David Filmer, rated above extreme)
8.000 milliseconds (W_a_x_man's challenge)
2.079 milliseconds (minforth's challenge #1)
0.689 milliseconds (minforth's challenge #2) ok

It does not really explain explain why challenge #2 is easier
than challenge #1, but a different starting value definitely
makes a difference.
If I had to beat Go, a parallel program (9 threads) might be worth a try.

-marcel

Re: Sudoku revisited

<2a103d3c-ecc7-43f6-a039-643f0d6b06b1n@googlegroups.com>

copy mid

https://news.novabbs.org/devel/article-flat.php?id=24974&group=comp.lang.forth#24974

copy link Newsgroups: comp.lang.forth

X-Received: by 2002:a05:6214:43c7:b0:66c:ffe5:1984 with SMTP id oi7-20020a05621443c700b0066cffe51984mr165830qvb.6.1697656507460;
Wed, 18 Oct 2023 12:15:07 -0700 (PDT)
X-Received: by 2002:a05:6808:15a3:b0:3b2:e7a8:f7dd with SMTP id
t35-20020a05680815a300b003b2e7a8f7ddmr9991oiw.11.1697656507121; Wed, 18 Oct
2023 12:15:07 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!feeder.erje.net!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.lang.forth
Date: Wed, 18 Oct 2023 12:15:06 -0700 (PDT)
In-Reply-To: <cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2001:1c05:2f18:6d00:8465:5624:d989:34a4;
posting-account=-JQ2RQoAAAB6B5tcBTSdvOqrD1HpT_Rk
NNTP-Posting-Host: 2001:1c05:2f18:6d00:8465:5624:d989:34a4
References: <ca5d0a35-9693-4ed8-8729-58bce3cdd61en@googlegroups.com>
<cfa5da64-95e4-4001-b896-201117078748n@googlegroups.com> <255a3fa7-6b1e-4d3f-8031-6ffa108cf97bn@googlegroups.com>
<e1bb7bd8-2195-4cea-ab04-7f3995676abdn@googlegroups.com> <nnd$6d0069ac$7fb26984@efebf0675e8eb255>
<cf4f5cba-ca28-4cf3-8b31-252c2be11cdcn@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <2a103d3c-ecc7-43f6-a039-643f0d6b06b1n@googlegroups.com>
Subject: Re: Sudoku revisited
From: mhx@iae.nl (Marcel Hendrix)
Injection-Date: Wed, 18 Oct 2023 19:15:07 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 3629

by: Marcel Hendrix - Wed, 18 Oct 2023 19:15 UTC

A really good deduction.

I changed SOLVER to test for 9 to 1 instead of from 1 to 9 in sudoku_fast

This gave the following substantial differences:

It does not really explain why challenge #2 is easier
than challenge #1, but a different starting value definitely
makes a difference.
If I had to beat Go, a parallel program (9 threads) might be worth a try.

-marcel

Subject	Author
Sudoku revisited	minforth
Re: Sudoku revisited	P Falth
Re: Sudoku revisited	minforth
Re: Sudoku revisited	Hans Bezemer
Re: Sudoku revisited	minforth
Re: Sudoku revisited	Hans Bezemer
Re: Sudoku revisited	minforth
Re: Sudoku revisited	none
Re: Sudoku revisited	minforth
Re: Sudoku revisited	Marcel Hendrix
Re: Sudoku revisited	Marcel Hendrix
Re: Sudoku revisited	Marcel Hendrix
Re: Sudoku revisited	minforth