* OT: A bit of Sudoku @ 2014-06-05 17:49 Mike H 2014-06-05 18:30 ` Adam Beneschan 0 siblings, 1 reply; 25+ messages in thread From: Mike H @ 2014-06-05 17:49 UTC (permalink / raw) 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) ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 17:49 OT: A bit of Sudoku Mike H @ 2014-06-05 18:30 ` Adam Beneschan 2014-06-05 19:00 ` J-P. Rosen 2014-06-05 20:03 ` Mike H 0 siblings, 2 replies; 25+ messages in thread From: Adam Beneschan @ 2014-06-05 18:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 18:30 ` Adam Beneschan @ 2014-06-05 19:00 ` J-P. Rosen 2014-06-05 19:18 ` Jeffrey Carter ` (3 more replies) 2014-06-05 20:03 ` Mike H 1 sibling, 4 replies; 25+ messages in thread From: J-P. Rosen @ 2014-06-05 19:00 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 19:00 ` J-P. Rosen @ 2014-06-05 19:18 ` Jeffrey Carter 2014-06-05 19:43 ` J-P. Rosen 2014-06-05 20:05 ` Mike H ` (2 subsequent siblings) 3 siblings, 1 reply; 25+ messages in thread From: Jeffrey Carter @ 2014-06-05 19:18 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 19:18 ` Jeffrey Carter @ 2014-06-05 19:43 ` J-P. Rosen 0 siblings, 0 replies; 25+ messages in thread From: J-P. Rosen @ 2014-06-05 19:43 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 19:00 ` J-P. Rosen 2014-06-05 19:18 ` Jeffrey Carter @ 2014-06-05 20:05 ` Mike H 2014-06-05 23:12 ` Robert A Duff 2014-06-13 0:21 ` Shark8 3 siblings, 0 replies; 25+ messages in thread From: Mike H @ 2014-06-05 20:05 UTC (permalink / raw) 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 ;-) ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 19:00 ` J-P. Rosen 2014-06-05 19:18 ` Jeffrey Carter 2014-06-05 20:05 ` Mike H @ 2014-06-05 23:12 ` Robert A Duff 2014-06-05 23:39 ` Adam Beneschan 2014-06-13 0:21 ` Shark8 3 siblings, 1 reply; 25+ messages in thread From: Robert A Duff @ 2014-06-05 23:12 UTC (permalink / raw) "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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 23:12 ` Robert A Duff @ 2014-06-05 23:39 ` Adam Beneschan 2014-06-06 7:51 ` Dmitry A. Kazakov 2014-06-06 14:13 ` Brad Moore 0 siblings, 2 replies; 25+ messages in thread From: Adam Beneschan @ 2014-06-05 23:39 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 23:39 ` Adam Beneschan @ 2014-06-06 7:51 ` Dmitry A. Kazakov 2014-06-06 9:21 ` Georg Bauhaus 2014-06-06 15:47 ` Adam Beneschan 2014-06-06 14:13 ` Brad Moore 1 sibling, 2 replies; 25+ messages in thread From: Dmitry A. Kazakov @ 2014-06-06 7:51 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 7:51 ` Dmitry A. Kazakov @ 2014-06-06 9:21 ` Georg Bauhaus 2014-06-06 13:38 ` Dmitry A. Kazakov 2014-06-06 15:47 ` Adam Beneschan 1 sibling, 1 reply; 25+ messages in thread From: Georg Bauhaus @ 2014-06-06 9:21 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 9:21 ` Georg Bauhaus @ 2014-06-06 13:38 ` Dmitry A. Kazakov 0 siblings, 0 replies; 25+ messages in thread From: Dmitry A. Kazakov @ 2014-06-06 13:38 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 7:51 ` Dmitry A. Kazakov 2014-06-06 9:21 ` Georg Bauhaus @ 2014-06-06 15:47 ` Adam Beneschan 2014-06-06 17:09 ` Dmitry A. Kazakov 2014-06-07 6:03 ` J-P. Rosen 1 sibling, 2 replies; 25+ messages in thread From: Adam Beneschan @ 2014-06-06 15:47 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 15:47 ` Adam Beneschan @ 2014-06-06 17:09 ` Dmitry A. Kazakov 2014-06-07 6:03 ` J-P. Rosen 1 sibling, 0 replies; 25+ messages in thread From: Dmitry A. Kazakov @ 2014-06-06 17:09 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 15:47 ` Adam Beneschan 2014-06-06 17:09 ` Dmitry A. Kazakov @ 2014-06-07 6:03 ` J-P. Rosen 1 sibling, 0 replies; 25+ messages in thread From: J-P. Rosen @ 2014-06-07 6:03 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 23:39 ` Adam Beneschan 2014-06-06 7:51 ` Dmitry A. Kazakov @ 2014-06-06 14:13 ` Brad Moore 1 sibling, 0 replies; 25+ messages in thread From: Brad Moore @ 2014-06-06 14:13 UTC (permalink / raw) 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; ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 19:00 ` J-P. Rosen ` (2 preceding siblings ...) 2014-06-05 23:12 ` Robert A Duff @ 2014-06-13 0:21 ` Shark8 2014-06-13 6:30 ` J-P. Rosen 2014-06-13 10:10 ` Mike H 3 siblings, 2 replies; 25+ messages in thread From: Shark8 @ 2014-06-13 0:21 UTC (permalink / raw) 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 "="; ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-13 0:21 ` Shark8 @ 2014-06-13 6:30 ` J-P. Rosen 2014-06-13 10:10 ` Mike H 1 sibling, 0 replies; 25+ messages in thread From: J-P. Rosen @ 2014-06-13 6:30 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-13 0:21 ` Shark8 2014-06-13 6:30 ` J-P. Rosen @ 2014-06-13 10:10 ` Mike H 2014-06-13 12:37 ` Dmitry A. Kazakov 2014-06-13 15:47 ` Shark8 1 sibling, 2 replies; 25+ messages in thread From: Mike H @ 2014-06-13 10:10 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-13 10:10 ` Mike H @ 2014-06-13 12:37 ` Dmitry A. Kazakov 2014-06-13 15:47 ` Shark8 1 sibling, 0 replies; 25+ messages in thread From: Dmitry A. Kazakov @ 2014-06-13 12:37 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-13 10:10 ` Mike H 2014-06-13 12:37 ` Dmitry A. Kazakov @ 2014-06-13 15:47 ` Shark8 1 sibling, 0 replies; 25+ messages in thread From: Shark8 @ 2014-06-13 15:47 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 18:30 ` Adam Beneschan 2014-06-05 19:00 ` J-P. Rosen @ 2014-06-05 20:03 ` Mike H 2014-06-05 20:40 ` Adam Beneschan 1 sibling, 1 reply; 25+ messages in thread From: Mike H @ 2014-06-05 20:03 UTC (permalink / raw) 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/> ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 20:03 ` Mike H @ 2014-06-05 20:40 ` Adam Beneschan 2014-06-06 9:10 ` Stefan.Lucks 0 siblings, 1 reply; 25+ messages in thread From: Adam Beneschan @ 2014-06-05 20:40 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-05 20:40 ` Adam Beneschan @ 2014-06-06 9:10 ` Stefan.Lucks 2014-06-06 10:59 ` Mike H 2014-06-06 16:06 ` Adam Beneschan 0 siblings, 2 replies; 25+ messages in thread From: Stefan.Lucks @ 2014-06-06 9:10 UTC (permalink / raw) [-- 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-- ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 9:10 ` Stefan.Lucks @ 2014-06-06 10:59 ` Mike H 2014-06-06 16:06 ` Adam Beneschan 1 sibling, 0 replies; 25+ messages in thread From: Mike H @ 2014-06-06 10:59 UTC (permalink / raw) 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 ;-( ^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: OT: A bit of Sudoku 2014-06-06 9:10 ` Stefan.Lucks 2014-06-06 10:59 ` Mike H @ 2014-06-06 16:06 ` Adam Beneschan 1 sibling, 0 replies; 25+ messages in thread From: Adam Beneschan @ 2014-06-06 16:06 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2014-06-13 15:47 UTC | newest] Thread overview: 25+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2014-06-05 17:49 OT: A bit of Sudoku Mike H 2014-06-05 18:30 ` Adam Beneschan 2014-06-05 19:00 ` J-P. Rosen 2014-06-05 19:18 ` Jeffrey Carter 2014-06-05 19:43 ` J-P. Rosen 2014-06-05 20:05 ` Mike H 2014-06-05 23:12 ` Robert A Duff 2014-06-05 23:39 ` Adam Beneschan 2014-06-06 7:51 ` Dmitry A. Kazakov 2014-06-06 9:21 ` Georg Bauhaus 2014-06-06 13:38 ` Dmitry A. Kazakov 2014-06-06 15:47 ` Adam Beneschan 2014-06-06 17:09 ` Dmitry A. Kazakov 2014-06-07 6:03 ` J-P. Rosen 2014-06-06 14:13 ` Brad Moore 2014-06-13 0:21 ` Shark8 2014-06-13 6:30 ` J-P. Rosen 2014-06-13 10:10 ` Mike H 2014-06-13 12:37 ` Dmitry A. Kazakov 2014-06-13 15:47 ` Shark8 2014-06-05 20:03 ` Mike H 2014-06-05 20:40 ` Adam Beneschan 2014-06-06 9:10 ` Stefan.Lucks 2014-06-06 10:59 ` Mike H 2014-06-06 16:06 ` Adam Beneschan
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox