{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programme Python: Problème De N-Reines\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "donner nombre de reine \n",
      "4\n",
      "1 -\n",
      "\n",
      "0 0 1 0 \n",
      "\n",
      "1 0 0 0 \n",
      "\n",
      "0 0 0 1 \n",
      "\n",
      "0 1 0 0 \n",
      "\n",
      "\n",
      "\n",
      "2 -\n",
      "\n",
      "0 1 0 0 \n",
      "\n",
      "0 0 0 1 \n",
      "\n",
      "1 0 0 0 \n",
      "\n",
      "0 0 1 0 \n",
      "\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "#''' Python3 program to solve N Queen Problem using backtracking '''\n",
    "k = 1\n",
    "print('donner nombre de reine ');\n",
    "n=int(input())\n",
    "# A utility function to print solution \n",
    "def printSolution(board): \n",
    " \n",
    "    global k\n",
    "    print(k, \"-\\n\")\n",
    "    k = k + 1\n",
    "    for i in range(n): \n",
    "        for j in range(n):\n",
    "            print(board[i][j], end = \" \")\n",
    "        print(\"\\n\")\n",
    "    print(\"\\n\") \n",
    " \n",
    " #A utility function to check if a queen can be placed on board[row][col]. Note that this function is called when \"col\" queens are \n",
    "#already placed in columns from 0 to col -1. So we need to check only left side for attacking queens '''\n",
    "def isSafe(board, row, col) :\n",
    "     \n",
    "    # Check this row on left side \n",
    "    for i in range(col): \n",
    "        if (board[row][i]): \n",
    "            return False\n",
    " \n",
    "    # Check upper diagonal on left side \n",
    "    i = row\n",
    "    j = col\n",
    "    while i >= 0 and j >= 0:\n",
    "        if(board[i][j]):\n",
    "            return False;\n",
    "        i -= 1\n",
    "        j -= 1\n",
    " \n",
    "    # Check lower diagonal on left side \n",
    "    i = row\n",
    "    j = col\n",
    "    while j >= 0 and i < n:\n",
    "        if(board[i][j]):\n",
    "            return False\n",
    "        i = i + 1\n",
    "        j = j - 1\n",
    " \n",
    "    return True\n",
    " \n",
    "#''' A recursive utility function to solve N Queen problem '''\n",
    "def placerReines(board, col) :\n",
    "     \n",
    "    #''' base case: If all queens are placed  then return true '''\n",
    "    if (col == n): \n",
    "        printSolution(board) \n",
    "        return True\n",
    " \n",
    "   # ''' Consider this column and try placing this queen in all rows one by one '''\n",
    "    res = False\n",
    "    for i in range(n):\n",
    "     \n",
    "        #''' Check if queen can be placed on board[i][col] '''\n",
    "        if (isSafe(board, i, col)): \n",
    "         \n",
    "            # Place this queen in board[i][col] \n",
    "            board[i][col] = 1; \n",
    " \n",
    "            # Make result true if any placement \n",
    "            # is possible \n",
    "            res = placerReines(board, col + 1) or res; \n",
    " \n",
    "            #''' If placing queen in board[i][col] doesn't lead to a solution, then remove queen from board[i][col] '''\n",
    "            board[i][col] = 0 # BACKTRACK \n",
    "         \n",
    "   # ''' If queen can not be place in any row in  this column col then return false '''\n",
    "    return res\n",
    " \n",
    "#''' This function solves the N Queen problem using Backtracking. It mainly uses placerReines to solve the problem. It returns false if queens \n",
    "#cannot be placed, otherwise return true and prints placement of queens in the form of 1s. Please note that there may be more than one \n",
    "#solutions, this function prints one of the feasible solutions.'''\n",
    "def TrouverReine() :\n",
    " \n",
    "    board = [[0 for j in range(10)] \n",
    "                for i in range(10)]\n",
    " \n",
    "    if (placerReines(board, 0) == False): \n",
    "     \n",
    "        print(\"Solution does not exist\") \n",
    "        return\n",
    "    return\n",
    " \n",
    "# Driver Code \n",
    "TrouverReine() \n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}