-----------------------------------

Cervantes

Fri Aug 05, 2005 7:19 pm


2D Arrays

-----------------------------------

I'm having difficulty working with 2D arrays in Ruby.


grid = 

Would someone kindly shed some light on what is going on here, and how to use 2D arrays properly?  :)
Thanks


-----------------------------------

wtd

Fri Aug 05, 2005 7:38 pm



-----------------------------------

There's no such thing as a two dimensional array in Ruby.  An array can hold any kind of object, including other arrays, so you just have an array of arrays.

grid = Array.new(5) do | j |
   Array.new(5) do | k |
      j * k
   end
end

I think that does what you want.

Then to access, (3, 2):

puts grid[3][2]


-----------------------------------

Cervantes

Fri Aug 05, 2005 7:44 pm



-----------------------------------

Intriguing  :)  Thanks wtd!  That works just fine.


-----------------------------------

wtd

Fri Aug 05, 2005 10:34 pm



-----------------------------------

Embrace the power of blocks.  :)


-----------------------------------

wtd

Fri Aug 05, 2005 10:40 pm



-----------------------------------

Or in "I hate whitespace" mode...

grid=Array.new(5){|j|Array.new(5){|k|j*k}}


-----------------------------------

Cervantes

Sat Aug 06, 2005 7:01 am



-----------------------------------

Using my newfound knowledge of the make-shift 2D array, I tried to convert the N-Queen's solver into Ruby.  I failed:

class NQueensSolver

	def initialize
		@N = 3	
		@solutions = 0
		@grid = Array.new(@N) do |x|
			Array.new(@N) do |y|
				false
			end
		end
	end

	def display
		@N.times do |x| 
			@N.times do |y|
				if @grid 

When run, this program says:

n_queens.rb:52in 'solve': stack level too deep (SystemStackError)

Then if goes through "from this method, from that method" a lot of times, then it says 1038 levels later, and lists the last three methods that it traced.
I can't understand why this isn't working, especially since I've got @N set to a measily 3!  A 3x3 grid should be very simple to solve.  I've lifted this code from zylum's NQueen's solver in Turing, which does work.  Here's his code:

setscreen ("offscreenonly,graphics:500;500,nobuttonbar")

const N := 8
const gridSize := maxx div (N + 2)
var grid : array 1 .. N, 1 .. N of boolean
var solutions : int := 0
colorback (grey)

