Как я могу преобразовать рекурсию проблемы NQueen в итеративную? - PullRequest
Новая
       14

Как я могу преобразовать рекурсию проблемы NQueen в итеративную?

0 голосов
/ 14 апреля 2019

Я пытаюсь преобразовать рекурсивное решение проблемы Nqueen в итеративное решение.

Я пытался изменить свой код, используя «While» в «solveNQforThisColumn» вместо использования рекурсивной функции. 

'
public class NqueenIter1 {
static final int NN = 4;

public static boolean isSafePositionQ (int board[ ][ ], int row, int col 
) {

//check this row on left
    for(int cCnt = 0; cCnt < col; cCnt++) {
        if(board[row][cCnt]==1) {
            return false;
        }
    }
//check upper diagonal on left
  for(int rCnt = row, cCnt = col; rCnt>=0 && cCnt >=0;rCnt-- , cCnt--) {
        if(board[rCnt][cCnt] ==1)
            return false;
    }
//check lower diagonal on left
for(int rCnt = row, cCnt = col; rCnt < NN && cCnt >=0;rCnt++ , cCnt--) {
        if(board[rCnt][cCnt] ==1)
            return false;
    }

    return true;
}

 public static boolean solveNQforThisColumn( int board[ ][ ], int col ) {

 while(col<NN) {
    for(int rowCnt=0;rowCnt<NN;rowCnt++) {
        if(isSafePositionQ(board,rowCnt,col)) {
            board[rowCnt][col] = 1;
        }
        }
    col ++; 
    }
    if(col==NN) {
        return true;
    }
    return false;
}

public static void main(String[] args) {
    int board[][] = {
            { 0, 0, 0, 0 },
            { 0, 0, 0, 0 },
            { 0, 0, 0, 0 },
            { 0, 0, 0, 0 }
        };

    if(!solveNQforThisColumn(board, 0)) {
        System.out.println("cannot solve the puzzle");
        return;
    }
    printSolution(board);
    return;
    /* A utility function to print solution */
        }
 public static void printSolution( int board[][] ) {
    for(int row=0;row<NN;row++) {
        for(int col=0;col<NN;col++) {
            System.out.print(" "+board[row][col]+" ");
        }
    System.out.println();
    }

    }
 }

`

Я ожидаю выхода

0 0 1 0

1 0 0 0

0 0 0 1

0 1 0 0

но фактический результат равен

1 0 0 0

1 0 0 0

1 0 0 0

1 0 0 0

...