The New Sudoku Players' Forum

[yzfwsf]

Code: Select all

100900020040060008005001000020030009500700000006004800050090010000002007003000600


By default configuration, Hodoku uses brute force two times.
SE Rate:9.3 \ Hodoku Rate:46078 \ YZF_SUDOKU Rate:13894

[denis_berthier]

Code: Select all

100900020040060008005001000020030009500700000006004800050090010000002007003000600

By default configuration, Hodoku uses brute force two times.
SE Rate:9.3 \ Hodoku Rate:46078 \ YZF_SUDOKU Rate:13894

Hi yzfwsf,
This is a very interesting puzzle.
A puzzle with SER 9.3 is very unlikely to come out of a mere top-down generator.
--> My first question to you is therefore: how did you produce it? Did you search specifically for this level of difficulty?
I'm very interested if you have more puzzles at this level, which I called years ago the "grey zone".


I've just seen this puzzle that was proposed a week ago. As I also see that nobody has had any solution to propose (besides brute force), I've checked Hodoku, Sudoku Explainer and philsophy.net. None of these solvers can find a solution without brute force. I can't use your solver, as it runs only on Windows (AFAIK). I can't use XSudo either for the same reason.
--> My second question to you is thus: does your solver produce a solution without brute force? And if yes, can you copy it in this thread?


--> Now, dealing with the puzzle myself.
SER 9.3 is usually beyond T&E(1), so this was my first check. But NO. This puzzle is indeed in T&E(1). As a result, it must have a solution using only braids (thanks to my T&E vs braids theorem).

I have a pure pattern-based resolution path. I will give it later, after more people give this puzzle a try. It is worth it.

[yzfwsf]

A puzzle with SER 9.3 is very unlikely to come out of a mere top-down generator.
My first question to you is therefore: how did you produce it? Did you search specifically for this level of difficulty?

In fact, my solver uses the top-down method to generate puzzles, which can easily generate puzzles from SE9.0 to SE9.2. Those over SE9.3 are rare, but occasionally there are puzzles over SE10. The highest record is SE10.5. I produced more than 20, 000 of these grey puzzles.

I'm very interested if you have more puzzles at this level, which I called years ago the "grey zone".
My second question to you is thus: does your solver produce a solution without brute force? And if yes, can you copy it in this thread?

My solver uses 20 dynamic force chains to solve this puzzle, which should be similar to what you said about T & E (1)

grayZone.png (36.65 KiB) Viewed 1420 times

BTW:AFAIK , you can use wine to run my solver and xsudo

[denis_berthier]

I produced more than 20, 000 of these grey puzzles.

Could you post a few of them in the SER 9.1 - 9.3 range ?

My solver uses 20 dynamic force chains to solve this puzzle, which should be similar to what you said about T & E (1)

grayZone.png

I see; but it seems your solver doesn't output the details of each of these chains, in particular their lengths. Or is there an option for this?

BTW:AFAIK , you can use wine to run my solver and xsudo

No, wine doesn't work with Catalina (the current last version of MacOS ).

[tarek]

In fact, my solver uses the top-down method to generate puzzles, which can easily generate puzzles from SE9.0 to SE9.2. Those over SE9.3 are rare, but occasionally there are puzzles over SE10. The highest record is SE10.5. I produced more than 20, 000 of these grey puzzles.

I find that hard to believe. My feeling is that your generator is not a (pseudo) random generator if it can achieve that. I’m telling you this from experience in attempting generating difficult puzzles in the past. Computers have gone much more powerful over the past 12 years though, so 1 in a trillion may not sound too out of reach nowadays.

Tarek

[denis_berthier]

In fact, my solver uses the top-down method to generate puzzles, which can easily generate puzzles from SE9.0 to SE9.2. Those over SE9.3 are rare, but occasionally there are puzzles over SE10. The highest record is SE10.5. I produced more than 20, 000 of these grey puzzles.

I find that hard to believe. My feeling is that your generator is not a (pseudo) random generator if it can achieve that. I’m telling you this from experience in attempting generating difficult puzzles in the past. Computers have gone much more powerful over the past 12 years though, so 1 in a trillion may not sound too out of reach nowadays.Tarek

