Oh, yes, that's primarily what I'm using it for, to prune the search tree.
And yes, the row/columns with all zeroes have a v in them somewhere. I erase their domain bits when a cell is set.
Futoshiki Generation, properties
Fishy Futoshiki
by Mathimagics » Wed Jun 17, 2015 7:13 pm
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Futoshiki Generation, properties
by Mathimagics » Wed Jun 17, 2015 7:27 pm
By the way, I added bits (7, 1) and (2,6) myself! For the purpose of demonstration.
Clearly one has to be careful, sometimes a valid state might allow a little domain trimming, others will indicate backtracking required. Like this one:
Clearly one has to be careful, sometimes a valid state might allow a little domain trimming, others will indicate backtracking required. Like this one:
- Code: Select all
0 0 0 0 0 0 0
0 0 1 0 1 0 1
0 0 1 0 1 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
DFS solver
by Mathimagics » Thu Jun 18, 2015 11:57 am
Thanks again for providing your solver log info, it really helped me sort out my DFS solver:
I wonder now whether your report for 1A and 2A (which you rated as W5 and W10 respectively) might have swapped them around - the hint listing appears to be correct, but my DFS scores suggest that 2A is easier than 1A.
Perhaps you might provide your solver logs for those 3 items in any case, if that's not too much trouble?
By the way, I tested 1B with option "No fishing", which disabled the "Xwing" case detection, and to my surprise it only increased DFS by 200, and it ran slightly faster (25s).
Given the puzzle difficulty I expected a little more "oomph" from this fishing expedition, but the cost of checking seems to outweigh any benefit.
- 21:47:12 Puzzle id = ATK_H4062
21:47:12 Hints = 49, max chain len = 5
21:47:14 NS = 1, DFS = 7, et = 0.012528
21:47:14
21:47:20 Puzzle id = Reduction_1A
21:47:20 Hints = 38, max chain len = 9
21:47:22 NS = 1, DFS = 254, et = 0.262682
21:47:22
21:47:30 Puzzle id = Reduction_1B
21:47:30 Hints = 44, max chain len = 6
21:47:59 NS = 1, DFS = 24579, et = 26.114126
21:47:59
21:48:06 Puzzle id = Reduction_2A
21:48:06 Hints = 46, max chain len = 9
21:48:09 NS = 1, DFS = 26, et = 0.023361
I wonder now whether your report for 1A and 2A (which you rated as W5 and W10 respectively) might have swapped them around - the hint listing appears to be correct, but my DFS scores suggest that 2A is easier than 1A.
Perhaps you might provide your solver logs for those 3 items in any case, if that's not too much trouble?
By the way, I tested 1B with option "No fishing", which disabled the "Xwing" case detection, and to my surprise it only increased DFS by 200, and it ran slightly faster (25s).
Given the puzzle difficulty I expected a little more "oomph" from this fishing expedition, but the cost of checking seems to outweigh any benefit.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: DFS solver
by denis_berthier » Thu Jun 18, 2015 4:00 pm
Mathimagics wrote:I wonder now whether your report for 1A and 2A (which you rated as W5 and W10 respectively) might have swapped them around - the hint listing appears to be correct, but my DFS scores suggest that 2A is easier than 1A.
Perhaps you might provide your solver logs for those 3 items in any case, if that's not too much trouble?
OK, I put them with the solve command, so that you can check there's no error.
Hidden Text: Show
Hidden Text: Show
Mathimagics wrote:By the way, I tested 1B with option "No fishing", which disabled the "Xwing" case detection, and to my surprise it only increased DFS by 200, and it ran slightly faster (25s).
Given the puzzle difficulty I expected a little more "oomph" from this fishing expedition, but the cost of checking seems to outweigh any benefit.
It is well known in Sudoku that the fastest solvers are DFS that do not look for any pattern. As I said before "fast" and "pattern-based" are contradictory goals
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: Futoshiki Generation, properties
by denis_berthier » Thu Jun 18, 2015 4:43 pm
About your DFS rating, could you do the following experiment:
Take a puzzle (say 2A), apply each of the Futoshiki isomorphisms (horiz, verti, diag, 1<>9 symmetries) and see how it varies.
Take a puzzle (say 2A), apply each of the Futoshiki isomorphisms (horiz, verti, diag, 1<>9 symmetries) and see how it varies.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
DFS v Patterns
by Mathimagics » Thu Jun 18, 2015 4:49 pm
denis_berthier wrote:As I said before ...
Sorry, Denis, you must get the impression I don't really read your posts!
The reason I queried those results was simply that I was under the (possibly mistaken) impression that, no matter how it does it, your solver still reaches the same sort of conclusions that mine does, like "naked pair in r3", etc.
So I rather naively imagined that when my DFS solves H4062 and Reduction 2A with very little searching, having filled in most of the grid at the first level, then that would correlate more strongly with your solver's difficulty rating. Thus I thought 2A was "easier" than 1A.
I appreciate that it's a bit more subtle than that.
And the DFS is certainly anything but subtle! It hammers away at each level until every possible domain reduction has been squeezed out of the current state.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: DFS v Patterns
by denis_berthier » Thu Jun 18, 2015 6:33 pm
Mathimagics wrote:denis_berthier wrote:As I said before ...
Sorry, Denis, you must get the impression I don't really read your posts!
It's not what I meant. The important part of the sentence was the end : "fast" and "pattern-based" are contradictory goals. The more patterns you introduce, the slower the solver will be.
Mathimagics wrote: I was under the (possibly mistaken) impression that, no matter how it does it, your solver still reaches the same sort of conclusions that mine does, like "naked pair in r3", etc.
It is likely that the same elementary patterns are found by the two solvers at the start of the resolution paths, as we both proceed from simplest to most complex patterns.
But, after this initial phase, the methods are very different.
Just to mention two simple (related) points:
- is your rating stable under isos ?
- what happens when your solver finds a solution by chance, i.e. before proving that all the other options are impossible (normal DFS accepts it)?
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Futoshiki: Reduced Forms
by Mathimagics » Thu Jun 18, 2015 6:58 pm
Now that I've got my DFS going, I've discovered something new about maximal (wrt hints) forms.
Firstly, p(U) is probably much higher than I earlier indicated. The old solver had to abandon many tests because it couldn't cope, so failed to detect many cases which were in fact U, and easily found to be so by the new DFS.
I ran the random generator a while at N=9, and now got 8 hits for 600 generations, which gives an estimate of p(U) = 1.5%.
the second interesting discovery was just how "hard" a maximal form can still be:
I wonder what your solver makes of it. A word of warning (in case it makes a difference), the DFS was running in "Uniqueness Test" mode, so bailed out on hitting a second solution. There are in fact 372,377 solutions! It took about 25 minutes to count them all.
It could boil down to the length of the longest chain being a dominant factor (for DFS). This one has no chains > 5.
Firstly, p(U) is probably much higher than I earlier indicated. The old solver had to abandon many tests because it couldn't cope, so failed to detect many cases which were in fact U, and easily found to be so by the new DFS.
I ran the random generator a while at N=9, and now got 8 hits for 600 generations, which gives an estimate of p(U) = 1.5%.
the second interesting discovery was just how "hard" a maximal form can still be:
04:31:06 Puzzle id = Maximal_but_Hard2
04:31:06 Hints = 144, max chain len = 5
04:32:10 Solver abandon, NFS = 2, DFS = 23390, et = 47.492424
- Code: Select all
9
><>><><<><><<>><>><><<>><><<><><<<<><><><>><<>><<>>><><>><<<><><<><<><<>
><>><<<>><<><<><>><<><>>><><><<><><><><><>><<>><<<>><><<<<><><><<><><><>
I wonder what your solver makes of it. A word of warning (in case it makes a difference), the DFS was running in "Uniqueness Test" mode, so bailed out on hitting a second solution. There are in fact 372,377 solutions! It took about 25 minutes to count them all.
It could boil down to the length of the longest chain being a dominant factor (for DFS). This one has no chains > 5.
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
DFS behaviour
by Mathimagics » Thu Jun 18, 2015 7:01 pm
I seem to have answered your second question (without knowing you asked!)
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Isomorphisms in Futoshiki
by Mathimagics » Thu Jun 18, 2015 7:38 pm
By "1<>9 symmetry", do you mean mapping {1...9} to {9...1}?
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
DFS vs Symbol reflection
by Mathimagics » Thu Jun 18, 2015 8:13 pm
I ran the DFS on Reduction_1B, with all the hints reversed. It produced the expected solution (a reflection of the grid values) and with the same DFS visit count and time.
That suggests iso-stability, I think?
That suggests iso-stability, I think?
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
pU values
by blue » Thu Jun 18, 2015 9:31 pm
Mathimagics wrote:Firstly, p(U) is probably much higher than I earlier indicated. The old solver had to abandon many tests because it couldn't cope, so failed to detect many cases which were in fact U, and easily found to be so by the new DFS.
I ran the random generator a while at N=9, and now got 8 hits for 600 generations, which gives an estimate of p(U) = 1.5%.
I'm happy to see that
... I had been wondering if I had bugs on my end.I'm getting these results, combining two runs of 40000 grid samples:
- Code: Select all
4x4 : (24295+24252)/80000 = 60.68% +/- 0.34 (95% confidence)
5x5 : (20464+20509)/80000 = 51.22% +/- 0.35 (95% confidence)
6x6 : (10634+10645)/80000 = 26.60% +/- 0.31 (95% confidence)
7x7 : ( 4754+ 4870)/80000 = 12.03% +/- 0.22 (95% confidence)
8x8 : ( 1676+ 1612)/80000 = 4.11% +/- 0.14 (95% confidence)
9x9 : ( 428+ 419)/80000 = 1.06% +/- 0.07 (95% confidence)
For grids with at least one maximum length chain:
- Code: Select all
4x4 : (25885+25868)/80000 = 64.69% +/- 0.33 (95% confidence)
5x5 : (27471+27323)/80000 = 68.49% +/- 0.32 (95% confidence)
6x6 : (17583+17518)/80000 = 43.99% +/- 0.34 (95% confidence)
7x7 : (10746+10899)/80000 = 27.06% +/- 0.31 (95% confidence)
8x8 : ( 5651+ 5576)/80000 = 14.03% +/- 0.24 (95% confidence)
9x9 : ( 2192+ 2238)/80000 = 5.54% +/- 0.16 (95% confidence)
BTW: These statistics are highly sensitive to having an unbiased random LS generator.
For N=9 and a "quick and dirty" bottom up LS generator, I got 3.04%(+/- 0.19) as the estimate, instead of ~1.06%.
For the values above, I used an algorithm based on Pittenger's Markov chain process ... with (N*N) steps between each reported result.
The results for N=4,5,6,7, have been double checked (by now), using a complete enumeration, and for N=6 and N=7, a random sampling of the enumerated results.
- blue
- Posts: 1045
- Joined: 11 March 2013
pU estimating
by Mathimagics » Thu Jun 18, 2015 10:13 pm
blue wrote:I used an algorithm based on Pittenger's Markov chain process ..
Snap!
I also have some versions of Jacobson-Matthews lying round somewhere. They are both very good with, I believe as near as truly random LS generation as it gets.
Thanks for joining the conversation ... and sorry about the junk posts!
That's really good to know that you have similar results for p(U).
-
Mathimagics - 2017 Supporter
- Posts: 1926
- Joined: 27 May 2015
- Location: Canberra
Re: Futoshiki: Reduced Forms
by denis_berthier » Fri Jun 19, 2015 3:18 am
Mathimagics wrote:p(U) is probably much higher than I earlier indicated. [/i]
I ran the random generator a while at N=9, and now got 8 hits for 600 generations, which gives an estimate of p(U) = 1.5%.
Good news. It makes the whole generation process a reasonable one.
Mathimagics wrote:That's awfully tough, probably as tough as my reduced form 1B. Here's the specs for it:
- Code: Select all
9
><>><><<><><<>><>><><<>><><<><><<<<><><><>><<>><<>>><><>><<<><><<><<><<>
><>><<<>><<><<><>><<><>>><><><<><><><><><>><<>><<<>><><<<<><><><<><><><>
I wonder what your solver makes of it. 5
Being purely logic, it can only prove what's common to all the solutions, i.e. it can only assert or eliminate what's asserted or eliminated in all the solutions.
Of course, I could launch T&E, but it seems pointless here.
Hidden Text: Show
Mathimagics wrote:It could boil down to the length of the longest chain being a dominant factor (for DFS). This one has no chains > 5.
It is probably a factor, but I think there are many factors that make a puzzle hard or not. The relative places of the chains (their interactions) is important.
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
Re: Isomorphisms in Futoshiki
by denis_berthier » Fri Jun 19, 2015 3:20 am
Mathimagics wrote:By "1<>9 symmetry", do you mean mapping {1...9} to {9...1}?
yes, and reversing the <
- denis_berthier
- 2010 Supporter
- Posts: 4213
- Joined: 19 June 2007
- Location: Paris
