|
| View previous topic :: View next topic |
| Author |
Message |
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
 Posted: Thu Jan 12, 2006 2:33 pm Post subject: |
 |
|
| mugnyte wrote: |
| Code: |
.1.|.7.|...
.26|...|.57
5..|...|..3
-----------
..8|2..|...
.5.|..4|3.2
4..|.37|.8.
-----------
...|.53|4..
..5|...|..8
.8.|...|.96
|
was what i typed in a found to take only my sovler's trivial logic. (55 moves)
|
This is getting too confusing mugnyte, I tried this puzzle which you solved using trivial techniques. I can show (as soon as I develop the proper solver log for the specific function) that it can be solved using six double implication chains.(the actual number is between 3 & 6)
I'm sure that all trivial logic has already been used up to that point, where advanced techniques take over.
this should make it easy for everybody, what is your solver's next step following this:
| Code: | *-----------------------------------------------------------------*
| 389 1 349 | 3569 7 25689 | 2689 246 49 |
| 389 2 6 | 1349 149 189 | 189 5 7 |
| 5 479 479 | 169 1269 12689 | 12689 1246 3 |
|---------------------+---------------------+---------------------|
| 1679 3 8 | 2 169 1569 | 1679 1467 459 |
| 1679 5 179 | 169 8 4 | 3 167 2 |
| 4 69 2 | 1569 3 7 | 169 8 59 |
|---------------------+---------------------+---------------------|
| 2679 679 79 | 8 5 3 | 4 27 1 |
| 127 47 5 | 14679 12469 1269 | 27 3 8 |
| 1237 8 1347 | 147 124 12 | 5 9 6 |
*-----------------------------------------------------------------*
|
|
|
| Back to top |
|
 |
| rkral
| | Joined: 21 Oct 2005 | | Posts: 233 | | : | |
Items |
|
| Posted: Thu Jan 12, 2006 3:27 pm Post subject: |
|
|
| mugnyte wrote: | the first:
| Code: |
.1.|.7.|...
.26|...|.57
5..|...|..3
-----------
..8|2..|...
.5.|..4|3.2
4..|.37|.8.
-----------
...|.53|4..
..5|...|..8
.8.|...|.96
|
|
Like Ruud's solver needing tabling, my solver needs implication chains at this stage ... | Code: |
389 1 349 | 3569 7 25689 | 2689 246 49
389 2 6 | 1349 149 189 | 189 5 7
5 479 479 | 169 1269 12689 | 12689 1246 3
-------------------+-------------------+----------------
1679 3 8 | 2 169 1569 | 1679 1467 459
1679 5 179 | 169 8 4 | 3 167 2
4 69 2 | 1569 3 7 | 169 8 59
-------------------+-------------------+----------------
2679 679 79 | 8 5 3 | 4 27 1
127 47 5 | 14679 12469 1269 | 27 3 8
1237 8 1347 | 147 124 12 | 5 9 6 |
Would you please identify your solver's next move ... and the reason?
Thanks, Ron
[edit: Oops, I see tarek's "sticking point" is exactly the same ... and has asked the same question.] |
|
| Back to top |
|
|
| mugnyte
| | Joined: 07 Dec 2005 | | Posts: 13 | | : | | Location: portland, or |
Items |
|
| Posted: Thu Jan 12, 2006 10:36 pm Post subject: |
|
|
Thanks for you patience guys. I'm really sorry for the confusion. There's no magic, but indeed the board is solved without backups*. Here's why:
At the point you mention...
| Code: |
389 1 349 | 3569 7 25689 | 2689 246 49
389 2 6 | 1349 149 189 | 189 5 7
5 479 479 | 169 1269 12689 | 12689 1246 3
-------------------+-------------------+----------------
1679 3 8 | 2 169 1569 | 1679 1467 459
1679 5 179 | 169 8 4 | 3 167 2
4 69 2 | 1569 3 7 | 169 8 59
-------------------+-------------------+----------------
2679 679 79 | 8 5 3 | 4 27 1
127 47 5 | 14679 12469 1269 | 27 3 8
1237 8 1347 | 147 124 12 | 5 9 6
|
...my sovler scans for the next best move. It applies all logic, resulting in the above. It works downward, leftward (in such order) from the top left square, and keeps the cell with best choices.
This is [2,6] from [top left], which presents choices of 6 or 9. *It guesses 6, the lowest number. This turns out to be a "magic cell" - for logic up to subset elim - in this puzzle, requiring no more guessses and no more higher logic.
I eluded to bias a bit before, but here's where my sovler may rate games mistakenly: The act of always choosing the lowest number in a choice (until a backup forces the next value) can result in puzzles which are sovled quickly but actually involve quite a bit more logic.
As I add output to the solver log, I find that some games require quite a large number of guesses, but solve without backups due to the puzzle and the solver having a matched bias. Since the values themselves are completely interchangeable, the integer amount shouldn't introduce bias, but the solver has to guess something.
If you guys have a better algorithm than pure random for guesses, then by all means let me know. Such a guess is after all the logic the code has (or the user chooses to employ).
A near-future version will choose a random value from the set, and if a guess was made, solve at least 2 times (with different rnd seeds) to compensate for this bias in my puzzle-rating code. Oh, and I'll have a few more modules, which can allow me to perhaps participate in the discussion a little more.
Sadly, all this confusion is a combination of my lack of a proper solving log (not tracking the number of times a guess was taken) and the built-in bias of the solver. I hope I've not lost your respect, haha, if any, in this little goose chase.
Jim
_________________
thanks |
|
| Back to top |
|
|
| tarek
| | Joined: 31 Dec 2005 | | Posts: 153 | | : | | Location: London, UK |
Items |
|
| Posted: Thu Jan 12, 2006 11:01 pm Post subject: |
|
|
This looks clearer now mugnyte, Guessing is not a trivial technique at all.
As matter of fact, you should try avoiding using it at all costs. A Human-style solver would leave Guessing as the last step, it can't be trivial !
A human-style solver would find patterns first & guess last.
tarek |
|
| Back to top |
|
|
| mugnyte
| | Joined: 07 Dec 2005 | | Posts: 13 | | : | | Location: portland, or |
Items |
|
| Posted: Thu Jan 12, 2006 11:32 pm Post subject: |
|
|
oh, I agree completely. Like many folks here, I'm trying to implement modules that point out a single for every move of every puzzle (so far). Seems like many have it down, so i started referred to guessing as trivial since it really doesn't involve any logic (as in "choose the lowest value", as I explained above).
The platform I have has two phases: apply logic modules to reduce choices, then make a move. The guessing only occurs when my current modules don't afford a single. The design benefits, I guess, from having the ability to guess as much as necessary without recursion. A stack structure is still used, but it's quite minimal compared to method calls.
Jim
_________________
thanks |
|
| Back to top |
|
|
| rkral
| | Joined: 21 Oct 2005 | | Posts: 233 | | : | |
Items |
|
| Posted: Fri Jan 13, 2006 12:00 am Post subject: |
|
|
| mugnyte wrote: | ...my sovler scans for the next best move. It applies all logic, resulting in the above. It works downward, leftward (in such order) from the top left square, and keeps the cell with best choices.
This is [2,6] from [top left], which presents choices of 6 or 9. |
So your solver is scanning the cells of a column top to bottom, columns left to right and then trying the lowest digit of the first pair it finds? Or is it doing something more sophisticated to determine the "next best move". |
|
| Back to top |
|
|
| mugnyte
| | Joined: 07 Dec 2005 | | Posts: 13 | | : | | Location: portland, or |
Items |
|
| Posted: Fri Jan 13, 2006 12:08 am Post subject: |
|
|
Oh, it has more complex logic than that, implementing Cross Hatch Scanning, Range Check and Subset Elimination (then, upcoming, Grid Analysis and 3DMedusa) before such scanning.
The scanning is simply to choose a "move" - a filling in of a cell, for the sake of the board/log/user.
_________________
thanks |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
