The New Sudoku Players' Forum

[PIsaacson]

Danny,

My UR loop code does assemble the loop level by level, but it currently only processes even length chains (N or level odd since my arrays are base 0) that pass the SE validity checks. I have a separate remote_pair method, but unless it is activated in the sudoku.ini config file, it does not participate in scoring. I'm not even sure where it would "fit" in terms of a base score.

Activating it for the supplied PM shows the 2 remote pairs that I arbitrarily gave a base score of 4.6:

Code: Select all

058260041340105826612804905034021568165348297820056413473512689281600054596480102 puzzle 1

 79        5         8        |2         6         379      |37        4         1
 3         4         79       |1         79        5        |8         2         6
 6         1         2        |8         37        4        |9         37        5
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 79        3         4        |79        2         1        |5         6         8
 1         6         5        |3         4         8        |2         9         7
 8         2         79       |79        5         6        |4         1         3
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 4         7         3        |5         1         2        |6         8         9
 2         8         1        |6         379       379      |37        5         4
 5         9         6        |4         8         37       |1         37        2

  1)  4.6 r8c5 <> 37 remote pair[4]-chain r8c7 r1c7 r3c8 r3c5 <37>
  2)  4.6 r1c6 <> 37 remote pair[4]-chain r9c6 r9c8 r3c8 r1c7 <37>
  3)  1.5 r1c7 <= 3 hidden single in r1
  4)  1.5 r1c1 <= 7 hidden single in r1
  5)  1.5 r1c6 <= 9 hidden single in r1
  6)  1.5 r4c1 <= 9 hidden single in c1
  7)  1.5 r2c3 <= 9 hidden single in b1
  8)  1.5 r3c5 <= 3 hidden single in b2
  9)  1.5 r2c5 <= 7 hidden single in r2
 10)  1.5 r3c8 <= 7 hidden single in r3
 11)  1.5 r6c3 <= 7 hidden single in c3
 12)  1.5 r4c4 <= 7 hidden single in r4
 13)  1.5 r6c4 <= 9 hidden single in c4
 14)  1.5 r8c5 <= 9 hidden single in c5
 15)  1.5 r8c7 <= 7 hidden single in c7
 16)  1.5 r8c6 <= 3 hidden single in r8
 17)  1.5 r9c8 <= 3 hidden single in c8
 18)  1.5 r9c6 <= 7 hidden single in b8

058260041340105826612804905034021568165348297820056413473512689281600054596480102;4.6/4.6/4.6

Are you suggesting that we should consider discontinuous unique-rectangle or otherwise deadly pattern chains??? I'm not sure I'm following where you seem to be going with this. Could you offer some specific examples of what you're looking for out of UR loop algorithms???

Cheers,
Paul

[daj95376]

Danny,

My UR loop code does assemble the loop level by level, but it currently only processes even length chains (N or level odd since my arrays are base 0) that pass the SE validity checks.

Are you suggesting that we should consider discontinuous unique-rectangle or otherwise deadly pattern chains??? I'm not sure I'm following where you seem to be going with this. Could you offer some specific examples of what you're looking for out of UR loop algorithms???

My objective was to examine Champagne's 8 cells in light of the ur_loop_valid() routine you were kind enough to provide as C++ code. Using your example information and following the routine logic, I realized that the routine returned false after reaching cell r3c8 -- an odd cell in the chain. The remaining three cells in the chain were extraneous.

A little further digging led me to realize that r8c5 was the only poly-valued cell among the five cells examined. This led me to conclude r8c5<>37, and I wondered why there was no reference to SE reaching this same conclusion. In addition, I realized that I could get ur_loop_valid() to return false if I fed it 5-cell chains equivalent to a 4-cell Remote Pair plus an elimination cell.

What I didn't consider was that chains with even numbers of cells had to be created before calling ur_loop_valid() -- as indicated by yourself and ronk. This explained why the UL logic was unsuitable to emulate Remote Pair logic. My curiousity/objective was satisfied.

Regards, Danny

Note: If ur_loop_valid() was called every time you added a cell to the chain, then it would also be able to emulate all Remote Pair scenarios where two candidates are eliminated from a cell. _

[lksudoku]

Besides, a clone should clone, not redefine existing patterns.

I already "un cloned" the crazy "K" rule (lksudoku found a bug in my attempt to duplicate it) , and I don't try to copy found bugs in SE, but may be somebody will be better than me in the "pure cloning". As far as I can see, Paul gave up as well in an attempt to build a pure clone.

champagne

It is not likely that there will be a pure clone of the original SE version 1.2.1 with its inherent bugs

The question therefore becomes what is a SE bug that should not be cloned and what is not

Sure the "parity check" can be cloned, and if required I can easily add it to champagne's code, but given that the clone will not be a pure clone of SE version 1.2.1, it is required to determine
- what is a bug that should not be cloned and instead should be fixed in SE
- and what is a valid SE rating rule that the clone should adapt

Surely ronk would like a pure clone of SE version 1.2.1 for his own reasons

But when creating a new rating software, others may think that version 1.2.1 is not the best possible option, and this is where questions such as the "parity check" rule comes in mind

[champagne]

It is not likely that there will be a pure clone of the original SE version 1.2.1 with its inherent bugs

The question therefore becomes what is a SE bug that should not be cloned and what is not

Sure the "parity check" can be cloned, and if required I can easily add it to champagne's code, but given that the clone will not be a pure clone of SE version 1.2.1, it is required to determine
- what is a bug that should not be cloned and instead should be fixed in SE
- and what is a valid SE rating rule that the clone should adapt

Surely ronk would like a pure clone of SE version 1.2.1 for his own reasons

But when creating a new rating software, others may think that version 1.2.1 is not the best possible option, and this is where questions such as the "parity check" rule comes in mind

I am 100% in line with your comments.

Regarding the "0 solution UL" I agree that it will be very easy to include the filter (and it would speed up the process) but as I wrote, this is anecdotal.

I feel the code will require much more important changes and we will have to define in due time a process to avoid duplicated work (could be worst, with 2 guys doing exactly the contrary).

I am still working to deliver before my departure (early January) a code matching your "ffixed8 batch version" at least up to rating 7.0 and likely slightly above.

This could be the time for you to work freely on it during 2 months if you find any interest in doing so.

Next non matching puzzles in my sample file has a rating 6.7 and I have 3 more below 7.0, but I know I have still 2 processes that need a serious reshaping

champagne

[lksudoku]

What I didn't consider was that chains with even numbers of cells had to be created before calling ur_loop_valid() -- as indicated by yourself and ronk. This explained why the UL logic was unsuitable to emulate Remote Pair logic. My curiousity/objective was satisfied.

Regards, Danny

Note: If ur_loop_valid() was called every time you added a cell to the chain, then it would also be able to emulate all Remote Pair scenarios where two candidates are eliminated from a cell. _

In SE there is an equivalent function to the ur_loop_valid function, it is named "isValidLoop"

Code: Select all

    private boolean isValidLoop(Grid grid, List<Cell> loop) {
        HashSet<Grid.Region> visitedOdd = new HashSet<Grid.Region>();
        HashSet<Grid.Region> visitedEven = new HashSet<Grid.Region>();
        boolean isOdd = false;
        for (Cell cell : loop) {
            for (Class<? extends Grid.Region> regionType : grid.getRegionTypes()) {
                Grid.Region region = grid.getRegionAt(regionType, cell.getX(), cell.getY());
                if (isOdd) {
                    if (visitedOdd.contains(region))
                        return false;
                    else
                        visitedOdd.add(region);
                } else {
                    if (visitedEven.contains(region))
                        return false;
                    else
                        visitedEven.add(region);
                }
            }
            isOdd = !isOdd;
        }
        // All regions must have been visited once with each parity (or never)
        return visitedOdd.equals(visitedEven);
    }


In SE, this function is called for odd and even length loops, so the claim that SE does not check the validation of odd length loops is incorrect, and yes, this check in SE can identify Remote Pairs (if the loop has only one cell with extra values), however, SE does not recognize the Remote Pair technique

[daj95376]

In SE there is an equivalent function to the ur_loop_valid function, it is named "isValidLoop"

In SE, this function is called for odd and even length loops, so the claim that SE does not check the validation of odd length loops is incorrect, and yes, this check in SE can identify Remote Pairs (if the loop has only one cell with extra values), however, SE does not recognize the Remote Pair technique

Thanks lksudoku for the particulars on SE.

[PIsaacson]

Regarding calling valid checks with odd length chains:

It looks to me like SE uses checkForLoops to build an complete loop (cell 0 must match next) before the isValidLoop is called, which is exactly the same way that I handle it. Plus, I don't see how an odd length loop can pass the test requiring equality for the sectors visited by the even vs odd cells. Calling this function while building the chain will surely fail at each odd level regardless, and at each even level until a loop is truly generated.

With that said, it is fairly easy to modify the UR loop code to include the exit criteria checking that I have in the remote_pair code such that RPs could be detected and processed. All I need to know is what base score I should use for these new discontinuous UL/RP chains???

Cheers,
Paul

[champagne]

Hi,

Happy new year to everybody.

Before I leave, I wanted to post the last available version of the code.

here is the file with the code solving puzzles in the range 1.0 to 7.4 (and most of 7.5).

Tests have been made using the last (private) delivery from lksudoku.

49 puzzles are still rated below the "SE fixed" rating, mostly, as far as I can see, due to problems in the Y loop field.

We enter now new areas. Multi chains should not be a problem, it's nearly standard for me.

Simulation of Nishio thru tagging is slightly more challenging.

The improvement ratio seems smaller in the area 7.0 7.4 than before (about i to 30), but I used the "batch" option created by lksudoku which is significantly faster than the classical SE run.

I also sent to Paul and Lior some big files coming from the pattern games to have the possibility to make the same "mass tests". I can send them to anybody providing and email link.

champagne

[Patrice]

Hello,

It seems that there is no more activity is this stream.

Do you think it is not possible to clone Serate in C or C++ ?

Some of you though to optimize Serate, using Java and an optimisation process ? are there people continuing this track ?

Serate bugs make the cloning process difficult because it not enough to implement Serate rules, you sould take in account implementation order of rules and grid or house traversal... and bugs in the algorithms... and some odd rating rules...

But for Patterns Game Serate stays as the "stone" in our garden that consumes most of our PC ressources !

I'm ready to work on one of the 2 following tracks :
- making a clone of Serate in C (or C++)
- optimizing Java Serate sources with techniques as profiling, modification of data structures, short cuts in algorithms...

I've already worked on the second track, with some results... up to scores 7.5... I've not worked at all on the nested loops...
I'm just looking at the way to follow the first track... necessary steps... working environment... reference puzzles database for test and so on

But it seems a huge work so if some people are interested this could be a second start for this stream.

Best regards
Patrice

[PIsaacson]

Patrice,

Here's my 2 cents, or: Everyone has an opinion, regardless of whether or not it's relevent:

Is it possible to clone serate in C/C++? Absolutely! "It's a mere matter of coding!" as one of my CS professors liked to quip.

A better question is, "Why would you want to?" If the answer is to improve the speed, but maintain the exact same algorithms, then converting to C/C++ will probably be a very large waste of time. I experimented with a strictly "blind" port (no algorithmic changes) using the current Java to C++ translators and posted the results in this thread some time ago. There was little improvement in run times and it validated what many of the latest Java benchmarks have indicated: The current Oracle/Sun Java x64 HotSpot VM can achieve execution times comparable to compiled C/C++ code in many cases. So if you're running a 32 bit OS and want to instantly double your serate speeds, install a 64 bit OS and run the latest x64 Java HotSpot VM.

An even better question is, "Why don't the pattern game players want something more current than serate?" Sudoku Explainer, and hence serate, lacks many of the current modern techniques. Some of these, such as SK loops, make mince-meat of high rated puzzles. I was more interested in creating something brand new with a framework allowing easy modification/addition of new techniques with a configurable scoring system. I offered my source code to anyone interested in participating, but there were only two takers: Champagne, who is attacking this based on his own code, and LKSudoku, who has released versions of SE/serate with various bug fixes and enhancements.

