CODEWITHSUNDEEP
rubyalgorithmknights-tour
xxyyxx
xxyyxx

Reputation: 2396

Having trouble with Knights Tour in Ruby

I'm trying to the knights tour problem as an exercise in recursion since I have not used it in awhile, but my script does not seem to find a solution and only goes as high as 56 moves. Any tips to point me in the right direction would be appreciated.

class KnightsTour
def initialize
    board = [nil, nil, nil, nil, nil, nil, nil, nil]
    8.times do |i|
        board[i] = [0, 0, 0, 0, 0, 0, 0, 0]
    end
    tour(0,0,board)
end

def tour(x,y,board,current_move=0)
    puts board if current_move == 64

    return if board[x] == nil || 
              board[x][y] == nil || 
              board[x][y] != 0 || 
              x < 0 ||
              y < 0 ||
              current_move == 64

    current_move +=1
    board[x][y] = current_move

    tour(x+2, y+1, board.dup, current_move)
    tour(x+2, y-1, board.dup, current_move)
    tour(x+1, y-2, board.dup, current_move)
    tour(x-1, y-2, board.dup, current_move)
    tour(x-1, y+2, board.dup, current_move)
    tour(x+1, y+2, board.dup, current_move)
    tour(x-2, y+1, board.dup, current_move)
    tour(x-2, y-1, board.dup, current_move)
end
end

KnightsTour.new

Upvotes: 1

Views: 201

Answers (2)

caiyun liu
caiyun liu

Reputation: 1

def is_safe?(solution, x, y)
   x >= 0 && x < solution.length && y>= 0 && y < solution.length && solution[x][y] == -1
end

def solve_nt_helper(size, solution, curr_x, curr_y, num, xmoves, ymoves)
    return true if num == size * size
    size.times.each do |i|
        # p "i:#{i}"
        next_x = curr_x + xmoves[i]
        next_y = curr_y + ymoves[i]
        if is_safe?(solution, next_x, next_y)
            solution[next_x][next_y] = num
            return true if solve_nt_helper(size, solution, next_x, next_y, num + 1, xmoves, ymoves)
  
            solution[next_x][next_y] = -1
        end
    end
    # p "failed at num #{num}"
    false
end

def solve_nt(n)
    xmoves = [2, 1, -1, -2, -2, -1, 1, 2]
    ymoves = [1, 2, 2, 1, -1, -2, -2, -1]
    solution = Array.new(n) { Array.new(n) { -1 } }
    solution[0][0] = 0
    solution.each do |row|
      p row
    end
    return 'invalid' unless solve_nt_helper(n, solution, 0, 0, 1, xmoves, ymoves)
    solution.each do |row|
      p row
    end
    solution
end

n = 8
require 'memory_profiler'
report = MemoryProfiler.report do
solve_nt(n)
end
report.pretty_print

here is a ruby version that works. The trick of this solution is

  1. don't put any debugging message in the recursive method.
  2. pass xmoves, and ymoves as variable to the recursive method.don't define a constant KNIGHTS_MOVES = [[2, 1],[2, -1], [-2, 1],[-2, -1],[1, 2],[1, -2], [-1, 2], [-1, -2]] and iterate over it in solve_nt_helper. sizes.each would generate a lot of Enumerator objects, but iterater over constant seems slows the whole process down.

trick 1 also seems to applicalbe to java and python.did not try item2 for java and python. The algorithm is borrowed from geekstogeeks

Upvotes: 0

Eric Duminil
Eric Duminil

Reputation: 54223

The main problem is that you only use one board object for all the recursions. You should use a copy of board anytime you try a move. dup produces a shallow copy, and isn't enough to duplicate the board.

Another problem might be that the bruteforce approach is too slow because of exponential growth (8 moves at every iteration, even if you stop early for some).

The usual approach is to pick the cell having the fewest possibilities as the next move.

Upvotes: 1

Related Questions