Add a nonogram solver
Allow the user to check if there's a unique solution for a new pattern, and solve a game based on the information on the headers.
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- Federico Vera
- Definition:
- Approved
- Series goal:
- None
- Implementation:
-
Implemented
- Milestone target:
- None
- Started by
- Federico Vera
- Completed by
- Federico Vera
Related branches
Related bugs
Sprints
Whiteboard
The solution is found by overlapping all possible combinations and marking all those cells that are 'definitely full' and 'definitely empty', once this process is done in all the rows and columns, then the solutions that can't fit are removed from the 'possible solutions' list. This is repeated until no more changes are available, if the game is solved when the big loop finish then you know that there's only one logical solution.
The current version of the solver besides having several limitations, tends to throw OutOfMemoryError whenever the number of solutions is to big... the only way to solve this is rewriting it from scratch in a very different way, but at least it works for most cases.
--Update 01/09/2010--
I found a mayor memory leak in the way the solver computes solutions, the problem is that in order to solve it a lot of performance needs to be sacrificed. So for now the solver will stay as it is (there's a working draft of the optimized solver in the PictoSolverNew class).
As soon as I have some time I'll use it to radically change the way the solver works hoping against hope that it will become as cool as the other solvers...
--Update 05/12/2010--
This brute force method will stay for a while since I have little time to improve it. Nonetheless I'm working on a more human solver, I expect to have it working for version 1.0
