Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Mon Aug 19, 2013 4:43 pm

saul wrote:[...]but if you've been systematically checking and have only found the same pattern of black cells for equivalent puzzles, then they must be using an entirely different approach. Of course, you didn't say that you have been systematically checking, did you?.

No, my checks haven't been that systematic.
I've first visually compared puzzles with close names and similar patterns (this is very fast, using their png icons - but I may have missed a few).
For the matching sets, I checked that they had the same W rating (already calculated before) - they couldn't be essentially the same if they had different W ratings. Then I randomly checked on a small sample that they were indeed the same.


Given a pattern of black cells having at least one solution, we have no idea of how many different sets of sums lead to a solvable puzzle.

The atk puzzles (and most of the published puzzles) have givens for all the sectors. This probably entails that they are not minimal. But we have no idea of how many sums should be given in a minimal puzzle. Perhaps very few (even zero - err, no, at least one) for some patterns.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Naming scheme of the atk puzzles

Postby denis_berthier » Wed Aug 21, 2013 7:25 am



Naming scheme of the atk puzzles



It appears that there is no chance at all in the similarity of atk puzzles with related names: equivalent variants are generated in a systematic way.

More precisely, for each puzzle size, atk puzzles are named according to the following pattern: RBxy

R = E | M | H (stands for: Easy | Medium | Hard)
B = Number (B names the pattern of black cells)
x = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
y = 1 | 2
(Had anyone noticed that all the puzzle names have a 1 or a 2 as their last digit or that none of them has an 8 or a 9 as their last-but-one digit ?)

All the puzzles with the same R and B are essentially equivalent to the first in the series (i.e. the one with x = 0 and y = 1) via the following transformations:

- from y = 1 pass to y = 2 by replacing each S in a sector of size n by 10*n - S (in the corresponding solution, each digit i is replaced by 10 - i)

- from x = 0, pass to:
x = 1 by vertical symmetry
x = 2 by horizontal symmetry
x = 3 by 180° rotation (central symmetry)
x = 4 by +90° rotation
x = 5 by first diagonal symmetry
x = 6 by second diagonal symmetry
x = 7 by -90° rotation

As a result, each puzzle appears in the collection under 16 equivalent forms.

