Showing posts with label Data Structures and Algorithms. Show all posts
Showing posts with label Data Structures and Algorithms. Show all posts

Solving the N-Queens Problem in C# | Print all possible solutions to N–Queens problem in C#

The N–queens puzzle is the problem of placing N chess queens on an N × N chessboard so that no two queens threaten each other. Thus, the solution requires that no two queens share the same row, column, or diagonal.

N-Queens is a tricky problem. To solve this problem efficiently, it requires knowing the backtracking algorithm. Basically, the problem is to place N queens on an NxN chessboard. So in this article, we will discuss how to solve the N-Queens problem using a backtracking algorithm.


C# Code

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace ConsoleApp1

{

    class Program

    {

        const int N = 4;

        static void Main(string[] args)

        {

            int count = 0;

            int[,] board = new int[N, N];

 

            //Initialize the board array to 0

            for (int i = 0; i < N; i++)

            {

                for (int j = 0; j < N; j++)

                {

                    board[i, j] = 0;

                }

            }

 

            //Initialize the pointer array

            int[] pointer = new int[N];

            for (int i = 0; i < N; i++)

            {

                pointer[i] = -1;

            }

 

            //Implementation of Back Tracking Algorithm

            for (int j = 0; ;)

            {

                pointer[j]++;

                //Reset and move one column back

                if (pointer[j] == N)

                {

                    board[pointer[j] - 1, j] = 0;

                    pointer[j] = -1;

                    j--;

                    if (j == -1)

                    {

                        Console.WriteLine("all possible solutions to N–Queens problem are done");

                        break;

                    }

                }

                else

                {

                    board[pointer[j], j] = 1;

                    if (pointer[j] != 0)

                    {

                        board[pointer[j] - 1, j] = 0;

                    }

                    if (SolutionCheck(board))

                    {

                        j++;//move to next column

                        if (j == N)

                        {

                            j--;

                            count++;

                            Console.WriteLine("Solution" + count.ToString() + ":");

                            for (int p = 0; p < N; p++)

                            {

                                for (int q = 0; q < N; q++)

                                {

                                    Console.Write(board[p, q] + " ");

                                }

                                Console.WriteLine();

                            }

                        }

                    }

                }

            }

 

            Console.ReadLine();

        }

        public static bool SolutionCheck(int[,] board)

        {

            //Row check

            for (int i = 0; i < N; i++)

            {

                int sum = 0;

                for (int j = 0; j < N; j++)

                {

                    sum = sum + board[i, j];

                }

                if (sum > 1)

                {

                    return false;

                }

            }

            //Main diagonal check

            //above

            for (int i = 0, j = N - 2; j >= 0; j--)

            {

                int sum = 0;

                for (int p = i, q = j; q < N; p++, q++)

                {

                    sum = sum + board[p, q];

                }

                if (sum > 1)

                {

                    return false;

                }

            }

            //below

            for (int i = 1, j = 0; i < N - 1; i++)

            {

                int sum = 0;

                for (int p = i, q = j; p < N; p++, q++)

                {

                    sum = sum + board[p, q];

                }

                if (sum > 1)

                {

                    return false;

                }

            }

            //Minor diagonal check

            //above

            for (int i = 0, j = 1; j < N; j++)

            {

                int sum = 0;

                for (int p = i, q = j; q >= 0; p++, q--)

                {

                    sum = sum + board[p, q];

                }

                if (sum > 1)

                {

                    return false;

                }

            }

            //below

            for (int i = 1, j = N - 1; i < N - 1; i++)

            {

                int sum = 0;

                for (int p = i, q = j; p < N; p++, q--)

                {

                    sum = sum + board[p, q];

                }

                if (sum > 1)

                {

                    return false;

                }

            }

            return true;

        }

    }

 

}

 


Output





Sudoku Problem Solve in C# | sudoku solver 9x9 in C#

 

In this article, we're going to look at Sudoku puzzle and algorithms used for solving it.

The Sudoku Puzzle

Simply put, Sudoku is a combinatorial number placement puzzle with 9 x 9 cell grid partially filled in with numbers from 1 to 9. The goal is to fill remaining, blank fields with the rest of numbers so that each row and column will have only one number of each kind.

What's more, every 3 x 3 subsection of the grid can't have any number duplicated as well. The level of difficulty naturally rises with the number of blank fields in each board.

 

Problem Board

8 . . . . . . . . 
. . 3 6 . . . . . 
. 7 . . 9 . 2 . . 
. 5 . . . 7 . . . 
. . . . 4 5 7 . . 
. . . 1 . . . 3 . 
. . 1 . . . . 6 8 
. . 8 5 . . . 1 . 
. 9 . . . . 4 . .
 
 Solved Board

And, to spoil the solution quickly – the correctly solved puzzle will give us the following result:

8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

 

C# code

static void Main(string[] args)

        {

            var sudoku = new char[,]

    {

        { '8', '.', '.', '.', '.', '.', '.', '.', '.' },

        { '.', '.', '3', '6', '.', '.', '.', '.', '.' },

        { '.', '7', '.', '.', '9', '.', '2', '.', '.' },

        { '.', '5', '.', '.', '.', '7', '.', '.', '.' },

        { '.', '.', '.', '.', '4', '5', '7', '.', '.' },

        { '.', '.', '.', '1', '.', '.', '.', '3', '.' },

        { '.', '.', '1', '.', '.', '.', '.', '6', '8' },

        { '.', '.', '8', '5', '.', '.', '.', '1', '.' },

        { '.', '9', '.', '.', '.', '.', '4', '.', '.' }

    };

            solveSudoku(sudoku);

            Console.ReadLine();

        }

 

        public static void solveSudoku(char[,] sudokuBoard)

        {

            if (sudokuBoard == null || sudokuBoard.Length == 0)

                return;

            Problemsolver(sudokuBoard);

        }

        private static bool Problemsolver(char[,] sudokuBoard)

        {

            for (int i = 0; i < sudokuBoard.GetLength(0); i++)

            {

                for (int j = 0; j < sudokuBoard.GetLength(1); j++)

                {                 

 

                    if (sudokuBoard[i, j] == '.')

                    {

                        for (char c = '1'; c <= '9'; c++)

                        {

                            if (isValid(sudokuBoard, i, j, c))

                            {

                                sudokuBoard[i, j] = c;

                                

                                if (Problemsolver(sudokuBoard))

                                    return true;

                                else

                                    sudokuBoard[i, j] = '.';

                            }

                        }

                        return false;

                    }

                }

            }

            for (int i = 0; i < sudokuBoard.GetLength(0); i++)

            {

                for (int j = 0; j < sudokuBoard.GetLength(1); j++)

                {

                    Console.Write(sudokuBoard[i, j] + " ");

                }

                Console.Write(Environment.NewLine);

            }

 

            return true;

        }

        private static bool isValid(char[,] board, int row, int col, char c)

        {

            for (int i = 0; i < 9; i++)

            {

                //check row 

                if (board[i, col] != '.' && board[i, col] == c)

                    return false;

                //check column 

                if (board[row, i] != '.' && board[row, i] == c)

                    return false;

                //check 3*3 block 

                if (board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] != '.' && board[3 * (row / 3) + i / 3, 3 * (col / 3) + i % 3] == c)

                    return false;

            }

            return true;

        }


Output