View unanswered posts | View active topics It is currently Mon Oct 23, 2017 7:03 pm



← Back to the Calcudoku puzzle page




Reply to topic  [ 17 posts ]  Go to page Previous  1, 2
 My new puzzles 
Author Message
User avatar

Posted on: Fri Nov 23, 2012 5:41 pm




Posts: 2197
Joined: Thu May 12, 2011 11:58 pm
Post Re: My new puzzles
nicow wrote:
My program solves the first one in 737 seconds, with 540 reboots. And then some 2000 reboots more to prove its uniqueness. So this one is very, very difficult.
My pc is an i5 on 2.8 GHz, and the system uses some basic logic, naked pairs included. But of coarse not all the logic CLM is capable of!!

The second puzzle is solved in 3.3 seconds with only logic. So this one is easy.

Thanks for providing the puzzle files. My solver clearly misses a few heuristics: for the first puzzle, I stopped it after about an hour.

The 2nd one was solved in 0.5 seconds.

Patrick


Profile

Posted on: Sat Nov 24, 2012 12:27 am




Posts: 54
Joined: Thu Nov 03, 2011 8:52 am
Post Re: My new puzzles
Thanks nikow and pnm.
My solver only uses brute force. Therefore, it doesn't tell me anything about whether trial and error is needed or not. It's not easy to write a program that applies the strategies a human with paper and pencil can use. But it seems that this is the only way to discriminate between what I call "solvable" and "non-solvable" puzzles...


Profile

Posted on: Sat Nov 24, 2012 12:31 am




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post Re: My new puzzles
pnm wrote:
nicow wrote:
My program solves the first one in 737 seconds, with 540 reboots. And then some 2000 reboots more to prove its uniqueness. So this one is very, very difficult.
My pc is an i5 on 2.8 GHz, and the system uses some basic logic, naked pairs included. But of coarse not all the logic CLM is capable of!!

The second puzzle is solved in 3.3 seconds with only logic. So this one is easy.

Thanks for providing the puzzle files. My solver clearly misses a few heuristics: for the first puzzle, I stopped it after about an hour.

The 2nd one was solved in 0.5 seconds.

Patrick


It's very interesting to observe the different strategies to solve the puzzles by the different programs (thanks to nicow for the translation to the code) and the different times obtained (and ratings if you have the possibility of calculating them, I am impatient, Patrick, for your "solver rating" for this puzzle, I am sure you will have it soon, it's clear that one hour for the solution phase looks too much ... ).