I have checked this in detail on the M73901 case, and in lesser detail for the other puzzles I had already solved (but I've found no exception).


This is rather weird for a collection of puzzles. But, once you know it and you don't want to solve the "same" puzzle several times, it remains that this collection is the most interesting of those I could find on the web.

(Secondarily, it allowed me to check - somewhat involuntarily - that all the essentially equivalent puzzles I had tried had the same W rating. As CSP-Rules is entirely written in a way that cannot introduce any difference between essentially equivalent puzzles, this is for me a test that I didn't introduce bugs - at least not of this type - in my Kakuro interface to CSP-Rules).
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sat Aug 31, 2013 5:30 pm

Good afternoon. Have either of you looked at skyscraper puzzles? I just ran acroos these: http://www.iqflash.com/skyscraper-puzzle.shtml They're reminiscent of sudoku in that they involve latin squares, but somehow I find them more engaging. Unfortunately, the interface at this site is not very good. I think I'll have to copy them to paper to attempt the harder puzzles. (The first 8 or 9 are pretty easy, but then they get harder.) I found so many sites by googling "skyscraper puzzle" that I didn't even make a note of them. I can't recall seeing these under a Japanese name, and didn't find them on Nikoli's website.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Sep 01, 2013 10:44 am

saul wrote:Have either of you looked at skyscraper puzzles?

I had already seen some, but I never tried. I'm not likely to try in the near future.

After solving manually a few tens of any of these kinds of puzzles (including Sudoku), I find it very boring (always the same tricks).
[At least, in non-Sudoku puzzles, there isn't the flood of absurdly complex rules or pseudo-rules with ridiculous fish or missile names that a non-desperatedly-addicted player will never be able to remember - let alone try.]

But I find it exciting to formulate precise general rules allowing to automate their solving.
I'm still fighting with the global only-one-loop constraint in Slitherlink. I'm not far from being able to eliminate the "small" loops (that may indeed not be so small) and to solve without T&E all the puzzles I've found.

Are you still working on your Kakuro solver ? What about Slitherlink ?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Sep 01, 2013 2:41 pm

denis_berthier wrote:Are you still working on your Kakuro solver ? What about Slitherlink ?


I haven't worked on the kakuro solver for quite some time, first because I've been busy with other things, and second, because I'm not as fascinated by kakuro as I was. I still intend to finish the solver at some point, but it won't be as ambitious as I originally planned.

I haven't been playing slitherlink at all. It just hasn't caught my fancy this time around.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Sep 15, 2013 8:25 pm

Have a look at M54231. It's easy to get here

Image

but after that I can only solve it by repeated trial and error.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Mon Sep 16, 2013 3:08 am

Hi Saul,

saul wrote:Have a look at M54231. It's easy to get here

Image

but after that I can only solve it by repeated trial and error.


Starting from the values you've found (but discarding the candidate data), the following sequence solves the grid:

Code: Select all
naked-pairs-in-horiz-sector: r6{c2 c7}{n6 n7} ==> r6c6 <> 7, r6c6 <> 6, r6c4 <> 6
naked-pairs-in-verti-sector: c7{r2 r4}{n1 n2} ==> r8c7 <> 2, r8c7 <> 1, r5c7 <> 2, r5c7 <> 1, r3c7 <> 2, r3c7 <> 1
whip[2]: r4c3{n8 n7} - r4c2{n7 .} ==> hr4c1 <> 3479
whip[2]: hr7c5{n579 n489} - r7c7{n5 .} ==> r7c8 <> 4, r7c6 <> 4
whip[2]: hr8c5{n135 n126} - r8c7{n3 .} ==> r8c8 <> 6, r8c6 <> 6
whip[2]: vr4c6{n2789 n3689} - r8c6{n2 .} ==> r5c6 <> 3
whip[2]: vr4c6{n3689 n2789} - r8c6{n3 .} ==> r5c6 <> 2
whip[4]: r3c3{n8 n7} - hr3c1{n1345689 n1245789} - r3c7{n6 n5} - r3c2{n5 .} ==> r3c4 <> 8, r3c8 <> 8

However, this implies that the candidates (e.g. for cell r3c7) are not what you write.


If I also use your candidates (manually, because I have no input functions for candidates), a Naked Pairs can be seen in column c7, leading to r3c7 = 3. The puzzle can then be solved by bivalue-chains:

Code: Select all
biv-chain[2]: hr3c1{n1345689 n2345679} - r3c3{n8 n7} ==> r3c2 <> 7
biv-chain[2]: hr3c1{n2345679 n1345689} - r3c3{n7 n8} ==> r3c8 <> 8
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Mon Sep 16, 2013 12:19 pm

denis_berthier wrote:
If I also use your candidates (manually, because I have no input functions for candidates), a Naked Pairs can be seen in column c7, leading to r3c7 = 3. The puzzle can then be solved by bivalue-chains:



Right you are! It's hard to believe I kept overlooking that.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby kakuroatk » Tue Sep 17, 2013 11:09 pm

sometimes I find that after crunching #'s the next move is the most obvious :D
kakuroatk
 
Posts: 39
Joined: 17 September 2013
Location: NY

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Sep 29, 2013 3:31 pm

kakuroatk wrote:sometimes I find that after crunching #'s the next move is the most obvious :D


Hi,

Sorry I've gone so long without replying. Yes, sometimes I'm amazed at the simple moves I can overlook for quite a while. Does the name "kakuroatk" mean that you have something to do with producing the ATK kakuro puzzles? In any case, it's good to see somebody else who's interested in kakuro.

Denis, how does M51221 rate on your scale? This is a 6-by-6 that just seems to be terribly difficult to me. I've gone back to it a number of time over the course of a few days, so if I'm overlooking something simple, I'm being very stupid.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Sun Oct 06, 2013 12:49 am

saul wrote: .... how does M51221 rate on your scale? This is a 6-by-6 that just seems to be terribly difficult to me. .....

You got that right. Whenever I come across a 6-by-6 ATK Medium, I shudder. I figure there must be something about it that makes it difficult to solve, otherwise such a small puzzle wouldn't be labeled Medium. But with small puzzles, it's tough to find anything to latch onto right at the beginning.

A while ago I solved M51232, but it took quite a while and some trial and error. When I saw your post, I looked up M51221, and found it similarly difficult. I hadn't gotten very far when it occurred to me to see if it was isomorphic to M51232.

Sure enough, if you flip either of these puzzles about its vertical axis, and subtract each sum S from 10*N (where N is the number of digits in S), you get the corresponding sum in the other puzzle. It follows that each cell C in either puzzle is 10-C in the other. Boo!

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Oct 06, 2013 2:53 am

saul wrote:Denis, how does M51221 rate on your scale? This is a 6-by-6 that just seems to be terribly difficult to me. I've gone back to it a number of time over the course of a few days, so if I'm overlooking something simple, I'm being very stupid.


Hi Saul,
Sorry for the late answer. Contrary to what usually happens, I hadn't received any mail about a new post in this thread. I would never have noticed if I hadn't scanned the forum as I do from time to time.

M51221 rates W7 - which, for a supposedly "medium" puzzle, is extremely difficult.

Here is the full whip solution - but it has nothing interesting, not even any Subset.

Hidden Text: Show
Code: Select all
*****  KakuRules 1.2 based on CSP-Rules 1.2, config: gW   *****
       Uppermost (black) row and leftmost (black) column have index 0.
singles ==> r4c1 = 6, hr4c0 = 69, r4c2 = 9, r1c2 = 7, r1c1 = 9, vr0c1 = 69, r2c1 = 6, vr3c1 = 16, r5c1 = 1
cell-to-horiz-ctr  ==> hr3c1 <> 39
ctr-to-horiz-sector  ==> r3c3 <> 3
cell-to-horiz-ctr  ==> hr1c3 <> 34
ctr-to-horiz-sector  ==> r1c5 <> 3
ctr-to-horiz-sector  ==> r1c5 <> 4
cell-to-horiz-ctr  ==> hr4c3 <> 49
ctr-to-horiz-sector  ==> r4c5 <> 4
ctr-to-horiz-sector  ==> r4c5 <> 9
cell-to-verti-ctr  ==> vr1c3 <> 36
ctr-to-verti-sector  ==> r2c3 <> 3
verti-sector-to-ctr  ==> vr3c4 <> 17
ctr-to-verti-sector  ==> r4c4 <> 7
ctr-to-verti-sector  ==> r5c4 <> 7
biv-chain[2]: vr3c4{n26 n35} - r4c4{n6 n5} ==> r5c4 <> 5
biv-chain[2]: vr3c4{n35 n26} - r4c4{n5 n6} ==> r5c4 <> 6
biv-chain[2]: hr4c3{n58 n67} - r4c4{n5 n6} ==> r4c5 <> 6
cell-to-verti-ctr  ==> vr0c5 <> 123469
ctr-to-verti-sector  ==> r2c5 <> 9
ctr-to-verti-sector  ==> r5c5 <> 9
ctr-to-verti-sector  ==> r6c5 <> 9
biv-chain[2]: hr4c3{n67 n58} - r4c4{n6 n5} ==> r4c5 <> 5
biv-chain[2]: hr1c3{n16 n25} - r1c4{n1 n2} ==> r1c5 <> 2
biv-chain[2]: hr1c3{n25 n16} - r1c4{n2 n1} ==> r1c5 <> 1
cell-to-verti-ctr  ==> vr0c5 <> 123478
biv-chain[2]: vr0c5{n124567 n123568} - r4c5{n7 n8} ==> r6c5 <> 8, r5c5 <> 8, r2c5 <> 8
biv-chain[2]: r4c5{n7 n8} - vr0c5{n124567 n123568} ==> r6c5 <> 7, r5c5 <> 7, r2c5 <> 7
whip[2]: hr3c1{n48 n57} - r3c2{n4 .} ==> r3c3 <> 5
whip[2]: hr3c4{n16 n25} - r3c6{n4 .} ==> r3c5 <> 5
whip[2]: hr3c4{n16 n34} - r3c6{n5 .} ==> r3c5 <> 4
whip[2]: hr3c4{n25 n16} - r3c6{n4 .} ==> r3c5 <> 6
whip[2]: hr6c1{n58 n49} - r6c2{n5 .} ==> r6c3 <> 4
whip[2]: hr6c4{n19 n37} - r6c5{n1 .} ==> r6c6 <> 3
whip[2]: hr6c4{n19 n46} - r6c6{n7 .} ==> r6c5 <> 4
whip[2]: vr1c3{n18 n27} - r3c3{n4 .} ==> r2c3 <> 7
whip[2]: vr1c3{n18 n45} - r3c3{n7 .} ==> r2c3 <> 4
whip[2]: vr1c3{n27 n18} - r3c3{n4 .} ==> r2c3 <> 8
whip[2]: vr4c3{n39 n48} - r6c3{n5 .} ==> r5c3 <> 8
whip[2]: vr4c3{n48 n39} - r6c3{n5 .} ==> r5c3 <> 9
whip[2]: vr1c6{n49 n58} - r3c6{n4 .} ==> r2c6 <> 5
whip[2]: hr2c0{n123469 n123568} - r2c6{n9 .} ==> r2c2 <> 8
whip[2]: vr1c6{n58 n49} - r3c6{n5 .} ==> r2c6 <> 4
whip[2]: vr4c6{n39 n57} - r6c6{n4 .} ==> r5c6 <> 7
whip[2]: vr4c6{n48 n39} - r6c6{n4 .} ==> r5c6 <> 9
horiz-sector-to-ctr  ==> hr5c0 <> 123469
whip[5]: c2n6{r5 r6} - hr6c1{n49 n67} - r6c3{n9 n7} - vr4c3{n39 n57} - r5c3{n3 .} ==> r5c2 <> 5, hr5c0 <> 123478
biv-chain[6]: r5n2{c5 c4} - vr3c4{n35 n26} - r4c4{n5 n6} - hr4c3{n58 n67} - r4c5{n8 n7} - vr0c5{n123568 n124567} ==> r5c5 <> 3
whip[6]: r2c2{n4 n5} - r3c2{n5 n8} - hr3c1{n57 n48} - r3c3{n7 n4} - vr1c3{n18 n45} - r2c3{n1 .} ==> r6c2 <> 4
cell-to-horiz-ctr  ==> hr6c1 <> 49
ctr-to-horiz-sector  ==> r6c3 <> 9
cell-to-verti-ctr  ==> vr4c3 <> 39
ctr-to-verti-sector  ==> r5c3 <> 3
whip[6]: r2c2{n4 n5} - r3c2{n5 n8} - hr3c1{n57 n48} - r3c3{n7 n4} - vr1c3{n18 n45} - r2c3{n1 .} ==> r5c2 <> 4
whip[7]: hr5c0{n123568 n124567} - r5c6{n3 n5} - vr4c6{n48 n57} - r6c6{n4 n7} - hr6c4{n19 n37} - r6c5{n6 n3} - vr0c5{n124567 .} ==> r5c5 <> 4
whip[7]: hr5c0{n124567 n123568} - r5c3{n7 n5} - vr4c3{n48 n57} - r6c3{n8 n7} - hr6c1{n58 n67} - r6c2{n8 n6} - r5c2{n6 .} ==> r5c6 <> 8
whip[2]: vr4c6{n39 n48} - r5c6{n3 .} ==> r6c6 <> 4
cell-to-horiz-ctr  ==> hr6c4 <> 46
ctr-to-horiz-sector  ==> r6c5 <> 6
whip[3]: hr5c0{n124567 n123568} - r5c3{n4 n5} - r5c6{n5 .} ==> r5c4 <> 3
the sequel is easy
-------
-97-16-
-651247
--48-16
-69-67-
-167254
--85-28




Smythe Dakota wrote:
saul wrote:
A while ago I solved M51232, but it took quite a while and some trial and error. When I saw your post, I looked up M51221, and found it similarly difficult. I hadn't gotten very far when it occurred to me to see if it was isomorphic to M51232.

Sure enough, if you flip either of these puzzles about its vertical axis, and subtract each sum S from 10*N (where N is the number of digits in S), you get the corresponding sum in the other puzzle. It follows that each cell C in either puzzle is 10-C in the other. Boo!


Hi Bill,
According to the general atk naming scheme described here: http://forum.enjoysudoku.com/can-you-solve-this-without-trial-and-error-t30960-181.html:

M51221 is obtained from M51201 by horizontal symmetry
M51321 is obtained from M51201 by central symmetry
therefore M51321 is obtained from M51221 by vertical symmetry.

M51322 is obtained from M51321 by what could be called "digit complementation in sectors"
Finally M51322 is obtained from M51221 by the transformation you describe - which is easy to see directly; but I wanted to show we have the same result.



kakuroatk wrote:sometimes I find that after crunching #'s the next move is the most obvious :D

Hi kakuroatk,
Welcome on board.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Oct 06, 2013 2:59 am

I tend to like the smaller puzzles (though maybe not so small as 6-by-6.) I find that with the bigger ones, much of of the puzzle tends to be easy, and you spend a bunch of time clearing away the underbrush, as it were,before you get to the section that really presents a "puzzle." One like M51221 though, that I can only only solve by extensive trial-and-error isn't any fun at all, and I don't get any feeling of accomplishment from solving it. I'm not too bothered by isomorphic puzzles, myself. I agree that ATK is giving a false impression of the number of different puzzles, but I don't imagine I'd ever notice if I solved two isomorphic ones, any more than I'd notice if I solved the same one twice. I'm astonished that you were able to recognize that you'd solved an isomorph. Do you perhaps keep records of which puzzles you've solved?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Oct 06, 2013 4:05 am

saul wrote:I tend to like the smaller puzzles (though maybe not so small as 6-by-6.) I find that with the bigger ones, much of of the puzzle tends to be easy, and you spend a bunch of time clearing away the underbrush, as it were,before you get to the section that really presents a "puzzle."

Yes, the problem with large puzzles is, as they require much paper scratching at the start, puzzle creators tend to keep them easy. One thing I appreciate with atk is, they have difficult (but still solvable) large ones.

saul wrote:One like M51221 though, that I can only only solve by extensive trial-and-error isn't any fun at all, and I don't get any feeling of accomplishment from solving it.

I think most of the fun in this kind of puzzles is for the creator. It's interesting to find the hardest puzzles with the smallest size. But, like the "hardest" sudokus, nobody really wants to solve them.

saul wrote:I'm not too bothered by isomorphic puzzles, myself. I agree that ATK is giving a false impression of the number of different puzzles, but I don't imagine I'd ever notice if I solved two isomorphic ones, any more than I'd notice if I solved the same one twice.

The truth is I didn't notice before I had solved a few hundred puzzles (using KakuRules) ! I'm not sure when I finally realised it, but it seems to date back to my 16 Aug 2013 post in this thread.

saul wrote:I'm astonished that you were able to recognize that you'd solved an isomorph. Do you perhaps keep records of which puzzles you've solved?

Yes.
Considering how long it takes to manually copy a puzzle in a format that I can input to KakuRules, I keep them.
I now have more than 500 puzzles (from different websites, but the most part from atk). Most of them are "hard" and most of them have size 12 to 14.
When I try a new puzzle, I first make a screen copy of it (cmd+shift+4 on a Mac). The screen copies are png files that have small icons. I put them in different folders, depending on grid size. When they are in the same folder, they get automatically classified by name. This is how I first noticed that some of them, physically close to each other on my screen, looked alike. Then I checked that they had the same W rating, and then that they were indeed isomorphs. As you can see, this is more akin to chance "discovery" than remembering anything about solving a similar puzzle.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby kakuroatk » Mon Oct 07, 2013 5:54 pm

Hi kakuroatk,
Welcome on board.

Thank you for the warm welcome, good to be here!
saul wrote: Does the name "kakuroatk" mean that you have something to do with producing the ATK kakuro puzzles?

yes, it's my game... here is a nice small hard puzzle for anyone to try...H23152 ... good luck! :D
kakuroatk
 
Posts: 39
Joined: 17 September 2013
Location: NY

PreviousNext

Return to Kakuro