Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #13050 > unrolled thread

Euro's and Dollars.

Back to article view | Back to comp.lang.forth

Contents

  Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-18 19:00 +0000
    Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-18 23:18 +0200
      Re: Euro's and Dollars. Mark Wills <markrobertwills@yahoo.co.uk> - 2012-06-19 00:20 -0700
        Re: Euro's and Dollars. "Elizabeth D. Rather" <erather@forth.com> - 2012-06-18 21:51 -1000
    Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 00:49 +0000
      Re: Euro's and Dollars. Spam@ControlQ.com - 2012-06-18 21:43 -0400
        Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 07:20 +0200
          Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-19 09:26 +0200
            Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:58 +0000
              Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-19 19:58 +0200
                Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 01:31 +0000
                  Re: Euro's and Dollars. "A. K." <akk@nospam.org> - 2012-06-20 07:15 +0200
              Re: Euro's and Dollars. Ecki <ecki@intershop.de> - 2012-06-20 10:15 +0200
              Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-20 10:46 +0000
                Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 17:39 +0000
                  Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-21 16:21 +0000
                    Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-21 11:58 -0500
                      Re: Euro's and Dollars. anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-06-22 14:57 +0000
                    Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-21 20:38 +0000
        Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:49 +0000
      Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:43 +0000
        Re: Euro's and Dollars. vandys@vsta.org - 2012-06-19 15:51 +0000
    Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-19 15:41 +0000
      Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 10:26 -0700
        Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:34 -0700
      Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-19 12:41 -0500
        Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 11:10 -0700
          Re: Euro's and Dollars. Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-06-20 03:12 +0000
            Re: Euro's and Dollars. Paul Rubin <no.email@nospam.invalid> - 2012-06-19 23:51 -0700
          Re: Euro's and Dollars. Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-06-20 03:15 -0500

Page 1 of 2  [1] 2  Next page →

#13050 — Euro's and Dollars.

In studying Scheme I came across the example program to count
in how many ways one dollar can be changed.
Of much more interest is the same problem for the Euro.

