OT: A bit of Sudoku

OT: A bit of Sudoku

[Mike H]

Purely for my own amusement I have written a Sudoku puzzle solver. The 
program is written In Ada. However being in my ninth decade I am firmly 
stuck in an Ada95 time-warp. As a general rule, Sudoku puzzles rated as 
'gentle' or 'moderate' can be solved by systematic elimination of 
alternatives. But these relatively simple deterministic methods can be 
expected to fail when confronted by a puzzle rated as 'tough' or a 
'diabolical'. When this happens in my program, trial and error is 
invoked. It is rare that more than four or five trial and error passes 
are required.

The enclosing subprogram is called recursively by the trial and error 
process. Each recursive call adds a pair of nodes onto an implicit but 
invisible binary tree (the run-time call stack). What I was hoping was 
that on detected that the solution has been found, it would be possible 
to return to, and exit from, the main program by simply exiting each 
recursive call in turn in order climb back up the recursion ladder. 
However, each step of that climb is a re-entry into the caller where 
there may be remaining unfinished business. The solution having been 
found, that unfinished business is now known to be no more than garbage. 
Nevertheless an elegant solution might be expected to clear garbage 
before that caller re-enters its own caller.

The only solution that I can see is to jump straight out of the tree. 
But that seems to lack elegance. The jump is made by raising an 
exception which has been declared in, and is handled by, the enclosing 
subprogram. The exception is 'silent' because the handler contains a 
null statement.

I fear that perhaps I am missing something but have no idea what.
-- 
Cotswold Mike
'Homo sum, humani nihil a me alienum puto' =
'I am human, (so) I (should) judge nothing of humanity to be strange.'
Publius Terentius (195/185–159 BC)

Re: OT: A bit of Sudoku

[Adam Beneschan]

On Thursday, June 5, 2014 10:49:01 AM UTC-7, Mike H wrote:
> Purely for my own amusement I have written a Sudoku puzzle solver. The 
> program is written In Ada. However being in my ninth decade I am firmly 
> stuck in an Ada95 time-warp. As a general rule, Sudoku puzzles rated as 
> 'gentle' or 'moderate' can be solved by systematic elimination of 
> alternatives. But these relatively simple deterministic methods can be 
> expected to fail when confronted by a puzzle rated as 'tough' or a 
> 'diabolical'. When this happens in my program, trial and error is 
> invoked. It is rare that more than four or five trial and error passes 
> are required.
> 
> The enclosing subprogram is called recursively by the trial and error 
> process. Each recursive call adds a pair of nodes onto an implicit but 
> invisible binary tree (the run-time call stack). What I was hoping was 
> that on detected that the solution has been found, it would be possible 
> to return to, and exit from, the main program by simply exiting each 
> recursive call in turn in order climb back up the recursion ladder. 
> 
> However, each step of that climb is a re-entry into the caller where 
> there may be remaining unfinished business. The solution having been 
> found, that unfinished business is now known to be no more than garbage. 
> Nevertheless an elegant solution might be expected to clear garbage 
> before that caller re-enters its own caller.
> 
> 
> The only solution that I can see is to jump straight out of the tree. 
> But that seems to lack elegance. The jump is made by raising an 
> exception which has been declared in, and is handled by, the enclosing 
> subprogram. The exception is 'silent' because the handler contains a 
> null statement.
> 
> I fear that perhaps I am missing something but have no idea what.

Without seeing an actual program or any code at all, I can't really tell, but ... when a caller calls itself recursively, isn't there either a function result or an OUT parameter that allows the callee to tell the caller whether it has succeeded?  In which case the caller simply exits, and returns to *its* caller passing back the correct answer and if necessary a flag indicating that it's succeeded.  I have no idea whether I've identified the problem correctly, but it's the best I can do without seeing any code.  Anyway, I think that's the general approach to handling backtracking problems.

                                -- Adam

Re: OT: A bit of Sudoku

[J-P. Rosen]

Le 05/06/2014 20:30, Adam Beneschan a écrit :
>> The only solution that I can see is to jump straight out of the 
>> tree.
>>> But that seems to lack elegance. The jump is made by raising an 
>>> exception which has been declared in, and is handled by, the 
>>> enclosing subprogram. The exception is 'silent' because the 
>>> handler contains a null statement.
>>> 
>>> I fear that perhaps I am missing something but have no idea 
>>> what.
On the contrary, I think exception are perfectly appropriate for that:
they allow to unwind the call stack directly up to the point where you
want to catch it by providing a handler.

I know that not everybody likes this idea, but to me exceptions are a
powerful programming structure, not limited to handling errors.

> Without seeing an actual program or any code at all, I can't really 
> tell, but ... when a caller calls itself recursively, isn't there 
> either a function result or an OUT parameter that allows the callee 
> to tell the caller whether it has succeeded?  In which case the 
> caller simply exits, and returns to *its* caller passing back the 
> correct answer and if necessary a flag indicating that it's 
> succeeded.  I have no idea whether I've identified the problem 
> correctly, but it's the best I can do without seeing any code. 
> Anyway, I think that's the general approach to handling backtracking 
> problems.
What you are doing here is just implementing by hand an exception
mechanism; that's the only solution when the language does not provide
exceptions, but fortunately we have them in Ada....

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: OT: A bit of Sudoku

[Jeffrey Carter]

On 06/05/2014 12:00 PM, J-P. Rosen wrote:
> On the contrary, I think exception are perfectly appropriate for that:
> they allow to unwind the call stack directly up to the point where you
> want to catch it by providing a handler.
>
> I know that not everybody likes this idea, but to me exceptions are a
> powerful programming structure, not limited to handling errors.

As the name indicates, exceptions are for exceptional situations. Finding a 
solution doesn't seem exceptional for a solver.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail
23

Re: OT: A bit of Sudoku

[J-P. Rosen]

Le 05/06/2014 21:18, Jeffrey Carter a écrit :
>> I know that not everybody likes this idea, but to me exceptions are a
>> powerful programming structure, not limited to handling errors.
> 
> As the name indicates, exceptions are for exceptional situations.
> Finding a solution doesn't seem exceptional for a solver.
> 
It IS an exceptional condition!

