hitorini-sitekure-problem-7-1.rb

hitorini-sitekure-problem-7-1.rb

# coding: utf-8

def dfs(board, i, j)
  return if  (i <= 0 || i > LEN) ||
             (j <= 0 || j > LEN) ||
             board[i][j] <= 0 || board[i][j] > M
  board[i][j] += M
  [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]].each do |pos|
    l, m = pos
    v = board[l][m]
    if v > 0 && v < M
      dfs(board, l, m)
    end
  end
end

def is_connect_board(board, i, j)
  [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]].each do |v|
    l, m = v
    dfs(board, l, m) and break if board[l][m] > 0    
  end
  ret = true
  board.each.with_index do |row, l|
    row.each.with_index do |v, m|
      ret = ret && (v > M || v <= 0)
      board[l][m] -= M if board[l][m] > M
    end
  end
  ret
end

def show_board(board)
  c = 0
  board.each do |row|
    puts row.map {|x| x === -1 ? '*' : x}.join(" ")
    c += row.select {|x| x === -1}.count
  end
  puts c
end
$count = 0

def candidate_col(board, i)
  state = {}
  for k in 1..LEN
    if board[k][i] > 0
      state[board[k][i]] ||= []
      state[board[k][i]] << k
    end
  end
  state.select {|_, v| v.length > 1}.values
end

def candidate_row(board, i)
  state = {}
  for k in 1..LEN
    if board[i][k] > 0
      state[board[i][k]] ||= []
      state[board[i][k]] << k
    end
  end
  state.select {|_, v| v.length > 1}.values
end

def is_continuous?(board, i, j)
  [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]].any? {|x| board[x[0]][x[1]] === -1}
end

def put_and_next_row(board, row, i, n)
  backup = {}
  for m in row
    backup[m] = board[i][m] and board[i][m] = -1 if n != m
  end
  solve(board, i) and return true if is_connect_board(board, i, n)
  for m in row
    board[i][m] = backup[m] if n != m
  end
  false
end

def solve_row(board, i)
  row = candidate_row(board, i).first
  return :next if row.nil?
  
  # 連続チェック
  ans = nil
  for n in row
    if is_continuous?(board, i, n)
      return :fail unless ans.nil? # 探索失敗
      ans = n
    end
  end

  return (put_and_next_row(board, row, i, ans) === true ? :success : :fail) if ans

  for n in row
    put_and_next_row(board, row, i, n) and return :success
  end
  :fail
end

def put_and_next_col(board, col, n, i)  
  backup = {}
  for m in col
    backup[m] = board[m][i] and board[m][i] = -1 if n != m
  end
  solve(board, i) and return true if is_connect_board(board, n, i)
  for m in col
    board[m][i] = backup[m] if n != m
  end
  false
end

def solve_col(board, i)
  col = candidate_col(board, i).first
  return :next if col.nil?
  
  # 連続チェック
  ans = nil
  for n in col
    if is_continuous?(board, n, i)
      return :fail unless ans.nil? # 探索失敗
      ans = n
    end
  end

  return (put_and_next_col(board, col, ans, i) === true ? :success : :fail) if ans

  for n in col
    put_and_next_col(board, col, n, i) and return :success
  end
  :fail
end

def solve(board, i)
  $count += 1
  case solve_col(board, i)
  when :fail
    return false
  when :success
    return true
  when :next
  else
    fail
  end  
  case solve_row(board, i)
  when :fail
    return false
  when :success
    return true
  when :next
  else
    fail
  end
  (k = i + 1) > LEN ? true : solve(board, k)
end

b = $stdin.readlines.map {|line| line.split(" ").map(&:to_i)}
LEN = b.length
$count = 0
board = Array.new(LEN + 2) {Array.new(LEN + 2, 0)}
maximum = -1
b.each.with_index do |row, i|
  row.each.with_index do |v, j|
    board[i + 1][j + 1] = v
    maximum = [v, maximum].max
    raise if v < 1 # 前提条件
  end
end
M = maximum + 1

Signal.trap("INT") { |signo|
  puts $count
  exit 1
}

show_board(board) if solve(board, 1)
p $count