This can be even shorter in Forth.
Translating the Lisp source is probably easier then debugging a
Forth version. :-(
-----------8< --------------------------------
CREATE kind-of-coins 0 , 1 ,  5 ,  10 ,  25 ,  50 ,
: first-denomination kind-of-coins SWAP CELLS + @ ;

( amount kinds-of-coins -- count )
: cc   OVER 0= IF 2DROP 1 ELSE   OVER 0< OVER 0= OR IF 2DROP 0 ELSE
   2DUP 1- RECURSE >R  >R R@ first-denomination - R> RECURSE   R> +
   THEN THEN ;

( amount -- count )
: count-change   5 cc ;

100 count-change "Dollars :" TYPE . CR

-----------8< --------------------------------

For euro's you need:

-----------8< --------------------------------
CREATE euro-change 0 , 1 ,  2 , 5 ,  10 ,  20 ,  50 ,
: count-change   6 cc ;
-----------8< --------------------------------


Dollars : 292

Euro's : 4562

The Euro wins. (As long as you use cents and tuppences,
 which will be over shortly.)

Now for the $100 question.
If we order the coins in descending order then :

A. It gives a wrong result
B. It runs faster
C. It runs slower but not by an order of magnitude
D. It runs so slow that you may loose your patience, or risk
    a stack overflow

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [next] | [standalone]

#13051

On 18.06.2012 21:00, Albert van der Horst wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.
> Of much more interest is the same problem for the Euro.
>
> This can be even shorter in Forth.
> Translating the Lisp source is probably easier then debugging a
> Forth version. :-(
> -----------8< --------------------------------
> CREATE kind-of-coins 0 , 1 ,  5 ,  10 ,  25 ,  50 ,
> : first-denomination kind-of-coins SWAP CELLS + @ ;
>
> ( amount kinds-of-coins -- count )
> : cc   OVER 0= IF 2DROP 1 ELSE   OVER 0< OVER 0= OR IF 2DROP 0 ELSE
>     2DUP 1- RECURSE >R  >R R@ first-denomination - R> RECURSE   R> +
>     THEN THEN ;
>
> ( amount -- count )
> : count-change   5 cc ;
>
> 100 count-change "Dollars :" TYPE . CR
>
> -----------8< --------------------------------
>
> For euro's you need:
>
> -----------8< --------------------------------
> CREATE euro-change 0 , 1 ,  2 , 5 ,  10 ,  20 ,  50 ,
> : count-change   6 cc ;
> -----------8< --------------------------------
>
>
> Dollars : 292
>
> Euro's : 4562
>
> The Euro wins. (As long as you use cents and tuppences,
>   which will be over shortly.)
>
> Now for the $100 question.
> If we order the coins in descending order then :
>
> A. It gives a wrong result
> B. It runs faster
> C. It runs slower but not by an order of magnitude
> D. It runs so slow that you may loose your patience, or risk
>      a stack overflow
>
> Groetjes Albert
>
> --
>

Thank you for this piece of code as absolutely bad coding example.
;-)

[toc] | [prev] | [next] | [standalone]

#13057

On Jun 18, 10:18 pm, "A. K." <a...@nospam.org> wrote:
> On 18.06.2012 21:00, Albert van der Horst wrote:
>
>
>
>
>
> > In studying Scheme I came across the example program to count
> > in how many ways one dollar can be changed.
> > Of much more interest is the same problem for the Euro.
>
> > This can be even shorter in Forth.
> > Translating the Lisp source is probably easier then debugging a
> > Forth version. :-(
> > -----------8< --------------------------------
> > CREATE kind-of-coins 0 , 1 ,  5 ,  10 ,  25 ,  50 ,
> > : first-denomination kind-of-coins SWAP CELLS + @ ;
>
> > ( amount kinds-of-coins -- count )
> > : cc   OVER 0= IF 2DROP 1 ELSE   OVER 0< OVER 0= OR IF 2DROP 0 ELSE
> >     2DUP 1- RECURSE >R  >R R@ first-denomination - R> RECURSE   R> +
> >     THEN THEN ;
>
> > ( amount -- count )
> > : count-change   5 cc ;
>
> > 100 count-change "Dollars :" TYPE . CR
>
> > -----------8< --------------------------------
>
> > For euro's you need:
>
> > -----------8< --------------------------------
> > CREATE euro-change 0 , 1 ,  2 , 5 ,  10 ,  20 ,  50 ,
> > : count-change   6 cc ;
> > -----------8< --------------------------------
>
> > Dollars : 292
>
> > Euro's : 4562
>
> > The Euro wins. (As long as you use cents and tuppences,
> >   which will be over shortly.)
>
> > Now for the $100 question.
> > If we order the coins in descending order then :
>
> > A. It gives a wrong result
> > B. It runs faster
> > C. It runs slower but not by an order of magnitude
> > D. It runs so slow that you may loose your patience, or risk
> >      a stack overflow
>
> > Groetjes Albert
>
> > --
>
> Thank you for this piece of code as absolutely bad coding example.
> ;-)- Hide quoted text -
>
> - Show quoted text -

What, specifically, is wrong with his code? You call his code a "bad
coding example" and then give no justification at all for your
comment.

Please clarify.

[toc] | [prev] | [next] | [standalone]

#13059

On 6/18/12 9:20 PM, Mark Wills wrote:
> On Jun 18, 10:18 pm, "A. K."<a...@nospam.org>  wrote:
>> On 18.06.2012 21:00, Albert van der Horst wrote:
>>
>>
>>
>>
>>
>>> In studying Scheme I came across the example program to count
>>> in how many ways one dollar can be changed.
>>> Of much more interest is the same problem for the Euro.
>>
>>> This can be even shorter in Forth.
>>> Translating the Lisp source is probably easier then debugging a
>>> Forth version. :-(
>>> -----------8<  --------------------------------
>>> CREATE kind-of-coins 0 , 1 ,  5 ,  10 ,  25 ,  50 ,
>>> : first-denomination kind-of-coins SWAP CELLS + @ ;
>>
>>> ( amount kinds-of-coins -- count )
>>> : cc   OVER 0= IF 2DROP 1 ELSE   OVER 0<  OVER 0= OR IF 2DROP 0 ELSE
>>>      2DUP 1- RECURSE>R>R R@ first-denomination - R>  RECURSE   R>  +
>>>      THEN THEN ;
>>
>>> ( amount -- count )
>>> : count-change   5 cc ;
>>
>>> 100 count-change "Dollars :" TYPE . CR
>>
>>> -----------8<  --------------------------------
>>
>>> For euro's you need:
>>
>>> -----------8<  --------------------------------
>>> CREATE euro-change 0 , 1 ,  2 , 5 ,  10 ,  20 ,  50 ,
>>> : count-change   6 cc ;
>>> -----------8<  --------------------------------
>>
>>> Dollars : 292
>>
>>> Euro's : 4562
>>
>>> The Euro wins. (As long as you use cents and tuppences,
>>>    which will be over shortly.)
>>
>>> Now for the $100 question.
>>> If we order the coins in descending order then :
>>
>>> A. It gives a wrong result
>>> B. It runs faster
>>> C. It runs slower but not by an order of magnitude
>>> D. It runs so slow that you may loose your patience, or risk
>>>       a stack overflow
>>
>>> Groetjes Albert
>>
>>> --
>>
>> Thank you for this piece of code as absolutely bad coding example.
>> ;-)- Hide quoted text -
>>
>> - Show quoted text -
>
> What, specifically, is wrong with his code? You call his code a "bad
> coding example" and then give no justification at all for your
> comment.
>
> Please clarify.

Insane stack thrashing and recursion. No stack comments. Can't untangle 
his algorithm enough to try to improve. I think the recursion is to 
blame for #D.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#13054

Albert van der Horst <albert@spenarnc.xs4all.nl> wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.

From: vandys@vsta.org
To: Albert van der Horst <albert@spenarnc.xs4all.nl>
Subject: Re: Euro's and Dollars.
In-Reply-To: <m5tu4r.9ba@spenarnc.xs4all.nl>
X-Newsgroups: comp.lang.forth

In article <m5tu4r.9ba@spenarnc.xs4all.nl> you wrote:
> In studying Scheme I came across the example program to count
> in how many ways one dollar can be changed.

Here's the search in Prolog, FWIW (not tested, just wanted to play with
the idea):

