Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Fishy Futoshiki

Postby Mathimagics » Wed Jun 17, 2015 7:13 pm

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki Generation, properties

Postby 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:

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

DFS solver

Postby 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:


    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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: DFS solver

Postby 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
Code: Select all
(solve 9
"................................................................................."
(sub-string 1 72 "--------------->->---<<---<---<<-----------<---->----->--->-----<----<<-------<------>----->>------<<<<-<<-->-<-----<-<----->>------><->->-<<<->")
(sub-string 73 144 "--------------->->---<<---<---<<-----------<---->----->--->-----<----<<-------<------>----->>------<<<<-<<-->-<-----<-<----->>------><->->-<<<->"))
***********************************************************************************************
***  FutoRules 2.0.s based on CSP-Rules 2.0.s, config = W+S
***  using CLIPS 6.30-r286
***********************************************************************************************
asc[1]: r9c9<r8c9 ==> r9c9 ≠ 9, r8c9 ≠ 1,
asc[2]: r3c9<r2c9<r2c8 ==> r3c9 ≠ 9, r3c9 ≠ 8, r2c9 ≠ 9, r2c9 ≠ 1, r2c8 ≠ 2, r2c8 ≠ 1,
asc[4]: r6c8<r7c8<r7c7<r6c7<r5c7 ==> r7c8 ≠ 9, r7c8 ≠ 8, r7c8 ≠ 7, r7c8 ≠ 1, r7c7 ≠ 9, r7c7 ≠ 8, r7c7 ≠ 2, r7c7 ≠ 1, r6c8 ≠ 9, r6c8 ≠ 8, r6c8 ≠ 7, r6c8 ≠ 6, r6c7 ≠ 9, r6c7 ≠ 3, r6c7 ≠ 2, r6c7 ≠ 1, r5c7 ≠ 4, r5c7 ≠ 3, r5c7 ≠ 2, r5c7 ≠ 1,
asc[1]: r6c8<r5c8 ==> r5c8 ≠ 1,
asc[1]: r7c6<r8c6 ==> r8c6 ≠ 1, r7c6 ≠ 9,
asc[1]: r5c6<r6c6 ==> r6c6 ≠ 1, r5c6 ≠ 9,
asc[1]: r7c5<r8c5 ==> r8c5 ≠ 1, r7c5 ≠ 9,
asc[2]: r1c5<r2c5<r3c5 ==> r3c5 ≠ 2, r3c5 ≠ 1, r2c5 ≠ 9, r2c5 ≠ 1, r1c5 ≠ 9, r1c5 ≠ 8,
asc[8]: r6c3<r5c3<r4c3<r4c4<r5c4<r6c4<r7c4<r8c4<r8c3 ==> r8c4 ≠ 9, r8c4 ≠ 7, r8c4 ≠ 6, r8c4 ≠ 5, r8c4 ≠ 4, r8c4 ≠ 3, r8c4 ≠ 2, r8c4 ≠ 1, r8c3 ≠ 8, r8c3 ≠ 7, r8c3 ≠ 6, r8c3 ≠ 5, r8c3 ≠ 4, r8c3 ≠ 3, r8c3 ≠ 2, r8c3 ≠ 1, r7c4 ≠ 9, r7c4 ≠ 8, r7c4 ≠ 6, r7c4 ≠ 5, r7c4 ≠ 4, r7c4 ≠ 3, r7c4 ≠ 2, r7c4 ≠ 1, r6c4 ≠ 9, r6c4 ≠ 8, r6c4 ≠ 7, r6c4 ≠ 5, r6c4 ≠ 4, r6c4 ≠ 3, r6c4 ≠ 2, r6c4 ≠ 1, r6c3 ≠ 9, r6c3 ≠ 8, r6c3 ≠ 7, r6c3 ≠ 6, r6c3 ≠ 5, r6c3 ≠ 4, r6c3 ≠ 3, r6c3 ≠ 2, r5c4 ≠ 9, r5c4 ≠ 8, r5c4 ≠ 7, r5c4 ≠ 6, r5c4 ≠ 4, r5c4 ≠ 3, r5c4 ≠ 2, r5c4 ≠ 1, r5c3 ≠ 9, r5c3 ≠ 8, r5c3 ≠ 7, r5c3 ≠ 6, r5c3 ≠ 5, r5c3 ≠ 4, r5c3 ≠ 3, r5c3 ≠ 1, r4c4 ≠ 9, r4c4 ≠ 8, r4c4 ≠ 7, r4c4 ≠ 6, r4c4 ≠ 5, r4c4 ≠ 3, r4c4 ≠ 2, r4c4 ≠ 1, r4c3 ≠ 9, r4c3 ≠ 8, r4c3 ≠ 7, r4c3 ≠ 6, r4c3 ≠ 5, r4c3 ≠ 4, r4c3 ≠ 2, r4c3 ≠ 1,
asc[7]: r6c3<r5c3<r4c3<r4c4<r5c4<r6c4<r6c5<r5c5 ==> r6c5 ≠ 9, r6c5 ≠ 6, r6c5 ≠ 5, r6c5 ≠ 4, r6c5 ≠ 3, r6c5 ≠ 2, r6c5 ≠ 1, r5c5 ≠ 7, r5c5 ≠ 6, r5c5 ≠ 5, r5c5 ≠ 4, r5c5 ≠ 3, r5c5 ≠ 2, r5c5 ≠ 1,
asc[1]: r7c2<r6c2 ==> r7c2 ≠ 9, r6c2 ≠ 1,
asc[3]: r9c6<r9c7<r9c8<r8c8 ==> r9c8 ≠ 9, r9c8 ≠ 2, r9c8 ≠ 1, r9c7 ≠ 9, r9c7 ≠ 8, r9c7 ≠ 1, r9c6 ≠ 9, r9c6 ≠ 8, r9c6 ≠ 7, r8c8 ≠ 3, r8c8 ≠ 2, r8c8 ≠ 1,
asc[1]: r9c1<r9c2 ==> r9c2 ≠ 1, r9c1 ≠ 9,
asc[2]: r7c2<r7c1<r8c1 ==> r8c1 ≠ 2, r8c1 ≠ 1, r7c2 ≠ 8, r7c1 ≠ 9, r7c1 ≠ 1,
asc[5]: r4c7<r4c8<r4c9<r5c9<r6c9<r7c9 ==> r7c9 ≠ 5, r7c9 ≠ 4, r7c9 ≠ 3, r7c9 ≠ 2, r7c9 ≠ 1, r6c9 ≠ 9, r6c9 ≠ 4, r6c9 ≠ 3, r6c9 ≠ 2, r6c9 ≠ 1, r5c9 ≠ 9, r5c9 ≠ 8, r5c9 ≠ 3, r5c9 ≠ 2, r5c9 ≠ 1, r4c9 ≠ 9, r4c9 ≠ 8, r4c9 ≠ 7, r4c9 ≠ 2, r4c9 ≠ 1, r4c8 ≠ 9, r4c8 ≠ 8, r4c8 ≠ 7, r4c8 ≠ 6, r4c8 ≠ 1, r4c7 ≠ 9, r4c7 ≠ 8, r4c7 ≠ 7, r4c7 ≠ 6, r4c7 ≠ 5,
asc[2]: r3c6<r3c7<r3c8 ==> r3c8 ≠ 2, r3c8 ≠ 1, r3c7 ≠ 9, r3c7 ≠ 1, r3c6 ≠ 9, r3c6 ≠ 8,
asc[1]: r3c3<r3c2 ==> r3c3 ≠ 9, r3c2 ≠ 1,
naked-single ==> r8c4 = 8
naked-single ==> r8c3 = 9
naked-single ==> r7c4 = 7
naked-single ==> r6c4 = 6
naked-single ==> r6c3 = 1
naked-single ==> r5c4 = 5
naked-single ==> r5c3 = 2
naked-single ==> r4c4 = 4
naked-single ==> r4c3 = 3
hidden-single-in-a-row ==> r7c9 = 9
hidden-single-in-a-column ==> r1c8 = 1
str-asc[1]: r3c3<r3c2 ==> r3c2 ≠ 4
str-asc[1]: r3c3<r3c2 ==> r3c2 ≠ 3
str-asc[1]: r3c3<r3c2 ==> r3c2 ≠ 2
str-asc[2]: r4c9<r5c9<r6c9 ==> r6c9 ≠ 5
str-asc[2]: r4c9<r5c9<r6c9 ==> r5c9 ≠ 4
str-asc[1]: r7c1<r8c1 ==> r7c1 ≠ 8
str-asc[1]: r7c2<r7c1 ==> r7c2 ≠ 6
str-asc[1]: r9c8<r8c8 ==> r9c8 ≠ 8
str-asc[1]: r9c8<r8c8 ==> r9c8 ≠ 7
str-asc[2]: r9c6<r9c7<r9c8 ==> r9c7 ≠ 7
str-asc[2]: r9c6<r9c7<r9c8 ==> r9c7 ≠ 6
str-asc[2]: r9c6<r9c7<r9c8 ==> r9c6 ≠ 6
str-asc[2]: r9c6<r9c7<r9c8 ==> r9c6 ≠ 5
str-asc[2]: r1c5<r2c5<r3c5 ==> r3c5 ≠ 3
str-asc[2]: r1c5<r2c5<r3c5 ==> r2c5 ≠ 2
str-asc[1]: r7c5<r8c5 ==> r7c5 ≠ 8
str-asc[1]: r7c6<r8c6 ==> r7c6 ≠ 8
hidden-single-in-a-row ==> r7c3 = 8
str-asc[1]: r7c8<r7c7 ==> r7c8 ≠ 6
str-asc[1]: r6c8<r7c8 ==> r7c8 ≠ 2
str-asc[1]: r6c8<r7c8 ==> r6c8 ≠ 5
str-asc[1]: r7c8<r7c7 ==> r7c7 ≠ 3
str-asc[1]: r7c7<r6c7 ==> r6c7 ≠ 4
str-asc[1]: r9c9<r8c9 ==> r9c9 ≠ 8
str-asc[1]: r9c9<r8c9 ==> r9c9 ≠ 7
613 candidates, 3069 csp-links and 4621 links. Density = 2.4635085137916%
naked-pairs-in-a-row: r6{c5 c9}{n7 n8} ==> r6c7 ≠ 8
naked-pairs-in-a-row: r6{c5 c9}{n7 n8} ==> r6c7 ≠ 7
naked-single ==> r6c7 = 5
naked-single ==> r7c7 = 4
naked-single ==> r7c8 = 3
naked-single ==> r6c8 = 2
naked-single ==> r4c8 = 5
naked-single ==> r4c9 = 6
naked-single ==> r5c9 = 7
naked-single ==> r6c9 = 8
naked-single ==> r6c5 = 7
str-asc[1]: r7c5<r8c5 ==> r7c5 ≠ 6
str-asc[1]: r3c9<r2c9 ==> r3c9 ≠ 5
str-asc[1]: r9c9<r8c9 ==> r9c9 ≠ 5
str-asc[1]: r9c8<r8c8 ==> r8c8 ≠ 4
str-asc[1]: r9c6<r9c7 ==> r9c6 ≠ 4
str-asc[1]: r9c6<r9c7 ==> r9c6 ≠ 3
whip[2]: r9c6{n2 n1} - r9c1{n1 .} ==> r9c2 ≠ 2
whip[2]: r9c6{n2 n1} - r7c6{n1 .} ==> r8c6 ≠ 2
whip[2]: r3c5{n6 n9} - r5c5{n9 .} ==> r2c5 ≠ 8
str-asc[1]: r1c5<r2c5 ==> r1c5 ≠ 6
whip[3]: r9n8{c2 c5} - r9n5{c5 c3} - r9n7{c3 .} ==> r9c2 ≠ 4
whip[3]: r9c7{n3 n2} - r9c6{n2 n1} - r9c1{n1 .} ==> r9c2 ≠ 3
whip[3]: r7n6{c6 c1} - r8c1{n5 n7} - r8c8{n7 .} ==> r8c6 ≠ 6
whip[3]: r7n6{c1 c6} - r8c6{n5 n7} - r8c8{n7 .} ==> r8c1 ≠ 6
whip[3]: r7n6{c1 c6} - r8c6{n5 n7} - r8c1{n7 .} ==> r7c1 ≠ 5
whip[3]: r7n6{c6 c1} - r8c1{n5 n7} - r8c6{n7 .} ==> r7c6 ≠ 5
whip[5]: r9n7{c2 c3} - r9n5{c3 c5} - r7n5{c5 c2} - r9c2{n5 n9} - r6c2{n9 .} ==> r9c1 ≠ 8
whip[5]: r7c1{n6 n2} - r7n5{c2 c5} - r8c5{n4 n6} - r8c8{n6 n7} - r8c6{n7 .} ==> r7c6 ≠ 6
hidden-single-in-a-row ==> r7c1 = 6
naked-single ==> r8c1 = 7
naked-single ==> r8c8 = 6
naked-single ==> r9c8 = 4
str-asc[1]: r7c5<r8c5 ==> r7c5 ≠ 5
hidden-single-in-a-row ==> r7c2 = 5
naked-single ==> r6c2 = 9
str-asc[1]: r5c6<r6c6 ==> r5c6 ≠ 8
str-asc[1]: r5c6<r6c6 ==> r5c6 ≠ 6
str-asc[1]: r5c6<r6c6 ==> r5c6 ≠ 4
naked-pairs-in-a-row: r5{c5 c8}{n8 n9} ==> r5c7 ≠ 9
naked-pairs-in-a-row: r5{c5 c8}{n8 n9} ==> r5c7 ≠ 8
naked-single ==> r5c7 = 6
naked-pairs-in-a-row: r5{c5 c8}{n8 n9} ==> r5c2 ≠ 8
naked-pairs-in-a-row: r5{c5 c8}{n8 n9} ==> r5c1 ≠ 9
naked-pairs-in-a-row: r5{c5 c8}{n8 n9} ==> r5c1 ≠ 8
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r5c6 ≠ 1
naked-single ==> r5c6 = 3
naked-single ==> r6c6 = 4
naked-single ==> r6c1 = 3
naked-single ==> r8c6 = 5
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r4c6 ≠ 2
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r4c6 ≠ 1
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r3c6 ≠ 2
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r3c6 ≠ 1
str-asc[1]: r3c6<r3c7 ==> r3c7 ≠ 3
str-asc[1]: r3c6<r3c7 ==> r3c7 ≠ 2
str-asc[1]: r3c7<r3c8 ==> r3c8 ≠ 7
hidden-single-in-a-column ==> r2c8 = 7
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r2c6 ≠ 2
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r2c6 ≠ 1
naked-pairs-in-a-column: c6{r7 r9}{n1 n2} ==> r1c6 ≠ 2
whip[2]: r3c7{n7 n8} - r3c2{n8 .} ==> r3c3 ≠ 7
naked-triplets-in-a-row: r3{c2 c6 c7}{n8 n6 n7} ==> r3c8 ≠ 8
naked-single ==> r3c8 = 9
naked-single ==> r5c8 = 8
naked-single ==> r5c5 = 9
hidden-single-in-a-row ==> r9c4 = 9
naked-triplets-in-a-row: r3{c2 c6 c7}{n8 n6 n7} ==> r3c5 ≠ 8
str-asc[1]: r2c5<r3c5 ==> r2c5 ≠ 6
str-asc[1]: r1c5<r2c5 ==> r1c5 ≠ 5
whip[2]: c5n6{r3 r9} - c5n5{r9 .} ==> r3c5 ≠ 4
naked-triplets-in-a-row: r3{c2 c6 c7}{n8 n6 n7} ==> r3c5 ≠ 6
naked-single ==> r3c5 = 5
hidden-single-in-a-column ==> r9c5 = 6
hidden-single-in-a-column ==> r4c5 = 8
hidden-single-in-a-column ==> r7c5 = 1
naked-single ==> r7c6 = 2
naked-single ==> r9c6 = 1
hidden-single-in-a-column ==> r3c9 = 1
hidden-single-in-a-column ==> r2c4 = 1
hidden-single-in-a-row ==> r3c4 = 3
naked-single ==> r1c4 = 2
hidden-single-in-a-column ==> r8c5 = 2
hidden-single-in-a-row ==> r3c1 = 2
naked-single ==> r9c1 = 5
naked-single ==> r9c3 = 7
naked-single ==> r9c2 = 8
hidden-single-in-a-row ==> r3c7 = 8
hidden-single-in-a-column ==> r1c7 = 7
hidden-single-in-a-column ==> r2c7 = 9
hidden-single-in-a-row ==> r3c3 = 4
str-asc[1]: r1c5<r2c5 ==> r2c5 ≠ 3
naked-single ==> r2c5 = 4
naked-single ==> r1c5 = 3
naked-single ==> r2c1 = 8
naked-single ==> r2c6 = 6
naked-single ==> r2c3 = 5
naked-single ==> r1c3 = 6
naked-single ==> r1c2 = 4
naked-single ==> r1c1 = 9
naked-single ==> r1c6 = 8
naked-single ==> r4c1 = 1
naked-single ==> r4c7 = 2
naked-single ==> r4c2 = 7
naked-single ==> r3c2 = 6
naked-single ==> r4c6 = 9
naked-single ==> r9c7 = 3
naked-single ==> r8c7 = 1
naked-single ==> r8c2 = 3
naked-single ==> r2c2 = 2
naked-single ==> r2c9 = 3
naked-single ==> r8c9 = 4
naked-single ==> r9c9 = 2
naked-single ==> r5c1 = 4
naked-single ==> r1c9 = 5
naked-single ==> r5c2 = 1
naked-single ==> r3c6 = 7
PUZZLE SOLVED. rating-type = W+S, MOST COMPLEX RULE = W[5]
946238715
825146973
264357891
173489256
412593687
391674528
658712439
739825164
587961342

