Bug 198878

Summary:	Grandfather: Solver falsely reports games as unwinnable
Product:	[Applications] kpat	Reporter:	Uli Bellgardt <uli_bellgardt>
Component:	general	Assignee:	Stephan Kulow <coolo>
Status:	RESOLVED FIXED
Severity:	normal	CC:	coates, kde-games-bugs-null
Priority:	NOR
Version First Reported In:	unspecified
Target Milestone:	---
Platform:	Ubuntu
OS:	Linux
Latest Commit:		Version Fixed/Implemented In:
Sentry Crash Report:

Description Uli Bellgardt 2009-07-04 09:42:22 UTC

Version:           Version 3.1 Using KDE 4.2.2 (KDE 4.2.2) (using KDE 4.2.2)
OS:                Linux
Installed from:    Ubuntu Packages

The solver of the Grandfather game often reports "Nope, this game cannot be won anymore" even if the game can be finished just by continued playing.

Grandfather game # 394291353 may serve as a reproducer. It is reported as "not winnable" from the very beginning, however after some playing, the status line shows "This line can still be won! Good luck to you". I  played this game until I reached the following situation, where I first time saw the message that the game can be solved (which was correct). 

<!DOCTYPE kpat>
<dealer number="394291353" moves="32" id="1" data="3" >
 <pile z="0" index="0" />
 <pile z="0" index="1" >
  <card z="1" faceup="1" value="1" suit="2" />
  <card z="2" faceup="1" value="2" suit="2" />
  <card z="3" faceup="1" value="3" suit="2" />
 </pile>
 <pile z="0" index="2" >
  <card z="1" faceup="1" value="1" suit="1" />
  <card z="2" faceup="1" value="2" suit="1" />
 </pile>
 <pile z="0" index="3" />
 <pile z="0" index="4" />
 <pile z="0" index="5" >
  <card z="1" faceup="1" value="12" suit="3" />
 </pile>
 <pile z="0" index="6" >
  <card z="1" faceup="0" value="12" suit="1" />
  <card z="2" faceup="0" value="12" suit="0" />
  <card z="3" faceup="1" value="13" suit="0" />
  <card z="4" faceup="1" value="11" suit="3" />
  <card z="5" faceup="1" value="6" suit="0" />
  <card z="6" faceup="1" value="9" suit="3" />
  <card z="7" faceup="1" value="13" suit="3" />
 </pile>
 <pile z="0" index="7" >
  <card z="1" faceup="0" value="13" suit="1" />
  <card z="2" faceup="0" value="11" suit="0" />
  <card z="3" faceup="0" value="5" suit="2" />
  <card z="4" faceup="0" value="6" suit="3" />
  <card z="5" faceup="1" value="5" suit="0" />
  <card z="6" faceup="1" value="9" suit="1" />
  <card z="7" faceup="1" value="1" suit="3" />
  <card z="8" faceup="1" value="7" suit="0" />
  <card z="9" faceup="1" value="6" suit="1" />
 </pile>
 <pile z="0" index="8" >
  <card z="1" faceup="0" value="2" suit="3" />
  <card z="2" faceup="0" value="10" suit="0" />
  <card z="3" faceup="0" value="2" suit="0" />
  <card z="4" faceup="0" value="8" suit="3" />
  <card z="5" faceup="0" value="10" suit="3" />
  <card z="6" faceup="0" value="8" suit="1" />
  <card z="7" faceup="1" value="4" suit="0" />
  <card z="8" faceup="1" value="10" suit="2" />
  <card z="9" faceup="1" value="12" suit="2" />
  <card z="10" faceup="1" value="10" suit="1" />
  <card z="11" faceup="1" value="5" suit="1" />
  <card z="12" faceup="1" value="4" suit="1" />
 </pile>
 <pile z="0" index="9" >
  <card z="1" faceup="0" value="3" suit="3" />
  <card z="2" faceup="0" value="9" suit="0" />
  <card z="3" faceup="0" value="6" suit="2" />
  <card z="4" faceup="0" value="9" suit="2" />
  <card z="5" faceup="0" value="13" suit="2" />
  <card z="6" faceup="1" value="7" suit="3" />
  <card z="7" faceup="1" value="11" suit="2" />
 </pile>
 <pile z="0" index="10" >
  <card z="1" faceup="0" value="4" suit="3" />
  <card z="2" faceup="0" value="8" suit="0" />
  <card z="3" faceup="0" value="7" suit="2" />
  <card z="4" faceup="1" value="8" suit="2" />
  <card z="5" faceup="1" value="1" suit="0" />
  <card z="6" faceup="1" value="7" suit="1" />
 </pile>
 <pile z="0" index="11" >
  <card z="1" faceup="0" value="5" suit="3" />
  <card z="2" faceup="1" value="3" suit="1" />
  <card z="3" faceup="1" value="11" suit="1" />
  <card z="4" faceup="1" value="4" suit="2" />
  <card z="5" faceup="1" value="3" suit="0" />
 </pile>
</dealer>

Comment 1 Parker Coates 2009-07-07 21:46:04 UTC

Do you think this could be the same or related to the issue described in bug 192721? Are these always situations that involved moving cards to empty piles?

Comment 2 Uli Bellgardt 2009-07-08 14:56:34 UTC

(In reply to comment #1)
> Do you think this could be the same or related to the issue described in bug
> 192721? Are these always situations that involved moving cards to empty piles?

Not knowing the solver nor its algorithm, I can only guess whether or not the two bugs are related (which is not helpful). 
And no, I do not see that the situation occurs when moving cards to empty piles. As an example, look at another simple reproducer: Grandfather Game #154468991. It is marked as unsolvable from the beginning. Only three moves can be done (each time there is exactly one possible move), then there is no more move left. Immediately after the first "Redeal" the status line shows that it is possible to solve this game.

Comment 3 Parker Coates 2009-07-08 15:19:12 UTC

Sorry, I was confused. Bug 192721 is reported against Grandfather's Clock, not Grandfather. I can confirm this issue with the latest trunk.

Comment 4 Stephan Kulow 2009-07-30 12:28:31 UTC

yep, I can reproduce #2 - the initial report I can't reproduce though.

Comment 5 Stephan Kulow 2009-07-30 12:44:29 UTC

SVN commit 1004492 by coolo:

follow the redeal logic of the original algorithm
BUG: 198878


 M  +4 -2      grandf.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=1004492