Advertisement
t_a_w

True Knight - all solutions

Jan 6th, 2017
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Ruby 1.40 KB | None | 0 0
  1. #!/usr/bin/env ruby
  2.  
  3. require "z3"
  4.  
  5. class TrueKnight
  6.   def initialize
  7.     @solver = Z3::Solver.new
  8.     @cell_x = (0...30).map{|i| Z3::Int("x#{i}")}
  9.     @cell_y = (0...30).map{|i| Z3::Int("y#{i}")}
  10.     @cell_n = (0...30).map{|i| Z3::Int("n#{i}")}
  11.   end
  12.  
  13.   def solve!
  14.     (0...30).each do |i|
  15.       @solver.assert @cell_x[i] >= 0
  16.       @solver.assert @cell_x[i] <= 5
  17.       @solver.assert @cell_y[i] >= 0
  18.       @solver.assert @cell_y[i] <= 4
  19.       @solver.assert @cell_n[i] == @cell_x[i] + 6 * @cell_y[i] + 1
  20.     end
  21.     @solver.assert @cell_n[0] == 1
  22.     @solver.assert @cell_n[3] == 18
  23.     @solver.assert @cell_n[6] == 25
  24.     @solver.assert @cell_n[10] == 12
  25.     @solver.assert @cell_n[18] == 20
  26.     @solver.assert @cell_n[27] == 6
  27.     (0...30).each_cons(2) do |a,b|
  28.       dx = @cell_x[a] - @cell_x[b]
  29.       dy = @cell_y[a] - @cell_y[b]
  30.       abs_dx = (dx > 0).ite(dx, -dx)
  31.       abs_dy = (dy > 0).ite(dy, -dy)
  32.       @solver.assert ((abs_dx == 1) & (abs_dy == 2)) | ((abs_dx == 2) & (abs_dy == 1))
  33.     end
  34.     @solver.assert Z3.Distinct(*@cell_n)
  35.  
  36.     puts "Solutions:"
  37.     while @solver.satisfiable?
  38.       model = @solver.model
  39.       s = (1...30).map{|i| model[@cell_n[i]].to_s }.join
  40.       puts "http://www.rankk.org/challenges/the-rising-knight.py?solution=#{s}"
  41.       @solver.assert Z3.Or(*
  42.         @cell_n.map{|n| n != model[n] }
  43.       )
  44.     end
  45.   end
  46. end
  47.  
  48. TrueKnight.new.solve!
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement