Computer Science Canada

2D Arrays
Author:  Cervantes [ Fri Aug 05, 2005 7:19 pm ]
Post subject:  2D Arrays
I'm having difficulty working with 2D arrays in Ruby.

Ruby:

grid = [5, 5]    #I'm just guessing at the syntax here
5.times do |j|
    5.times do |k|
        grid [j, k] = j * k
    end
end
=> 5
grid.display
0481216=>nil
grid [0, 4]
=> [0, 4, 8, 12]
grid [4, 0]
=> []


Would someone kindly shed some light on what is going on here, and how to use 2D arrays properly? Smile
Thanks
Author:  wtd [ Fri Aug 05, 2005 7:38 pm ]
Post subject: 
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.

code:
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):

code:
puts grid[3][2]
Author:  Cervantes [ Fri Aug 05, 2005 7:44 pm ]
Post subject: 
Intriguing Smile Thanks wtd! That works just fine.
Author:  wtd [ Fri Aug 05, 2005 10:34 pm ]
Post subject: 
Embrace the power of blocks. Smile
Author:  wtd [ Fri Aug 05, 2005 10:40 pm ]
Post subject: 
Or in "I hate whitespace" mode...

code:
grid=Array.new(5){|j|Array.new(5){|k|j*k}}
Author:  Cervantes [ Sat Aug 06, 2005 7:01 am ]
Post subject: 
Using my newfound knowledge of the make-shift 2D array, I tried to convert the N-Queen's solver into Ruby. I failed:
Ruby:

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 [x] [y]
                                        print "1"
                                else
                                        print "0"
                                end
                        end
                        puts ""
                end
        end

        def clearSpot (x, y)
                @N.times do |i|
                        if  @grid[i] [y] == true
                                return false
                        elsif x + i <= @N - 1 and y + i <= @N - 1 and @grid[x + i] [ y + i]
                                return false
                        elsif x - i >= 0      and y + i <= @N - 1 and @grid[x - i] [ y + i]
                                return false
                        elsif x + i <= @N - 1 and y - i >= 0      and @grid[x + i] [ y - i]
                                return false
                        elsif x - i >= 0      and y - i >= 0      and @grid[x - i] [ y - i]
                                return false
                        end
                end
                return true
        end

        def displaySolutions
                "Number of solutions found on a #{@N} by #{@N} grid: #{@solutions}"
        end

        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
                        end
                        solve(col + 1)
                        @grid[col][i] = false
                end
        end

end

puts NQueensSolver.new.solve(0).displaySolutions


When run, this program says:
Quote:

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:
Turing:

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 <= N and j + k <= N and grid (i + k, j + k) then
            result false
        elsif i - k > 0 and j - k > 0 and grid (i - k, j - k) then
            result false
        elsif i + k <= N and j - k > 0 and grid (i + k, j - k) then
            result false
        elsif i - k > 0 and j + k <= N and grid (i - k, j + k) then
            result false
        end if
    end for
    result true
end clearSpot

proc drawGrid
    drawfillbox (0, 0, maxx, maxy, grey)
    for i : 1 .. N
        for j : 1 .. N
            if grid (i, j) then
                drawfillbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, black)
            else
                drawfillbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, white)
            end if
            drawbox (i * gridSize, j * gridSize, i * gridSize + gridSize, j * gridSize + gridSize, black)
        end for
    end for
end drawGrid

proc Solve (col : int)
    if col > N then
        return
    end if
    for i : 1 .. N
        if clearSpot (col, i) then
            grid (col, i) := true
            if col = N then
                solutions += 1
                %/* <- take out '%' to comment this block (may need to hit F2)
                drawGrid
                put "SOLUTION!!! (", solutions, ")"
                View.Update
                cls
                Input.Pause
                %*/
            end if
            %/* <- take out '%' to comment this block (may need to hit F2)
            cls
            drawGrid
            View.Update
            delay (250)
            %*/
            Solve (col + 1)
            grid (col, i) := false
        end if
    end for
end Solve

for i : 1 .. N
    for j : 1 .. N
        grid (i, j) := false
    end for
end for

Solve (1)
put "Solutions: ", solutions, " Time: ", Time.Elapsed / 1000
View.Update


Also, are there any other ways I can shorten/simplify my program? I was wondering about this bit:
Ruby:

                                if @grid [x] [y]
                                        print "1"
                                else
                                        print "0"
                                end

Since if statements can return a value, I was looking to do something like this:
Ruby:

                                print
                                        if @grid [x] [y]
                                                "1"
                                        else
                                                "0"
                                        end

But that is printing "nil" instead of 1's and 0's.

Once again, thanks in advance!
Author:  zylum [ Sat Aug 06, 2005 7:21 am ]
Post subject: 
one mistake i see:

code:
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
                        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:

code:
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.
Author:  Cervantes [ Sat Aug 06, 2005 10:47 am ]
Post subject: 
Thanks for pointing that out zylum. Unfortunately, I've still got some problems, though that fixes the stack overflow. Laughing
The next error wrote:

n_queens.rb:33:in 'clearSpot': undefined method '[]' for nil:NilClass (NoMethodError)

Then it lists about 20 levels of methods.
I don't understand where the nil is coming in. If I have an array
Ruby:

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

then calling
Ruby:

my_arr [6]

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
code:

if condition1 && condition2

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

Thoughts? Thanks once again.
Author:  wtd [ Sat Aug 06, 2005 2:30 pm ]
Post subject: 
Ruby's arrays are indexed starting at zero, not one.
Author:  Cervantes [ Sat Aug 06, 2005 3:48 pm ]
Post subject: 
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.
Author:  wtd [ Sat Aug 06, 2005 4:25 pm ]
Post subject: 
Can you please post your current code, exactly as you're using it? Smile
Author:  Cervantes [ Sat Aug 06, 2005 5:04 pm ]
Post subject: 
Sure.
Ruby:

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 [x] [y]
                                        "1"
                                else
                                        "0"
                                end
                        end
                        puts ""
                end
        end

        def clearSpot (x, y)
                @N.times do |i|
                        if  @grid[i] [y]
                                return false
                        elsif x + i <= @N - 1 && y + i <= @N - 1 && @grid[x + i] [ y + i]
                                return false
                        elsif x - i >= 0      && y + i <= @N - 1 && @grid[x - i] [ y + i]
                                return false
                        elsif x + i <= @N - 1 && y - i >= 0      && @grid[x + i] [ y - i]
                                return false
                        elsif x - i >= 0      && y - i >= 0      && @grid[x - i] [ y - i]
                                return false
                        end
                end
                return true
        end

        def displaySolutions
                "Number of solutions found on a #{@N} by #{@N} grid: #{@solutions}"
        end

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

end

NQueensSolver.new.solve(0).displaySolutions
Author:  wtd [ Sat Aug 06, 2005 5:39 pm ]
Post subject: 
code:
elsif x - i >= 0      && y + i <= @N - 1 && @grid[x - i] [ y + i]


Something's happening here. I don't think your bounds checking is sufficient, though my head hurts too much right now to rewrite it.
Author:  Cervantes [ Sat Aug 06, 2005 7:07 pm ]
Post subject: 
I just did a check and the && works as in Java. If the first condition is false then the second condition will not be checked. Since this rules the possibility of checking outside the grid's bounds, I'm stunped as well.
Author:  wtd [ Sat Aug 06, 2005 7:27 pm ]
Post subject: 
Are you certain? In each of those checks it looks like you're only checking one boundary. For instance:

code:
x - 1 >= 0


Only checks the lower boundary.
Author:  Cervantes [ Sun Aug 07, 2005 6:11 am ]
Post subject: 
That shouldn't be a problem, so long as the position I pass in as (x,y), which is (col, i), is on the grid. I think it is. i must be between 0 and 7, and col must also be between 0 and 7 (if it were bigger than 7, the method returns 0 [Actually, that line (49) should be changed to
code:
if col > @N - 1

instead of
code:
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:
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. Smile
Author:  zylum [ Sun Aug 07, 2005 4:31 pm ]
Post subject: 
Cervantes wrote:
I've also discovered that it makes no difference what I do with the following bit of code:
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. Smile


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 Laughing. im guessing that will make you program a little less efficient with larger Ns.
Author:  wtd [ Wed Aug 10, 2005 7:59 pm ]
Post subject: 
Perhaps my code, that does work could help. Smile

code:
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

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy