Multiple For Loop condition in Swift

Question

I am working on N-Queens problem and to check whether the queen has been already placed on upper and lower left diagonals, I am finding difficulty in formulating for loop condition.

func isPlaceable(row: Int, column: Int) -> Bool {

    // check if one same row another queen exits
    for i in 0..<column {
        if (solution[row][i] == 1) {
            return false
        }
    }

    // check upper left diagonal
    // in C or C++ I can do
    // for (int i = row, int j = col; i >= 0 && j >= 0; i--, j--) {
    //    if (board[i][j])
    //       return false;
    //}
}

What would be Swifty way of doing it i.e. Combing the two condition?

You can iterate over the array of [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]. In every iteration, start adding the item to (row, column) until the position is not out of bounds. That will find all the diagonals and straight lines. Also, instead of checking all the diagonals when placing the queen, it will be faster to mark all the cells that are "attacked" by a queen after the placement). Then, checking whether a cell is "attacked" will be instantaneous. — Sulthan
– Sulthan, Commented Apr 26, 2017 at 7:25
@Sulthan I am only checking left diagonals which are not marked. This method is just a part of overall solution. I was looking for better way to wrap the for loop condition instead of using while or reapeat. — Rahul
– Rahul, Commented Apr 27, 2017 at 7:56

Nirav D · Accepted Answer · 2017-04-26 06:57:23Z

1

One possible solution is you can use zip(_:_:) with two sequence.

func isPlaceable(row: Int, column: Int) -> Bool {

    // check if one same row another queen exits
    for i in 0..<column {
        if (solution[row][i] == 1) {
            return false
        }
    }

    // check upper left diagonal
    let seq1 = (0...row).reversed()
    let seq2 = (0...column).reversed()
    for (i,j) in zip(seq1, seq2) {
        if (board[i][j]) {
            return false
        } 
    }
    //your code
}

answered Apr 26, 2017 at 6:57

Nirav D

72.6k12 gold badges168 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rahul Over a year ago

Till now your solution seems best one. I will be waiting for more.

Nirav D Over a year ago

@Rahul Will wait for it :)

rsc · Accepted Answer · 2017-04-26 06:41:36Z

0

var i = row
var j = col
while (i >= 0 && j >= 0) {
    if (board[i][j])
        return false;
    i -= 1
    j -= 1
}

answered Apr 26, 2017 at 6:41

rsc

10.7k5 gold badges43 silver badges38 bronze badges

1 Comment

Rahul Over a year ago

This was my first solution. I am looking for better way to do it.

Alain T. · Accepted Answer · 2017-04-28 00:54:54Z

This type of process benefits a lot from double indirection and prepared matrices.

For example, you could give an identifier to each line segment on the board and check that no two queens use the same line segment.

There are 46 line segments on a standard chess board:

8 vertical 8 horizontal 30 diagonals (15 each)

(I numbered them 1 through 46)

When the queens are properly placed, they will each use 4 line segments (axes) that no other queen uses. Sets are the ideal structure to check for this non intersecting union. By preparing a matrix with a Set of 4 axis identifiers at each row/column, a simple union of the sets for the 8 queens will tell us if they align with each other.

// vertical axes (1...8)
let vAxis =    [ [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ],
                 [ 1, 2, 3, 4, 5, 6, 7, 8 ]
               ]

// horizontal axes (9...16)                
let hAxis =  [ [ 9,   9,  9,  9,  9,  9,  9,  9 ],
               [ 10, 10, 10, 10, 10, 10, 10, 10 ],
               [ 11, 11, 11, 11, 11, 11, 11, 11 ],
               [ 12, 12, 12, 12, 12, 12, 12, 12 ],
               [ 13, 13, 13, 13, 13, 13, 13, 13 ],
               [ 14, 14, 14, 14, 14, 14, 14, 14 ],
               [ 15, 15, 15, 15, 15, 15, 15, 15 ],
               [ 16, 16, 16, 16, 16, 16, 16, 16 ],
             ]

// up right axes (17...31)                
let uAxis =  [ [ 17, 18, 19, 20, 21, 22, 23, 24 ],
               [ 18, 19, 20, 21, 22, 23, 24, 25 ],
               [ 19, 20, 21, 22, 23, 24, 25, 26 ],
               [ 20, 21, 22, 23, 24, 25, 26, 27 ],
               [ 21, 22, 23, 24, 25, 26, 27, 28 ],
               [ 22, 23, 24, 25, 26, 27, 28, 29 ],
               [ 23, 24, 25, 26, 27, 28, 29, 30 ],
               [ 24, 25, 26, 27, 28, 29, 30, 31 ],
             ]

// down right axes (32...46)                
let dAxis = [ [ 39, 40, 41, 42, 43, 44, 45, 46 ],
              [ 38, 39, 40, 41, 42, 43, 44, 45 ],
              [ 37, 38, 39, 40, 41, 42, 43, 44 ],
              [ 36, 37, 38, 39, 40, 41, 42, 43 ],
              [ 35, 36, 37, 38, 39, 40, 41, 42 ],
              [ 34, 35, 36, 37, 38, 39, 40, 41 ],
              [ 33, 34, 35, 36, 37, 38, 39, 40 ],
              [ 32, 33, 34, 35, 36, 37, 38, 39 ],
            ]

// Set of axis numbers for each [row][col] of the board                  
let axes = (0..<8).map()
           { 
             row in (0..<8).map()
             { Set([ vAxis[row][$0], hAxis[row][$0], uAxis[row][$0], dAxis[row][$0] ]) }
           }

// position of each queen ( column number at each row )                  
var queenCols = [5, 3, 6, 0, 7, 1, 4, 2]

// Check if each queen in queenCols is on its own 4 axes 
// We will have 32 (8 x 4) different axes used if no queen aligns with another

let fullCover = queenCols.enumerated()
                .reduce(Set<Int>()){ $0.union(axes[$1.0][$1.1]) }
                .count == 32

This "fullCover" check can be used in a brute force loop on all 16,777,216 combinations or it can be refined to perform incremental checks in an optimized search tree. (BTW the brute force solution takes only 80 seconds to compute on a MacBook Pro)

So, in the end, you can avoid for loops altogether.

[EDIT] function to find the 92 solutions in a brute force loop:

public func queenPositions() -> [[Int]]
{
   var result : [[Int]] = []
   let rows   : [Int]   = Array(0..<8)
   for i in 0..<16777216
   {
      var N:Int = i
      let queenCols = rows.map{ _ -> Int in let col = N % 8; N = N / 8; return col}
      let fullCover = queenCols.enumerated()
                      .reduce(Set<Int>()){ $0.union(axes[$1.0][$1.1]) }
                      .count == 32
      if fullCover { result.append(queenCols) }
   }
   return result
}

[EDIT2] Using the set matrices in an optimized tree search produces the 92 solutions in 0.03 second.

Here is the optimized (and generic) function:

public func queenPositions2(boardSize:Int = 8) -> [[Int]]
{
   let vAxis     = (0..<boardSize).map{ _ in (0..<boardSize).map{$0} }
   let hAxis     = (0..<boardSize).map{ Array(repeating:$0+boardSize, count:boardSize) }
   let uAxis     = (0..<boardSize).map{ row in (0..<boardSize).map{ 2 * boardSize + row + $0} }
   let dAxis     = (0..<boardSize).map{ row in (0..<boardSize).map{ 5 * boardSize - row + $0} }
   let axes      = (0..<boardSize).map()
                   { 
                     row in (0..<boardSize).map()
                     { Set([ vAxis[row][$0], hAxis[row][$0], uAxis[row][$0], dAxis[row][$0] ]) }
                   }

   var result    : [[Int]] = []
   var queenCols : [Int]   = Array(repeating:0,          count:boardSize)
   var colAxes             = Array(repeating:Set<Int>(), count:boardSize)
   var queenAxes           = Set<Int>()
   var row                 = 0
   while row >= 0
   {          
      if queenCols[row] < boardSize
      {
         let newAxes = axes[row][queenCols[row]]
         if newAxes.isDisjoint(with: queenAxes)
         {
            if row == boardSize - 1 
            { 
              result.append(queenCols)
              queenCols[row] = boardSize
              continue
            }
            else
            { 
              colAxes[row] = newAxes
              queenAxes.formUnion(newAxes)
              row += 1
              queenCols[row] = 0
              continue
            }
         }
      }
      else
      {
         row -= 1
         if row < 0 { break }
      }
      queenAxes.subtract(colAxes[row])
      colAxes[row] = Set<Int>()
      queenCols[row] += 1 

   }
   return result
}

Given a 10x10 board, the 724 solutions are generated in 0.11 second.

[EDIT3] one liner "for loop" ...

You can generate an array of (row,column) coordinate for the 4 axes of a given position and use that as your data in the for loop:

func isPlaceable(row: Int, column: Int) -> Bool 
{
   var coverage  = (0..<8).map{($0,column)}  // horizontal
       coverage += (0..<8).map{(row,$0)}     // vertical
       coverage += zip((max(0,row-column)..<8),(max(0,column-row)..<8)) // diagonal down
       coverage += zip((0...min(7,row+column)).reversed(),(max(0,column+row-7)..<8)) // diagonal up

   // return !coverage.contains{solution[$0][$1] == 1}   

   for (r,c) in coverage
   { 
      if solution[r][c] == 1 { return false }
   }             
   return true

}

It feels wasteful to rebuild the whole coverage list every time though. I would compute it once for every coordinate and place it in a row/column matrix for reuse in the isPlaceable() function.

Thanks Alain for an alternative solution. It is really good. My question was just to wrap the for loop condition in a single line.

Collectives™ on Stack Overflow

Multiple For Loop condition in Swift

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related