The New Sudoku Players' Forum

[m_b_metcalf]

Thanks for that. I've been adapting my samurai generator/solver to tackle tarek's nightmare puzzle, which it still doesn't solve. It solves this one in two iterations in 0.33s.

Mike

[tarek]

Even after 7 years and quicker more powerful machines, my algorithms (BFS and backtracking) are still struggling with these puzzles when minimising.

The matrix size becomes too big & i wonder if the way forward with these big puzzles is another way of constraint problem solving like SAT.

I didn't spend time investing in a SAT solver and therefore wouldn't know much about it. I have optimised many of my backtracking algorithms including DLX and still find it challenging to create a random minimal puzzle beyond 49x49. From what I have been reading ... SAT is the way forward (dukosu said it so many years ago ... I know!!!)

tarek

[creint]

Here is a Windmill WX with a single fish.
So in order to solve it (298 cells to solve), you need
- box-line reduction and/or pointing pairs
- naked/hidden pairs/triples
- X-Wing (only one small fish swimming around)

No you only need singles and locked singles to solve the one you posted.

[m_b_metcalf]

No you only need singles and locked singles to solve the one you posted.

Interesting. My program is still a work-in-progress but it needs more than that to solve it.

Still, it can now generate windmill-Xs; here's a first effort, the first is very hard (I believe), the second an easier version:

Code: Select all

......................4....................18.............................6......  TL
..5........8.....................8.......2.................................1..9..  TR
.................................................................................   M
...1..........5......8..............................................4..........5.  BL
.................7..........1.............8......4.23........4...2.........81....  BR
25 clues, minimal(?), all diagonals empty, central puzzle empty.


Code: Select all

......................4..........9.........18.............................6......  TL
..5........8.9...................8.......2.................................1..9..  TR
.................................................................................   M
...1..........5......8..............................................4.........15.  BL
.................7..........1........2....8......4.23........4...2.........81....  BR
Same with 29 clues, basic techniques.

Comments welcome.

Regards,

Mike

[Hajime]

Here is a Windmill WX with a single fish.
So in order to solve it (298 cells to solve), you need
- box-line reduction and/or pointing pairs
- naked/hidden pairs/triples
- X-Wing (only one small fish swimming around)

No you only need singles and locked singles to solve the one you posted.

Only 12 cells can be filled using basic methods.
The 13th cell already needs box <-> line reduction.
I think....

[Hajime]

... It solves this one in two iterations in 0.33s.

SiSeSuSo takes 20.0 seconds to solve it.
It takes about 18 minutes to generate it.
I had to make 15 attempts before a Fish turned up (although creint states otherwise).
So you can imagine, I had 15*18*60 seconds of fun.

[creint]

No you only need singles and locked singles to solve the one you posted.

Interesting. My program is still a work-in-progress but it needs more than that to solve it.

Still, it can now generate windmill-Xs; here's a first effort, the first is very hard (I believe), the second an easier version:

Your solver needs only a small fix for locked singles to find that those exclusions. When all candidates in 1 constraints are seeing a target cell not in that constraint, you can remove that candidate.

You first one is very hard but not minimal.
Because i still did not had a good bruteforce solving solver, so i implemented SAT (with sat4j). Well that one is even easier to implement for alldifferent constraint compared to a normal strategy. Its very fast too, restarting sat4j takes most of the time.
In around 7 seconds it checked the last 27 cells and found only 15,4 number 5 can be removed.

Only 12 cells can be filled using basic methods.
The 13th cell already needs box <-> line reduction.
I think....

Yes you are right with box-line reduction is just a term and you have probably implemented only that. In this case you can call it line-line reduction that you are missing, but i call the tactic locked singles. If there is a better name that summarize this i will use that.

[blue]

In around 7 seconds it checked the last 27 cells and found only 15,4 number 5 can be removed.

If by that, you mean the "r2c6=5" clue in the "BL" puzzle, then as a bug-check for me, would you provide two solutions to this puzzle:

Code: Select all

......................4....................18.............................6......  TL
...........8.....................8.......2.................................1..9..  TR
.................................................................................   M
...1.................8..............................................4..........5.  BL
.................7...............................4..3........4...2.........81....  BR

(It's Mike's first puzzle, with 5 clues removed, including the one that I mentioned).

Only 12 cells can be filled using basic methods.
The 13th cell already needs box <-> line reduction.
I think....

