Skip to content

Instantly share code, notes, and snippets.

@tom-lord
Created May 14, 2020 11:24
Show Gist options
  • Save tom-lord/f36a7d7028254d5c72d804b6455826f8 to your computer and use it in GitHub Desktop.
Save tom-lord/f36a7d7028254d5c72d804b6455826f8 to your computer and use it in GitHub Desktop.
Find all unique solutions to the 4x4 playing cards puzzle
class Array
def no_duplicates?
tally.values.all? {|v| v == 1 }
end
end
class Card
attr_reader :picture, :suit
def initialize(picture, suit)
@picture = picture
@suit = suit
end
end
class Board
attr_reader :cards
def initialize
@cards = Array.new(16)
end
def valid?
card_lines.all? do |card_line|
card_line.compact.map(&:picture).no_duplicates? && card_line.compact.map(&:suit).no_duplicates?
end
end
def display
cards.each_slice(4) do |card_row|
card_row.each do |card|
if card
print "#{card.picture}#{card.suit} "
else
print '-- '
end
end
puts # new line
end
end
private
def card_lines
[
# rows
[cards[0], cards[1], cards[2], cards[3]],
[cards[4], cards[5], cards[6], cards[7]],
[cards[8], cards[9], cards[10], cards[11]],
[cards[12], cards[13], cards[14], cards[15]],
# columns
[cards[0], cards[4], cards[8], cards[12]],
[cards[1], cards[5], cards[9], cards[13]],
[cards[2], cards[6], cards[10], cards[14]],
[cards[3], cards[7], cards[11], cards[15]],
# diagonals
[cards[0], cards[5], cards[10], cards[15]],
[cards[3], cards[6], cards[9], cards[12]]
]
end
end
@solution_count = 0
def solve(board, available_cards)
missing_card_idx = board.cards.index(&:nil?)
if missing_card_idx
available_cards.each do |chosen_card|
board.cards[missing_card_idx] = chosen_card
solve(board, available_cards - [chosen_card]) if board.valid?
end
# we reached a dead end! Backtrack...
board.cards[missing_card_idx] = nil
return
end
@solution_count += 1
puts "\n\nFound solution: #@solution_count"
board.display
end
board = Board.new
PICTURES = %i(A K Q J)
SUITS = %i(C H S D)
available_cards = PICTURES.product(SUITS).map { |picture, suit| Card.new(picture, suit) }
board.cards[0] = available_cards.find { |c| c.picture == :A && c.suit == :C }
board.cards[1] = available_cards.find { |c| c.picture == :K && c.suit == :H }
board.cards[2] = available_cards.find { |c| c.picture == :Q && c.suit == :S }
board.cards[3] = available_cards.find { |c| c.picture == :J && c.suit == :D }
solve(board, available_cards)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment