2020/07/07 postscript The execution result of the program was added.
Tools used: (C) |"Online execution environment" that can be programmed and executed with a browser| paiza.IO
#include <stdio.h>
/*Function that returns an absolute value*/
int abs(int a)
{
if (a < 0)
return a * -1;
else
return a;
}
/*Check vertical and diagonal(The horizontal axis is indicated by the variable itself, so the horizontal axis does not overlap.) */
int check(int q1, int q2, int q3, int q4, int q5, int q6, int q7, int q8)
{
if (
/*Check vertical*/
(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) &&
/*Check diagonally*/
(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
2020/06/11 postscript @Fujitanozomu commented on the code for N Queens. Please see the comment section. Thank you very much.
#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++;
}
}
/*Add d vertically, horizontally and diagonally from any point on the board*/
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;
}
/*An image of stacking cushions on a chess board, three-dimensional processing*/
for (col = 0; col < 8; col++)
{
if (board[row][col] == 0)
{
/* board[row][col]Place the queen in the position of*/
queen_position[row] = col;
/*Place a cushion in a place where you cannot use it vertically, horizontally and diagonally.+1 */
change_board(board, row, col, 1);
/*Position the queen on the next line*/
set_queen(queen_position, board, row + 1);
/*Stacked cushions-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
In (1), it became clear that the premise that there are queens in all columns is important in considering this problem.
③ change_board function is intuitive but redundant.
I was able to notice from this problem that the two-dimensional array is doing a tertiary process. Not only true and false, but by adding 1 it is possible to reduce the number of cases and it is smart.
Recommended Posts