Btw, giulio, I will be among those volunteers (depending on the available time [smile], I enjoy the new challenges) though I am not very sure about the comparison between the "human experience" and the "computer experience" to derive conclusions though the statistics are always useful (in chess, for instance, the computers actually defeat the humans, let's say in a 99,99%, because they "see" beyond or "more deeply", but sometimes the theory, the "previous knowledge", has been an advantage; the chess software has been refined a lot in the last 20-25 years); the Calcudoku is relatively new and a question arises: Is the software taking into account all the solving strategies, all the rules, all the "libraries", or the computers mainly use the "Trial And Error" :-)?; in other words, the quality of the software (algorithms, ... ) is a very important factor.


Profile

Posted on: Sat Nov 24, 2012 3:30 am




Posts: 54
Joined: Thu Nov 03, 2011 8:52 am
Post Re: My new puzzles
My Sudoku solver uses all strategies I am aware of, and grades the difficulty of the puzzles on the basis of how difficult the strategies necessary to solve them are. And I graded the difficulty of the strategies depending on how difficult I find them. No objective measurement.

I tried to do the same with CalcuDokus, but ran into all sorts of problems, because I found the strategies applicable to CalcuDokus much more "open" (for lack of a better word). With Sudoku, most strategies rely on the interaction of boxes and lines (i.e., rows and columns). Once you have defined a strategy, it is comparatively easy to write a program to apply it. With CalcuDoku, I found it very difficult to define strategies in generic terms.

With enough memory to store lists of permutations, you can certainly solve all puzzles analytically, but what interests me is what a human without photographic memory can solve analytically, without guessing and only using as memory aid the sheet of paper on which the puzzle has been printed. I would also exclude the techniques used by people who remember decks of cards or long seuences of numbers, because they are in fact "programs". Then, whether a puzzle is solvable or not depends on the ability to recognise patterns and analyse them. The puzzle becomes a sort of IQ test. I realise that this definition is ambiguous. But all IQ tests only have a limited range of applicability.

How long it takes to reach a solution is of no interest to me. I was involved with hig-IQ societies for a while, and discovered that there are problems that many people cannot solve, regardless of how much time they spend on them. Some IQ problems don't ever appear as problems to most people. That's why I am convinced that the patterns necessary to solve the most difficult CalcuDoku puzzles are invisible to the majority of solvers.

In fact, I would also be interested in exploring possible correlations between the ability to solve difficult CalcuDokus and IQ values as measured with tests that focus on fluid intelligence. I believe that this would require an "objective" measure of CalcuDoku difficulties, though...

I'm diverging, I guess.

My statistical approach to infer an empiric grading of CalcuDokus based on measurable parameters could be useful as a benchmark for other grading techniques, including the grading produced by a computer program. Incidentally, IMO, if enough people (TBD how many are "enough") perceive a puzzle more difficult than another, it means that it is more difficult. At least, let's say that such definition of "difficulty" is the one I prefer over any definition based on computer programs. Wouldn't it be great if we could identify CalcuDokus that require a certain IQ to be solved? At the very least, I would like to know whether posing such a question makes sense at all!

clm, thanks for volunteering, but I'm not working on it yet. I'll let you know... [smile]


Profile

Posted on: Sat Dec 29, 2012 3:34 pm




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post Re: My new puzzles
Hi Giulio, around a month and a half has elapsed since you proposed that really difficult 9x9. Since no more comments have been sent in a long time, perhaps it's time already to show the full solution. Here is it (we must wait anyway to see if we finally may know the "solver rating" provided by the Patrick's software supposing the problems initially found have already been corrected by Patrick):

Image


Profile
User avatar

Posted on: Mon Dec 31, 2012 2:13 pm




Posts: 2197
Joined: Thu May 12, 2011 11:58 pm
Post Re: My new puzzles
clm wrote:
Hi Giulio, around a month and a half has elapsed since you proposed that really difficult 9x9. Since no more comments have been sent in a long time, perhaps it's time already to show the full solution. Here is it (we must wait anyway to see if we finally may know the "solver rating" provided by the Patrick's software supposing the problems initially found have already been corrected by Patrick):

Not really (i.e. no changes made yet to the solver).
As such, the puzzle should be a good source for finding
new heuristics my software doesn't use yet. Or maybe that would
make the puzzles too hard :-/

I ran the solver to a finish: this puzzle was solved in about 2 hours,
with the unique solution confirmed. Too much brute force involved,
testing about 11.5 x 10^9 possibilities...

If this puzzle had appeared on the site, it would have shown a difficulty factor of 291 (!)

Patrick


Profile

Posted on: Mon Dec 31, 2012 11:50 pm




Posts: 690
Joined: Fri May 13, 2011 6:51 pm
Post Re: My new puzzles
pnm wrote:
... Not really (i.e. no changes made yet to the solver).
As such, the puzzle should be a good source for finding
new heuristics my software doesn't use yet. Or maybe that would
make the puzzles too hard :-/

I ran the solver to a finish: this puzzle was solved in about 2 hours,
with the unique solution confirmed. Too much brute force involved,
testing about 11.5 x 10^9 possibilities...

If this puzzle had appeared on the site, it would have shown a difficulty factor of 291 (!)

Patrick


Thanks, finally we have the "computer's opinion", really interesting, certainly 291 !!!, the higher calculated in this site IIRC, it looks very high for using this level in the regular weekly days [scared] [scared] .
I suppose the difficulty factor is mainly related to that huge amount of possibilities than to the time spent in the solution (2 hours). Anyway the brute force is always a big advantage for the computers with respect to humans, they never give up ... :-) :-)


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 17 posts ]  Go to page Previous  1, 2

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

Search for:
Jump to:  
cron
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.