% A solution
change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.

% No solution
change([], _, _) :- !, fail.
change([Coin|_], Balance, _) :-
    Coin > Balance, !, fail.

% Apply current coin
change(Coins, Balance, Solve) :-
    [Coin|_]=Coins,
    Balance2 is Balance-Coin,
    change(Coins, Balance2, [Coin|Solve]).

% Step down to next coin
change([_|Coins], Balance, Solve) :- change(Coins, Balance, Solve).

Invocation for US money WRT one dollar:

change([1, 5, 10, 25, 50], 100, []).

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

[toc] | [prev] | [next] | [standalone]

#13055

On Mon, 19 Jun 2012, vandys@vsta.org wrote:
>
> Here's the search in Prolog, FWIW (not tested, just wanted to play with
> the idea):
>
> % A solution
> change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.

Is anyone still using Prolog?  Are there problem domains where Prolog is 
still viable??  I haven't heard of anyone using it since the 1980's when 
the AI fad was fresh, and backtracking all the rage ...

[toc] | [prev] | [next] | [standalone]

#13056

On 19.06.2012 03:43, Spam@ControlQ.com wrote:
> On Mon, 19 Jun 2012, vandys@vsta.org wrote:
>>
>> Here's the search in Prolog, FWIW (not tested, just wanted to play with
>> the idea):
>>
>> % A solution
>> change(_, 0, _, Solve) :- debug("solve", Solve), !, fail.
>
> Is anyone still using Prolog?  Are there problem domains where Prolog is
> still viable??  I haven't heard of anyone using it since the 1980's when
> the AI fad was fresh, and backtracking all the rage ...
>

Unknown to the "masses" it is used in many professional applications, 
although not as elementary Prolog, but as its successor Constraint 
Programming.

Typical application fields are
- production planning
- transportation optimization
- crew rotation
- network design
- time tabling
- military applications
- financial applications
-

