New Kakuro Generator/Site

For fans of Kakuro

What are my goals?

Postby Mathimagics » Sun Jun 07, 2015 7:06 am

Got it ... I'll prepare a small sample. The idea is simply to confirm that my rating tends to correspond to your model, so I'll provide a batch in increasing order of expected-difficulty.

Basically I've already achieved my initial goal, to be able to generate puzzles for my personal use. My favourite puzzles are Futoshiki, Skyscraper and Kakuro and I'm well on the way to being able to produce them on demand.

But I have an overarching desire to learn more about the underlying properties of the puzzle objects. So I'm not content to stop until I learn a lot more about what makes them tick.

For that reason I'm keen on learning more about the properties of {U}, with a view to perhaps generating a puzzle of any level of difficulty by direct construction, ie. from a blank grid. Or if I can't then I'll not be content until I understand why! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Kakuro Generator

Postby Mathimagics » Sun Jun 07, 2015 7:59 am

denis_berthier wrote:It was not "\" and "\\" but "/" and "//" ...


Sorry, it just goes to show what platform I'm on. Why the %$#$ Bill Gates chose to use "\" as a pathname directory delimiter when the entire civilised world would have chosen "/" is beyond me!
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Perturbing details ...

Postby Mathimagics » Sun Jun 07, 2015 8:23 am

I'm using very simple 1 or 2 cell changes. The first simply changes one cell from one value to another, the second swaps 2 values in a horizontal or vertical block. In either case the new values or positions are randomly selected from the allowable valid options.

Early tests indicate that, even for a larger puzzle like P103, the chances that a perturbation produces a new U are about 25%. For H3712 it's about 35%.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Test data

Postby Mathimagics » Sun Jun 07, 2015 10:16 am

Here's a batch of 35 variants on H3712. One per line, Unix format.

I don't expect much from this set, the variation from easiest to hardest is not that great. But if it works I'll knock up some samples from P103 which should exhibit more variety.
Attachments
TestBatch.txt
(28.81 KiB) Downloaded 86 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Test data

Postby denis_berthier » Mon Jun 08, 2015 3:33 am

Mathimagics wrote:Here's a batch of 35 variants on H3712. One per line, Unix format.
I don't expect much from this set, the variation from easiest to hardest is not that great.

In my view, there is more variety than you suspected. I've computed only the W ratings. They run from 6 to infinity.
Attachments
ratings.txt
ratings - same order
(247 Bytes) Downloaded 92 times
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

W ratings

Postby Mathimagics » Mon Jun 08, 2015 12:42 pm

Can I reasonably infer that higher W generally means harder, and infinity means extremely?
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: W ratings

Postby denis_berthier » Mon Jun 08, 2015 1:11 pm

Mathimagics wrote:Can I reasonably infer that higher W generally means harder,

yes

Mathimagics wrote:and infinity means extremely?

infinity means not solvable by whips of any length
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Latin Square problem

Postby Mathimagics » Mon Jun 08, 2015 6:13 pm

Just spotted an interesting question on Latin Squares over at stack exchange:

Latin square with no Sudoku square?

Couldn't resist it!
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Difficulty ratings

Postby Mathimagics » Tue Jun 09, 2015 2:56 am

I'd be interested to know the W-ratings for these two small grids:

The first is an example taken from an IBM posting Can you design a Kauro puzzle?, and is a dead simple puzzle but with interesting properties.
Code: Select all
8 16 . . B 24 . . . /
 17 . . 29 . . . . /
 35 . . . . . B B /
 B 7 . . 8 . . B /
 B B 16 . . . . . /
 21 . . . . 5 . . /
 6 . . . B 3 . . //
 23 . . . B 11 . . /
 30 . . . . 10 . . /
 B B 15 . . . . . /
 B 17 . . 7 . . B /
 27 . . . . . B B /
 12 . . 12 . . . . /
 16 . . B 7 . . . //


The second is one of my perturbations of the above, only this one is not so simple - quite the opposite.
Code: Select all
8 14 . . B 14 . . . /
 10 . . 30 . . . . /
 28 . . . . . B B /
 B 14 . . 4 . . B /
 B B 32 . . . . . /
 14 . . . . 16 . . /
 21 . . . B 8 . . //
 15 . . . B 12 . . /
 27 . . . . 8 . . /
 B B 34 . . . . . /
 B 8 . . 12 . . B /
 26 . . . . . B B /
 15 . . 15 . . . . /
 11 . . B 22 . . . //
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Difficulty ratings

Postby denis_berthier » Tue Jun 09, 2015 3:25 am

Mathimagics wrote:I'd be interested to know the W-ratings for these two small grids:

first : W0 (i.e. it requires only singles)
second : W7
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Kakuro Generator - Progress Report

Postby Mathimagics » Thu Sep 24, 2015 3:01 pm

Hi there!

I've been absent for quite a while from this thread.

First we diverted to Futoshiki generation/properties for quite a bit (!), which I think we've given the full treatment.

Then I took a break from coding/research for a while, during which time I kept myself supplied with Kakuro puzzles by simply tweaking (perturbing) known examples.

I have taken up the project once again, with the target of producing puzzles from scratch.

The first objective is a template (blank-grid) generator, which has now been achieved. I can produce templates of arbitrary size, with the following properties:

  • 3 symmetry options (none, 1=diagonal, 2=mirror)
  • max blank-cell run length (4-9)
  • density (% of blank cells)

The next stage is to generate a puzzle of arbitrary DD (degree of difficulty) from a given template ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

I've been here before!

Postby Mathimagics » Mon Sep 28, 2015 9:11 am

Mathimagics wrote:The next stage is to generate a puzzle of arbitrary DD (degree of difficulty) from a given template ...


And so it begins ... let me rephrase that! I'd like to be able to generate a puzzle of arbitrary difficulty, so long as it's reasonably well-formed!

Just as with Futoshiki, a well-formed puzzle is one with a US (unique solution). But for Kakuro the probability of a random Kakuro grid of even modest size having a US appears to be very small.

I have perturbation models in place that can generate a new US from a known US.

But for a non-US, that works only if the number of solutions is known, and is reasonably small. I'm trying to implement some of the ideas used in Futoshiki to narrow down the search, but it's a tricky problem ....
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

New Kakuro Generator is born

Postby Mathimagics » Thu Oct 15, 2015 3:48 am

After a painful delivery, my new generator came up with the goods! I am a happy vegemite! 8-)

For posterity's sake, here it is:



As for degree of difficulty, it comes (by design) in relatively easy, but I can easily turn it into something quite nasty ... or anywhere between.
Attachments
LastGenXR_USB.jpg
LastGenXR_USB.jpg (32.62 KiB) Viewed 220 times
Last edited by Mathimagics on Wed Oct 21, 2015 3:38 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Postby Pat » Wed Oct 21, 2015 2:35 pm

Mathimagics wrote:

    As for degree of difficulty,
    it comes (by design) in relatively easy---

relatively easy -- for you

should i try solving it?

could you provide a version without the answer?
User avatar
Pat
 
Posts: 3448
Joined: 18 July 2005

Re: New Kakuro Generator/Site

Postby Mathimagics » Wed Oct 21, 2015 3:38 pm

Done, see above! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

PreviousNext

Return to Kakuro