Yes you are right with box-line reduction is just a term and you have probably implemented only that. In this case you can call it line-line reduction that you are missing, but i call the tactic locked singles. If there is a better name that summarize this i will use that.

Please provide an example of a "locked singles" elimination.
It looks to me, like what Hajime needs, is "line-window" eliminations.

Line-box, line-window (including with diagonal lines), and box-window eliminations are possible -- "locked candidate" eliminations.

There's also a "line-line" option -- that's apparently not the same thing that you're talking about -- where parallel overlapping lines in different 9x9 sections, have all of the candidates for a digit in one line, constrained to the cells in the intersection of the two lines. In that case, candidates for that digit in the other line, and outside of the intersection, could be eliminated. For this kind of puzzle, though, it seems like that doesn't add anything that can't be gotten with simple line-box eliminations [ since the intersection of the two lines, is always a minirow in a box that's common to both 9x9 sections ].

[creint]

Blue, you are right, don't know exactly what went wrong that time.
Can remove 15,4:5
Can remove 6,11:5
Can remove 8,18:5
Can remove 11,16:1
Can remove 16,17:8
Can remove 14,18:4
Can remove 16,18:2
Can remove 17,19:4
Can remove 12,20:2
Can remove 14,21:1

Well this was what i meant: Common Peer Elimination
http://jcbonsai.free.fr/sudoku/JSudokuU ... nting_pair

[tarek]

Great effort from all,

When we are in non-vanilla sudoku or Gattai territory, The locked candidates term would include what blue mentioned.

Regarding digital aids for solving Gattai: If you decide to solve each grid individually & update all grids as you progress, then you may miss a trick or 2 because you may miss this Line-Line interaction that blue mentioned for example. That is why it is better to visualise these gattai as 1 big puzzle with some cells having more constraints than others.

You can design puzzles where techniques would require the use of the non-vanilla areas and/or traverse more than one sub-grid. You may want to rank these techniques as more difficult than vanilla-only or single-subgrid techniques (although essentially they are the same principle). JC has done that in Jsudoku!

gsf has mentioned that your progress in programming these puzzles should be solving (BF, Recursive, SAT, ... etc) then generating and finally rating (which is the tricky bit). Being able to rate puzzles would then allow you to tailor your puzzles to the needs of solvers!!!

For programming enthusiasts and players, the "doubledoku" which is 2 subgrids with a 4 nonet overlap is a good training ground for these techniques! adding another simple non-vanilla region (e.g. asterisk) to one of them then you'll have possibly the simplest complex canvass for your training/programming.

We have been fortunate to have freely available solver/generators for a big variety of gattai!

tarek

[enxio27]

We have been fortunate to have freely available solver/generators for a big variety of gattai!

Many solvers, and a number of creators, but few freely available gattai generators, and even fewer that can create symmetric puzzles on request. There are still some grid patterns and variants that are not accounted for among the freely available generators (although JSudoku comes close).

I'm extremely grateful for all of you who generate these awesome gattai for us, but I think about all of those (Ruud, Boerge, Jean-Christophe, etc.) who used to generate puzzles for us who have now disappeared into the ether, and I'm trying to prepare for the possibility that someday I may be left with only the puzzles I can generate with the software I have on my computer. I've dabbled with trying to learn enough programming to write my own gattai generator (or even to extend JSudoku, which was released under a Creative Commons license), but life gets in the way and I haven't made much progress.

[creint]

Simple generator would be very easy if you go with only SAT generating.
I can try to generate one for you if you give a template. Something like a new Hatman's blade sudoku would be easy.
My solver is still not public.

[tarek]

There are a few tricks that would make generating puzzles (even symmetry easier).

The 1st issue which I’m sure SAT would help in is minimality but not many are bothered about that
The 2nd which is crucial is rating

Tarek

[m_b_metcalf]

The 1st issue which I’m sure SAT would help in is minimality but not many are bothered about that
Tarek

Well, I am. I find it very to publish a puzzle claiming that it's minimal when it isn't. I'm slowly working on doing this better for Windmill X, but as training I've gone back to X-samurai and established that this puzzle had, at least, two redundant clues. I'm now planning a completely new approach in my code.
Mike

[tarek]

The 1st issue which I’m sure SAT would help in is minimality but not many are bothered about that
Tarek

Well, I am. I find it very to publish a puzzle claiming that it's minimal when it isn't

I am like you on that one Mike. I try for symmetrically minimal if I can't do Symmetrical & minimal

tarek