My current position: The active members of the patterns game need to reach a consensus, define their requirements and appoint a project lead. I am more than willing to contribute to such a project and offer my programming skills (I'll ignore the scoffs and laughter on that point). Not being a player, my hubris was in thinking that I understood the issues and intended end product.

Cheers and good luck with your own efforts,
Paul

[Patrice]

Hello,

I was more interested in creating something brand new with a framework allowing easy modification/addition of new techniques with a configurable scoring system.

Good idea... but as you say there were only 2 people interested : champagne and LKSudoku

"Why don't the pattern game players want something more current than serate?"

But it is not only for Patterns Game players... there are a lot of people interested in the Sudoku rating...
I'm quite new to Sudoku rating but it seems that Serate is the most used rating program.

Perhaps we could ask to more active Patterns Game player what they dream of (ronk, gsf, champagne, joel64, m_b_metcalf, BryanL...).

So if you're running a 32 bit OS and want to instantly double your serate speeds, install a 64 bit OS and run the latest x64 Java HotSpot VM.

I've already made this : using latest Java 64bits, Windows 7 64bits on an AMD PhenomII x4: there is a very good improve...

I've compared also writing good optimized Java to good C programs, we can have x2 factor in favor of C but no more (and sometimes it is less than 1.5), this is why I'm looking to both possibilities. I think that an optimized version of Serate in Java could take much less efforts.

Best regards
Patrice

[JasonLion]

The style of the code in SE is straightforward, with no particular attempt to optimize. It should be easy to get large speed improvements by making changes to the algorithm design. Making those changes, while also remaining 100% back compatible, is possible, but rather more complex. The only difference between C and Java that matters in this case is that many of the people here have a personal preference for C when writing highly optimized code, while SE was originally written in Java.

People who spend a lot of time optimizing code tend not to have any interest in losing any performance anywhere. No matter how good the most recent Java implementations have gotten, they aren't quite as fast as C code. Huge optimizations could still be made to the Java code, but the people who have experience doing that kind of optimizing appear to prefer to do it in C, I certainly do.

My take is that there are a number of people who would contribute if there was a framework to work in that allowed easier participation and was more in line with the original goals. Very few people are interested in starting from scratch, and the only code framework offered so far was both fairly difficult for an English speaker to follow/understand and had already made some fundamental design decisions that appeared to be inconsistent with some of the original goals of the project. I don't mean to belittle that work, it is very impressive. It just didn't seem to align with the interest we have available.

There is some question if we actually have enough interest and possible volunteers to ever make progress. The first step is finding a framework that invites participation. I'm not sure how easy that is to do, even if someone devoted a fair bit of time. There are a number of fundamental design decisions, like using floats vs ints for ratings values, using Java, C, or C++, matching SE ratings exactly or only approximately, that appear to be divisive. Forging enough of a consensus to gather together enough of the available interest to make a team that is large enough to have a viable project is, shall we say, challenging.

[champagne]

Let me bring some views following the last posts.

1) The Pattern Game has been a huge source of progress in the field of Sudoku and remains the most active area in that forum.
2) Sharing views on the strategy helped, (at least I hope so), newcomers to step in the game with remarkable results.
3) The process is speeding up in such a way that I have no idea about the results I’ll get in my next participation.
4) The rules settled for the game have been defined long ago and worked pretty well.
5) To-day, the bottleneck in the game is clearly the rating, but nobody seems prepared to change the referee. It could cause more damages that it would bring benefits.
6) I got good results using my solver as tool to focus on puzzles of value in the game, but my “rating” is very far from SE’s.
7) I am convinced that some of the specs of SE could be included in my solver and improve it’s overall efficiency.
8) SE specs are not explicit. The program has not been designed to be a rating program. The work done recently on the program shows many areas of inconsistency. (However, most of these “bugs” would not affect the rating of hardest puzzles. They are located up to now in the area of “easy moves”,)
9) I know nearly nothing about the JAVA language which does not make i t easy to decipher SE apparent specifications
10) I basically disagree on a rating based on the toughest move only, but SE gives a commonly agreed preliminary view on the puzzle hardness.
11) Many contributors in that forum are also waiting for a faster “commonly agreed rating” for hardest puzzles. Up to now, SE plays that role.


At the end

a) I am convinced that a ratio in the range 1/50 to 1/100 can be achieved with specs not too far from SE’s
b) I doubt more and more than the additional work to come to a perfect clone of SE is worth doing it.
c) I’ll continue to work on the target of a so called “se clone” using my solver global lay-out. I’ll share code with anybody willing to go in that way.
d) Considering my weakness in JAVA, a team work with players having skills in that language would speed up the construction. Lksudoku started collaboration, but I am not sure he has free time for the time being to do a lot.
e) I agree with some of the last remarks from Patrice. The key point is not that much to do it in “C” “C°°” or JAVA, this is at the end in a ratio 1:2. I work in C++ just because this is he language I know the best. Switching from C++ to JAVA would be possible at the end.


I’ll be back home in about a week. I’ll find back my work where it was.Next significant step should be an emulation of the Nishio process included in the SE program and activation of the multi-chains process.
For the following steps, I still have to decipher SE’s code..
I’ll likely try to use that partial version of the program in one of the next games

champagne

[champagne]

the only code framework offered so far was both fairly difficult for an English speaker to follow/understand and had already made some fundamental design decisions that appeared to be inconsistent with some of the original goals of the project.

Hi JasoLion,

Let me react to that sentence assuming it's refering to my attempt to clone SE and share my code.

I would be happy to follow the "best pratice" you are describing after. It's just that the ways things are going, I'll have finished my approximative cloning before any stone has been put in the future "best" design.

I even could die or loose my brain capabilities before a new lay-out is ready (I am close to 70).

I understand and share your remarks on the language problems with my code. This is a daily issue for non native English speakers in that forum. Reversely, any of the decisions I took can't be changed if a better process comes. It could be also that anybody just pick up ideas thru an overview of the code to buidl up a better design.

I do my best anyway to give to others the possibility to take benefit of my work.

champagne

[JasonLion]

I would be happy to follow the "best pratice" you are describing after. It's just that the ways things are going, I'll have finished my approximative cloning before any stone has been put in the future "best" design.

I completely understand. Some of the things that are important on a group project are very different from what you would do on a personal project, and there is no way of knowing if the group project will ever go anywhere.