Sudoku Solver, N-Queens, N-Queens II

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

Solution

• for each tuple that’s not a number already, try 1-9 numbers
• if the board is still valid after placing the number, place it for now
• continue to solve board, only if all number placed are valid can we return true
• if we reached unvalid board, redo by setting the numbers to ‘.’

 public void solveSudoku(char[][] board){
  	solver(board);
  }
  
  public boolean solver(char[][] board){
  	
      for(int i=0; i<board.length; i++){
          for(int j=0; j<board[0].length; j++){
          	if(board[i][j]=='.'){
          		for(char k='1'; k<='9'; k++){
          			if(isValidSudoku(board, i, j, k)){
              			board[i][j]=k; //place number if valid
          				if(solver(board))
          					{
          						return true; //if after placed still can be solved
          					}
          				else{
              				board[i][j]='.'; //else redo
              			}
          			}
          		}
          		return false;
          	}
          }
      }
return true;
  }
  
  public boolean isValidSudoku(char[][] board, int row, int col, char tmp) {
      //row
      for(int i=0; i<board[0].length;i++){
          if(board[row][i]==tmp) return false;
      }
      //col
      for(int i=0; i<board.length;i++){
      	if(board[i][col]==tmp) return false;
      }
      //tuple
      for(int m=row/3*3;m<3+row/3*3;m++){
          for(int n=col/3*3;n<3+col/3*3;n++){
              if(board[m][n]==tmp) return false;
          }
      }
      return true;
  }

---

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution

• Very interesting problem: The queen can be moved any number of unoccupied squares in a straight line vertically, horizontally, or diagonally. So easily we come to the conclusion that each row can only stand 1 queen, as well as each column, diagonal.

• Because of the previous observation, we can use a 1D array to store the positions, instead of using 2D array.
  ColforRow[i] records the queen in row i is in which column

• For each row, try all columns and if is valid, check for next row

• When row == n, all rows have found their queens, these are valid solutions

• What are valid positions for current row? Only need to check column and diagonal

public static List<List<String>> solveNQueens(int n) {
   	List<List<String>> res=new ArrayList<List<String>>();
   	solve(res, n, 0, new int[n]);
   	return res;
   } 
   
   private static void solve(List<List<String>> res, int n, int row, int[] ColforRow){
   	if(row==n){
   		ArrayList<String> rowitem=new ArrayList<String>();
   		for(int i=0;i<n;i++){	
   			StringBuilder rowstring = new StringBuilder();
   			for(int j=0;j<n;j++){	
   				if(ColforRow[i]==j){
   					rowstring.append('Q');
   				}
   				else{
   					rowstring.append('.');
   				}
   			}
   			rowitem.add(rowstring.toString());
   		}
   		res.add(rowitem);
   		return;
   	}
   	for(int i=0;i<n;i++){
   		ColforRow[row] = i;
   		if(isValid(row, ColforRow)){
   			solve(res, n, row+1, ColforRow);
   		}
   	}
   }
   
   private static boolean isValid(int row, int[] ColforRow){
   	for(int i=0;i<row;i++){
   		if(ColforRow[row]==ColforRow[i] || Math.abs(ColforRow[row]-ColforRow[i])==row-i) // if same column, or same diagonal
   			return false;
   	}
   	return true;
   }

---

N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

Solution

• Add count when a new solution is found (row==n)

public static int totalNQueens(int n) {
      int[] count={0};
  	solve(n, 0, new int[n], count);
  	return count[0];
  }
  private static void solve(int n, int row, int[] ColforRow, int[] count){
  	if(row==n){
  		count[0]+=1;
  		return;
  	}
  	for(int i=0;i<n;i++){
  		ColforRow[row] = i;
  		if(isValid(row, ColforRow)){
  			solve(n, row+1, ColforRow, count);
  		}
  	}
  }
  
  private static boolean isValid(int row, int[] ColforRow){
  	for(int i=0;i<row;i++){
  		if(ColforRow[row]==ColforRow[i] || Math.abs(ColforRow[row]-ColforRow[i])==row-i) // if same column, or same diagonal
  			return false;
  	}
  	return true;
  }