That reminds me that, when we developed the controlled bias generator as a collaborative work in 2011 (more or less - I don't remember exactly), we compared several top-down and bottom-up generators. None of the top-down generators (let alone the bottom-up ones) was able to generate puzzles with so high SER. If SER 9.3 seems reachable, SER 10 seems to require some strong bias in the generator.

[yzfwsf]

Could you post a few of them in the SER 9.1 - 9.3 range ?

9.3.txt.7z

(30.12 KiB) Downloaded 133 times

I see; but it seems your solver doesn't output the details of each of these chains, in particular their lengths. Or is there an option for this?

My solver gives a detailed explanation of DFC in the text box at the bottom when you click on the DFC step in the solution path list

I find that hard to believe. My feeling is that your generator is not a (pseudo) random generator if it can achieve that. I’m telling you this from experience in attempting generating difficult puzzles in the past. Computers have gone much more powerful over the past 12 years though, so 1 in a trillion may not sound too out of reach nowadays.
Tarek

My puzzle generator is not based on pattern or neighborhood search, it is based on top-down method, but I first set the rule to dig holes, which is to make the maximum number of clues for each house up to 3

[tarek]

I find that hard to believe. My feeling is that your generator is not a (pseudo) random generator if it can achieve that. I’m telling you this from experience in attempting generating difficult puzzles in the past. Computers have gone much more powerful over the past 12 years though, so 1 in a trillion may not sound too out of reach nowadays.
Tarek

My puzzle generator is not based on pattern or neighborhood search, it is based on top-down method, but I first set the rule to dig holes, which is to make the maximum number of clues for each house up to 3

What does you generator do when it finds a valid puzzle which doesn't satisfy your difficulty criteria (in this case SE>9.2)? Does it start from the beginning?

[denis_berthier]

Could you post a few of them in the SER 9.1 - 9.3 range ?

9.3.txt.7z

Thanks a lot. I'll try them.

[

I see; but it seems your solver doesn't output the details of each of these chains, in particular their lengths. Or is there an option for this?

My solver gives a detailed explanation of DFC in the text box at the bottom when you click on the DFC step in the solution path list

It can't include this explanation as a chain pattern in the final output?

I find that hard to believe. My feeling is that your generator is not a (pseudo) random generator if it can achieve that. I’m telling you this from experience in attempting generating difficult puzzles in the past. Computers have gone much more powerful over the past 12 years though, so 1 in a trillion may not sound too out of reach nowadays.
Tarek

My puzzle generator is not based on pattern or neighborhood search, it is based on top-down method, but I first set the rule to dig holes, which is to make the maximum number of clues for each house up to 3

This idea of "digging holes" definitely makes it different from a standard top-down generator. It's great that it allows to get harder puzzles than the standard generators. Probably much faster than neighbourhood search.
AFAIK, there's been no study on any correlation between maximum number of clues per house and difficulty.

[yzfwsf]

What does you generator do when it finds a valid puzzle which doesn't satisfy your difficulty criteria (in this case SE>9.2)? Does it start from the beginning?

For each valid solution grid, the puzzle generator will randomly dig holes to generate an valid puzzle and call skfr to rate it. If the required level is met, the puzzle will be output. When the requirement is not met and the generation amount reaches 1000, the random valid solution grid will be generated again, and the above steps will be repeated.The method of digging holes is as mentioned in the previous post.

[tarek]

AFAIK, there's been no study on any correlation between maximum number of clues per house and difficulty.

The 3 clue per house makes it more likely that boxes would display a "Diagonal pattern of clues": Which essentially can be mapped on an "X". Puzzles with boxes displaying these diagonal patterns are associated with higher SE difficulty rating.

tarek

[tarek]

What does you generator do when it finds a valid puzzle which doesn't satisfy your difficulty criteria (in this case SE>9.2)? Does it start from the beginning?

For each valid solution grid, the puzzle generator will randomly dig holes to generate an valid puzzle and call skfr to rate it. If the required level is met, the puzzle will be output. When the requirement is not met and the generation amount reaches 1000, the random valid solution grid will be generated again, and the above steps will be repeated.The method of digging holes is as mentioned in the previous post.

Thanks, what is not clear is what happens if you have an invalid puzzle before your generation amount reaches 1000! Do you cover 1 hole and dig another or do you cover all holes and start digging from the start?

tarek

[Mauriès Robert]

Hi Denis,

I have a pure pattern-based resolution path. I will give it later, after more people give this puzzle a try. It is worth it.

I have already made a resolution by hand, I hope to give it soon.
Robert

[yzfwsf]

Thanks, what is not clear is what happens if you have an invalid puzzle before your generation amount reaches 1000! Do you cover 1 hole and dig another or do you cover all holes and start digging from the start?

The process of digging a hole is the same as that of the conventional top-down method. Every time a hole is dug, a brute force solver will be called to verify whether there will be multiply solutions and ensure that the puzzles generated are valid. After the minimal puzzles are obtained, skfr will be called. That is to say, a solution grid can generate up to 1000 minimal puzzles.The goal of hole digging is to have only one clue for each minirow / minicol. My method is to make these positions which are supposed to keep the clues in advance try to dig holes at the last time.In the end, there will not be exactly one clue per minirow/minicol, but this is enough to easily produce a grey puzzle.
In the first stage, we try to dig holes in a random order at a predetermined unreserved position, and in the second stage, we try to dig holes in a random order at a predetermined reserved position


I corrected the code of my solver's built-in puzzle generator. Now I can guarantee to generate puzzles of SE9.1 ~ 9.3 in 1 minute, generally no more than 30 seconds.

[denis_berthier]

Could you post a few of them in the SER 9.1 - 9.3 range ?

9.3.txt.7z

Thanks again for this collection of puzzles.

I've now checked the 1272 puzzles in it :
- all of them have skfr 9.3
- their SER varies between 9.3 and 9.5
- all of them can be solved by gT&E=T&E(whips[1], 1)
- what's more surprising to me is, half of them (634) can be solved by mere T&E(1)

Until now, I hadn't seen many puzzles in this range of SER, probably not enough to make valid stats; but only a very small proportion of them were in T&E(1). So, there's something definitely new in this way of producing puzzles.

If you have similar collections for skfr = 9.2 and skfr = 9.4, I'm curious to see how the proportion of puzzles in T&E(1) varies.