Knights Tour

kt.rb

# Knights Tour - unpolished

module KnightsTour

  class Game
    def initialize (boardHeight, boardWidth)
      @board = Array.new(boardHeight) {Array.new(boardWidth, 0)}
      @moveCounter = 0;
    end
      
    def make_move (x, y)
      # return if square already taken
      unless @board[x][y] == 0
        return false
      end
        
      # mark square taken
      @moveCounter += 1
      @board[x][y] = @moveCounter     
      
      # check board complete  
      check_board_complete  

      # while available moves - make move 
      get_available_moves(x,y).each do |move|
        make_move(move[:x], move[:y])
      end 

      # board not complete? (should have seen output from prev call if it is) 
      # then we've exhausted moves from this initial square, so rollback
      @board[x][y] = 0  
      @moveCounter -= 1
      false
    end

    def check_board_complete
      finished = true

      @board.each do |row| 
        row.each do |sq|
          #TODO: ruby equivalent of "break"?
          unless sq > 0
            finished = false  
          end
        end 
      end

      # just throw an error until I decide how this should bubble up through recursions
      if finished 
        print_board
        raise "BOARD COMPLETE!! " 
      end
        
      finished
    end

    # return array of all possible moves from current position
    def get_available_moves (x, y)

      moves = []

      @board.each_index do |r|
        @board[r].each_index do |c|
          # TODO: this is not pretty...
          if @board[r][c] == 0 && (
            (r == x-1 && c == y-2) ||
            (r == x-2 && c == y-1) ||
            (r == x-2 && c == y+1) ||
            (r == x-1 && c == y+2) ||
            (r == x+1 && c == y+2) ||
            (r == x+2 && c == y+1) ||
            (r == x+2 && c == y-1) ||
            (r == x+1 && c == y-2)
            )
            moves.push({:x => r, :y => c})
          end 
        end
      end     
      
      moves
    end

    def print_board 
      rows = @board.map do |row| 
        row.inspect 
      end     

      puts rows.join("\n") + "\n" 
    end
  end
end

game = KnightsTour::Game.new(8,8)
game.make_move(0,0)
game.print_board