The New Sudoku Players' Forum

[ronk]

That makes me wonder if I should ... change my role to just improving SE code regardless of this project

There are a couple things that I feel would considerably improve the Explainer GUI. To the Edit menu ...

• Add 'Copy pencilmarks' and 'Paste pencilmarks' (with ctrl-shift-C and ctrl-shift-V as possible hotkeys)
• Add 'Undo' and 'Redo' of solution path steps (with ctrl-Z and ctrl-shift-Z as possible hotkeys)

[lksudoku]

I'm really having problems trying to exactly match SE on even simple stuff like the following:

Code: Select all

023000000450000000000100060007800000000000200000000450000024000608000000000000307

 1789      2         3        |45679     456789    56789    |15789     14789     14589   
 4         5         169      |23679     36789     236789   |1789      123789    12389   
 789       789       9        |1         345789    235789   |5789      6         234589   
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 12359     13469     7        |8         134569    123569   |169       139       1369     
 13589     134689    14569    |345679    1345679   135679   |2         13789     13689   
 12389     13689     1269     |23679     13679     123679   |4         5         13689   
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 13579     1379      159      |35679     2         4        |15689     189       15689   
 6         13479     8        |3579      13579     13579    |159       1249      12459   
 1259      149       12459    |569       15689     15689    |3         12489     7       

  1)  1.2 r2c3 <= 6 hidden single in b1
  2)  1.2 r1c1 <= 1 hidden single in b1
  3)  1.2 r5c8 <= 7 hidden single in b6
  4)  2.0 r3c3 <= 9    direct hidden pair b1x78.<78>
  5)  2.5 r3c7 <= 5    direct hidden triple r3c69.<234>
  6)  2.6 r3c5 <> 7 locked candidates type 1 (pointing) b1/r3
  7)  2.6 r3c6 <> 7 locked candidates type 1 (pointing) b1/r3
  8)  2.6 r3c5 <> 8 locked candidates type 1 (pointing) b1/r3
  9)  2.6 r3c6 <> 8 locked candidates type 1 (pointing) b1/r3
 10)  2.6 r3c9 <> 8 locked candidates type 1 (pointing) b1/r3
 11)  2.6 r1c9 <> 8 locked candidates type 1 (pointing) b6/c9
 12)  2.6 r2c9 <> 8 locked candidates type 1 (pointing) b6/c9
 13)  2.6 r7c9 <> 8 locked candidates type 1 (pointing) b6/c9
 14)  2.6 r9c8 <> 2 locked candidates type 1 (pointing) b7/r9
 15)  2.6 r9c8 <> 8 locked candidates type 1 (pointing) b8/r9
 16)  2.6 r7c4 <> 6 locked candidates type 1 (pointing) b9/r7
 17)  7.0 r9c1 <> 5 xy-cycle[6]-chain [r9c1]=2=[r9c3]-2-[r6c3]=2=[r6c3]-1-[r7c3]=1=[r7c3]-5
 18)  7.1 r5c5 <> 4 xy-cycle[10]-chain [r5c3]=4=[r9c3]-4-[r9c3]=2=[r9c1]-2-[r4c1]=2=[r4c6]-2-[r3c6]=2=[r3c6]-3-[r3c5]=3=[r3c5]-4
 19)  7.1 r2c4 <> 3 xy-cycle[10]-chain [r2c4]=2=[r6c4]-2-[r6c3]=2=[r9c3]-2-[r9c3]=4=[r5c3]-4-[r5c4]=4=[r4c5]-4-[r3c5]=4=[r3c5]-3
 20)  7.1 r8c9 <> 2 xy-cycle[10]-chain [r8c8]=2=[r2c8]-2-[r2c4]=2=[r6c4]-2-[r6c3]=2=[r6c3]-1-[r7c3]=1=[r7c3]-5-[r7c9]=5=[r8c9]-5
 21)  1.2 r8c8 <= 2 hidden single in b9
 22)  3.8 r5c2 <> 4 swordfish r348\c259
 23)  3.8 r9c2 <> 4 swordfish r348\c259
 24)  3.8 r1c5 <> 4 swordfish r348\c259
 25)  3.8 r1c9 <> 4 swordfish r348\c259
 26)  2.3 r1c9 <= 9 naked single
 27)  2.6 r4c1 <> 9 locked candidates type 1 (pointing) b6/r4
 28)  2.6 r4c2 <> 9 locked candidates type 1 (pointing) b6/r4
 29)  2.6 r4c5 <> 9 locked candidates type 1 (pointing) b6/r4
 30)  2.6 r4c6 <> 9 locked candidates type 1 (pointing) b6/r4
 31)  7.0 r7c8 <> 9 xy-cycle[6]-chain [r7c8]=8=[r7c7]-8-[r7c7]=6=[r4c7]-6-[r4c7]=9=[r4c8]-9
 32)  7.0 r7c9 <> 1 xy-cycle[8]-chain [r7c8]=1=[r7c8]-8-[r1c8]=8=[r1c8]-4-[r9c8]=4=[r8c9]-4-[r8c9]=5=[r7c9]-5
 33)  7.0 r8c2 <> 1 xy-cycle[6]-chain [r8c2]=4=[r8c9]-4-[r8c9]=5=[r7c9]-5-[r7c3]=5=[r7c3]-1
 34)  7.0 r8c2 <> 9 xy-cycle[8]-chain [r8c2]=4=[r8c9]-4-[r8c9]=5=[r7c9]-5-[r7c3]=5=[r7c3]-1-[r9c2]=1=[r9c2]-9
 35)  7.0 r5c3 <> 1 xy-cycle[8]-chain [r5c3]=4=[r9c3]-4-[r8c2]=4=[r8c9]-4-[r8c9]=5=[r7c9]-5-[r7c3]=5=[r7c3]-1
 36)  7.0 r8c9 <> 1 xy-cycle[6]-chain [r7c8]=1=[r7c8]-8-[r1c8]=8=[r1c8]-4-[r9c8]=4=[r8c9]-4
 37)  7.0 r4c2 <> 6 xy-cycle[8]-chain [r4c7]=6=[r7c7]-6-[r7c9]=6=[r7c9]-5-[r8c9]=5=[r8c9]-4-[r8c2]=4=[r4c2]-4
 38)  7.0 r2c8 <> 8 xy-cycle[8]-chain [r7c8]=8=[r7c7]-8-[r7c7]=6=[r4c7]-6-[r4c7]=9=[r4c8]-9-[r4c8]=3=[r2c8]-3
 39)  7.0 r9c3 <> 5 xy-cycle[8]-chain [r9c3]=4=[r9c8]-4-[r1c8]=4=[r1c8]-8-[r7c8]=8=[r7c8]-1-[r7c3]=1=[r7c3]-5
 40)  1.7 r8c9 <= 5 direct pointing b7/r7
 41)  1.2 r9c8 <= 4 hidden single in b9
 42)  1.2 r3c9 <= 4 hidden single in b3
 43)  1.2 r1c4 <= 4 hidden single in b2
 44)  1.2 r2c9 <= 2 hidden single in b3
 45)  1.2 r3c6 <= 2 hidden single in b2
 46)  1.2 r2c8 <= 3 hidden single in b3
 47)  1.2 r3c5 <= 3 hidden single in b2
 48)  1.2 r2c7 <= 1 hidden single in b3
 49)  1.2 r1c7 <= 7 hidden single in b3
 50)  1.0 r1c8 <= 8 full house in b3
 51)  1.2 r6c4 <= 2 hidden single in b5
 52)  1.2 r4c1 <= 2 hidden single in b4
 53)  1.2 r4c5 <= 4 hidden single in b5
 54)  1.2 r5c3 <= 4 hidden single in b4
 55)  1.2 r5c1 <= 5 hidden single in b4
 56)  1.2 r4c6 <= 5 hidden single in b5
 57)  1.2 r1c5 <= 5 hidden single in b2
 58)  1.0 r1c6 <= 6 full house in r1
 59)  1.2 r9c3 <= 2 hidden single in b7
 60)  1.2 r8c2 <= 4 hidden single in b7
 61)  1.2 r7c3 <= 5 hidden single in b7
 62)  1.0 r6c3 <= 1 full house in c3
 63)  1.2 r9c4 <= 5 hidden single in b8
 64)  1.2 r9c5 <= 6 hidden single in b8
 65)  1.2 r5c4 <= 6 hidden single in b5
 66)  1.2 r6c2 <= 6 hidden single in b4
 67)  1.2 r9c6 <= 8 hidden single in b8
 68)  1.2 r2c5 <= 8 hidden single in b2
 69)  1.2 r7c8 <= 1 hidden single in b9
 70)  1.0 r4c8 <= 9 full house in c8
 71)  1.2 r9c2 <= 1 hidden single in b7
 72)  1.0 r9c1 <= 9 full house in r9
 73)  1.2 r5c2 <= 9 hidden single in b4
 74)  1.2 r6c1 <= 8 hidden single in b4
 75)  1.0 r4c2 <= 3 full house in b4
 76)  1.2 r3c2 <= 8 hidden single in b1
 77)  1.0 r3c1 <= 7 full house in b1
 78)  1.0 r7c1 <= 3 full house in c1
 79)  1.0 r7c2 <= 7 full house in c2
 80)  1.2 r5c9 <= 8 hidden single in b6
 81)  1.2 r4c9 <= 1 hidden single in b6
 82)  1.0 r4c7 <= 6 full house in r4
 83)  1.0 r6c9 <= 3 full house in b6
 84)  1.0 r7c9 <= 6 full house in c9
 85)  1.2 r5c6 <= 3 hidden single in b5
 86)  1.0 r5c5 <= 1 full house in r5
 87)  1.2 r8c6 <= 1 hidden single in b8
 88)  1.2 r8c4 <= 3 hidden single in b8
 89)  1.2 r8c5 <= 7 hidden single in b8
 90)  1.0 r6c5 <= 9 full house in c5
 91)  1.0 r6c6 <= 7 full house in b5
 92)  1.0 r2c6 <= 9 full house in c6
 93)  1.0 r2c4 <= 7 full house in r2
 94)  1.0 r7c4 <= 9 full house in c4
 95)  1.0 r7c7 <= 8 full house in r7
 96)  1.0 r8c7 <= 9 full house in c7
