Skip to content

Instantly share code, notes, and snippets.

@davidvandusen
Created December 26, 2017 05:17
Show Gist options
  • Save davidvandusen/e923e213330b357332a4a9ea5428c620 to your computer and use it in GitHub Desktop.
Save davidvandusen/e923e213330b357332a4a9ea5428c620 to your computer and use it in GitHub Desktop.
a 7 2 4 0
a 4 0 5 2
a 4 8 5 2
a 9 3 1 8
a 7 2 9 3
a 5 3 7 0
b 4 0 7 2
b 9 3 7 2
b 7 2 4 6
b 4 2 9 8
b 5 0 7 3
b 5 2 9 3
c 7 0 5 3
c 7 0 4 2
c 4 0 5 2
c 7 0 4 6
c 4 0 7 6
c 4 6 1 8
d 7 6 4 0
d 4 6 9 2
d 5 3 9 2
d 1 3 7 0
d 7 6 1 3
d 5 8 4 0
e 4 2 5 8
e 1 8 4 0
e 9 3 1 6
e 4 2 9 6
e 1 3 5 8
e 7 6 4 2
f 7 2 5 3
f 9 3 7 6
f 9 6 7 3
f 9 8 4 6
f 5 2 7 3
f 4 8 9 6
require 'csv'
def permute(input)
if input.length == 2
[
[input[0], input[1]],
[input[1], input[0]]
]
else
input.inject([]) do |output, elem|
list = input.clone
list.delete(elem)
output + permute(list).map {|l| l.unshift(elem)}
end
end
end
def solve(guess)
solution = []
HEIGHT.times {solution << []}
solved = solve_r(0, 0, guess, solution, [])
solved && solution
end
def solve_r(row, col, guess, solution, used)
return true if used.length == NUM_CARDS
fish = guess[SQUARE[row][col] - 1]
CARD_GROUPS[fish].each do |card|
next if used.include? card
next if solution[row][col - 1][E] != card[W] if col > 0
next if solution[row - 1][col][S] != card[N] if row > 0
solution[row][col] = card
used << card
if col == WIDTH - 1
next_col = 0
next_row = row + 1
else
next_col = col + 1
next_row = row
end
solved = solve_r(next_row, next_col, guess, solution, used)
if solved
return true
else
used.delete(card)
end
end
false
end
F = 0
N = 1
W = 2
S = 3
E = 4
CARDS = CSV.read('fish.csv')
NUM_CARDS = CARDS.length
CARD_GROUPS = CARDS.group_by {|c| c[F]}
OPTS = CARD_GROUPS.keys
SQUARE = CSV.read('magic_square.csv', converters: :numeric)
WIDTH = HEIGHT = SQUARE.length
GUESSES = permute(OPTS)
GUESSES.each do |g|
solution = solve(g)
if solution
solution.each do |row|
puts row.map {|c| c.join('').upcase}.join(' ')
end
break
end
end
4 2 1 6 5 3
6 5 4 3 1 2
3 1 6 4 2 5
1 3 5 2 4 6
5 6 2 1 3 4
2 4 3 5 6 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment