GNOME Bugzilla – Bug 608907
Conflict Resolution is buggy
Last modified: 2010-04-11 20:19:25 UTC
Created attachment 152948 [details] Example Screenshot There is a problem with how conflicts are resolved. The problem has 2 consequences. 1) Sometimes a conflict will not be highlighted in red. 2) Sometimes the game won't dance, even though you've won. I use conflicts to resolve alternate pair matchings in the game so it is useful for me to do something like splat 9s everywhere they fit and narrow down the possible fit. The first consequence is only just annoying and can be worked around - by reentering the numbers until all of them turn red. The second problem is a bit more sinister - to deal with it, you have to just go around and reenter every number on the board till it says you win. To reproduce this problem 1) Enter a number that conflict in 2 cells of one box(A1 and A2 in the screenshot). The order in which you input them is important for the next step. 2) Create a conflict in an adjacent box with A2(the second number you entered in the first step). It will not be highlighted red. Currently, when you enter a number into the UI, SudokuGameDisplay.add_value() stores the number in __entries__[] and then ships the number off to the SudokuGrid class. When you add() the value, one of 2 outcomes is possible. If there are no conflicts then it will be added to the underlying grid. If there is a conflict then it will NOT be added to the underlying grid and it will raise a ConflictError. The problem is that the UI will then turn to the grid, which has no trace of the number that was just entered, for conflict resolution. Basically the UI has 2 numbers on it, but the underlying grid only has the original number that you're conflicting with in it. Conflicts with secondary conflicts are not reported. I have no idea how you want to handle it, but I made a patch that seems to work pretty solid. Essentially it consolidates the logic from SudokuGrid.find_conflicts() and SudokuGameDisplay.complain_conflicts() into a new method SudokuGameDisplay.highlight_conflicts(). The only substantial difference with this patch is that conflicts are resolved using SudokuGameDisplay.__entries__[] as opposed to the underlying grid(which doesn't have all of the numbers on the screen).
Created attachment 152949 [details] [review] My patch
yeah, this patch only fixes the highlighting problem. Unfortunately, the game winning problem(consequence 2 in my original post) is more sinister then I thought. My patch doesn't do anything with the underlying grid data, so any originally conflicting number(A2 in my screen-shot example) or any subsequent conflicts based on the originally entered number(A1 on my screen-shot) will still contain no value in the underlying grid when you delete the originally entered number(A1). I was thinking about it for a bit before making this post, because there's always a million ways to skin the cat. But maybe something simple like if (The entire grid is full && there are no conflicts && the game isn't won) commit all of the entries on the screen back to the grid again I'll see what I can do with it.
Alright, I had a chance to look into this a bit more today. I made a new patch that addresses both of the issues. This new patch has the same code as the last one for conflict resolution. It also has a new method SudokuGameDisplay.completed() which is used instead of InteractiveSudoku.check_for_completeness() for the game win test. The new method is more simple then I had originally thought. It doesn't do any commits to the underlying grid. It doesn't even query the underlying grid. It is based entirely what is on the screen. Turns out, that it is valid to say: if (there are no conflicts AND the entire grid is full) we have a winner
Created attachment 153781 [details] [review] New patch This patch fixes conflict resolution as well as the end game test.
The patch does resolve the two problems. But things are still not perfect (all because the underlying data is inaccurate): Test this: Input A1 (causing no conflict), input A2 (causing conflict with A1), delete A1. In this case, A2 exists on the screen, but is missing from the underlying grid. Possible glitches include: 1. The 'hints' are computed against the underlying data, so it's wrong. (Sudoku will give hints that are conflict with A2). 2. Game saving is wrong, same reason as 1. (A2 is not saved).
Thanks for the comments Zhang. You are correct. I completely agree that the game needs to account for the visual data more consistently and account for it in saving, loading, and hinting. I think I would start by storing the values from SudokuNumberGrid.__entries__ in the SudokuGrid class. From there, any adds or removes could use them to ensure that only unique values are used in the rows/cols/boxes/sets for proper hinting. I'm not as familiar with the saving/loading mechanism. I do know that it does not like to store conflicts. Ran into that one hacking around with it. Pretty sure it has something to do with this same issue though - that only one unique value is allowed in the underlying grid. It would be great if it could store these conflicts, because I like to use them and I have closed(saved) games before with conflicts up and when it comes back all my conflicts are gone. I'm not sure if this is the proper forum for design discussion. I really have no experience with the OS community. It is essentially the reason I stated that "I have no idea how you want to handle it" in my first post. I made the patches as small as I could. Thomas was kind enough to shoot me an email about reviewing this patch, and I think thats cool. I appreciate the fact that all modifications need to be reviewed in an open source project. I obviously have some ideas on how I would handle this particular problem. I don't know who's working on what and I could see a proper fix to the underlying data as a potentially large modification. I guess my real question is - is someone working on this? I can help.
Hey Jim, (In reply to comment #6) > It would be great if it could store these conflicts. Good idea. I think this is better than silently throwing the player's (conflicting) numbers away. The SudokuNumberGrid (UI) vs. SudokuGrid (underlying) design should be simpler. > I'm not sure if this is the proper forum for design discussion. It's good :). Contributors come up with patches, and talk around them, and apply it. > is someone working on this? I can help. I'm fairly sure no one is. At least nobody spoke out. It's great to see your contribution on this. Go, go, go.
Created attachment 157028 [details] [review] New conflict resolution patch Sorry it's taken me so long to get around to this. I did finally start developing a better solution for this a few days ago. It fixes my first 2 problems - where conflicts weren't highlighted properly and sometimes games wouldn't dance when you win. It also fixes the issues that Zhang brought up. You can save a game with conflicts and they load properly(complete and highlighted). Also, the hints have been modified to only work off of non-conflicting cells. The first thing you'll notice about the code is that all of the conflict resolution has been relegated to the InteractiveSudoku class. It seemed the most natural placement because - Conflict resolution is not strictly a UI thing. Its more of a data gathering/manipulation thing. - The UI uses InteractiveSudoku to interface to the grid. - It has a notion of what the original grid looked like(SudokuSolver.virgin) - As a feature, it kind of fit the class's description 'helping along a human who is in the midst of solving'. New add() and remove() methods were added to InteractiveGrid to extend the SudokuGrid ones. The ParallelDict class has been moved to sudoku.py(because it is indeed a handy class for tracking conflicts). Any calls using SudokuGameDisplay.__error_pairs__ were supplanted with its direct replacement InteractiveGrid.conflicts. From the caller's perspective, add() works very much the same as it used to but it also tracks the conflicts(InteractiveGrid.conflicts). Internally, the only added functionality is how it fidgets with the solution/hint arrays(SudokuGrid.rows/cols/boxes). Any cells in conflict will have their solution/hint removed...except for the cells that are part of the original problem(SudokuGrid.virgin). remove() is a bit more involved for the caller. When a cell that is in conflict is removed, all of the cells conflicting with it are checked to see if they are actually conflict-free because of the removal. These conflict-free cells have their solution/hints reinstated. They are also stored in a list - InteractiveSudoku.cleared_conflicts. The cleared_conflicts list is transient until the next call to remove() when it gets reinitialized. So, the caller is responsible for using the cleared_conflicts list to see what cells became conflict-free with the removal. That's the bulk of the patch really. These are the changes the rest of the code to integrate the new functionality. - Rewrote highlight_conflicts() to use the new InteractiveSudoku.conflicts list. - Rewrote remove_error_highlight() to use the new InteractiveSudoku.cleared_conflicts list. - Modified SudokuGrid.add() to always _set_() the value regardless of its conflict state - Modified SudokuGrid.remove() to be less strict about the presence of the values in the solution/hint arrays by using discard() instead of remove(). - Removed SudokuGrid.find_conflicts() - Catch ConflictErrors in SudokuGrid.populate_from_grid() - this one allows us to save/load games with conflicts :) - Modified SudokuGameDisplay.add_tracker() to properly highlight conflicts when a new game is loaded with conflicts in tracker cells That's pretty much it I think.
This is really, really awesome Jim. Nice patch, nice description of what you changed and why, good stuff. Only comment so far would be that the patch is not created with git format-patch. Could I convince you to do that? Zhang, what do you think?
Created attachment 157130 [details] [review] Overhaul of conflict resolution is this format ok?
Hey, This works nicely on a rough testing here. And the logic makes good sense to me. Only comment is about some aesthetic details. * 'git apply' tells that there are several trailing whitespaces. * There is no strict rule to line length, but it would be better if the comments are formatted according to PEP 8. Real code may be hard to re-format, so can be just left there. Sorry I'm becoming picky :) Otherwise this look good to me. Good work Jim!
Created attachment 157249 [details] [review] sudoku: PEP 8 code cleanup Picky is just fine. Its good especially with the newbs. Sorry its my first stab at Python and git...so I count as a newb and I appreciate any kind of guidance I can get. I took Thomas' pylintrc file posted in Bug 578903 and ran it on these changes. Yeah, there were quite a few lines too long. A couple of other things too - unnecessary semicolons and multiple statements on a line. This patch just fixes those little things up with the changes I made.
Hi Jim, Could you re-base this patch against current master? (making these two patches as one). I think you can use 'git reset --soft <commit>' to redo your local commits. Or use branches to merge them.
Yes, please allow me to fix this. I will take care of this today but I have a party to go to tonight. It will be done by Monday at the latest. I don't know exactly why I'm struggling with git so much. Its either the decentralized architecture or its content commit(as opposed to file commit) nature...or both. It is just very different from what I've used before(cvs, rcs, pvcs, svn, etc.). One other thing. While I was looking through the bug list, I realized that this problem is basically Bug 423478. I guess I didn't realize that was actually my problem when I originally posted this. Sorry about that.
Created attachment 157334 [details] [review] Consolidated patches for conflict resolution Alright - this patch is based on the latest source tree. It consolidates the 2 previous patches I made on this thread.
It's all right on my side. Thanks Jim!
Comment on attachment 157334 [details] [review] Consolidated patches for conflict resolution Committed with a few whitespace issues fixed. (No trailing whitespace allowed) http://git.gnome.org/browse/gnome-games/commit/?id=3da3d7dca0948d59f11c7d539179996ecb50a8a9 Great work!
Cool. Thanks.
*** Bug 423478 has been marked as a duplicate of this bug. ***
*** Bug 525685 has been marked as a duplicate of this bug. ***
Created attachment 158403 [details] [review] Fix SudokuSolver.fill_must_fills() for new conflict resolution code I found a some issues the solver was having with this new stuff. One issue causes puzzle generation and auto-fill(with a conflict on screen) to crash. It stems from the way that the numbers are stored in the underlying grid. SudokuSolver.fill_must_fills() uses _get_() on the underlying grid to figure out what a particular cell needs. Now that conflicts are stored, it may come across a value more than once - and del needs[val] was blowing up because of it. This patch adds a check for the value before calling del on the list. The other issue is the auto-fill really bugs out when there is a conflict on the grid. The best way I could figure to keep the most auto-filling functionality in place for the player is to basically skip auto filling a cell based on any conflict. To do this I moved the storage for the conflicts ParallelDict from InteractiveSudoku to the base class(SudokuGrid) so SudokuSolver could scope on it. Then I added a conflicting cell check in SudokuSolver.fill_must_fills().
Comment on attachment 158403 [details] [review] Fix SudokuSolver.fill_must_fills() for new conflict resolution code Really great work Jim. I actually ran into this issue when I was testing a patch to the sudoku maker. You just fixed the problem before I got time to look at it. That is really good timing :) Committed to master: http://git.gnome.org/browse/gnome-games/commit/?id=277f2dc91426066296abfa1c3fdf1952fcc0fb68
*** Bug 614664 has been marked as a duplicate of this bug. ***