.23......45..........1...6...78...........2........45.....24...6.8............3.7 1 7.1 1.2 1.2 161.5726ms


Run the same puzzle in SE and step until you hit the 7.3 bi-directional cycle (xy-cycle loop). Count the number of links - it's 12!!! I found several shorter/simpler standard discontinuous nice-loops (xy-cycle chain) length 10 which keeps my score to 7.1. Now, I'll admit that I'm having problems with the chain length score adjustments, but the length of a chain is pretty easy to count. Just another example of the SE anomalies that I'm tracking down...

The SE rate of a chain and loop is not a direct linear function of the number of links

In general, a chain has a +0.1 rate over a loop, and the length of the chain/loop adds another value, but that value is a logarithmic function related to the length so a length of 12 may add a value <= 0.1 more than a length of 10 thus the loop is chosen in your current case, if you view all hints, SE will probably find you shorter nice-loops, but you will find that they also rate 7.3 and not 7.1

[mjmogo]

I am new here, but as I am curious about this discussion of writing a program in C, I am curious what the current status of this project is?

I wrote a program in C a few years back, but only got as far as one that creates randomly generated boards, but never got to the point of adding in any of the tests for "levels" or "ratings". I had written the program from discussions with another programmer friend of mine, we both enjoyed doing sudoku, and with him being a professional programmer, I was interested in picking his brain for those of how such a program might be written.

