Arduino Solitaire Logic

logic.cpp

struct Card {
	CardColor Color;
	CardSuit Suit;
	CardValue Value;
	//
	bool FaceUp;
	//
	Card* Next;
	Card* Prev;
	//
	CardLocation Location; // Deck | Stack | 
	//
	static Card* getCard(CardValue, CardSuit);
};

struct BoardState {
	Card* Stacks[4];
	Card* Board[7];
	//
	Card* Deck;
	Card* DeckTop;
	//
	Card* Disc;
} state;

//description of a move to do
struct SubMove {
	Card* From;
	Card* To;
};
struct MoveDescription {
	Card* From;
	Card* To;
	size_t SubmoveCount;
	SubMove* SubmoveList;
};

void hint_get_tomove(Card* dest[7], int* count) {
	int put_inx = 0;
	for (int i = 0; i < 7; ++i) {
		Card* c = state.Board[i];
		while (c->Next && c->Next.FaceUp && c->Next.Value != 0)
			c = c->Next;
		if (c->Value != 0)
			dest[put_inx++] = c;
	}
	*count = put_inx;
}

void hint_get_dest(Card* source[11], int* count) {
	int put_inx = 0;
	//places to put down a card on the board
	for (int i = 0; i < 7; ++i) {
		dest[put_inx++] = state.Board[i];
	}
	//places to put down a card on the stacks
	for (int i = 0; i < 7; ++i) {
		dest[put_inx++] = state.Stacks[i];
	}
	*count = put_inx;
}

//check if a given card is `available`, that is, if it is face up
//on the board, or in the stack.
Card* hint_isavailable(CardValue, CardColor) {

}
Card* hint_isavailable(CardValue, CardSuit) {

}

//red => black, black => red
CardColor hint_otherColor(CardColor) {
	if (CardColor == ColorBlack)
		return ColorRed;
	else
		return ColorBlack;
}

Card* hint_canPlaceCardOn(Card* card, Card* dest[11]) {
	for (int i = 0; i < 11; ++i) {
		if (dest[i]->Location == LocationBoard) {
			if (card->Color == hint_otherColor(dest[i]->Color) && card->Value == dest[i]->Value+1)
				return dest[i];
		} else if (dest[i]->Location == LocationStack) {
			if (card->Suit == dest[i]->Suit && card->Value == dest[i]->Value+1)
				return dest[i];
		}
	}
}

void hint(Card** move_from, Card** move_to, bool do_move) {
	//get cards to move and places to move them to
	Card* toMove[7];
	int toMoveN;
	hint_get_moves(toMove, &toMoveN); 
	//
	Card* dest[11];
	int destN;
	hint_get_dest(dest, &destN);
	//
	struct HintRecord {
		Card* From;
		Card* To;
		int Difficulty;
		bool Possible;
	};
	int hintRecordComparator(const HintRecord* a, const HintRecord* b) {
		if (a->Possible && !b->Possible) {
			return 1;
		} else if (!a->Possible && b->Possible) {
			return -1;
		} else if (a->Possible && b->Possible) {
			return b->Difficulty - a->Difficulty;
		}
	}
	HintRecord moveArray[toMoveN];
	moveArrayN = 0;
	//
	for (int i = 0; i < toMoveN; ++i) {
		Card* cardToMove = toMove[i];
		//stats on the best move to do
		Card* whereToMove = 0;
		int moveDifficulty = 100; //large value to start
		bool requiresUnrevealed = true;
		//
		for (int j = 0; j < destN; ++j) {
			Card* cardDest = dest[j];
			//
			int difficulty = 100; //intial difficulty, larger
			bool reqUnrevealed = false;
			//
			if (cardDest.Location == LocationStack) {
				//on the stacks, we need to be the same color and +n
				if (cardToMove->Suit == cardDest->Suit || cardDest->Value == 0) {
					difficulty = cardToMove->Value - cardDest->Value - 1

					//Search to see if the between cards are available
					for (int value = cardDest->Value+1; value < cardToMove->Value; ++value) {
						if (!hint_isavailable(i, cardDest->Suit))
							reqUnrevealed = true;
					}
				}

			} else if (cardDest.Location == LocationBoard) {
				//on the board, we need to have alternating colors per stack, which 
				//is a bit more complicated logic
				int cardsBetween = cardToMove->Value - cardDest->Value - 1
				if (cardsBetween >= 0) {
					if (cardDest->Value > 0) {
						//normal placement on a stack
						if ((cardsBetween%2 == 1) == (cardToMove->Color == cardDest->Color)) {
							difficulty = cardsBetween;
							//Search to see if the between cards are available
							CardColor oddColor = hint_otherColor(cardToMove->Color);
							CardColor evenColor = cardToMove->Color;
							for (int ofs = 1; ofs <= cardsBetween; ++ofs) {
								if (!hint_isavailable(cardToMove->Value+ofs, (i%2==0)?evenColor:oddColor))
									reqUnrevealed = true;
							}
						}
					} else {
						//placement of a king in an empty stack
						if (cardToMove->Value == 13) {
							//king, can move
							difficulty = 0;
							reqUnrevealed = false;
						}
					}
				}
			} else {
				assert(false && "Unreachable");
			}

			//update the best move if we are "better" than it with this move
			if (difficulty < moveDifficulty && (!reqUnrevealed || requiresUnrevealed)) {
				moveDifficulty = difficulty;
				requiresUnrevealed = reqUnrevealed;
				whereToMove = cardDest;
			}
		}

		//update the hintRecord if we found a way to move this item
		if (whereToMove) {
			HintRecord& rec = moveArray[moveArrayN++];
			rec.From = cardToMove;
			rec.To = whereToMove;
			rec.Difficulty = moveDifficulty;
			rec.Possible = !requiresUnrevealed;
		}
	}

	//now sort the hintrecords by difficulty
	qsort(moveArray, moveArrayN, sizeof(HintRecord), hintRecordComparator);

	//sorted, see if we have a 0 difficulty item
	if (moveArray[0].Difficulty == 0 && moveArrayN[0].Possible) {
		//with a 0 difficult move we can just do it
		*move_from = moveArray[0].From;
		*move_to = moveArray[0].To;
		return;
	} else {
		//otherwise, we need a more complex logic to test the constraints of the move.
		//we can't just pull any old card out of the deck, so we may need to 

		//for each move, test if each of the constraints can be met
		for (int i = 0; i < moveArrayN; ++i) {
			HintRecord& rec = moveArrayN[i];

			//now, find the constraints, that is, which cards we need to move from the
			//deck or stacks into play to make a move we want to make.
			//Look for the first one and suggest that as the hint
			Card* targ = 0;
			if (rec.To->Location == LocationStack) {
				//stack, constraints are on-suit.
				//targ must be available, since we checked that before
				targ = hint_isavailable(rec.To->Value+1, rec.To->Suit);

			} else if (rec.To->Location == LocationBoard) {
				//board, constraints are alternating color
				//targ must be available, since we checked that before
				targ = hint_isavailable(rec.To->Value+1, hint_otherColor(rec.To->Color));
			}

			//now, try to make the target available
			//first, find the target's position in the deck
			Card* deck = State.Deck;
			int8_t deckPos = -1;
			int8_t deckTopPos = -1;
			Card* deckListing[52] = {0};
			for (int i = 0; i < 52; ++i) {
				if (deck) {
					deckListing[i] = deck;
					if (deck == State.DeckTop)
						deckTopPos = i;
					if (deck == targ) {
						deckPos = i;
						break;
					} else {
						deck = deck->Next;
					}	
				} else
					break;
			}

			//now, get the "offset" of the card from an index where we can directly get
			//it out of the stack by going through it
			//If we can't directly get the card we want, we may have to "pull" some extra
			//cards onto the board from the deck to "shift" the deck to where we can get
			//the card we want out.
			//If all else fails we just suggest possible moves from the deck onto the
			//board, even if they don't help win the game.
			//If there are no moves, we return NULL for source and dest.
			if (((deckPos>=deckTopPos) && (deckPos-deckTopPos)%3 == 0) || (deckPos%3) == 2) {
				//we can just cycle through the deck and get to it
				*move_from = targ;
				*move_to = rec.To;
			} else {
				//first see if we can remove one of the cards between the top and
				//the card that we want
				int startInx = 0;
				if (deckPos >= deckTopPos && deckTopPos != -1)
					//start search at the deck top pos, but only if there is one
					startInx = deckTopPos;
				else
					//start at the start
					startInx = 2;
				//search from the startinx, since this may be better than starting
				//from the start
				for (int i = startInx; i < deckPos; i += 3) {
					if (hint_canPlaceCardOn(deckListing[i], dest)) {
						*move_from = deckListing[i];
						*move_to = hint_canPlaceCardOn(deckListing[i], dest);
						return;
					}
				}
				//try again from the start of the deck (worse)
				for (int i = 2; i < deckPos; i += 3) {
					if (hint_canPlaceCardOn(deckListing[i], dest)) {
						*move_from = deckListing[i];
						*move_to = hint_canPlaceCardOn(deckListing[i], dest);
						return;
					}
				}
			}
		}

		//can't move any of the cards we want to

		//see if we can move any cards on the board onto the stacks
		uint8_t stackValues[4]; //max value on each stack indexed by suit
		for (int s = 0; s < 4; ++s) {
			Card* c = State.Stacks[i];
			while (c && c->Next) {
				c = c->Next;
			}
			if (c)
				stackValues[c->Suit] = c;
		}
		for (int i = 0; i < 7; ++i) {
			if (State.Board[i] && stackValues[State.Board[i]->Suit]->Value == State.Board[i]->Value+1) {
				*move_from = State.Board[i];
				*move_to = stackValues[State.Board[i]->Suit];
			}
		}

		//fallback and see if we can move any card from the deck to somewhere 
		//other than the deck
		Card* it = State.Deck;
		for (int i = 0; i < 52; ++i) {
			if (it) {
				Card* dst = hint_canPlaceCardOn(it, dest)
				if (dst) {
					*move_from = it;
					*move_to = dst;
					return;
				}
				it = it->Next;
			}
		}

		//no vaild moves in the move array
		*move_from = 0;
		*move_to = 0;
		return;
	}
}