Hidden Text: Show
Code: Select all
(solve 9
"................................................................................."
(sub-string 1 72 ">>>>->->-->->---->-----<--<-----<<--<>------>>><----->>--<->->---->-->-<-<<----><-<-->>>-<----------->-->----<<-<----------<---<----<-<----->---")
(sub-string 73 144 ">>>>->->-->->---->-----<--<-----<<--<>------>>><----->>--<->->---->-->-<-<<----><-<-->>>-<----------->-->----<<-<----------<---<----<-<----->---"))
***********************************************************************************************
***  FutoRules 2.0.s based on CSP-Rules 2.0.s, config = W+S
***  using CLIPS 6.30-r286
***********************************************************************************************
asc[1]: r7c8<r8c8 ==> r8c8 ≠ 1, r7c8 ≠ 9,
asc[3]: r5c8<r6c8<r6c9<r5c9 ==> r6c9 ≠ 9, r6c9 ≠ 2, r6c9 ≠ 1, r6c8 ≠ 9, r6c8 ≠ 8, r6c8 ≠ 1, r5c9 ≠ 3, r5c9 ≠ 2, r5c9 ≠ 1, r5c8 ≠ 9, r5c8 ≠ 8, r5c8 ≠ 7,
asc[7]: r5c8<r6c8<r6c7<r6c6<r6c5<r7c5<r8c5<r8c4 ==> r8c5 ≠ 9, r8c5 ≠ 6, r8c5 ≠ 5, r8c5 ≠ 4, r8c5 ≠ 3, r8c5 ≠ 2, r8c5 ≠ 1, r8c4 ≠ 7, r8c4 ≠ 6, r8c4 ≠ 5, r8c4 ≠ 4, r8c4 ≠ 3, r8c4 ≠ 2, r8c4 ≠ 1, r7c5 ≠ 9, r7c5 ≠ 8, r7c5 ≠ 5, r7c5 ≠ 4, r7c5 ≠ 3, r7c5 ≠ 2, r7c5 ≠ 1, r6c8 ≠ 7, r6c8 ≠ 6, r6c8 ≠ 5, r6c8 ≠ 4, r6c7 ≠ 9, r6c7 ≠ 8, r6c7 ≠ 7, r6c7 ≠ 6, r6c7 ≠ 5, r6c7 ≠ 2, r6c7 ≠ 1, r6c6 ≠ 9, r6c6 ≠ 8, r6c6 ≠ 7, r6c6 ≠ 6, r6c6 ≠ 3, r6c6 ≠ 2, r6c6 ≠ 1, r6c5 ≠ 9, r6c5 ≠ 8, r6c5 ≠ 7, r6c5 ≠ 4, r6c5 ≠ 3, r6c5 ≠ 2, r6c5 ≠ 1, r5c8 ≠ 6, r5c8 ≠ 5, r5c8 ≠ 4, r5c8 ≠ 3,
asc[2]: r8c7<r9c7<r9c6 ==> r9c7 ≠ 9, r9c7 ≠ 1, r9c6 ≠ 2, r9c6 ≠ 1, r8c7 ≠ 9, r8c7 ≠ 8,
asc[2]: r4c7<r5c7<r5c6 ==> r5c7 ≠ 9, r5c7 ≠ 1, r5c6 ≠ 2, r5c6 ≠ 1, r4c7 ≠ 9, r4c7 ≠ 8,
asc[1]: r7c4<r6c4 ==> r7c4 ≠ 9, r6c4 ≠ 1,
asc[3]: r9c2<r8c2<r7c2<r6c2 ==> r9c2 ≠ 9, r9c2 ≠ 8, r9c2 ≠ 7, r8c2 ≠ 9, r8c2 ≠ 8, r8c2 ≠ 1, r7c2 ≠ 9, r7c2 ≠ 2, r7c2 ≠ 1, r6c2 ≠ 3, r6c2 ≠ 2, r6c2 ≠ 1,
asc[2]: r9c2<r8c2<r8c3 ==> r8c3 ≠ 2, r8c3 ≠ 1,
asc[1]: r9c1<r8c1 ==> r9c1 ≠ 9, r8c1 ≠ 1,
asc[2]: r2c1<r3c1<r4c1 ==> r4c1 ≠ 2, r4c1 ≠ 1, r3c1 ≠ 9, r3c1 ≠ 1, r2c1 ≠ 9, r2c1 ≠ 8,
asc[1]: r9c8<r9c9 ==> r9c9 ≠ 1, r9c8 ≠ 9,
asc[1]: r9c4<r9c3 ==> r9c4 ≠ 9, r9c3 ≠ 1,
asc[1]: r8c7<r8c6 ==> r8c6 ≠ 1,
asc[2]: r7c8<r7c7<r7c6 ==> r7c8 ≠ 8, r7c7 ≠ 9, r7c7 ≠ 1, r7c6 ≠ 2, r7c6 ≠ 1,
asc[1]: r5c5<r5c6 ==> r5c5 ≠ 9,
asc[2]: r5c1<r5c2<r5c3 ==> r5c3 ≠ 2, r5c3 ≠ 1, r5c2 ≠ 9, r5c2 ≠ 1, r5c1 ≠ 9, r5c1 ≠ 8,
asc[1]: r4c3<r4c4 ==> r4c4 ≠ 1, r4c3 ≠ 9,
asc[1]: r3c8<r3c9 ==> r3c9 ≠ 1, r3c8 ≠ 9,
asc[4]: r2c4<r2c3<r3c3<r3c2<r4c2 ==> r4c2 ≠ 4, r4c2 ≠ 3, r4c2 ≠ 2, r4c2 ≠ 1, r3c3 ≠ 9, r3c3 ≠ 8, r3c3 ≠ 2, r3c3 ≠ 1, r3c2 ≠ 9, r3c2 ≠ 3, r3c2 ≠ 2, r3c2 ≠ 1, r2c4 ≠ 9, r2c4 ≠ 8, r2c4 ≠ 7, r2c4 ≠ 6, r2c3 ≠ 9, r2c3 ≠ 8, r2c3 ≠ 7, r2c3 ≠ 1,
asc[1]: r1c9<r1c8 ==> r1c9 ≠ 9, r1c8 ≠ 1,
asc[8]: r1c7<r1c6<r2c6<r2c5<r1c5<r1c4<r1c3<r1c2<r2c2 ==> r2c6 ≠ 9, r2c6 ≠ 8, r2c6 ≠ 7, r2c6 ≠ 6, r2c6 ≠ 5, r2c6 ≠ 4, r2c6 ≠ 2, r2c6 ≠ 1, r2c5 ≠ 9, r2c5 ≠ 8, r2c5 ≠ 7, r2c5 ≠ 6, r2c5 ≠ 5, r2c5 ≠ 3, r2c5 ≠ 2, r2c5 ≠ 1, r2c2 ≠ 8, r2c2 ≠ 7, r2c2 ≠ 6, r2c2 ≠ 5, r2c2 ≠ 4, r2c2 ≠ 3, r2c2 ≠ 2, r2c2 ≠ 1, r1c7 ≠ 9, r1c7 ≠ 8, r1c7 ≠ 7, r1c7 ≠ 6, r1c7 ≠ 5, r1c7 ≠ 4, r1c7 ≠ 3, r1c7 ≠ 2, r1c6 ≠ 9, r1c6 ≠ 8, r1c6 ≠ 7, r1c6 ≠ 6, r1c6 ≠ 5, r1c6 ≠ 4, r1c6 ≠ 3, r1c6 ≠ 1, r1c5 ≠ 9, r1c5 ≠ 8, r1c5 ≠ 7, r1c5 ≠ 6, r1c5 ≠ 4, r1c5 ≠ 3, r1c5 ≠ 2, r1c5 ≠ 1, r1c4 ≠ 9, r1c4 ≠ 8, r1c4 ≠ 7, r1c4 ≠ 5, r1c4 ≠ 4, r1c4 ≠ 3, r1c4 ≠ 2, r1c4 ≠ 1, r1c3 ≠ 9, r1c3 ≠ 8, r1c3 ≠ 6, r1c3 ≠ 5, r1c3 ≠ 4, r1c3 ≠ 3, r1c3 ≠ 2, r1c3 ≠ 1, r1c2 ≠ 9, r1c2 ≠ 7, r1c2 ≠ 6, r1c2 ≠ 5, r1c2 ≠ 4, r1c2 ≠ 3, r1c2 ≠ 2, r1c2 ≠ 1,
asc[8]: r1c7<r1c6<r2c6<r2c5<r1c5<r1c4<r1c3<r1c2<r1c1 ==> r1c1 ≠ 8, r1c1 ≠ 7, r1c1 ≠ 6, r1c1 ≠ 5, r1c1 ≠ 4, r1c1 ≠ 3, r1c1 ≠ 2, r1c1 ≠ 1,
naked-single ==> r2c6 = 3
naked-single ==> r2c5 = 4
naked-single ==> r2c2 = 9
naked-single ==> r1c7 = 1
naked-single ==> r1c6 = 2
naked-single ==> r1c5 = 5
naked-single ==> r6c5 = 6
naked-single ==> r7c5 = 7
naked-single ==> r8c5 = 8
naked-single ==> r8c4 = 9
naked-single ==> r1c4 = 6
naked-single ==> r1c3 = 7
naked-single ==> r1c2 = 8
naked-single ==> r1c1 = 9
hidden-single-in-a-column ==> r9c2 = 1
hidden-single-in-a-row ==> r8c9 = 1
hidden-single-in-a-row ==> r6c3 = 9
hidden-single-in-a-row ==> r6c1 = 1
hidden-single-in-a-column ==> r4c8 = 9
hidden-single-in-a-column ==> r3c7 = 9
hidden-single-in-a-column ==> r9c5 = 9
str-asc[1]: r1c9<r1c8 ==> r1c9 ≠ 4
naked-single ==> r1c9 = 3
naked-single ==> r1c8 = 4
str-asc[1]: r3c2<r4c2 ==> r3c2 ≠ 7
str-asc[3]: r2c4<r2c3<r3c3<r3c2 ==> r3c3 ≠ 6
str-asc[3]: r2c4<r2c3<r3c3<r3c2 ==> r2c4 ≠ 5
str-asc[3]: r2c4<r2c3<r3c3<r3c2 ==> r2c3 ≠ 6
str-asc[3]: r2c4<r2c3<r3c3<r3c2 ==> r2c3 ≠ 5
naked-single ==> r2c3 = 2
naked-single ==> r2c4 = 1
str-asc[1]: r3c8<r3c9 ==> r3c8 ≠ 8
str-asc[1]: r4c3<r4c4 ==> r4c3 ≠ 8
str-asc[2]: r5c1<r5c2<r5c3 ==> r5c3 ≠ 3
str-asc[2]: r5c1<r5c2<r5c3 ==> r5c2 ≠ 2
hidden-single-in-a-column ==> r8c2 = 2
str-asc[2]: r5c1<r5c2<r5c3 ==> r5c1 ≠ 7
str-asc[1]: r8c7<r8c6 ==> r8c7 ≠ 7
str-asc[1]: r9c4<r9c3 ==> r9c4 ≠ 8
str-asc[1]: r9c8<r9c9 ==> r9c9 ≠ 2
str-asc[1]: r9c8<r9c9 ==> r9c8 ≠ 8
hidden-single-in-a-column ==> r2c8 = 8
str-asc[1]: r3c1<r4c1 ==> r3c1 ≠ 8
str-asc[1]: r2c1<r3c1 ==> r3c1 ≠ 5
str-asc[1]: r2c1<r3c1 ==> r3c1 ≠ 4
str-asc[1]: r2c1<r3c1 ==> r3c1 ≠ 3
str-asc[1]: r2c1<r3c1 ==> r3c1 ≠ 2
str-asc[1]: r2c1<r3c1 ==> r2c1 ≠ 7
str-asc[1]: r3c1<r4c1 ==> r4c1 ≠ 6
str-asc[1]: r3c1<r4c1 ==> r4c1 ≠ 5
str-asc[1]: r3c1<r4c1 ==> r4c1 ≠ 4
str-asc[1]: r3c1<r4c1 ==> r4c1 ≠ 3
str-asc[1]: r9c1<r8c1 ==> r9c1 ≠ 8
str-asc[1]: r9c1<r8c1 ==> r9c1 ≠ 7
str-asc[1]: r7c4<r6c4 ==> r7c4 ≠ 8
str-asc[1]: r7c4<r6c4 ==> r6c4 ≠ 2
hidden-single-in-a-row ==> r6c8 = 2
naked-single ==> r5c8 = 1
hidden-single-in-a-row ==> r7c3 = 1
str-asc[1]: r4c3<r4c4 ==> r4c4 ≠ 3
str-asc[1]: r4c3<r4c4 ==> r4c4 ≠ 2
str-asc[1]: r3c8<r3c9 ==> r3c9 ≠ 2
str-asc[1]: r7c8<r7c7 ==> r7c7 ≠ 3
str-asc[1]: r7c8<r7c7 ==> r7c7 ≠ 2
str-asc[1]: r7c7<r7c6 ==> r7c6 ≠ 4
str-asc[2]: r4c7<r5c7<r5c6 ==> r5c7 ≠ 2
str-asc[1]: r9c7<r9c6 ==> r9c7 ≠ 8
str-asc[1]: r8c7<r9c7 ==> r9c7 ≠ 3
str-asc[1]: r8c7<r9c7 ==> r9c7 ≠ 2
hidden-single-in-a-column ==> r4c7 = 2
hidden-single-in-a-column ==> r7c9 = 2
hidden-single-in-a-column ==> r5c9 = 9
hidden-single-in-a-column ==> r7c6 = 9
str-asc[1]: r5c7<r5c6 ==> r5c7 ≠ 8
hidden-single-in-a-column ==> r7c7 = 8
hidden-single-in-a-column ==> r4c1 = 8
str-asc[1]: r7c4<r6c4 ==> r6c4 ≠ 3
hidden-single-in-a-row ==> r6c7 = 3
str-asc[1]: r5c7<r5c6 ==> r5c6 ≠ 4
str-asc[1]: r8c7<r8c6 ==> r8c6 ≠ 4
str-asc[1]: r8c7<r9c7 ==> r9c7 ≠ 4
str-asc[1]: r9c7<r9c6 ==> r9c6 ≠ 5
str-asc[1]: r9c7<r9c6 ==> r9c6 ≠ 4
str-asc[1]: r7c8<r8c8 ==> r8c8 ≠ 3
473 candidates, 781 csp-links and 2490 links. Density = 2.23062314114738%
whip[2]: r8c1{n6 n7} - r3c1{n7 .} ==> r9c1 ≠ 6
whip[2]: r5c5{n3 n2} - r5c1{n2 .} ==> r5c2 ≠ 3
hidden-single-in-a-column ==> r7c2 = 3
str-asc[1]: r7c4<r6c4 ==> r6c4 ≠ 4
str-asc[1]: r7c8<r8c8 ==> r8c8 ≠ 5
str-asc[1]: r5c2<r5c3 ==> r5c3 ≠ 4
whip[2]: r8c6{n6 n7} - r8c8{n7 .} ==> r8c7 ≠ 6
whip[2]: c1n2{r9 r5} - c1n3{r5 .} ==> r9c1 ≠ 5
whip[2]: c1n2{r9 r5} - c1n3{r5 .} ==> r9c1 ≠ 4
whip[2]: r9c4{n7 n2} - r9c1{n2 .} ==> r9c3 ≠ 3
biv-chain[3]: r8c8{n7 n6} - r7n6{c8 c1} - r3c1{n6 n7} ==> r3c8 ≠ 7
biv-chain[3]: r8c8{n7 n6} - r7n6{c8 c1} - r3c1{n6 n7} ==> r8c1 ≠ 7
hidden-single-in-a-column ==> r3c1 = 7
biv-chain[4]: c1n2{r9 r5} - r5c5{n2 n3} - r4n3{c5 c3} - r8n3{c3 c1} ==> r9c1 ≠ 3
naked-single ==> r9c1 = 2
whip[6]: c4n2{r3 r5} - c4n3{r5 r9} - c8n3{r9 r3} - r3c3{n3 n4} - r9n4{c3 c9} - r9c8{n5 .} ==> r3c4 ≠ 5
whip[7]: c3n8{r5 r9} - c6n8{r9 r3} - r3n1{c6 c5} - r3n2{c5 c4} - c4n3{r3 r9} - r9n4{c4 c9} - r9c8{n5 .} ==> r5c4 ≠ 8
whip[7]: r7c4{n4 n5} - r4c4{n5 n7} - r9c4{n7 n3} - c8n3{r9 r3} - r3c3{n3 n5} - r3c2{n5 n6} - r4c2{n6 .} ==> r3c4 ≠ 4
whip[8]: c8n7{r8 r9} - r9c9{n6 n8} - c3n8{r9 r5} - c6n8{r5 r3} - r9c6{n8 n6} - r5c6{n6 n5} - c7n7{r5 r2} - c7n6{r2 .} ==> r8c6 ≠ 7
hidden-single-in-a-row ==> r8c8 = 7
whip[8]: r5c2{n7 n4} - r5c1{n6 n3} - r8n3{c1 c3} - r3c3{n3 n4} - r4c3{n4 n6} - r4c4{n5 n7} - r5c4{n7 n2} - r5c5{n2 .} ==> r5c3 ≠ 5
whip[9]: c7n4{r5 r8} - c1n4{r8 r7} - r5c1{n4 n3} - r5c5{n3 n2} - c4n2{r5 r3} - c4n3{r3 r9} - c4n4{r9 r4} - r4c3{n6 n3} - r8n3{c3 .} ==> r5c2 ≠ 4
whip[5]: r8c6{n6 n5} - r6c6{n5 n4} - c2n4{r6 r3} - r3c3{n4 n3} - r8n3{c3 .} ==> r8c1 ≠ 6
whip[4]: r9c3{n6 n8} - r9c6{n8 n6} - r8n6{c6 c3} - r5c3{n6 .} ==> r9c4 ≠ 7
whip[4]: r8n6{c6 c3} - r5c3{n6 n8} - r9n8{c3 c9} - r9n7{c9 .} ==> r9c6 ≠ 6
whip[5]: c2n4{r6 r3} - r3c3{n4 n3} - r4n3{c3 c5} - r4n1{c5 c6} - c6n4{r4 .} ==> r6c9 ≠ 4
whip[5]: r6c6{n5 n4} - c2n4{r6 r3} - r3c3{n4 n3} - r4n3{c3 c5} - r4n1{c5 .} ==> r4c6 ≠ 5
whip[6]: r4n1{c6 c5} - r3n1{c5 c6} - c6n4{r3 r6} - c2n4{r6 r3} - r3c3{n4 n3} - r4n3{c3 .} ==> r4c6 ≠ 7
whip[6]: r4n1{c6 c5} - r3n1{c5 c6} - c6n4{r3 r6} - c2n4{r6 r3} - r3c3{n4 n3} - r4n3{c3 .} ==> r4c6 ≠ 6
whip[3]: r4c3{n6 n3} - r4c5{n3 n1} - r4c6{n1 .} ==> r4c4 ≠ 4
biv-chain[5]: c4n8{r6 r3} - r3n2{c4 c5} - r3n1{c5 c6} - r4c6{n1 n4} - r6c6{n4 n5} ==> r6c4 ≠ 5
whip[6]: r3c8{n6 n3} - r3c3{n3 n4} - c2n4{r3 r6} - c6n4{r6 r4} - c9n4{r4 r9} - r9c8{n5 .} ==> r3c9 ≠ 5
whip[9]: r7c4{n4 n5} - r9c4{n5 n3} - c8n3{r9 r3} - c8n5{r3 r9} - r9n4{c9 c3} - r3c3{n4 n5} - r3c2{n4 n6} - r4c2{n6 n7} - r4c4{n7 .} ==> r5c4 ≠ 4
biv-chain[3]: c1n3{r8 r5} - r5n4{c1 c7} - r8c7{n4 n5} ==> r8c1 ≠ 5
whip[9]: c8n3{r9 r3} - c8n5{r3 r7} - r7c4{n5 n4} - r9n4{c4 c3} - r3c3{n4 n5} - r9n5{c3 c7} - r8n5{c7 c6} - r6c6{n5 n4} - c2n4{r6 .} ==> r9c8 ≠ 6
whip[5]: r8c7{n5 n4} - r5n4{c7 c1} - r7n4{c1 c4} - r9c4{n4 n3} - r9c8{n3 .} ==> r9c7 ≠ 5
whip[9]: r4c4{n7 n5} - r7c4{n5 n4} - r9c4{n4 n3} - r9c8{n3 n5} - r9n4{c9 c3} - r4c3{n4 n3} - r3c3{n3 n5} - r3c2{n4 n6} - r4n6{c2 .} ==> r4c9 ≠ 7
whip[9]: r4c4{n7 n5} - r7c4{n5 n4} - r9c4{n4 n3} - r9c8{n3 n5} - r9n4{c9 c3} - r4c3{n4 n3} - r8n3{c3 c1} - r5n3{c1 c5} - r5n2{c5 .} ==> r5c4 ≠ 7
whip[9]: r5n7{c7 c2} - c6n7{r5 r9} - r9c7{n7 n6} - r5c7{n6 n4} - r8c7{n4 n5} - r8c6{n5 n6} - c3n6{r8 r4} - c2n6{r4 r3} - r4c2{n5 .} ==> r5c6 ≠ 5
whip[3]: r5c2{n5 n7} - r5c3{n6 n8} - r5c6{n8 .} ==> r5c1 ≠ 6
whip[7]: r9c8{n5 n3} - r9c4{n3 n4} - r7n4{c4 c1} - r5n4{c1 c7} - r8c7{n4 n5} - r2n5{c7 c1} - c1n6{r2 .} ==> r9c9 ≠ 5
whip[10]: r9c4{n5 n3} - c8n3{r9 r3} - r3c3{n3 n5} - r3c2{n4 n6} - r4c2{n6 n7} - r4c4{n7 n5} - r4c3{n5 n3} - r8c3{n3 n6} - c6n6{r8 r5} - r5n7{c6 .} ==> r9c3 ≠ 4
biv-chain[2]: r9n4{c9 c4} - r9n3{c4 c8} ==> r9c8 ≠ 5
naked-single ==> r9c8 = 3
str-asc[1]: r3c8<r3c9 ==> r3c9 ≠ 4
naked-pairs-in-a-column: c4{r7 r9}{n4 n5} ==> r5c4 ≠ 5
naked-pairs-in-a-row: r5{c4 c5}{n2 n3} ==> r5c1 ≠ 3
hidden-single-in-a-column ==> r8c1 = 3
naked-pairs-in-a-column: c4{r7 r9}{n4 n5} ==> r4c4 ≠ 5
naked-single ==> r4c4 = 7
naked-single ==> r6c4 = 8
str-asc[2]: r3c3<r3c2<r4c2 ==> r3c3 ≠ 5
str-asc[2]: r3c3<r3c2<r4c2 ==> r3c2 ≠ 6
whip[4]: r4c2{n5 n6} - r4c9{n6 n4} - r9n4{c9 c4} - r9n5{c4 .} ==> r4c3 ≠ 5
biv-chain[3]: r4n5{c2 c9} - r6c9{n5 n7} - c2n7{r6 r5} ==> r5c2 ≠ 5
str-asc[1]: r5c2<r5c3 ==> r5c3 ≠ 6
naked-single ==> r5c3 = 8
str-asc[1]: r5c7<r5c6 ==> r5c7 ≠ 7
naked-pairs-in-a-row: r5{c2 c6}{n6 n7} ==> r5c7 ≠ 6
naked-pairs-in-a-column: c7{r5 r8}{n4 n5} ==> r2c7 ≠ 5
biv-chain[4]: r4n5{c9 c2} - c2n6{r4 r5} - c2n7{r5 r6} - r6c9{n7 n5} ==> r2c9 ≠ 5
hidden-single-in-a-row ==> r2c1 = 5
naked-single ==> r5c1 = 4
naked-single ==> r5c7 = 5
naked-single ==> r8c7 = 4
naked-single ==> r7c1 = 6
naked-single ==> r7c8 = 5
naked-single ==> r3c8 = 6
naked-single ==> r3c9 = 8
naked-single ==> r7c4 = 4
naked-single ==> r9c4 = 5
naked-single ==> r9c3 = 6
naked-single ==> r8c3 = 5
naked-single ==> r8c6 = 6
naked-single ==> r5c6 = 7
naked-single ==> r5c2 = 6
naked-single ==> r4c2 = 5
naked-single ==> r3c2 = 4
naked-single ==> r3c3 = 3
naked-single ==> r3c4 = 2
naked-single ==> r3c5 = 1
naked-single ==> r3c6 = 5
naked-single ==> r6c6 = 4
naked-single ==> r4c6 = 1
naked-single ==> r4c5 = 3
naked-single ==> r5c5 = 2
naked-single ==> r5c4 = 3
naked-single ==> r4c3 = 4
naked-single ==> r4c9 = 6
naked-single ==> r2c9 = 7
naked-single ==> r2c7 = 6
naked-single ==> r6c9 = 5
naked-single ==> r9c9 = 4
naked-single ==> r6c2 = 7
naked-single ==> r9c6 = 8
naked-single ==> r9c7 = 7
PUZZLE SOLVED. rating-type = W+S, MOST COMPLEX RULE = W[10]
987652143
592143687
743215968
854731296
468327519
179864325
631479852
325986471
216598734


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: 3966
Joined: 19 June 2007
Location: Paris

Re: Futoshiki Generation, properties

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 3966
Joined: 19 June 2007
Location: Paris

DFS v Patterns

Postby 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! 8-)

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: DFS v Patterns

Postby 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! 8-)

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: 3966
Joined: 19 June 2007
Location: Paris

Futoshiki: Reduced Forms

Postby 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:

    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
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. 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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

DFS behaviour

Postby Mathimagics » Thu Jun 18, 2015 7:01 pm

I seem to have answered your second question (without knowing you asked!) 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Isomorphisms in Futoshiki

Postby Mathimagics » Thu Jun 18, 2015 7:38 pm

By "1<>9 symmetry", do you mean mapping {1...9} to {9...1}?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

DFS vs Symbol reflection

Postby 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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

pU values

Postby 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: 975
Joined: 11 March 2013

pU estimating

Postby Mathimagics » Thu Jun 18, 2015 10:13 pm

blue wrote:I used an algorithm based on Pittenger's Markov chain process ..


Snap! 8-)

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).
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Futoshiki: Reduced Forms

Postby 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
Code: Select all
(solve 9
"................................................................................."
"><>><><<><><<>><>><><<>><><<><><<<<><><><>><<>><<>>><><>><<<><><<><<><<>"
"><>><<<>><<><<><>><<><>>><><><<><><><><><>><<>><<<>><><<<<><><><<><><><>")
***********************************************************************************************
***  FutoRules 2.0.s based on CSP-Rules 2.0.s, config = W+S
***  using CLIPS 6.30-r286
***********************************************************************************************
asc[1]: r9c9<r8c9 ==> r9c9 ≠ 9, r8c9 ≠ 1,
asc[1]: r7c9<r8c9 ==> r7c9 ≠ 9,
asc[1]: r7c9<r6c9 ==> r6c9 ≠ 1,
asc[1]: r5c9<r6c9 ==> r5c9 ≠ 9,
asc[1]: r5c9<r4c9 ==> r4c9 ≠ 1,
asc[1]: r3c9<r4c9 ==> r3c9 ≠ 9,
asc[1]: r3c9<r2c9 ==> r2c9 ≠ 1,
asc[1]: r8c8<r9c8 ==> r9c8 ≠ 1, r8c8 ≠ 9,
asc[1]: r8c8<r7c8 ==> r7c8 ≠ 1,
asc[1]: r6c8<r7c8 ==> r6c8 ≠ 9,
asc[1]: r6c8<r5c8 ==> r5c8 ≠ 1,
asc[1]: r4c8<r5c8 ==> r4c8 ≠ 9,
asc[2]: r4c8<r3c8<r3c7 ==> r4c8 ≠ 8, r3c8 ≠ 9, r3c8 ≠ 1, r3c7 ≠ 2, r3c7 ≠ 1,
asc[3]: r7c7<r8c7<r9c7<r9c8 ==> r9c8 ≠ 3, r9c8 ≠ 2, r9c7 ≠ 9, r9c7 ≠ 2, r9c7 ≠ 1, r8c7 ≠ 9, r8c7 ≠ 8, r8c7 ≠ 1, r7c7 ≠ 9, r7c7 ≠ 8, r7c7 ≠ 7,
asc[2]: r7c7<r6c7<r6c6 ==> r6c7 ≠ 9, r6c7 ≠ 1, r6c6 ≠ 2, r6c6 ≠ 1,
asc[2]: r5c7<r6c7<r6c6 ==> r5c7 ≠ 9, r5c7 ≠ 8,
asc[2]: r5c7<r4c7<r3c7 ==> r4c7 ≠ 9, r4c7 ≠ 1,
asc[2]: r1c7<r2c7<r3c7 ==> r2c7 ≠ 9, r2c7 ≠ 1, r1c7 ≠ 9, r1c7 ≠ 8,
asc[2]: r1c7<r2c7<r2c6 ==> r2c6 ≠ 2, r2c6 ≠ 1,
asc[3]: r8c6<r9c6<r9c7<r9c8 ==> r9c6 ≠ 9, r9c6 ≠ 8, r9c6 ≠ 1, r8c6 ≠ 9, r8c6 ≠ 8, r8c6 ≠ 7,
asc[3]: r8c6<r9c6<r9c5<r8c5 ==> r9c5 ≠ 9, r9c5 ≠ 2, r9c5 ≠ 1, r8c5 ≠ 3, r8c5 ≠ 2, r8c5 ≠ 1,
asc[2]: r8c6<r7c6<r6c6 ==> r7c6 ≠ 9, r7c6 ≠ 1,
asc[2]: r4c6<r5c6<r6c6 ==> r5c6 ≠ 9, r5c6 ≠ 1, r4c6 ≠ 9, r4c6 ≠ 8,
asc[2]: r4c6<r3c6<r2c6 ==> r3c6 ≠ 9, r3c6 ≠ 1,
asc[2]: r4c6<r3c6<r3c7 ==>
asc[1]: r7c5<r8c5 ==> r7c5 ≠ 9,
asc[2]: r7c5<r6c5<r6c6 ==> r7c5 ≠ 8, r6c5 ≠ 9, r6c5 ≠ 1,
asc[2]: r5c5<r6c5<r6c6 ==> r5c5 ≠ 9, r5c5 ≠ 8,
asc[1]: r5c5<r4c5 ==> r4c5 ≠ 1,
asc[1]: r3c5<r4c5 ==> r3c5 ≠ 9,
asc[2]: r3c5<r2c5<r2c6 ==> r3c5 ≠ 8, r2c5 ≠ 9, r2c5 ≠ 1,
asc[2]: r1c5<r2c5<r2c6 ==> r1c5 ≠ 9, r1c5 ≠ 8,
asc[3]: r6c4<r7c4<r8c4<r8c5 ==> r8c4 ≠ 9, r8c4 ≠ 2, r8c4 ≠ 1, r7c4 ≠ 9, r7c4 ≠ 8, r7c4 ≠ 1, r6c4 ≠ 9, r6c4 ≠ 8, r6c4 ≠ 7,
asc[3]: r6c4<r7c4<r7c3<r7c2 ==> r7c3 ≠ 9, r7c3 ≠ 2, r7c3 ≠ 1, r7c2 ≠ 3, r7c2 ≠ 2, r7c2 ≠ 1,
asc[1]: r6c4<r5c4 ==> r5c4 ≠ 1,
asc[1]: r2c4<r3c4 ==> r3c4 ≠ 1, r2c4 ≠ 9,
asc[2]: r2c4<r1c4<r1c3 ==> r2c4 ≠ 8, r1c4 ≠ 9, r1c4 ≠ 1, r1c3 ≠ 2, r1c3 ≠ 1,
asc[3]: r9c3<r8c3<r7c3<r7c2 ==> r9c3 ≠ 9, r9c3 ≠ 8, r9c3 ≠ 7, r8c3 ≠ 9, r8c3 ≠ 8, r8c3 ≠ 1,
asc[3]: r9c3<r8c3<r8c4<r8c5 ==>
asc[3]: r3c3<r4c3<r5c3<r5c4 ==> r5c4 ≠ 3, r5c4 ≠ 2, r5c3 ≠ 9, r5c3 ≠ 2, r5c3 ≠ 1, r4c3 ≠ 9, r4c3 ≠ 8, r4c3 ≠ 1, r3c3 ≠ 9, r3c3 ≠ 8, r3c3 ≠ 7,
asc[3]: r3c3<r4c3<r4c4<r5c4 ==> r4c4 ≠ 9, r4c4 ≠ 2, r4c4 ≠ 1,
asc[3]: r3c3<r4c3<r4c4<r3c4 ==> r3c4 ≠ 3, r3c4 ≠ 2,
asc[3]: r3c3<r4c3<r4c4<r4c5 ==> r4c5 ≠ 3, r4c5 ≠ 2,
asc[2]: r3c3<r4c3<r4c2 ==> r4c2 ≠ 2, r4c2 ≠ 1,
asc[2]: r3c3<r2c3<r1c3 ==> r2c3 ≠ 9, r2c3 ≠ 1,
asc[1]: r8c2<r9c2 ==> r9c2 ≠ 1, r8c2 ≠ 9,
asc[2]: r2c2<r3c2<r4c2 ==> r3c2 ≠ 9, r3c2 ≠ 1, r2c2 ≠ 9, r2c2 ≠ 8,
asc[2]: r2c2<r3c2<r3c1 ==> r3c1 ≠ 2, r3c1 ≠ 1,
asc[2]: r2c2<r1c2<r1c3 ==> r1c2 ≠ 9, r1c2 ≠ 1,
asc[2]: r2c2<r1c2<r1c1 ==> r1c1 ≠ 2, r1c1 ≠ 1,
asc[1]: r9c1<r8c1 ==> r9c1 ≠ 9, r8c1 ≠ 1,
asc[3]: r5c1<r6c1<r7c1<r8c1 ==> r8c1 ≠ 3, r8c1 ≠ 2, r7c1 ≠ 9, r7c1 ≠ 2, r7c1 ≠ 1, r6c1 ≠ 9, r6c1 ≠ 8, r6c1 ≠ 1, r5c1 ≠ 9, r5c1 ≠ 8, r5c1 ≠ 7,
asc[3]: r5c1<r6c1<r6c2<r7c2 ==> r6c2 ≠ 9, r6c2 ≠ 2, r6c2 ≠ 1,
asc[2]: r5c1<r4c1<r3c1 ==> r4c1 ≠ 9, r4c1 ≠ 1,
asc[3]: r9c3<r9c4<r8c4<r8c5 ==> r9c4 ≠ 9, r9c4 ≠ 8, r9c4 ≠ 1,
asc[3]: r8c8<r8c7<r9c7<r9c8 ==> r8c8 ≠ 8, r8c8 ≠ 7,
asc[3]: r8c2<r8c3<r7c3<r7c2 ==> r8c2 ≠ 8, r8c2 ≠ 7,
asc[3]: r7c5<r7c4<r8c4<r8c5 ==> r7c5 ≠ 7,
asc[3]: r7c5<r7c4<r7c3<r7c2 ==>
asc[2]: r6c8<r6c7<r6c6 ==> r6c8 ≠ 8,
asc[3]: r6c4<r6c3<r7c3<r7c2 ==> r6c3 ≠ 9, r6c3 ≠ 8, r6c3 ≠ 1,
asc[3]: r5c1<r5c2<r6c2<r7c2 ==> r5c2 ≠ 9, r5c2 ≠ 8, r5c2 ≠ 1,
asc[2]: r3c9<r3c8<r3c7 ==> r3c9 ≠ 8,
asc[2]: r2c2<r2c1<r3c1 ==> r2c1 ≠ 9, r2c1 ≠ 1,
asc[4]: r1c7<r1c8<r2c8<r3c8<r3c7 ==> r3c8 ≠ 3, r3c8 ≠ 2, r3c7 ≠ 4, r3c7 ≠ 3, r2c8 ≠ 9, r2c8 ≠ 8, r2c8 ≠ 2, r2c8 ≠ 1, r1c8 ≠ 9, r1c8 ≠ 8, r1c8 ≠ 7, r1c8 ≠ 1, r1c7 ≠ 7, r1c7 ≠ 6,
asc[3]: r1c7<r1c8<r2c8<r2c9 ==> r2c9 ≠ 3, r2c9 ≠ 2,
asc[4]: r1c7<r1c8<r2c8<r2c7<r3c7 ==> r2c7 ≠ 3, r2c7 ≠ 2,
asc[4]: r1c7<r1c8<r2c8<r2c7<r2c6 ==> r2c6 ≠ 4, r2c6 ≠ 3,
asc[3]: r1c7<r1c8<r1c9<r2c9 ==> r1c9 ≠ 9, r1c9 ≠ 2, r1c9 ≠ 1,
asc[2]: r1c7<r1c6<r2c6 ==> r1c6 ≠ 9, r1c6 ≠ 1,
hidden-single-in-a-column ==> r3c7 = 9
hidden-single-in-a-column ==> r5c4 = 9
hidden-single-in-a-column ==> r1c3 = 9
hidden-single-in-a-column ==> r8c1 = 9
hidden-single-in-a-column ==> r4c5 = 9
str-asc[1]: r2c1<r1c1 ==> r2c1 ≠ 8
str-asc[1]: r2c2<r2c1 ==> r2c2 ≠ 7
str-asc[1]: r3c2<r3c1 ==> r3c2 ≠ 8
str-asc[1]: r5c9<r5c8 ==> r5c9 ≠ 8
str-asc[1]: r8c4<r8c5 ==> r8c4 ≠ 8
str-asc[2]: r7c5<r7c4<r8c4 ==> r7c5 ≠ 6
str-asc[2]: r7c5<r7c4<r8c4 ==> r7c4 ≠ 7
str-asc[2]: r8c3<r8c4<r8c5 ==> r8c3 ≠ 7
str-asc[1]: r8c2<r8c3 ==> r8c2 ≠ 6
str-asc[1]: r9c5<r8c5 ==> r9c5 ≠ 8
str-asc[2]: r9c3<r9c4<r9c5 ==> r9c4 ≠ 7
str-asc[2]: r9c3<r9c4<r9c5 ==> r9c3 ≠ 6
str-asc[1]: r4c1<r4c2 ==> r4c1 ≠ 8
str-asc[1]: r1c2<r1c1 ==> r1c2 ≠ 8
str-asc[1]: r4c4<r3c4 ==> r4c4 ≠ 8
str-asc[2]: r3c3<r4c3<r4c4 ==> r4c3 ≠ 7
str-asc[2]: r3c3<r4c3<r4c4 ==> r3c3 ≠ 6
str-asc[1]: r6c4<r7c4 ==> r6c4 ≠ 6
str-asc[2]: r9c6<r9c5<r8c5 ==> r9c6 ≠ 7
str-asc[1]: r8c6<r9c6 ==> r8c6 ≠ 6
str-asc[1]: r7c9<r8c9 ==> r7c9 ≠ 8
str-asc[1]: r9c9<r8c9 ==> r9c9 ≠ 8
hill[2]: r7c9<r8c9>r9c9 ==> r8c9 ≠ 2,
hill[2]: r5c9<r6c9>r7c9 ==> r6c9 ≠ 2,
hill[2]: r3c9<r4c9>r5c9 ==> r4c9 ≠ 2,
hill[2]: r6c8<r7c8>r8c8 ==> r7c8 ≠ 2,
hill[2]: r4c8<r5c8>r6c8 ==> r5c8 ≠ 2,
hill[2]: r5c7<r6c7>r7c7 ==> r6c7 ≠ 2, str-asc[1]: r6c7<r6c6 ==> r6c6 ≠ 3
valley[3]: r3c7>r4c7>r5c7<r6c7 ==> r5c7 ≠ 7,
hill[4]: r4c6<r5c6<r6c6>r7c6>r8c6 ==> r6c6 ≠ 4,
valley[4]: r2c6>r3c6>r4c6<r5c6<r6c6 ==> r4c6 ≠ 7,
valley[4]: r2c6>r3c6>r4c6<r5c6<r6c6 ==> r4c6 ≠ 6,
hill[2]: r5c5<r6c5>r7c5 ==> r6c5 ≠ 2,
hill[2]: r1c5<r2c5>r3c5 ==> r2c5 ≠ 2,
hill[3]: r6c4<r7c4<r8c4>r9c4 ==> r8c4 ≠ 3, str-asc[1]: r8c4<r8c5 ==> r8c5 ≠ 4
hill[3]: r6c3<r7c3>r8c3>r9c3 ==> r7c3 ≠ 3, str-asc[1]: r7c3<r7c2 ==> r7c2 ≠ 4
hill[3]: r3c3<r4c3<r5c3>r6c3 ==> r5c3 ≠ 3,
hill[3]: r2c2<r3c2<r4c2>r5c2 ==> r4c2 ≠ 3,
valley[3]: r4c2>r5c2<r6c2<r7c2 ==> r5c2 ≠ 7, str-asc[1]: r5c1<r5c2 ==> r5c1 ≠ 6
hill[3]: r2c1<r3c1>r4c1>r5c1 ==> r3c1 ≠ 3,
valley[5]: r3c1>r4c1>r5c1<r6c1<r7c1<r8c1 ==> r5c1 ≠ 5,
hill[3]: r9c3<r9c4<r9c5>r9c6 ==> r9c5 ≠ 3,
hill[2]: r9c1<r9c2>r9c3 ==> r9c2 ≠ 2,
hill[2]: r8c6<r8c7>r8c8 ==> r8c7 ≠ 2, str-asc[1]: r8c7<r9c7 ==> r9c7 ≠ 3
str-asc[1]: r9c7<r9c8 ==> r9c8 ≠ 4
hill[2]: r7c5<r7c6>r7c7 ==> r7c6 ≠ 2,
valley[3]: r6c6>r6c7>r6c8<r6c9 ==> r6c8 ≠ 7,
hill[3]: r6c1<r6c2>r6c3>r6c4 ==> r6c2 ≠ 3,
hill[2]: r5c5<r5c6>r5c7 ==> r5c6 ≠ 2,
hill[2]: r4c6<r4c7>r4c8 ==> r4c7 ≠ 2,
valley[3]: r3c4>r3c5<r3c6<r3c7 ==> r3c5 ≠ 7,
valley[3]: r2c6>r2c7>r2c8<r2c9 ==> r2c8 ≠ 7, str-asc[2]: r1c7<r1c8<r2c8 ==> r1c8 ≠ 6
str-asc[2]: r1c7<r1c8<r2c8 ==> r1c7 ≠ 5
hill[2]: r2c2<r2c3>r2c4 ==> r2c3 ≠ 2,
valley[3]: r2c3>r2c4<r2c5<r2c6 ==> r2c4 ≠ 7,
hill[2]: r1c5<r1c6>r1c7 ==> r1c6 ≠ 2,
valley[3]: r1c3>r1c4>r1c5<r1c6 ==> r1c5 ≠ 7,
str-hill[3]: r2c5<r2c6>r2c7>r2c8 ==> r2c6 ≠ 5
str-valley[2]: r4c7>r4c8<r4c9 ==> r4c8 ≠ 7
str-valley[2]: r1c1>r2c1<r3c1 ==> r2c1 ≠ 7
str-asc[1]: r2c2<r2c1 ==> r2c2 ≠ 6
str-valley[2]: r5c3>r6c3<r7c3 ==> r6c3 ≠ 7
str-valley[3]: r6c7>r7c7<r8c7<r9c7 ==> r7c7 ≠ 6
696 candidates, 3251 csp-links and 9072 links. Density = 3.75093029025056%
whip[2]: r2n2{c2 c4} - r2n1{c4 .} ==> r2c2 ≠ 5
whip[2]: r2n2{c2 c4} - r2n1{c4 .} ==> r2c2 ≠ 4
whip[2]: r2n2{c2 c4} - r2n1{c4 .} ==> r2c2 ≠ 3
whip[3]: r2n9{c6 c9} - r2n8{c9 c3} - r2n7{c3 .} ==> r2c6 ≠ 6
whip[5]: r7c3{n8 n4} - r7c1{n4 n3} - r7c4{n3 n2} - r7c7{n2 n1} - r7c5{n1 .} ==> r7c2 ≠ 5
whip[6]: r7n9{c2 c8} - r7n8{c8 c6} - r7n7{c6 c9} - r8c9{n6 n8} - r6c9{n8 n9} - r6c6{n9 .} ==> r7c2 ≠ 6


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: 3966
Joined: 19 June 2007
Location: Paris

Re: Isomorphisms in Futoshiki

Postby 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: 3966
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Sudoku variants