From: darren kirby <bulliver@...>
Date: 2006-08-16T07:16:50+09:00
Subject: Re: [QUIZ] Newbie doubts about the quiz

--nextPart3642194.UFVOC9M0qZ
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

quoth the Morton Goldberg:
> Well, you might look at the solution I posted earlier today for
> hints. It's not all that good, but I happened to take an approach
> very similar to what you outline here. It works, but just barely. My
> experience with it is that a simple depth-first search is too slow
> for grids bigger than 6 x 6 (which is pathetic considering some of
> huge grids solved by posted solutions).

This is exactly the problem my first solution had. 5*5 was reasonable, 6*6=
=20
took over a minute, and I gave up on 7*7 after ~30 minutes.

I finally realized ( thanks to other solutions posted) that if you implemen=
t a=20
way to score each potential move's /potential moves/ and go with the one wi=
th=20
the least amount it makes the solution _waaay_ faster (almost like magic).

As far as I can tell this is what pretty much every solution other than=20
random/brute force solutions are doing. It seems this is called a "Warnsdor=
ff=20
heuristic" though I wouldn't have known this but for Sander Land's post.

Of course other's solutions have implemented this better than mine as they =
are=20
still several orders of magnitude faster than my second solution.

I tried optimizing a bit this morning but wasn't able to improve it at all.=
=20

> Regards, Morton
>

=2Dd
=2D-=20
darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
=2D Dennis Ritchie and Ken Thompson, June 1972

--nextPart3642194.UFVOC9M0qZ
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.4 (GNU/Linux)

iD8DBQBE4ke1wPD5Cr/3CJgRAl9JAJ9pqUxif1whx8yWSozRQjUdK23RrQCgttBd
LZgOEZmDVApdGcP9ULvOSeU=
=4XuW
-----END PGP SIGNATURE-----

--nextPart3642194.UFVOC9M0qZ--