N-Queens

shriyanshi24jindal

Mar 30th, 2026

124

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 17.11 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
1. create a board matrix [n][n], assign every cell with character '.'
2. take boolean[][] visited matrix to keep track of current cell
3. call function placeQueens() by passing, board, visited, column index as 0 in params
4. In placeQueens() :
- iteratre over a row one by one to fill the valid positions with Queen 'Q'
- before filling check if current cell is valid cell or not by calling another function isValid()
- if it's valid cell, then assign Queen 'Q' at that position and call placeQueens() again by increment column++
- to backtrack asisgn cell with character '.'
- base condition will be when you reach last column of the board, then add construct result in format of string and add to list
5. in isValid() :
- checking for top-left diagonal attack:
- run a loop until row >=0 and col >=0
- if any cell [row][col] has Queen already placed, return false
- else decrement row-- and col--
- checking for left attack:
- run a loop until col >=0
- if any cell [row][col] has Queen already placed, return false
- else decrement col--
- checking for bottom-left diagonal attack:
- run a loop until row <n and col >=0
- if any cell [row][col] has Queen already placed, return false
- else decrement col-- and row++
- else return true
*/
public boolean isValid(int row,int col,char[][] board)
{
int dup_row=row,dup_col=col;
// checking for top-left diagonal attack
while(row>=0 && col>=0)
{
if(board[row][col]=='Q')
return false;
row--;
col--;
}
// checking for left attack
row=dup_row;
col=dup_col;
while(col>=0)
{
if(board[row][col]=='Q')
return false;
col--;
}
// checking for bottom-left diagonal attack
row=dup_row;
col=dup_col;
while(row<board.length && col>=0)
{
if(board[row][col]=='Q')
return false;
row++;
col--;
}
return true;
}
public List<String> construct(char[][] board)
{
List<String> ans=new ArrayList<String>();
for(int i=0;i<board.length;i++)
{
String s=new String(board[i]);
ans.add(s);
}
return ans;
}
public void placeQueen(int col,char[][] board,List<List<String>> ans)
{
if(col==board.length)
{
ans.add(construct(board));
return;
}
for(int row=0;row<board.length;row++)
{
if(isValid(row,col,board))
{
board[row][col]='Q';
placeQueen(col+1,board,ans);
board[row][col]='.';
}
}
}
public List<List<String>> solveNQueens(int n)
{
List<List<String>> ans=new ArrayList<>();
char[][] board=new char[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
board[i][j]='.';
}
}
int[][] visited=new int[n][n];
placeQueen(0,board,ans);
return ans;
}
}

RAW Paste Data Copied

class Solution {
    /**
    1. create a board matrix [n][n], assign every cell with character '.'
    2. take boolean[][] visited matrix to keep track of current cell
    3. call function placeQueens() by passing, board, visited, column index as 0 in params
    4. In placeQueens() :
        - iteratre over a row one by one to fill the valid positions with Queen 'Q'
        - before filling check if current cell is valid cell or not by calling another function isValid()
        - if it's valid cell, then assign Queen 'Q' at that position and call placeQueens() again by increment column++
        - to backtrack asisgn cell with character '.'
        - base condition will be when you reach last column of the board, then add construct result in format of string and add to list
    5. in isValid() :
        - checking for top-left diagonal attack:
            - run a loop until row >=0 and col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement row-- and col--
        
        - checking for left attack:
            - run a loop until col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement col--

- checking for bottom-left diagonal attack:
            - run a loop until row <n and col >=0
            - if any cell [row][col] has Queen already placed, return false
            - else decrement col-- and row++
        - else return true
    */
    public boolean isValid(int row,int col,char[][] board)
    {
        int dup_row=row,dup_col=col;
        // checking for top-left diagonal attack
        while(row>=0 && col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            row--;
            col--;
        }
        // checking for left attack
        row=dup_row;
        col=dup_col;
        while(col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            col--;
        }
        // checking for bottom-left diagonal attack
        row=dup_row;
        col=dup_col;
        while(row<board.length && col>=0)
        {
            if(board[row][col]=='Q')
                return false;
            row++;
            col--;
        }
        return true;
    }
    public List<String> construct(char[][] board)
    {
        List<String> ans=new ArrayList<String>();
        for(int i=0;i<board.length;i++)
        {
            String s=new String(board[i]);
            ans.add(s);
        }
        return ans;
    }

public void placeQueen(int col,char[][] board,List<List<String>> ans)
    {
        if(col==board.length)
        {
            ans.add(construct(board));
            return;
        }
        for(int row=0;row<board.length;row++)
        {
            if(isValid(row,col,board))
            {
                board[row][col]='Q';
                placeQueen(col+1,board,ans);
                board[row][col]='.';
            }
        }
    }
    
    public List<List<String>> solveNQueens(int n) 
    {
        List<List<String>> ans=new ArrayList<>();
        char[][] board=new char[n][n];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                board[i][j]='.';
            }
        }
        int[][] visited=new int[n][n];
        placeQueen(0,board,ans);
        return ans;
    }
}