Someone said, CP is the most underestimated area in the software industry.

[toc] | [prev] | [next] | [standalone]

#13058

> Someone said, CP is the most underestimated area in the software
> industry.

For Prolog, it's IMHO somehow the missing part, as it allows one to
"semi-bind" a variable, in contrast to either have it bound or
full-free. That in turn heavily reduces the possible search tree for
many problems, making them solvable with much less effort or at all --
think of how Sudoku is solved.

E.

[toc] | [prev] | [next] | [standalone]

#13065

In article <20120619092656.0d5cc45a@tiger.support.j.intershop.de>,
Ecki  <ecki@intershop.de> wrote:
>> Someone said, CP is the most underestimated area in the software
>> industry.
>
>For Prolog, it's IMHO somehow the missing part, as it allows one to
>"semi-bind" a variable, in contrast to either have it bound or
>full-free. That in turn heavily reduces the possible search tree for
>many problems, making them solvable with much less effort or at all --
>think of how Sudoku is solved.

The most natural way to solve a Sudoku is:
   for all unsolved squares find out how many possibilities it has.
   for all squares with 1 possibility fill it in
   repeat

so that is probably a bad example.
(Officially a sudoku must not require backtracking to solve it.)

>
>E.

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#13076

On 19.06.2012 17:58, Albert van der Horst wrote:
> In article <20120619092656.0d5cc45a@tiger.support.j.intershop.de>,
> Ecki  <ecki@intershop.de> wrote:
>>> Someone said, CP is the most underestimated area in the software
>>> industry.
>>
>> For Prolog, it's IMHO somehow the missing part, as it allows one to
>> "semi-bind" a variable, in contrast to either have it bound or
>> full-free. That in turn heavily reduces the possible search tree for
>> many problems, making them solvable with much less effort or at all --
>> think of how Sudoku is solved.
>
> The most natural way to solve a Sudoku is:
>     for all unsolved squares find out how many possibilities it has.
>     for all squares with 1 possibility fill it in
>     repeat
>

You are thinking algorithmically. But CP is data driven and requires a 
fundamentally different mindset.

F.ex. below is a _complete_ working plain vanilla straightforward 
generic Sudoku solver in BProlog. Non-optimized. It contains _only_ 
range and position information, and the rules of the game. Nothing else.


/* ##########
Sudoku solver
*/

:- initialization(main).

main :-

Vars = [  % the board
X11,X12,X13, X14,X15,X16, X17,X18,X19,
X21,X22,X23, X24,X25,X26, X27,X28,X29,
X31,X32,X33, X34,X35,X36, X37,X38,X39,

X41,X42,X43, X44,X45,X46, X47,X48,X49,
X51,X52,X53, X54,X55,X56, X57,X58,X59,
X61,X62,X63, X64,X65,X66, X67,X68,X69,

X71,X72,X73, X74,X75,X76, X77,X78,X79,
X81,X82,X83, X84,X85,X86, X87,X88,X89,
X91,X92,X93, X94,X95,X96, X97,X98,X99 ],
Vars :: 1..9,

sudoku(Vars),  % read in puzzle

%row rules
alldifferent([X11,X12,X13, X14,X15,X16, X17,X18,X19]),
alldifferent([X21,X22,X23, X24,X25,X26, X27,X28,X29]),
alldifferent([X31,X32,X33, X34,X35,X36, X37,X38,X39]),
alldifferent([X41,X42,X43, X44,X45,X46, X47,X48,X49]),
alldifferent([X51,X52,X53, X54,X55,X56, X57,X58,X59]),
alldifferent([X61,X62,X63, X64,X65,X66, X67,X68,X69]),
alldifferent([X71,X72,X73, X74,X75,X76, X77,X78,X79]),
alldifferent([X81,X82,X83, X84,X85,X86, X87,X88,X89]),
alldifferent([X91,X92,X93, X94,X95,X96, X97,X98,X99]),