The basic logic of the program was pretty much a "brute force" method of randomly filling in squares, then testing to see if the results were valid, and then repeating until the whole board was filled. If it ran into a situation where it was "stumped", it would back track to the point where all the squares effecting the boards valid results were erased, and then pick up again from that point. If after a number of attempts at that particular board failed, it erased the whole board, and started over again. I also wrote some functions that would randomly mask squares, and then output the starting layout to a file for testing with other sudoku validating programs. The results I got were not all that interesting, as many of the boards produced very simplistic sudoku starting layouts.

The main point of why I wanted to write this program was that I am interested in extending the generator to handle not only the traditional 3x3 board, but ones of higher order. I was able to get my program to generate board of up to 6x6 dimensions, but the generated boards took quite a while to "discover". I tried to run it using a 7x7 matrix, but it ran for about an hour before I decided to shut it down.
One thing that interested me in this discussion was how these board might be stored, and one of the things that I had done with my program was to interface it with "sqlite" to store these board in an SQL database. Not really sure if anyone else here has thought of doing that, but it is a very simple interface and "sqlite" is a free database to use. The only real issue would be designing the SQL database structure to be used for storing these board.

Anyway, I am curious to see what the state of this project is. If anyone is interested, I would be willing to share my program with those interested. As I don't have access to anything to put it up online, you can send me a private message, and I can forward the files to you. Please do be kind in critiquing it, as I only do this as a hobby, and I might not be quite up to "snuff" with how other people think.

Mike

PS... I have looked at Sudoku Explainer, and have given some thoughts to "translating" it into Lua. It is a quite elegant program, and I think it would be quite interesting to try something like that. The only thing about Lua is that it interfaces with standard C very well, and once the program is up and running, any of the functions that require longer run times can be translated into C without much trouble.

[champagne]

Hi Mike,

I guess Paul is working on its code.

On my side, I am interested, as a player in the pattern game, not only by a C or C++ version of Sudoku explainer, but by a program running much faster.

I am working for the time being on a change in my program (C++) to meet SE specifications keeping as much as possible of the current performance.

It's not so easy, and I am suffering in the area ER=6.5 to ER=7.0.

champagne

[mjmogo]

Thanks for the reply, Champagne... as I am still new here (only about 5 days now, if even that)... I have to admit that I really don't know what the "pattern game" is, but having read about it on this thread, it does sound like something that many people are interested. Could you provide a link to something that discusses what it is all about?

Thanks,

Mike

On Edit: I did try to search "pattern game" using the forum's search engine, but it said that the terms were too common to produce a result... not really sure why that would be...

[champagne]

I really don't know what the "pattern game" is, but having read about it on this thread, it does sound like something that many people are interested. Could you provide a link to something that discusses what it is all about?

The pattern game is played in the main chapter "interactive gave" you can find in the Board Index

The goal is to find puzzles having a given location of clues.
Sudoku Explainer is the referee to define if a puzzle can be submitted.

Lokk at the first page of the thread "pattern game" for more details

http://forum.enjoysudoku.com/patterns-game-t6290.html

champagne

[PIsaacson]

Mike,

I've taken various C++ modules that I've used in other solving engines and glued them together to produce something that emulates SE. Unfortunately, while the scores are close, they are not exactly the same. SudokuExplainer has various quirks/bugs that are difficult to introduce into my code, so it's questionable whether or not I'll ever precisely match SE scores. The Patterns Game participants are the ones that could benefit from a faster SE, but it would have to score exactly the same as SE, otherwise it would be worthless, or so I've been led to believe. Currently, my emulator scores exactly the same as SE through the forcing chains region (somewhere in the 7.0 - 8.0 area), but then starts deviating as it finds different solution paths/chains than SE.

I'm still working on an exact replication of the SE chaining code, but it's slow and will take months to complete. Even then, I'm not sure that my code will "exactly" reproduce the SE scores without a complete redesign to cache eliminations, and then sort/select them instead of my current apply-as-discovered solving approach. This seems to be one of the fundamental differences between a solving algorithm vs a scoring algorithm. I had hoped that the code that drives my chaining methods using an increasing depth-limited technique would emulate the caching and sorting approach of SE, but it doesn't, or at least not closely enough.

So I'm in a funk trying to work up the energy to do a boatload of design/coding, frustrated that this was supposed to be a "group effort" but no one volunteered to take charge, design it up front, and dole out coding tasks for others to do. LK has offered to take over my code to accomplish this, but I hate to dump the burden on him. Worse, my goal was to create a "new and improved" SE-like rating program using our latest state-of-the-art sudouk techniques, but I've conceded that the primary mission is to first produce a "C or C++ Explainer-like rating program" with the "-like" qualifier meaning one that scores exactly the same as SE.

Anyway, that's a summary of where my head and code is at right now. And again, if anyone wants the current code, just PM me with your e-mail and I'll send it to you.

Cheers,
Paul

[champagne]

may-be some remarks complementary to Paull's post.

I agree that, unless working full time on that topic, creating a clone of SE performing well can not be achieved quickly. As I'll be off from mid January to mid march, I do not see, on my side a first draft before may or june 2011, if no bad surprise comes in the highest part of the rating.

I would not overweigth the "bug issue". For me, there are bugs in SE each time a possibility of a lower rating is missed by SE. I don't have so many examples.

Reversely, a good clone must not produce higher ratings that SE. I do not intend to copy bugs in my program.

Generally speaking, I don't try to follow SE path.

I accept any eliminating having equal rating at the same moment and I do them in parallel,
I intend to stop the search as soon as I find an elimination with a rating below or equal to the highest ER found so far.

Normally, it should work.

champagne

[lksudoku]

I have looked into Paul's code, fixed some bugs in it and modified the scoring to match SE up to chains/loops,
In the same time, I have been working on SE to fix its bugs, so the matching was done with SE version 1.2.5.0

I compared all pattern game results until game 122 with rating less than 6.5 to the clone and they match (except one puzzle where one UR destroys another UR)

I suggest that Paul will publish the executable of the current clone, so that there will be some feedback, and I will know if I am heading the right direction

I looked into the x-chains/loops code and I think I can modify Paul's code to match it also, but as long as there is no feedback and no published version, I do not know if there is any point in the modification process

I think that the C/C++ code can be useful regardless of the pattern games, for everyone who is interested in a fast grading software, and my goal is creating a software library which can be SE compatible if chosen so (and by SE compatible I mean SE with all found bugs fixed)

If the binary executable of Paul's modified code will be published, I may start designing the chaining compatibility

[champagne]

I have looked into Paul's code, fixed some bugs in it and modified the scoring to match SE up to chains/loops,
In the same time, I have been working on SE to fix its bugs, so the matching was done with SE version 1.2.5.0

I compared all pattern game results until game 122 with rating less than 6.5 to the clone and they match (except one puzzle where one UR destroys another UR)

I suggest that Paul will publish the executable of the current clone, so that there will be some feedback, and I will know if I am heading the right direction

I looked into the x-chains/loops code and I think I can modify Paul's code to match it also, but as long as there is no feedback and no published version, I do not know if there is any point in the modification process

I think that the C/C++ code can be useful regardless of the pattern games, for everyone who is interested in a fast grading software, and my goal is creating a software library which can be SE compatible if chosen so (and by SE compatible I mean SE with all found bugs fixed)

If the binary executable of Paul's modified code will be published, I may start designing the chaining compatibility

I am interesting in getting that new version of SE.

up to 6.5, if I except some Bug4 not included in my program, All the rating done by my "clone" are below or equal to SE ratings using the pattern game sample file.

In the range 6.5/6.9 I have still a problem of Nice loop to manage, but it should be ok after that.

champagne

[ronk]

So I'm in a funk trying to work up the energy to do a boatload of design/coding, frustrated that this was supposed to be a "group effort" but no one volunteered to take charge, design it up front, and dole out coding tasks for others to do. LK has offered to take over my code to accomplish this, but I hate to dump the burden on him.

It shouldn't be too difficult to coordinate a project when there's only two people working on it. Are you and champagne now splitting the tasks ... or are you each still trying to do 100% of them?

[champagne]

It shouldn't be too difficult to coordinate a project when there's only two people working on it. Are you and champagne now splitting the tasks ... or are you each still trying to do 100% of them?

We are 3 at the moment, iksudoku is very active.

Paul and I have exchanged our code, but for the time being, each of us is trying to see what can be done out of the existing code on its side.

My opinion is that that step must exist and will bring at the end more creativity.

In due time, I don't expect any problem to see in both drafts what is better and to go to a final product.

champagne

[lksudoku]

We are 3 at the moment, iksudoku is very active.

Paul and I have exchanged our code, but for the time being, each of us is trying to see what can be done out of the existing code on its side.

My opinion is that that step must exist and will bring at the end more creativity.

In due time, I don't expect any problem to see in both drafts what is better and to go to a final product.

champagne

Since Paul was the only one willing to share his code, I modified Paul's code, and his sources are the only project files base I am considering

However, since Paul created the code base, I do not publish any executable or source

[champagne]

We are 3 at the moment, iksudoku is very active.

Paul and I have exchanged our code, but for the time being, each of us is trying to see what can be done out of the existing code on its side.

My opinion is that that step must exist and will bring at the end more creativity.

In due time, I don't expect any problem to see in both drafts what is better and to go to a final product.

champagne

Since Paul was the only one willing to share his code, I modified Paul's code, and his sources are the only project files base I am considering

However, since Paul created the code base, I do not publish any executable or source

It seems thare is some misunderstanding somewhere.
I sent my files to Paul's (up to BUGs analysis), i would have done the same to anybody willing to study it.

I first thought to open a thread to do it, but the lack of interest pushed me to delay that.

On the other way, I think Paul is far ahead of me in compréhension and drafting of the logic applied in the chains part of SE, so there is some logic that you are working on its code.

In that part, I have now a better idea on how to keep my tagging infrastructure, but I can't be sure before i have drafted at least up to the "dynamic chains".

I hope to stay with an improvement in performance somewhere between 1 to 10 and 1 to 100. The key point remains to see if ratings will match.

champagne

[lksudoku]

Now after I already started modifying Paul's code, it is simpler to remain with it

The thread for code idea can be useful, but owner permission should be granted first