fcn clearSpot (i, j : int) : boolean
    for k : 1 .. N
        if grid (k, j) then
            result false
        elsif i + k  0 and grid (i - k, j - k) then
            result false
        elsif i + k  0 and grid (i + k, j - k) then
            result false
        elsif i - k > 0 and j + k  N then
        return
    end if
    for i : 1 .. N
        if clearSpot (col, i) then
            grid (col, i) := true
            if col = N then
                solutions += 1
                %/* = @N - 1
                        return 0
                end if
                @N.times do |i|
                        if clearSpot(col, i) == true
                                @grid[col] [i] = true
                                if col == @N
                                        @solutions += 1
                                end
                        end
                        solve(col + 1)
                        @grid[col][i] = false
                end
        end 

you should not call solve(col + 1) unless you have successfully placed a peice in the current column. it should be:

def solve(col)
                if col >= @N - 1
                        return 0
                end if
                @N.times do |i|
                        if clearSpot(col, i) == true
                                @grid[col] [i] = true
                                if col == @N
                                        @solutions += 1
                                end
                                solve(col + 1)
                                @grid[col][i] = false
                        end
                end
        end 

also, there are no solutions for 3x3 board, so that may cause some issues as well although i doubt it.


-----------------------------------

Cervantes

Sat Aug 06, 2005 10:47 am



-----------------------------------

Thanks for pointing that out zylum.  Unfortunately, I've still got some problems, though that fixes the stack overflow.  :lol:

n_queens.rb:33:in 'clearSpot': undefined method '
Then it lists about 20 levels of methods.
I don't understand where the nil is coming in.  If I have an array

my_arr = Array.new(5) { |j| j }

then calling

my_arr 
yields nil.  But I don't see why I should be encountering nil, because my checks should be within the bounds of the array.  Right now I've switched from using "and" to "&&".  Is "&&" similar to as it is in Java?  That is, if an if statement is set up like this

if condition1 && condition2

and condition1 fails, will condition2 even be checked?  I hope not.

Thoughts?  Thanks once again.


-----------------------------------

wtd

Sat Aug 06, 2005 2:30 pm



-----------------------------------

Ruby's arrays are indexed starting at zero, not one.


-----------------------------------

Cervantes

Sat Aug 06, 2005 3:48 pm



-----------------------------------

I know.  That's why you see a bunch of minus one after @N in my code.  That's also why I start the solve at column 0, and why I check if x - i or y - i is >= 0, not 1.  Aah, I just discovered I forgot to subtract one from @N in my check for victory.  That doesn't make any difference though.  That just changes the number of solutions found, which, so far, has been none.


-----------------------------------

wtd

Sat Aug 06, 2005 4:25 pm



-----------------------------------

Can you please post your current code, exactly as you're using it?  :)


-----------------------------------

Cervantes

Sat Aug 06, 2005 5:04 pm



-----------------------------------

Sure.

class NQueensSolver

	def initialize
		@N = 4
		@solutions = 0
		@grid = Array.new(@N) do |x|
			Array.new(@N) do |y|
				false
			end
		end
	end

	def display
		@N.times do |x| 
			@N.times do |y|
				print @output = 
				if @grid 


-----------------------------------

wtd

Sat Aug 06, 2005 5:39 pm



-----------------------------------

elsif x - i >= 0      && y + i  @N - 1
instead of
if col >= @N - 1
This change does not make any difference though, in that I'm still getting the same errors message]).  

Hooah!  I just fixed it.  Turns out it I needed to add or subtract one from i inside my clearSpot method.  Say I was on the bottom left corner of the board.  I need to check the far right corner.  The counter, i, goes from 0 to 7.  x and y are both 0.  The furthest along the board I can get is (N - 1, N - 1).  I can understand why a thing like this would prevent the program from giving the correct output, but I'm baffled as to why it would crash the program.  Must be something that occurs later on, after a piece has been placed in a spot that it shouldn't be.

I've also optimized the clearSpot procedure a little bit by taking out the checks for pieces on the right side of the piece I'm placing.  We know everything on that side of the grid is empty, because we haven't got that far yet (or we've recursed back, in which case the grid spot is made false each time we recurse back).

I've also discovered that it makes no difference what I do with the following bit of code:

		if col > @N - 1
			return 0
		end if

I can comment it out and it will still work fine.  It doesn't seem to speed the program any, either.

Here's the working code.  I'd like to know how I could shorten it, however. Any thoughts there?  Thanks in advance.

I had to change the extension of the file to .txt because .rb files are not allowed.  Tony or Dan, please allow us to upload .rb files.  :)


-----------------------------------

zylum

Sun Aug 07, 2005 4:31 pm



-----------------------------------

I've also discovered that it makes no difference what I do with the following bit of code:

		if col > @N - 1
			return 0
		end if

I can comment it out and it will still work fine.  It doesn't seem to speed the program any, either.

Here's the working code.  I'd like to know how I could shorten it, however. Any thoughts there?  Thanks in advance.

I had to change the extension of the file to .txt because .rb files are not allowed.  Tony or Dan, please allow us to upload .rb files.  :)

lol that is strange. that means there is no place in you code preveting it from calling solve(N)... but i guess that doesnt matter because your program prevents any peices from being placed off the boad  :lol:. im guessing that will make you program a little less efficient with larger Ns.


-----------------------------------

wtd

Wed Aug 10, 2005 7:59 pm



-----------------------------------

Perhaps my code, that does work could help.  :)

Queen = Struct.new(:row, :column)

def conflict(queen1, queen2)
   queen1.row == queen2.row or
   (queen2.column - queen1.column).abs == (queen2.row - queen1.row).abs
end

def solutions(board_size = 8, column = 0, previous_solutions = [])
   if column >= board_size
      previous_solutions
   elsif column == 0
      previous_solutions = Array.new(board_size) { |row| [Queen.new(row, column)] }

      solutions(board_size, column + 1, previous_solutions)
   else
      previous_solutions = previous_solutions.collect do |previous_solution|
         (0 ... board_size).reject do |row_number|
            previous_solution.detect { |queen| conflict(queen, Queen.new(row_number, column)) }
         end.collect do |candidate_row|
            previous_solution + [Queen.new(candidate_row, column)]
         end
      end.inject [] do |a, b|
         a + b
      end

      solutions(board_size, column + 1, previous_solutions)
   end
end

def draw_solution(board_size, solution)
   (0 ... board_size).each do |row|
      current_queen = solution.find { |queen| queen.row == row }
      (0 ... board_size).each do |column|
         if column == current_queen.column
            print "Q"
         else
            print "_"
         end
      end

      puts
   end
end