%column rules
alldifferent([X11,X21,X31, X41,X51,X61, X71,X81,X91]),
alldifferent([X12,X22,X32, X42,X52,X62, X72,X82,X92]),
alldifferent([X13,X23,X33, X43,X53,X63, X73,X83,X93]),
alldifferent([X14,X24,X34, X44,X54,X64, X74,X84,X94]),
alldifferent([X15,X25,X35, X45,X55,X65, X75,X85,X95]),
alldifferent([X16,X26,X36, X46,X56,X66, X76,X86,X96]),
alldifferent([X17,X27,X37, X47,X57,X67, X77,X87,X97]),
alldifferent([X18,X28,X38, X48,X58,X68, X78,X88,X98]),
alldifferent([X19,X29,X39, X49,X59,X69, X79,X89,X99]),

%block rules
alldifferent([X11,X12,X13, X21,X22,X23, X31,X32,X33]),
alldifferent([X14,X15,X16, X24,X25,X26, X34,X35,X36]),
alldifferent([X17,X18,X19, X27,X28,X29, X37,X38,X39]),
alldifferent([X41,X42,X43, X51,X52,X53, X61,X62,X63]),
alldifferent([X44,X45,X46, X54,X55,X56, X64,X65,X66]),
alldifferent([X47,X48,X49, X57,X58,X59, X67,X68,X69]),
alldifferent([X71,X72,X73, X81,X82,X83, X91,X92,X93]),
alldifferent([X74,X75,X76, X84,X85,X86, X94,X95,X96]),
alldifferent([X77,X78,X79, X87,X88,X89, X97,X98,X99]),
	
labeling(Vars),  % get solution
writeln(Vars).

% #####################################################################

sudoku([  % Puzzle example
8,6,7,  _,_,5,  9,1,_,
1,_,_,  _,7,_,  _,8,5,
_,3,_,  _,_,_,  _,_,_,

_,_,_,  7,6,2,  1,_,_,
_,8,_,  _,9,_,  _,6,_,
_,_,2,  8,1,4,  _,_,_,

_,_,_,  _,_,_,  _,3,_,
9,1,_,  _,3,_,  _,_,6,
_,4,3,  1,_,_,  8,2,9
]).

% that's all folks

[toc] | [prev] | [next] | [standalone]

#13090

In article <4fe0bd9f$0$9525$9b4e6d93@newsspool1.arcor-online.net>,
A. K. <akk@nospam.org> wrote:
>On 19.06.2012 17:58, Albert van der Horst wrote:
>> In article <20120619092656.0d5cc45a@tiger.support.j.intershop.de>,
>> Ecki  <ecki@intershop.de> wrote:
>>>> Someone said, CP is the most underestimated area in the software
>>>> industry.
>>>
>>> For Prolog, it's IMHO somehow the missing part, as it allows one to
>>> "semi-bind" a variable, in contrast to either have it bound or
>>> full-free. That in turn heavily reduces the possible search tree for
>>> many problems, making them solvable with much less effort or at all --
>>> think of how Sudoku is solved.
>>
>> The most natural way to solve a Sudoku is:
>>     for all unsolved squares find out how many possibilities it has.
>>     for all squares with 1 possibility fill it in
>>     repeat
>>
>
>You are thinking algorithmically. But CP is data driven and requires a
>fundamentally different mindset.
>
>F.ex. below is a _complete_ working plain vanilla straightforward
>generic Sudoku solver in BProlog. Non-optimized. It contains _only_
>range and position information, and the rules of the game. Nothing else.
>
>
>/* ##########
>Sudoku solver
>*/
>
>:- initialization(main).
>
>main :-
>
>Vars = [  % the board
>X11,X12,X13, X14,X15,X16, X17,X18,X19,
>X21,X22,X23, X24,X25,X26, X27,X28,X29,
>X31,X32,X33, X34,X35,X36, X37,X38,X39,
>
>X41,X42,X43, X44,X45,X46, X47,X48,X49,
>X51,X52,X53, X54,X55,X56, X57,X58,X59,
>X61,X62,X63, X64,X65,X66, X67,X68,X69,
>
>X71,X72,X73, X74,X75,X76, X77,X78,X79,
>X81,X82,X83, X84,X85,X86, X87,X88,X89,
>X91,X92,X93, X94,X95,X96, X97,X98,X99 ],
>Vars :: 1..9,
>
>sudoku(Vars),  % read in puzzle
>
>%row rules
>alldifferent([X11,X12,X13, X14,X15,X16, X17,X18,X19]),
>alldifferent([X21,X22,X23, X24,X25,X26, X27,X28,X29]),
>alldifferent([X31,X32,X33, X34,X35,X36, X37,X38,X39]),
>alldifferent([X41,X42,X43, X44,X45,X46, X47,X48,X49]),
>alldifferent([X51,X52,X53, X54,X55,X56, X57,X58,X59]),
>alldifferent([X61,X62,X63, X64,X65,X66, X67,X68,X69]),
>alldifferent([X71,X72,X73, X74,X75,X76, X77,X78,X79]),
>alldifferent([X81,X82,X83, X84,X85,X86, X87,X88,X89]),
>alldifferent([X91,X92,X93, X94,X95,X96, X97,X98,X99]),
>
>%column rules
>alldifferent([X11,X21,X31, X41,X51,X61, X71,X81,X91]),
>alldifferent([X12,X22,X32, X42,X52,X62, X72,X82,X92]),
>alldifferent([X13,X23,X33, X43,X53,X63, X73,X83,X93]),
>alldifferent([X14,X24,X34, X44,X54,X64, X74,X84,X94]),
>alldifferent([X15,X25,X35, X45,X55,X65, X75,X85,X95]),
>alldifferent([X16,X26,X36, X46,X56,X66, X76,X86,X96]),
>alldifferent([X17,X27,X37, X47,X57,X67, X77,X87,X97]),
>alldifferent([X18,X28,X38, X48,X58,X68, X78,X88,X98]),
>alldifferent([X19,X29,X39, X49,X59,X69, X79,X89,X99]),
>
>%block rules
>alldifferent([X11,X12,X13, X21,X22,X23, X31,X32,X33]),
>alldifferent([X14,X15,X16, X24,X25,X26, X34,X35,X36]),
>alldifferent([X17,X18,X19, X27,X28,X29, X37,X38,X39]),
>alldifferent([X41,X42,X43, X51,X52,X53, X61,X62,X63]),
>alldifferent([X44,X45,X46, X54,X55,X56, X64,X65,X66]),
>alldifferent([X47,X48,X49, X57,X58,X59, X67,X68,X69]),
>alldifferent([X71,X72,X73, X81,X82,X83, X91,X92,X93]),
>alldifferent([X74,X75,X76, X84,X85,X86, X94,X95,X96]),
>alldifferent([X77,X78,X79, X87,X88,X89, X97,X98,X99]),
>
>labeling(Vars),  % get solution
>writeln(Vars).
>
>% #####################################################################
>
>sudoku([  % Puzzle example
>8,6,7,  _,_,5,  9,1,_,
>1,_,_,  _,7,_,  _,8,5,
>_,3,_,  _,_,_,  _,_,_,
>
>_,_,_,  7,6,2,  1,_,_,
>_,8,_,  _,9,_,  _,6,_,
>_,_,2,  8,1,4,  _,_,_,
>
>_,_,_,  _,_,_,  _,3,_,
>9,1,_,  _,3,_,  _,_,6,
>_,4,3,  1,_,_,  8,2,9
>]).
>
>% that's all folks
>


Of course, but Prolog was made for this kind of problems.

From the procedural side I was impressed with Python.
After I solved it for 3 by 3 by 3, I discovered that I could
reuse the very same code for 4 by 4 by 4 with not much more then
changing a few boundaries.
Of course nobody expects your code as is is to be reusable for 4 by 4
by 4, but I even doubt you could come close to anything resembling
reusable classes.

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#13094

On 20.06.2012 03:31, Albert van der Horst wrote:
> Of course, but Prolog was made for this kind of problems.
>
>  From the procedural side I was impressed with Python.
> After I solved it for 3 by 3 by 3, I discovered that I could
> reuse the very same code for 4 by 4 by 4 with not much more then
> changing a few boundaries.
> Of course nobody expects your code as is is to be reusable for 4 by 4
> by 4, but I even doubt you could come close to anything resembling
> reusable classes.
>

Yes. As I said, the example is not optimized and so does not reflect the 
symmetries in the Sudoku square (as you hinted with those 'classes', I 
presume). BTW modern Prologs offer objects and class libraries as well. 
But I do not advocate Prolog. It's just one of many tools in the trade.

Can you show the Python solution? I am interested.

[toc] | [prev] | [next] | [standalone]

#13100

Hello Albert,

> The most natural way to solve a Sudoku is:
>    for all unsolved squares find out how many possibilities it has.
>    for all squares with 1 possibility fill it in
>    repeat

The decision in the 1st two lines ("how many possibilities it has",
"with 1 possibility") is not that easy at all, because both require not
only to take 3 structures into account (row, column, square <- this
means NxN range of fields ("square" in your terminolgy)), but often also
have all of the numbers (symbols) to be different. That in turn means to
identify groups of symbols in those strutures (e.g. if a group of size
N in a row, column, or square only consists of N symbols, no other
(free) cell in that structure can carry one of that N symbols). With
Constraint rules this is both easy to describe (and to read) and
elegant to solve.

In Prolog, because of the different nature of variables (one-time-use,
either a variable is free and thus can be bound to any value needed, or
it is already bound to a given value and thus can never be re-bound),
being able to constrain a variable to (finite) set of values (in the
above example: to be in the (integral) range of [1..x^2] (value
condition) and to be all different in rows, columns, and squares (group
condition)) simply means to introduce a different kind of quantification
than existence quantification and restricts the search tree for
backtracking (what in turn is inherent to the language) in a manner,
that a large group of problems is solvable much easier or at all.

> so that is probably a bad example.

Maybe this depends heavily on one's view of the problem -- for me, I do
use Prolog occasionally (and Sudoku was one of the best examples for
Constraint Programming) and so maybe the imperative view is only one
possible (but I have to state that it took me some longer time to
switch to occasional functional/declarative programming, and
availability of Constraint Handling Rules/Constraint Programming was a
strong motivation for that).

> (Officially a sudoku must not require backtracking to solve it.)

Hehe, I could read the "for all" in your algorithm above as sort of
"limited" backtracking. Especially, I don't see the point, where looping
through possibilities differs much from backtracking over them.

Beside this, I wouldn't want to be urged to solve everything in Prolog
(or any other language).

[toc] | [prev] | [next] | [standalone]

#13102

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>(Officially a sudoku must not require backtracking to solve it.)

But what does that mean?  Of course a Sudoku must have only one
solution.  Given that, when does a Sudoku require backtracking?  For
any example you give, one can add a forward-looking rule that
eliminates the choice at the point where you think you need
backtracking.  So "does not require backtracking" must limit the
forward-looking rules you can apply.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

[toc] | [prev] | [next] | [standalone]

#13113

In article <2012Jun20.124603@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>(Officially a sudoku must not require backtracking to solve it.)
>
>But what does that mean?  Of course a Sudoku must have only one
>solution.  Given that, when does a Sudoku require backtracking?  For
>any example you give, one can add a forward-looking rule that
>eliminates the choice at the point where you think you need
>backtracking.  So "does not require backtracking" must limit the
>forward-looking rules you can apply.

It means that at every point towards a solution there is at least
one square that can be deduced with certainty.
That is to make it easier on humans. It is like the off side
rule in soccer, unnecessary.

You speak like some one who only ever tries to solve Sudoku's
using a program. (Not that that speaks against you ;-) )

>
>- anton

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#13133

Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>In article <2012Jun20.124603@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>(Officially a sudoku must not require backtracking to solve it.)
>>
>>But what does that mean?  Of course a Sudoku must have only one
>>solution.  Given that, when does a Sudoku require backtracking?  For
>>any example you give, one can add a forward-looking rule that
>>eliminates the choice at the point where you think you need
>>backtracking.  So "does not require backtracking" must limit the
>>forward-looking rules you can apply.
>
>It means that at every point towards a solution there is at least
>one square that can be deduced with certainty.

