#
# exercise of backtracking algorithm.
# 2008.07.26
#
require 'pp'

# (x, y) のマスに置けるか
def test(x, y, board)
  x.times do |i|
    # 左
    if board[i][y] == 1
      #p "1 false in board[#{i}][#{y}] == 1"
      return false
    end
    # 左ななめ上
    if x-i > 0 and y-i > 0 and board[x-i-1][y-i-1] == 1
      #p "2 false in board[#{x-i-1}][#{y-i-1}] == 1"
      return false
    end
    # 左ななめ下
    if x-i > 0 and y+i+1 < 8 and board[x-i-1][y+i+1] == 1
      #p "3 false in board[#{x-i-1}][#{y+i+1}] == 1"
      return false
    end
  end
  # 上
  y.times do |i|
    if board[x][i] == 1
      #p "4 false in board[#{x}][#{i}] == 1"
      return false
    end
  end
  return true
end

def solve(x, board)
  8.times do |y|
    if test(x, y, board)
      board[x][y] = 1 # 置く
      return true if x == 7 or solve(x+1, board)
      board[x][y] = 0 # とる
    end
  end
  false
end

# 結果表示
def show(board)
  8.times do |y|
    8.times do |x|
      print "#{board[x][y]} "
    end
    puts
  end
end

$solutions = []
board = []
8.times {|i| board.push Array.new(8, 0) }

# メイン
solve(0, board)
show(board)