2020/07/07 postscript Ajout du résultat d'exécution du programme.
Les outils utilisés: (C) |"Environnement d'exécution en ligne" qui peut être programmé et exécuté avec un navigateur| paiza.IO
#include <stdio.h>
/*Fonction qui renvoie une valeur absolue*/
int abs(int a)
{
if (a < 0)
return a * -1;
else
return a;
}
/*Vérifiez la verticale et la diagonale(Puisque l'axe horizontal est indiqué par la variable elle-même, l'axe horizontal ne se chevauche pas.) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{
if (
/*Vérifier la verticale*/
(q1 != q2) &&
(q1 != q3) &&
(q1 != q4) &&
(q1 != q5) &&
(q1 != q6) &&
(q1 != q7) &&
(q1 != q8) &&
(q2 != q3) &&
(q2 != q4) &&
(q2 != q5) &&
(q2 != q6) &&
(q2 != q7) &&
(q2 != q8) &&
(q3 != q4) &&
(q3 != q5) &&
(q3 != q6) &&
(q3 != q7) &&
(q3 != q8) &&
(q4 != q5) &&
(q4 != q6) &&
(q4 != q7) &&
(q4 != q8) &&
(q5 != q6) &&
(q5 != q7) &&
(q5 != q8) &&
(q6 != q7) &&
(q6 != q8) &&
(q7 != q8) &&
/*Vérifier en diagonale*/
(abs(q1 - q2) != 1) &&
(abs(q2 - q3) != 1) &&
(abs(q3 - q4) != 1) &&
(abs(q4 - q5) != 1) &&
(abs(q5 - q6) != 1) &&
(abs(q6 - q7) != 1) &&
(abs(q7 - q8) != 1) &&
(abs(q1 - q3) != 2) &&
(abs(q2 - q4) != 2) &&
(abs(q3 - q5) != 2) &&
(abs(q4 - q6) != 2) &&
(abs(q5 - q7) != 2) &&
(abs(q6 - q8) != 2) &&
(abs(q1 - q4) != 3) &&
(abs(q2 - q5) != 3) &&
(abs(q3 - q6) != 3) &&
(abs(q4 - q7) != 3) &&
(abs(q5 - q8) != 3) &&
(abs(q1 - q5) != 4) &&
(abs(q2 - q6) != 4) &&
(abs(q3 - q7) != 4) &&
(abs(q4 - q8) != 4) &&
(abs(q1 - q6) != 5) &&
(abs(q2 - q7) != 5) &&
(abs(q3 - q8) != 5) &&
(abs(q1 - q7) != 6) &&
(abs(q2 - q8) != 6) &&
(abs(q1 - q8) != 7))
{
return 1;
}
return 0;
}
int main(void)
{
int q1, q2, q3, q4, q5, q6, q7, q8;
int count = 0;
for (q1 = 0; q1 < 8; q1++)
for (q2 = 0; q2 < 8; q2++)
for (q3 = 0; q3 < 8; q3++)
for (q4 = 0; q4 < 8; q4++)
for (q5 = 0; q5 < 8; q5++)
for (q6 = 0; q6 < 8; q6++)
for (q7 = 0; q7 < 8; q7++)
for (q8 = 0; q8 < 8; q8++)
if (check(q1, q2, q3, q4, q5, q6, q7, q8))
count++;
printf("%d\n", count);
return 0;
}
Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.14 Memory: 2112000 Result: success
#include <stdio.h>
int count;
int abs(int a)
{
if (a < 0)
return a * -1;
else
return a;
}
int check(int queen_position[8])
{
int i;
int j;
i = 0;
while (i < 8 - 1)
{
j = i + 1;
while (j < 8)
{
if (queen_position[i] == queen_position[j] || abs(queen_position[i] - queen_position[j]) == j - i)
{
return 0;
}
j++;
}
i++;
}
return 1;
}
void set_queen(int queen_position[8], int queen_count)
{
if (queen_count == 8)
{
if (check(queen_position))
{
count++;
}
return;
}
for (int j = 0; j < 8; j++)
{
queen_position[queen_count] = j;
set_queen(queen_position, queen_count + 1);
}
}
int main(void)
{
int queen_position[8];
set_queen(queen_position, 0);
printf("%d\n", count);
return 0;
}
Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.08 Memory: 2120000 Result: success
Post-scriptum 2020/06/11 @Fujitanozomu a commenté le code de N Queen. Veuillez consulter la section des commentaires. Merci beaucoup.
#include <stdio.h>
int count;
void init_board(int board[8][8])
{
int row;
int col;
row = 0;
while (row < 8)
{
col = 0;
while (col < 8)
{
board[row][col] = 0;
col++;
}
row++;
}
}
/*Ajouter d verticalement, horizontalement et en diagonale à partir de n'importe quel point du plateau*/
void change_board(int board[8][8], int row, int col, int d)
{
int i;
int j;
i = 0;
while (i < 8)
{
board[row][i] += d;
board[i][col] += d;
i++;
}
i = row;
j = col;
while (i < 8 && j < 8)
{
board[i][j] += d;
i++;
j++;
}
i = row;
j = col;
while (i >= 0 && j >= 0)
{
board[i][j] += d;
i--;
j--;
}
i = row;
j = col;
while (i < 8 && j >= 0)
{
board[i][j] += d;
i++;
j--;
}
i = row;
j = col;
while (i >= 0 && j < 8)
{
board[i][j] += d;
i--;
j++;
}
}
void set_queen(int queen_position[8], int board[8][8], int row)
{
int col;
if (row == 8)
{
count++;
return;
}
/*Une image d'empilage de coussins sur un échiquier, traitement en trois dimensions*/
for (col = 0; col < 8; col++)
{
if (board[row][col] == 0)
{
/* board[row][col]Placez la reine dans la position de*/
queen_position[row] = col;
/*Placez un coussin dans un endroit où vous ne pouvez pas l'utiliser verticalement, horizontalement et en diagonale.+1 */
change_board(board, row, col, 1);
/*Positionnez la reine sur la ligne suivante*/
set_queen(queen_position, board, row + 1);
/*Coussins empilés-1 */
change_board(board, row, col, -1);
}
}
}
int main(void)
{
int queen_position[8];
int board[8][8];
init_board(board);
set_queen(queen_position, board, 0);
printf("%d\n", count);
return 0;
}
Build time: 0.08 Build exit code: 0 Build result: success Exit code: 0 Time: 0.00 Memory: 2104000 Result: success
Dans (1), il est devenu clair que l'hypothèse selon laquelle il y a des reines dans toutes les colonnes est importante pour considérer ce problème.
③ La fonction change_board est intuitive mais redondante.
J'ai pu remarquer à partir de ce problème que le tableau bidimensionnel effectue un processus tertiaire. Non seulement vrai et faux, mais en ajoutant 1, il est possible de réduire le nombre de cas et c'est intelligent.
Recommended Posts