If there is only one solution, that's always the case.  Obviously any
of the squares in the solution can be deduced with certainty with
enough foresight.

I guess what is meant is that the amount of foresight or the deduction
rules are restricted, and that you should be able to deduce at least
one square with certainty even under these restrictions.  My question
was: What are these restrictions?

>You speak like some one who only ever tries to solve Sudoku's
>using a program. (Not that that speaks against you ;-) )

I have done a few by hand, but it's not something that fascinates me.

However, the POV taken above is of someone who wants to write a
program to create Sudokus.  So if there is such an official rule, I
would need to know what it means.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

[toc] | [prev] | [next] | [standalone]

#13135

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>In article <2012Jun20.124603@mips.complang.tuwien.ac.at>,
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>>(Officially a sudoku must not require backtracking to solve it.)
>>>
>>>But what does that mean?  Of course a Sudoku must have only one
>>>solution.  Given that, when does a Sudoku require backtracking?  For
>>>any example you give, one can add a forward-looking rule that
>>>eliminates the choice at the point where you think you need
>>>backtracking.  So "does not require backtracking" must limit the
>>>forward-looking rules you can apply.
>>
>>It means that at every point towards a solution there is at least
>>one square that can be deduced with certainty.
> 
> If there is only one solution, that's always the case.  Obviously any
> of the squares in the solution can be deduced with certainty with
> enough foresight.
> 
> I guess what is meant is that the amount of foresight or the deduction
> rules are restricted, and that you should be able to deduce at least
> one square with certainty even under these restrictions.  My question
> was: What are these restrictions?
> 
>>You speak like some one who only ever tries to solve Sudoku's
>>using a program. (Not that that speaks against you ;-) )
> 
> I have done a few by hand, but it's not something that fascinates me.
> 
> However, the POV taken above is of someone who wants to write a
> program to create Sudokus. 
>
> So if there is such an official rule, I would need to know what it
> means.

It means that at every stage in a solution you can iterate around all
the empty squares and find at least one square that has only one
possible value, given the values already known.  You don't at any
point need to speculate about the value of a square and then make
trial solutions.

Andrew.

[toc] | [prev] | [next] | [standalone]

#13163

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>In article <2012Jun20.124603@mips.complang.tuwien.ac.at>,
>>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>>Albert van der Horst <albert@spenarnc.xs4all.nl> writes:
>>>>>(Officially a sudoku must not require backtracking to solve it.)
>>>>
>>>>But what does that mean?
...
>It means that at every stage in a solution you can iterate around all
>the empty squares and find at least one square that has only one
>possible value, given the values already known.  You don't at any
>point need to speculate about the value of a square and then make
>trial solutions.

Two people have misunderstood me.  I must be very unclear.  I'll try
to be clearer:

We have players Alice and Bob who have different Sudoku-solving
capabilities, for whatever reason.  So there will be a Sudoku where
Alice can deduce via a complex reasoning that a square has only one
possible value.  Bob does not use this reasoning and is not able to
deduce this, and can solve this Sudoku only with backtracking.

Does this Sudoku satisfy the non-backtracking rule?  Is there a limit
to what reasonings the players are required to apply before they can
claim that the Sudoku requires backtracking?

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

[toc] | [prev] | [next] | [standalone]

#13141

In article <2012Jun21.182159@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>
>I have done a few by hand, but it's not something that fascinates me.
>
>However, the POV taken above is of someone who wants to write a
>program to create Sudokus.  So if there is such an official rule, I
>would need to know what it means.

Very short, you must not need backtracking to find a solution.
W.r.t. a manual solution, you don't need an eraser to get rid of
a square that you *had* to guess.

I'm not sure how official this is, now that everybody does sudoku's.
I don't remember where I got this from, and my memory seems to
fail lately ;-) ,

>
>- anton

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#13067

Spam@controlq.com wrote:
> Is anyone still using Prolog?  Are there problem domains where Prolog is 
> still viable??  I haven't heard of anyone using it since the 1980's when 
> the AI fad was fresh, and backtracking all the rage ...

Very much so, just google with the terms ibm, watson, and prolog.  The IBM
team's observations very much match our own experience.

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web