複合魔方陣を制約論理プログラム iZ-Cを使って解きます。
複合魔方陣を制約論理プログラム iZ-Cを使って解きます。
-----------------------------------------------------------------------------
make && ./chk_mcons
gcc -Wall -O3 -I. -L. -o chk_mcons chk_mcons.c -L. -liz -L/home/sunasuna/TEST/IZC64/izC_v3_6_1_linux64/lib/
Tue Sep 8 17:51:42 2020
Solution 1 (NbFails = 613):
# . . . . . # #
# . . . . # . .
# # # # # . . .
. # # # # # # #
. . . . # # . .
. # # # # . . #
. . . . . . # .
. . . . . . . .
Solution 2 (NbFails = 613):
# . . . . . # #
# . . . . # . .
# # # # # . . .
. # # # # # # #
. . . . # # . .
. # # # # . # .
. . . . . . . #
. . . . . . . .
Solution 3 (NbFails = 647):
# . . . . # # .
# . . . . . . #
# # # # # . . .
. # # # # # # #
. . . . # # . .
. # # # # . . #
. . . . . . # .
. . . . . . . .
Solution 4 (NbFails = 647):
# . . . . # # .
# . . . . . . #
# # # # # . . .
. # # # # # # #
. . . . # # . .
. # # # # . # .
. . . . . . . #
. . . . . . . .
Nb Fails = 700
Nb Choice Points = 1406
Heap Size = 3072
Elapsed Time = 0.002062s
Tue Sep 8 17:51:42 2020
---------------------------------------------------------------------------------
#include <stdlib.h>
#include <time.h>
#include "iz.h"
#define app1
/********************************************************************************************/
#ifdef app1
#define N 8
int row_1 = {2, 1, 2};
int row_2 = {2, 1, 1};
int row_3 = {1, 5};
int row_4 = {1, 7};
int row_5 = {1, 2};
int row_6 = {2, 4, 1};
int row_7 = {1, 1};
int row_8 = {0};
int col_1 = {1, 3};
int col_2 = {2, 2, 1};
int col_3 = {2, 2, 1};
int col_4 = {2, 2, 1};
int col_5 = {1, 4};
int col_6 = {2, 1, 2};
int col_7 = {3, 1, 1, 1};
int col_8 = {3, 1, 1, 1};
int *row[N] = {row_1, row_2, row_3, row_4, row_5, row_6, row_7, row_8};
int *col[N] = {col_1, col_2, col_3, col_4, col_5, col_6, col_7, col_8};
#endif
/********************************************************************************************/
#ifdef app2
#define N 8
int row_1 = {1, 4};
int row_2 = {2, 2, 2};
int row_3 = {2, 2, 2};
int row_4 = {1, 8};
int row_5 = {1, 2};
int row_6 = {2, 2, 2};
int row_7 = {2, 2, 2};
int row_8 = {1, 4};
int col_1 = {1, 4};
int col_2 = {1, 6};
int col_3 = {3, 2, 1, 2};
int col_4 = {3, 1, 1, 1};
int col_5 = {3, 1, 1, 1};
int col_6 = {3, 2, 1, 2};
int col_7 = {2, 3, 2};
int col_8 = {2, 2, 1};
int *row[N] = {row_1, row_2, row_3, row_4, row_5, row_6, row_7, row_8};
int *col[N] = {col_1, col_2, col_3, col_4, col_5, col_6, col_7, col_8};
#endif
/********************************************************************************************/
#ifdef app4
#define N 8
int row_1 = {1, 4};
int row_2 = {1, 4};
int row_3 = {1, 4};
int row_4 = {1, 4};
int row_5 = {0};
int row_6 = {0};
int row_7 = {0};
int row_8 = {0};
int col_1 = {1, 4};
int col_2 = {1, 4};
int col_3 = {1, 4};
int col_4 = {1, 4};
int col_5 = {0};
int col_6 = {0};
int col_7 = {0};
int col_8 = {0};
int *row[N] = {row_1, row_2, row_3, row_4, row_5, row_6, row_7, row_8};
int *col[N] = {col_1, col_2, col_3, col_4, col_5, col_6, col_7, col_8};
#endif
/********************************************************************************************/
#ifdef app3
#define N 8
int row_1 = {1, 6};
int row_2 = {2, 1, 1};
int row_3 = {2, 1, 1};
int row_4 = {1, 6};
int row_5 = {1, 1};
int row_6 = {1, 1};
int row_7 = {1, 1};
int row_8 = {1, 1};
int col_1 = {1, 8};
int col_2 = {2, 1, 1};
int col_3 = {2, 1, 1};
int col_4 = {2, 1, 1};
int col_5 = {2, 1, 1};
int col_6 = {2, 1, 1};
int col_7 = {1, 2};
int col_8 = {0};
int *row[N] = {row_1, row_2, row_3, row_4, row_5, row_6, row_7, row_8};
int *col[N] = {col_1, col_2, col_3, col_4, col_5, col_6, col_7, col_8};
#endif
/********************************************************************************************/
#ifdef app10
#define N 15
int row_01 = {2, 1, 1};
int row_02 = {2, 2, 2};
int row_03 = {1, 9};
int row_04 = {2, 4, 6};
int row_05 = {2, 1, 7};
int row_06 = {4, 3, 1, 1, 5};
int row_07 = {4, 1, 1, 2, 3};
int row_08 = {2, 2, 5};
int row_09 = {2, 3, 4};
int row_10 = {2, 4, 1};
int row_11 = {2, 3, 1};
int row_12 = {1, 10};
int row_13 = {3, 2, 3, 2};
int row_14 = {1, 7};
int row_15 = {1, 5};
int col_01 = {1, 3};
int col_02 = {2, 1, 1};
int col_03 = {2, 1, 7};
int col_04 = {2, 4, 6};
int col_05 = {2, 2, 6};
int col_06 = {5, 1, 2, 1, 1, 2};
int col_07 = {2, 1, 4};
int col_08 = {3, 1, 2, 4};
int col_09 = {3, 1, 5, 4};
int col_10 = {4, 3, 2, 1, 2};
int col_11 = {2, 8, 3};
int col_12 = {1, 13};
int col_13 = {1, 4};
int col_14 = {1, 3};
int col_15 = {1, 3};
int *row[N] = {row_01, row_02, row_03, row_04, row_05, row_06, row_07, row_08, row_09, row_10,
row_11, row_12, row_13, row_14, row_15};
int *col[N] = {col_01, col_02, col_03, col_04, col_05, col_06, col_07, col_08, col_09, col_10,
col_11, col_12, col_13, col_14, col_15};
#endif
/********************************************************************************************/
/********************************************************************************************/
void printSolution(CSint **allvars, int nbVars)
{
int i, j, n = 0;
static int NbSolution = 0;
printf("\nSolution %d (NbFails = %d):\n", ++NbSolution, cs_getNbFails());
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++){
int nn = cs_getValue(allvars[n++]);
if(nn == 0) printf(" .");
else printf(" #");
}
putchar('\n');
}
/*
for (i = 0; i < N; i++) {
if(cs_getValue(cs_Sigma(&allvars[N * i], N)) == 0) {printf("_\n");}
else
cs_printf("%D\n", cs_Index(&allvars[N * i], N, 1));
}
*/
}
/********************************************************************************************/
/********************************************************************************************/
IZBOOL knownRC(int val, int index, CSint **allvars, int size, void *mat_allvars) {
if(val == 0) return TRUE;
int r = index / N, c = index % N;
CSint *pre_step = cs_Sigma(&allvars[index - c], c + 1);
int step = cs_getMin(pre_step);
int r_p = (index + row[r][step] -1) / N;
if( r != r_p) return FALSE;
return
cs_OccurConstraints(CSINT(row[r][step]), 1, (CSint **)mat_allvars + index, row[r][step]);
}
/********************************************************************************************/
/********************************************************************************************/
IZBOOL knownCR(int val, int index, CSint **allvars, int size, void *mat_allvars) {
if(val == 0) return TRUE;
int r = index / N, c = index % N;
CSint *pre_step = cs_Sigma(&allvars[index - c], c + 1);
int step = cs_getMin(pre_step);
int r_p = (index + col[r][step] -1) / N;
if( r != r_p) return FALSE;
return
cs_OccurConstraints(CSINT(col[r][step]), 1, (CSint **)mat_allvars + index, col[r][step]);
}
/********************************************************************************************/
/********************************************************************************************/
/********************************************************************************************/
int main(int argc, char **argv)
{
clock_t t0 = clock();
time_t nowtime;
CSint *matrixRC[N][N], *edgeRC[N][N];
CSint *matrixCR[N][N], *edgeCR[N][N];
CSint *allvars[N * N];
CSint *all_edgeRC[N * N], *all_edgeCR[N * N];
int i, j, n = 0;
cs_init();
time(&nowtime); printf("%s", ctime(&nowtime));
n = 0;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
allvars[n++] = matrixCR[j][i] = matrixRC[i][j] = cs_createCSint(0, 1);
}
}
for (i = 0; i < N; i++){
edgeRC[i][0] = cs_ReifEQ(matrixRC[i][0], 1);
edgeCR[i][0] = cs_ReifEQ(matrixCR[i][0], 1);
for (j = 1; j < N; j++){
edgeRC[i][j] = cs_ReifEQ(cs_Add(cs_ReifEQ(matrixRC[i][j-1], 0), cs_ReifEQ(matrixRC[i][j], 1)), 2);
edgeCR[i][j] = cs_ReifEQ(cs_Add(cs_ReifEQ(matrixCR[i][j-1], 0), cs_ReifEQ(matrixCR[i][j], 1)), 2);
}
}
for (i = 0; i < N; i++){
cs_OccurConstraints(CSINT(row[i][0]), 1, edgeRC[i], N);
cs_OccurConstraints(CSINT(col[i][0]), 1, edgeCR[i], N);
}
n = 0;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
all_edgeRC[n] = edgeRC[i][j];
all_edgeCR[n++] = edgeCR[i][j];
}
}
for (i = 0; i < N; i++){
int row_sum = 0, col_sum = 0;
for (j = 1; j <= row[i][0]; j++){
row_sum += row[i][j];
}
for (j = 1; j <= col[i][0]; j++){
col_sum += col[i][j];
}
cs_OccurConstraints(CSINT(row_sum), 1, matrixRC[i], N);
cs_OccurConstraints(CSINT(col_sum), 1, matrixCR[i], N);
}
/*
printf("matrixRC \n");
for (i = 0; i < N; i++){
cs_printf("%A\n", matrixRC[i], N);
}
printf("edgeRC \n");
for (i = 0; i < N; i++){
cs_printf("%A\n", edgeRC[i], N);
}
cs_printf("RC: %A\n", &all_edgeRC[0], N * N);
cs_printf("CR: %A\n", &all_edgeCR[0], N * N);
*/
cs_eventKnown(&all_edgeRC[0], N * N, knownRC, (void *)allvars);
CSint *Tallvars[N * N];
n = 0;
for (i = 0; i < N; i++){
for (j = 0; j < N; j++){
Tallvars[n++] = matrixCR[i][j];
}
}
cs_eventKnown(&all_edgeCR[0], N * N, knownCR, (void *)Tallvars);
cs_findAll(allvars, N * N, cs_findFreeVar, printSolution);
cs_printStats();
printf("Elapsed Time = %fs\n", (double) (clock() - t0) / CLOCKS_PER_SEC);
time(&nowtime); printf("%s", ctime(&nowtime));
cs_end();
return EXIT_SUCCESS;
}