An exceptional condition is a condition that makes it impossible or
unnecessary to continue with the normal algorithm, and requires suddenly
a different behaviour. Finding the solution is precisely that.
(although it is not an error or an abnormal condition, which is
precisely the point I made).

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: OT: A bit of Sudoku

[Mike H]

In message <lmqeoe$o76$1@dont-email.me>, J-P. Rosen <rosen@adalog.fr> 
writes
>I think exception are perfectly appropriate for that:
>they allow to unwind the call stack directly up to the point where you
>want to catch it by providing a handler.
>
>I know that not everybody likes this idea, but to me exceptions are a
>powerful programming structure, not limited to handling errors.
>
Many thanks for that vote of confidence.
-- 
Knowledge is knowing a tomato is a fruit
Wisdom in knowing not to put it in the fruit salad.
Mike ;-)

Re: OT: A bit of Sudoku

[Robert A Duff]

"J-P. Rosen" <rosen@adalog.fr> writes:

> On the contrary, I think exception are perfectly appropriate for that:
> they allow to unwind the call stack directly up to the point where you
> want to catch it by providing a handler.

I'm with J-P here.  There are cases where exceptions can reasonably
be used for not-so-exceptional cases.  Maybe the OP's Sudoku solver
is one such -- I haven't seen the code, so I don't know.

> I know that not everybody likes this idea, ...

That's somewhat of an understatement; many people are quite passionate
about it, and say things like "Never use exceptions for control flow".

But exceptions ARE control flow.  When an exception is raised,
a transfer of control to the handler happens (or to the end of
the program if unhandled).  It is impossible to use exceptions
other than for control flow!

Others add the word "normal": "Don't use exceptions for normal control
flow".  Unfortunately, it's unclear what "normal" means.

>...but to me exceptions are a
> powerful programming structure, not limited to handling errors.

I agree.  IMHO, the purpose of exceptions is to deal with the case
where one piece of code detects an error (or maybe just an unusual
situation), and a different piece of code knows what to do about it
(or even to decide it's not an error after all).

"end of file" might be considered an error by the file-reading
procedure, but might be considered perfectly normal by the
caller.  So I don't think it makes sense to say "exceptions
are ONLY for errors" -- different pieces of code have different
views on whether it's an error.

In any case, if you need to jump out of many layers of (recursive?)
calls, an exception might well be the best way.  Checking error
codes at each level might be verbose and error prone.

- Bob

Re: OT: A bit of Sudoku

[Adam Beneschan]

On Thursday, June 5, 2014 4:12:55 PM UTC-7, Robert A Duff wrote:

> In any case, if you need to jump out of many layers of (recursive?)
> calls, an exception might well be the best way.  Checking error
> codes at each level might be verbose and error prone.

I don't like it.  But if you do something like this, I'd suggest that this use be limited to an exception that you declare inside a subprogram, so that you raise and handle it only inside that subprogram or nested subprograms.  Otherwise, someone could look at a subprogram that is called in between, and never guess that the subprogram might not complete normally (A calls B, B calls C, C raises an exception that gets passed over B's head back to A; a programmer trying to read B might not suspect that B may not complete in a non-error situation.)  In other words, keep such usages as localized as possible.

Another thing to keep in mind is that exceptions cause overhead.  I've seen implementations that have to do some stuff any time a subprogram or a block with an exception handler is entered.  I've seen other implementations that, in order to eliminate this overhead in "normal" (non-exception) cases, perform table lookups on each address in the stack until it finds a handler; this is a relatively expensive operation that those implementations have decided is justified because exceptions aren't supposed to happen in "normal" cases.  Whether this overhead is less than the expense of going through a number of returns, I don't know--I'm sure it depends on various factors.  But efficiency should not be a reason to use exceptions instead of straight returns, because it may well make things slower.

                                     -- Adam

Re: OT: A bit of Sudoku

[Dmitry A. Kazakov]

On Thu, 5 Jun 2014 16:39:47 -0700 (PDT), Adam Beneschan wrote:

> On Thursday, June 5, 2014 4:12:55 PM UTC-7, Robert A Duff wrote:
> 
>> In any case, if you need to jump out of many layers of (recursive?)
>> calls, an exception might well be the best way.  Checking error
>> codes at each level might be verbose and error prone.
> 
> I don't like it.  But if you do something like this, I'd suggest that this
> use be limited to an exception that you declare inside a subprogram, so
> that you raise and handle it only inside that subprogram or nested
> subprograms.

Exceptions is a part of the subprogram contract.

> Otherwise, someone could look at a subprogram that is called in between,
> and never guess that the subprogram might not complete normally (A calls
> B, B calls C, C raises an exception that gets passed over B's head back to
> A; a programmer trying to read B might not suspect that B may not complete
> in a non-error situation.)  In other words, keep such usages as localized
> as possible.

Rather, let Ada 2X formalize exception contracts and leave checking the
contracts to the compiler.

The scenario you described is the valid and very useful use case of
exceptions. The reason is that, likely, C and B could not handle the state
when the exception was raised and propagated because in order to be able to
handle it, they must be redesigned completely. They must have the
information hidden from them for very good reason, affect program states
possibly unrelated to them etc. I.e. it would make the design tightly
coupled and fragile. The idea of exception is postponing handling of some
[exceptional] states up to a context where handling were possible, e.g. in
A. That context can be and usually is totally unknown to the designer of
the code raising the exception.

> Another thing to keep in mind is that exceptions cause overhead.

Or reduce overhead when used properly, e.g.

   while not End_Of_File (File) loop
       ...
   end loop;

vs.

   loop
      ...
   end loop;
exception
   when End_Error =>
        ...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: OT: A bit of Sudoku

[Georg Bauhaus]

On 06/06/14 09:51, Dmitry A. Kazakov wrote:
> Or reduce overhead

Will there be less overhead if programmers can announce
some controlled jump, back to where "it" came from?
Subprograms to be called this way would have defaults
declared as necessary:

procedure Top
is
    type T is (yes, no, unknown);

    function Search return T
       with <> => (T'Result => Unknown);

    function Search return T
    is
       procedure Maybe
       is
       begin
          goto null;  -- jump
       end Maybe;

    begin
       Maybe;
       return yes;
    end Search;
    
    Result : T;
begin
    Result := Search with goto;  -- resume here
end Top;

Re: OT: A bit of Sudoku

[Dmitry A. Kazakov]

On Fri, 06 Jun 2014 11:21:51 +0200, Georg Bauhaus wrote:

> On 06/06/14 09:51, Dmitry A. Kazakov wrote:
>> Or reduce overhead
> 
> Will there be less overhead if programmers can announce
> some controlled jump, back to where "it" came from?

A model of error handling based on returning back to the point of raising
was in PL/1 (on-error stuff). It proved to be wrong, because the whole idea
of exception is that you cannot go back because you cannot and will not
handle it where you detected it.

Regarding overhead, it is stack winding which takes most time. This
overhead is necessary per the logic of exception processing = leaving all
contexts compromised by the unexpected/undefined/undesired state. You must
finish these contexts regardless exception propagation or if-then-goto.

And testing/checking state is sometimes far more expensive that handling
it. Which is why exceptions are often less overhead than doing looking
ahead for an unanticipated condition, like EOF. Or an extreme example:

   if Check_Syntax (Ada_Program) then
      Compile (Ada_Program);
   else
      Put_Line ("I won't compile that mess!");
   end if;

If you moving forward checking each step you made, you are much slower than
when walking normally.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: OT: A bit of Sudoku

[Adam Beneschan]

On Friday, June 6, 2014 12:51:47 AM UTC-7, Dmitry A. Kazakov wrote:

> > Otherwise, someone could look at a subprogram that is called in between,
> > and never guess that the subprogram might not complete normally (A calls
> > B, B calls C, C raises an exception that gets passed over B's head back to
> > A; a programmer trying to read B might not suspect that B may not complete
> > in a non-error situation.)  In other words, keep such usages as localized
> > as possible.
> 
> Rather, let Ada 2X formalize exception contracts and leave checking the
> contracts to the compiler.
> 
> The scenario you described is the valid and very useful use case of
> exceptions. The reason is that, likely, C and B could not handle the state
> when the exception was raised and propagated because in order to be able to
> handle it, they must be redesigned completely. They must have the
> information hidden from them for very good reason, affect program states
> possibly unrelated to them etc. I.e. it would make the design tightly
> coupled and fragile. The idea of exception is postponing handling of some
> [exceptional] states up to a context where handling were possible, e.g. in
> A. That context can be and usually is totally unknown to the designer of
> the code raising the exception.

I'm not sure we're on the same page.  What you're describing sounds more like the "normal" use case for exceptions, as I understand it (i.e. for "exceptional" conditions); but I thought the discussion was about something different, namely using exceptions as sort of a stack-unwinding "goto".  Even with an explicit contract, it still seems like using exceptions in this way, for non-exceptional situations, is going to impair readability if its use isn't kept within a small, local area of the source.  This is just my instinct, though, and I'm finding it difficult to explain why.  

                               -- Adam

Re: OT: A bit of Sudoku

[Dmitry A. Kazakov]

On Fri, 6 Jun 2014 08:47:02 -0700 (PDT), Adam Beneschan wrote:

> but I thought the discussion was about something different, namely using
> exceptions as sort of a stack-unwinding "goto".

I prefer to have explicit stack/context object + iteration. But otherwise
why not, better than checking return codes.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: OT: A bit of Sudoku

[J-P. Rosen]

Le 06/06/2014 17:47, Adam Beneschan a écrit :
> What you're describing sounds more like the "normal" use case for
> exceptions, as I understand it (i.e. for "exceptional" conditions);

The whole thing boils down to the difference between "normal" and
"exceptional". FWIW, here is how I explain it in my courses:

A program is basically looping (if it were to do things just once, it
would be faster by hand than writing a program). The loop is the general
case, the "rule". Sometimes, you encounter a condition that cannot be
handled by the normal "rule" and requires a different treatement: it is
an "exception" to the rule. That's why it's called exception, and not
trap, abnormality, failure...

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: OT: A bit of Sudoku

[Brad Moore]

On 14-06-05 05:39 PM, Adam Beneschan wrote:
> On Thursday, June 5, 2014 4:12:55 PM UTC-7, Robert A Duff wrote:
>
>> In any case, if you need to jump out of many layers of (recursive?)
>> calls, an exception might well be the best way.  Checking error
>> codes at each level might be verbose and error prone.
>
> I don't like it.  But if you do something like this, I'd suggest that this use be limited to an exception that you declare inside a subprogram, so that you raise and handle it only inside that subprogram or nested subprograms.  Otherwise, someone could look at a subprogram that is called in between, and never guess that the subprogram might not complete normally (A calls B, B calls C, C raises an exception that gets passed over B's head back to A; a programmer trying to read B might not suspect that B may not complete in a non-error situation.)  In other words, keep such usages as localized as possible.
>
> Another thing to keep in mind is that exceptions cause overhead.  I've seen implementations that have to do some stuff any time a subprogram or a block with an exception handler is entered.  I've seen other implementations that, in order to eliminate this overhead in "normal" (non-exception) cases, perform table lookups on each address in the stack until it finds a handler; this is a relatively expensive operation that those implementations have decided is justified because exceptions aren't supposed to happen in "normal" cases.  Whether this overhead is less than the expense of going through a number of returns, I don't know--I'm sure it depends on various factors.  But efficiency should not be a reason to use exceptions instead of straight returns, because it may well make things slower.
>

Another point to keep in mind is that although the exception mechanism 
may or may not be technically faster than the normal recursion exit, 
depending on implementation, it may not be noticeably faster. A 
guideline I try to follow generally is to write the code naturally and 
simply, and let the compiler worry about performance, and then only look 
at using different constructs if there is still a performance problem 
that needs to be addressed.

I have actually written a sudoku solver, that executes in Parallel.
My approach was to just let the recursion unwind naturally.

In my parallelism framework, workers tasks catch and handle exceptions,
where if exceptions are raised in multiple worker threads, only one of 
those exceptions is saved, and gets reraised in the calling thread 
before returning from the parallel call.

Here exceptions are generally used to report failures, but could 
probably be used to report a solution in this case. However if a 
different exception occurs in a worker thread (such as a constraint 
error), that may or may not be the exception that ends up getting reported.

I suspect that trying to use exceptions to report solutions for Sudoku, 
would not noticeably improve performance, as most of the time is spent 
trying to find a solution, not report it.

My Sudoku solver uses a brute force approach. (I was mostly interested 
in trying out the parallelism). I believe the performance could be 
improved significantly by updating local cells to maintain a list of 
possible values, thus ruling out trial values much more sooner.
I would think such an approach would improve performance far more than 
using exceptions to exit recursion, so that would be where I would 
suggest programming effort be spent.

I have several versions of the solver.
(A sequential version,
  A load balancing version,
  A load balanciong version that adds some stack safety (prevents stack 
overflow)

Here is my sequential version. I'd be happy to share the other versions 
also....

Brad

generic
    N : Positive := 3;
package Sequential_Sudoku is

    Max_Range : constant Positive := N**2;

    subtype Sudoku_Value is
      Natural range 0 .. Max_Range;

    Null_Value : constant Sudoku_Value := 0;

    subtype Sudoku_Solution_Value is Sudoku_Value range 1 .. Max_Range;

    subtype Sudoku_Index is Sudoku_Solution_Value;

    type Sudoku_Board is private;

    procedure Initialize (Board : in out Sudoku_Board);

    function Get
      (Board : Sudoku_Board;
       Row, Column : Sudoku_Index) return Sudoku_Value;

    procedure Set
      (Board : in out Sudoku_Board;
       Row, Column : Sudoku_Index;
       Value : Sudoku_Solution_Value)
    with Pre => Is_Valid (Board, Row, Column, Value),
         Post => Get (Board, Row, Column) = Value;

    function Is_Valid (Board : Sudoku_Board;
                       Row, Column : Sudoku_Index;
                       Value : Sudoku_Solution_Value) return Boolean;

    procedure Generate (Board : out Sudoku_Board);

    procedure Solve (Board : in out Sudoku_Board);

private

    type Sudoku_Value_Array is
      array (Sudoku_Index, Sudoku_Index) of Sudoku_Value;

    type Sudoku_Board is
       record
          Initialized : Boolean := False;
          Values : Sudoku_Value_Array;
       end record;

    function Get (Board : Sudoku_Board;
                  Row, Column : Sudoku_Index) return Sudoku_Value is
      (Board.Values (Row, Column));

    function Value_In_Row
      (Board : Sudoku_Board;
       Row : Sudoku_Index;
       Value : Sudoku_Solution_Value) return Boolean is
       (for some I in Board.Values'Range (2) => Board.Values (Row, I) = 
Value);

    function Value_In_Column
      (Board : Sudoku_Board;
       Col : Sudoku_Index;
       Value : Sudoku_Solution_Value) return Boolean is
       (for some I in Board.Values'Range (1) => Board.Values (I, Col) = 
Value);

    function On_Diagonal
      (Board : Sudoku_Board;
       Row, Col : Sudoku_Index) return Boolean is
      (Row = Col or else Row + Col = Max_Range + 1);

    function Value_In_Diagonal
      (Board : Sudoku_Board;
       Row, Col : Sudoku_Index;
       Value : Sudoku_Solution_Value) return Boolean;

    --     function Value_In_Diagonal
--       (Board : Sudoku_Board;
--        Row, Col : Sudoku_Index;
--        Value : Sudoku_Solution_Value) return Boolean is
--       (if Row = Col then
--          (for some I in Board.Values'Range (1) =>
--              Board.Values (I, I) = Value)
--        or else
--          (for some I in Board.Values'Range (1) =>
--           Board.Values (Max_Range + 1 - I, I) = Value));

    function Value_In_Sector
      (Board : Sudoku_Board;
       Row, Col : Sudoku_Index;
       Value : Sudoku_Solution_Value) return Boolean;

    function Is_Valid (Board : Sudoku_Board;
                       Row, Column : Sudoku_Index;
                       Value : Sudoku_Solution_Value) return Boolean is
      (Board.Initialized and then
         not Value_In_Row (Board, Row, Value) and then
         not Value_In_Column (Board, Column, Value) and then
         not Value_In_Sector (Board, Row, Column, Value)
--        and then
--          (not On_Diagonal (Board, Row, Column) or else not
       --             Value_In_Diagonal (Board, Row, Column, Value))
      );

end Sequential_Sudoku;
with Ada.Numerics.Discrete_Random;

package body Sequential_Sudoku is

    package Random_Index is new Ada.Numerics.Discrete_Random
      (Result_Subtype => Sudoku_Index);

    procedure Random_Solution
      (Board : out Sudoku_Board);

    function Multiple_Solutions_Exist
      (Board : Sudoku_Board) return Boolean;

    Generator : Random_Index.Generator;

    procedure Generate (Board : out Sudoku_Board)
    is
       Scratch_Board : Sudoku_Board;
    begin

       Random_Solution (Board);

       Filter_Loop : loop
          declare
             Delete_Row : constant Sudoku_Index :=
               Random_Index.Random (Generator);
             Delete_Column : constant Sudoku_Index :=
               Random_Index.Random (Generator);

             Delete_Value : constant Sudoku_Value :=
               Board.Values (Delete_Row, Delete_Column);
          begin

             if Delete_Value /= 0 then

                Board.Values (Delete_Row, Delete_Column) := 0;
                Scratch_Board := Board;

                if Multiple_Solutions_Exist (Board => Scratch_Board) then
                   Board.Values (Delete_Row, Delete_Column) :=
                        Delete_Value;
                   exit Filter_Loop;
                end if;
             end if;
          end;
       end loop Filter_Loop;

    end Generate;

    ----------------
    -- Initialize --
    ----------------

    procedure Initialize (Board : in out Sudoku_Board) is
    begin
       for I in Board.Values'Range (1) loop
          for J in Board.Values'Range (2) loop
             Board.Values (I, J) := Null_Value;
          end loop;
       end loop;

       Board.Initialized := True;
    end Initialize;

    function Multiple_Solutions_Exist
      (Board : Sudoku_Board) return Boolean is

       --  Note: We do not need to worry about deallocating scratch boards
       --  that were allocated from the heap, since they will all get
       --  automatically deallocated when this access type goes out of 
scope,
       --  i.e. before returning from Solve
       type Board_Access is access all Sudoku_Board;

       type Sudoku_Work is
          record
             Row, Column   : Sudoku_Index'Base;
             Scratch_Board : Board_Access;
          end record;

       Multiple_Solutions : Boolean := False;

       protected Solution_Checker is
          procedure Note_Solution;
       private
          Solved : Boolean := False;
       end Solution_Checker;

       protected body Solution_Checker is
          procedure Note_Solution is
          begin
             if Solved then
                Multiple_Solutions := True;
             else
                Solved := True;
             end if;
          end Note_Solution;
       end Solution_Checker;

       function Next_Work (Row : Sudoku_Index'Base := 0;
                           Column : Sudoku_Index'Base := 1;
                           Board : Board_Access) return Sudoku_Work
       is
          Next_Row : Sudoku_Index'Base := Row;
          Next_Column : Sudoku_Index'Base := Column;
       begin

          Search_Loop : loop
             Next_Row := Next_Row + 1;

             if Next_Row > Max_Range then
                Next_Row := 1;
                Next_Column := Next_Column + 1;

                if Next_Column > Max_Range then

                   Solution_Checker.Note_Solution;

                   return (Row => Sudoku_Index'Last,
                           Column => Sudoku_Index'Last,
                           Scratch_Board => null);
                end if;
             end if;

             exit Search_Loop when Get (Board.all,
                                        Next_Row,
                                        Next_Column) = 0;
          end loop Search_Loop;

          return (Row => Next_Row,
                  Column => Next_Column,
                  Scratch_Board => Board);

       end Next_Work;

       procedure Solution_Check_Sequential (Work : Sudoku_Work) is
       begin

          if Multiple_Solutions or else Work.Scratch_Board = null then

             --  No need to worry about deleting any outstanding boards,
             --  Once we return from Solve, all boards get deleted, 
since the
             --  access type gets finalized
             return;

          end if;

          --  Try all values
          for I in Sudoku_Index'Range loop

             if Is_Valid (Board  => Work.Scratch_Board.all,
                          Row    => Work.Row,
                          Column => Work.Column,
                          Value  => I) then

                --  Same worker proceeds to continue work on same board

                --  Try another solution
                Work.Scratch_Board.all.Values
                  (Work.Row, Work.Column) := I;

                Solution_Check_Sequential
                  (Next_Work (Row    => Work.Row,
                              Column => Work.Column,
                              Board  => Work.Scratch_Board));

                --  Solution didn't work, undo
                Work.Scratch_Board.all.Values
                  (Work.Row, Work.Column) := 0;

             end if;
          end loop;

       end Solution_Check_Sequential;

       Scratch_Board : aliased Sudoku_Board := Board;

    begin

       Solution_Check_Sequential
         (Work => Next_Work (Board => Scratch_Board'Access));

       return Multiple_Solutions;

    end Multiple_Solutions_Exist;

    ---------------------------------------------------------------

    procedure Random_Solution (Board : out Sudoku_Board) is

       --  Note: We do not need to worry about deallocating scratch boards
       --  that were allocated from the heap, since they will all get
       --  automatically deallocated when this access type goes out of 
scope,
       --  i.e. before returning from Solve
       type Board_Access is access all Sudoku_Board;

       type Sudoku_Work is
          record
             Row, Column   : Sudoku_Index'Base;
             Scratch_Board : Board_Access;
          end record;

       Done : Boolean := False;

       protected Store_Result is
          procedure Store (Result : Sudoku_Board);
       end Store_Result;

       protected body Store_Result is
          procedure Store (Result : Sudoku_Board) is
          begin
             Board := Result;
             Done   := True;
          end Store;
       end Store_Result;

       function Next_Work (Row : Sudoku_Index'Base := 0;
                           Column : Sudoku_Index'Base := 1;
                           Board : Board_Access) return Sudoku_Work;

       procedure Generate_Random_Solution (Work : Sudoku_Work)
       is
          Start_Value : constant Sudoku_Solution_Value :=
            Random_Index.Random (Generator);
       begin

          if Done then

             --  No need to worry about deleting any outstanding boards,
             --  Once we return from Solve, all boards get deleted, 
since the
             --  access type gets finalized
             return;

          end if;

          --  Try all values
          for I in Sudoku_Index'Range loop
             declare
                Value : constant Sudoku_Solution_Value :=
                  (if I + Start_Value - 1 > Max_Range then
                   I + Start_Value - 1 - Max_Range else I + Start_Value 
- 1);
             begin

                if Is_Valid (Board  => Work.Scratch_Board.all,
                             Row    => Work.Row,
                             Column => Work.Column,
                             Value  => Value) then

                   --  Same worker proceeds to continue work on same board

                   --  Try another solution
                   Work.Scratch_Board.all.Values
                     (Work.Row, Work.Column) := Value;

                   Generate_Random_Solution
                     (Next_Work (Row    => Work.Row,
                                 Column => Work.Column,
                                 Board  => Work.Scratch_Board));

                   --  Solution didn't work, undo
                   Work.Scratch_Board.all.Values
                     (Work.Row, Work.Column) := 0;

                end if;
             end;
          end loop;

       end Generate_Random_Solution;

       function Next_Work (Row : Sudoku_Index'Base := 0;
                           Column : Sudoku_Index'Base := 1;
                           Board : Board_Access) return Sudoku_Work
       is
          Next_Row : Sudoku_Index'Base := Row;
          Next_Column : Sudoku_Index'Base := Column;
       begin

          Search_Loop : loop
             Next_Row := Next_Row + 1;

             if Next_Row > Max_Range then
                Next_Row := 1;
                Next_Column := Next_Column + 1;

                if Next_Column > Max_Range then

                   Store_Result.Store (Board.all);

                   return (Row => Sudoku_Index'Last,
                           Column => Sudoku_Index'Last,
                           Scratch_Board => null);
                end if;
             end if;

             exit Search_Loop when Get (Board.all,
                                        Next_Row,
                                        Next_Column) = 0;
          end loop Search_Loop;

          return (Row => Next_Row,
                  Column => Next_Column,
                  Scratch_Board => Board);

       end Next_Work;

       Scratch_Board : aliased Sudoku_Board := Board;

    begin

       Initialize (Scratch_Board);

       Generate_Random_Solution (Next_Work (Board => Scratch_Board'Access));

    end Random_Solution;

    ---------------------------------------------------------------

    procedure Set
      (Board       : in out Sudoku_Board;
       Row, Column : Sudoku_Index;
       Value       : Sudoku_Solution_Value) is
    begin
       Board.Values (Row, Column) := Value;
    end Set;

    ---------------------------------------------------------------

    procedure Solve (Board : in out Sudoku_Board) is

       --  Note: We do not need to worry about deallocating scratch boards
       --  that were allocated from the heap, since they will all get
       --  automatically deallocated when this access type goes out of 
scope,
       --  i.e. before returning from Solve
       type Board_Access is access all Sudoku_Board;

       type Sudoku_Work is
          record
             Row, Column   : Sudoku_Index'Base;
             Scratch_Board : Board_Access;
          end record;

       Done : Boolean := False;

       protected Store_Result is
          procedure Store (Result : Sudoku_Board);
       private
          Solved : Boolean := False;
       end Store_Result;

       protected body Store_Result is
          procedure Store (Result : Sudoku_Board) is
          begin
             if not Solved then
                Board := Result;
                Solved := True;
                Done   := True;
             end if;
          end Store;
       end Store_Result;

       function Next_Work (Row : Sudoku_Index'Base := 0;
                           Column : Sudoku_Index'Base := 1;
                           Board : Board_Access) return Sudoku_Work
       is
          Next_Row : Sudoku_Index'Base := Row;
          Next_Column : Sudoku_Index'Base := Column;
       begin

          Search_Loop : loop
             Next_Row := Next_Row + 1;

             if Next_Row > Max_Range then
                Next_Row := 1;
                Next_Column := Next_Column + 1;

                if Next_Column > Max_Range then

                   Store_Result.Store (Board.all);

                   return (Row => Sudoku_Index'Last,
                           Column => Sudoku_Index'Last,
                           Scratch_Board => null);
                end if;
             end if;

             exit Search_Loop when Get (Board.all,
                                        Next_Row,
                                        Next_Column) = 0;
          end loop Search_Loop;

          return (Row => Next_Row,
                  Column => Next_Column,
                  Scratch_Board => Board);

       end Next_Work;

       procedure Solve_Sequential (Work : Sudoku_Work) is
       begin

          if Done then

             --  No need to worry about deleting any outstanding boards,
             --  Once we return from Solve, all boards get deleted, 
since the
             --  access type gets finalized
             return;

          end if;

          --  Try all values
          for I in Sudoku_Index'Range loop

             if Is_Valid (Board  => Work.Scratch_Board.all,
                          Row    => Work.Row,
                          Column => Work.Column,
                          Value  => I) then

                --  Same worker proceeds to continue work on same board

                --  Try another solution
                Work.Scratch_Board.all.Values
                  (Work.Row, Work.Column) := I;

                Solve_Sequential (Next_Work (Row    => Work.Row,
                                             Column => Work.Column,
                                             Board  => Work.Scratch_Board));

                --  Solution didn't work, undo
                Work.Scratch_Board.all.Values
                  (Work.Row, Work.Column) := 0;

             end if;
          end loop;

       end Solve_Sequential;

       Scratch_Board : aliased Sudoku_Board := Board;

    begin
       Solve_Sequential (Next_Work (Board => Scratch_Board'Access));
    end Solve;

    ---------------------------------------------------------------

    function Value_In_Diagonal
      (Board    : Sudoku_Board;
       Row, Col : Sudoku_Index;
       Value    : Sudoku_Solution_Value) return Boolean is
    begin

       if Row = Col then
          return
            (for some I in Board.Values'Range (1) =>
               Board.Values (I, I) = Value);
       else
          return
            (for some I in Board.Values'Range (1) =>
               Board.Values (Max_Range + 1 - I, I) = Value);
       end if;

    end Value_In_Diagonal;

    ---------------------------------------------------------------

    function Value_In_Sector
      (Board : Sudoku_Board;
       Row, Col : Sudoku_Index;
       Value : Sudoku_Solution_Value)
       return Boolean
    is
       Start_Row : constant Sudoku_Index :=
         1 + ((Sudoku_Index'Base (Row) - 1) / N) * N;
       Start_Col : constant Sudoku_Index :=
         1 + ((Sudoku_Index'Base (Col) - 1) / N) * N;
    begin
       for I in Start_Row .. Start_Row + N - 1 loop
          for J in Start_Col .. Start_Col + N - 1 loop
             if Board.Values (I, J) = Value then
                return True;
             end if;
          end loop;
       end loop;

       return False;

    end Value_In_Sector;

end Sequential_Sudoku;

Re: OT: A bit of Sudoku

[Shark8]

On 05-Jun-14 13:00, J-P. Rosen wrote:
> I know that not everybody likes this idea, but to me exceptions are a
> powerful programming structure, not limited to handling errors.

Indeed, you can [ab]use them to get out of otherwise sticky situations, 
like the recursion problem when defining your "=" function:

   -- Nullable access-string type.
   Type LString is Access String;

   -- Definition of "=" returns true when both sides are NULL,
   -- returns false when only one side is NULL, and behaves as
   -- normal string-equality when neither side is NULL.
   Function "=" (Left, Right: IN LString) Return Boolean is

      Function Is_Equal(Left : LString; Right : String) Return Boolean is
      begin
         Return Right = Left.All;
      exception
         When CONSTRAINT_ERROR => Return False;
      end Is_Equal;

   Begin
      Return Is_Equal(Left, Right.All);
   Exception
      When CONSTRAINT_ERROR =>
         begin
            -- If this raises CONSTRAINT_ERROR, then both were NULL.
            Return Is_Equal(Right,Left.All);
         Exception
            When CONSTRAINT_ERROR => Return True;
         end;
   End "=";

Re: OT: A bit of Sudoku

[J-P. Rosen]

Le 13/06/2014 02:21, Shark8 a écrit :
> Indeed, you can [ab]use them to get out of otherwise sticky situations,
> like the recursion problem when defining your "=" function:
Sure, any good thing can be abused of, and your example is clearly an
abuse. And there are borderline cases, where it is not obvious whether
it is better to use exceptions or a simple test.

I guess that's why "programming is a human activity" (Introduction (6/3)...

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: OT: A bit of Sudoku

[Mike H]

In message <ourmv.598292$hv6.317046@fx17.iad>, Shark8 
<OneWingedShark@gmail.com> writes
>
>  -- Definition of "=" returns true when both sides are NULL,
>  -- returns false when only one side is NULL, and behaves as
>  -- normal string-equality when neither side is NULL.
Is this an example where Dmitry's three state logical (True, Uncertain, 
False)  might be useful?
See <http://www.dmitry-kazakov.de/ada/intervals.htm>

-- 
The moving finger keys; and, having keyed, keys 'send';
nor all one's piety nor wit shall lure it back to cancel half a line,
nor all one's tears wash out one word of it. Mike

Re: OT: A bit of Sudoku

[Dmitry A. Kazakov]

On Fri, 13 Jun 2014 11:10:25 +0100, Mike H wrote:

> In message <ourmv.598292$hv6.317046@fx17.iad>, Shark8 
> <OneWingedShark@gmail.com> writes
>>
>>  -- Definition of "=" returns true when both sides are NULL,
>>  -- returns false when only one side is NULL, and behaves as
>>  -- normal string-equality when neither side is NULL.
> Is this an example where Dmitry's three state logical (True, Uncertain, 
> False)  might be useful?
> See <http://www.dmitry-kazakov.de/ada/intervals.htm>

As much as I wished, I can take credit for tri-state logic. It was known
since first third of XX century.

The extension is four-state Dunn-Belnap's logic (true, false, uncertain,
contradictory), of which natural application is for run-time check
conditions. [*]

Run-time checks could be inconsistent, e.g. when two sources contradict
each other. A trustful (AKA gullibility) combination of the sources (say
from two independent packages) yields "contradictory". A conservative (AKA
consensus) combination does "uncertain".

Interval relation use only conservative combination, thus tri-state logic
is sufficient for them.

----------------
* Reasoning based on lies, so to say.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: OT: A bit of Sudoku

[Shark8]

On 13-Jun-14 04:10, Mike H wrote:
> In message <ourmv.598292$hv6.317046@fx17.iad>, Shark8
> <OneWingedShark@gmail.com> writes
>>
>>  -- Definition of "=" returns true when both sides are NULL,
>>  -- returns false when only one side is NULL, and behaves as
>>  -- normal string-equality when neither side is NULL.
> Is this an example where Dmitry's three state logical (True, Uncertain,
> False)  might be useful?
> See <http://www.dmitry-kazakov.de/ada/intervals.htm>
>

No, not really.
You want "=" to behave like "=" on strings, but extended to handle the 
NULL-cases, and that means a standard boolean result.

Re: OT: A bit of Sudoku

[Mike H]

In message <5365d3f0-43cc-47ef-989c-d47992c84c9f@googlegroups.com
>Without seeing an actual program or any code at all, I can't really 
>tell, but ... when a caller calls itself recursively, isn't there 
>either a function result or an OUT parameter that allows the callee to 
>tell the caller whether it has succeeded?  In which case the caller 
>simply exits, and returns to *its* caller passing back the correct 
>answer and if necessary a flag indicating that it's succeeded.  I have 
>no idea whether I've identified the problem correctly, but it's the 
>best I can do without seeing any code. Anyway, I think that's the 
>general approach to handling backtracking problems.
Thank you for giving me an alternative angle of view.

The trial and error process is optimised by preselection of a matching 
pair of cells, they match in the sharing of a common pair of candidate 
solutions. By analogy, it is a choice of left or right. On  average, 50% 
of trials will have explored both possibilities in which the first will 
have been wrong and the second will have proved to be correct. In the 
other 50%, the first choice will have been correct so the second choice 
is left dangling and unvisited..

I chose, perhaps wrongly, that the complete grid of 81 cells is passed 
down the recursion tree (as IN OUT). At each level, the grid is further 
completed as the full gamut of deterministic algorithms is exercised 
before either a lack of further success prompts a further trial and 
error attempt or a positive failure forces a return of up the tree. 
Thus, a return of control to a caller is taken as a positive signal of 
failure. But, currently, there is no equivalent positive indicator of 
success.

I am beginning to think that a three-state flag is required (NO,  MAYBE, 
YES). YES is not known until the 81st cell is solved. The job is now 
complete and control must now be passed back up the tree. What is 
different is that a YES would be a tangible way of contradicting the 
previous assumption that a return of control means failure.

-- 
Mike
Swim? Naturally at Severn Vale
<http://www.severnvalesc.org/>

Re: OT: A bit of Sudoku

[Adam Beneschan]

On Thursday, June 5, 2014 1:03:10 PM UTC-7, Mike H wrote:

> I chose, perhaps wrongly, that the complete grid of 81 cells is passed 
> down the recursion tree (as IN OUT). At each level, the grid is further 
> completed as the full gamut of deterministic algorithms is exercised 
> before either a lack of further success prompts a further trial and 
> error attempt or a positive failure forces a return of up the tree. 
> Thus, a return of control to a caller is taken as a positive signal of 
> failure. But, currently, there is no equivalent positive indicator of 
> success.

My own experience with problems of this sort has been that passing the entire problem-state to the next level as an IN OUT parameter (or the equivalent, in other languages) makes life more difficult.  The callee needs to be able to make changes to the problem-state in order to try different possibilities; the caller needs the problem-state to stay the same, so that if the callee returns without finding a solution, the caller can try the next thing on the problem-state it was given as an input parameter.  The last time I wrote a Sudoku solver, I therefore made sure the grid I passed to recursive calls was a (modified) copy of the input parameter, not a reference to the same parameter.  For some kinds of problems, this might be unfeasible; but an array of 81 integers is pretty easy to handle.  By the way, the program found answers almost instantaneously, and it used only backtracking--no attempt to try to deal with simple cases the way I would approach it if solving by hand.  So while it might be interesting (and instructive) to try to write a program that will work optimally, in practice it isn't necessary for this particular game.

Good luck.  Backtracking programs aren't easy to write correctly.

                                    -- Adam

Re: OT: A bit of Sudoku

[Stefan.Lucks]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1783 bytes --]

On Thu, 5 Jun 2014, Adam Beneschan wrote:

> My own experience with problems of this sort has been that passing the 
> entire problem-state to the next level as an IN OUT parameter (or the 
> equivalent, in other languages) makes life more difficult.

It really depends on the problem you are trying to solve.

> The callee needs to be able to make changes to the problem-state in 
> order to try different possibilities; the caller needs the problem-state 
> to stay the same, so that if the callee returns without finding a 
> solution, the caller can try the next thing on the problem-state it was 
> given as an input parameter.

Right. So the callee *must* undo the change(s) it made, before returning 
without a solution. If undoing is that trivial, then an in-out parameter 
(or "global" variable declared in some outer scope) for the state is 
reasonable. It may even be useful to transfer a solution found back to the 
callee (just don't undo the changes you made ...).

As I understand for the Sudoku case, the entire change is to assign a 
digit to an empty cell, and undoing means to turn the cell's state back to 
empty. If I am right, undoing changes is very easy, indeed!

> The last time I wrote a Sudoku solver,

Well, I have never written a Sudoku solver, but I did apply the 
above approach to other backtracking problems, see, e.g., 
<http://rosettacode.org/wiki/Knight%27s_tour#Ada>.

BTW, a Sudoku-solver for Ada is still missing at Rosetta Code 
<http://rosettacode.org/wiki/Sudoku>.


So long

Stefan

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--

Re: OT: A bit of Sudoku

[Mike H]

In message <alpine.DEB.2.10.1406061056170.1469@debian>, 
Stefan.Lucks@uni-weimar.de writes
>As I understand for the Sudoku case, the entire change is to assign a 
>digit to an empty cell, and undoing means to turn the cell's state back 
>to empty. If I am right, undoing changes is very easy, indeed!
Not quite? Unless one is using brute force trial and error, there is 
some unavoidable housekeeping to be done Every cell, or rather the value 
or absence of value in that cell, influences the 24 other cells that 
have its line, column and block in common. However, if the caller 
retains its own copy of the state of the problem domain at the time that 
it made its call, it now has an additional piece of information. It now 
"knows" that calling the callee was not a correct option and, if the 
program is to continue, must have some alternative course of action up 
its sleeve. In a recursive process, one such alternative must be to 
return control to its own caller.

-- 
"Why," said Ford squatting down beside him and shivering, "are you lying face
down in the dust?" "It's a very effective way of being wretched," said Marvin.
Mike ;-(

Re: OT: A bit of Sudoku

[Adam Beneschan]

On Friday, June 6, 2014 2:10:43 AM UTC-7, Stefan...@uni-weimar.de wrote:
> On Thu, 5 Jun 2014, Adam Beneschan wrote:
> 
> > My own experience with problems of this sort has been that passing the 
> > entire problem-state to the next level as an IN OUT parameter (or the 
> > equivalent, in other languages) makes life more difficult.
> 
> It really depends on the problem you are trying to solve.
> 
> > The callee needs to be able to make changes to the problem-state in 
> > order to try different possibilities; the caller needs the problem-state 
> > to stay the same, so that if the callee returns without finding a 
> > solution, the caller can try the next thing on the problem-state it was 
> > given as an input parameter.
> 
> Right. So the callee *must* undo the change(s) it made, before returning 
> without a solution. If undoing is that trivial, then an in-out parameter 
> 
> (or "global" variable declared in some outer scope) for the state is 
> reasonable. It may even be useful to transfer a solution found back to the 
> callee (just don't undo the changes you made ...).
> 
> As I understand for the Sudoku case, the entire change is to assign a 
> digit to an empty cell, and undoing means to turn the cell's state back to 
> empty. If I am right, undoing changes is very easy, indeed!

That makes assumptions about the algorithm.  If the data structure that represents the current problem state has additional information--for instance, if the data structure also has some additional summary information intended to help optimize the solver's search process--then undoing changes becomes more difficult.  You *could* use a simple 81-integer array as the entire state information, but there's nothing that says you have to; if you use a record that has, say, an 81-integer array, an 9-element array that holds a bit vector to indicate which numbers have been used in row, and similar 9-element arrays for each column and 3x3 grid, then undoing becomes messier, while copying is still simple.  (I'd have to go back and look for the algorithm I used last time I wrote a program for this, but I think I was using bit vectors like this to speed up the process.)  Copying becomes more difficult when the state information involves linked lists or trees or something like that.

Anyway, either way is a possibility; I'm just saying that in the cases I've worked with, the copying approach has worked better.  

                              -- Adam