ドットボックス 3×3 必勝
Dots&Boxesという外国のゲームの3×3の必勝手順を調べました。
結果は後手必勝となったんですが、問題はプログラムを走らせるとあまりにも早く結果が出るんですよね(-_-;)
プログラムが間違ってるのか私が間違っているのか・・・
#include<stdio.h> bool dotbox(int *c); bool turn(int *c); void calq(int *c, bool *q); void calsq(int s, int *sq); bool winlose(int *c); void printc(int *c); int main(){ int i; int c[24]; int result; for (i = 0; i < 24; i++){ c[i] = -1; } result = dotbox(c); printf("%d\n", result); return 0; } bool dotbox(int *c){ int i,j,k; bool t; for (k = 0; k < 24; k++){ if (c[k] == -1) break; } if (k == 24){ return winlose(c); }else{ for (i = 0; i < 24; i++){ for (j = 0; j < 24; j++){ if (c[j] == i) break; } if (j == 24){ t = turn(c); c[k] = i; //printc(c); if (t == dotbox(c)){ c[k] = -1; return t; } } } return !turn(c); } } bool turn(int *c){ int i, j; int sq[9] = {}; bool turn = 0, turnflag = 0; for (i = 0; i < 24; i++){ if (c[i] == -1) break; calsq(c[i], sq); for (j = 0; j < 9; j++){ if (sq[j] == 4){ sq[j]++; turnflag = 1; } } if (turnflag == 1){ turn = !turn; turnflag = 0; } turn = !turn; } return turn; } void calq(int *c, bool *q){ int i, j; int sq[9] = {}; bool turn=0,turnflag=0; for (i = 0; i < 24; i++){ calsq(c[i], sq); for (j = 0; j < 9; j++){ if (sq[j] == 4){ q[j] = turn; sq[j]++; turnflag = 1; } } if (turnflag == 1){ turn = !turn; turnflag = 0; } turn = !turn; } } void calsq(int s, int *sq){ if (s == 0 || s == 1 || s == 12 || s == 15) sq[0]++; if (s == 1 || s == 2 || s == 13 || s == 16) sq[1]++; if (s == 2 || s == 3 || s == 14 || s == 17) sq[2]++; if (s == 4 || s == 5 || s == 15 || s == 18) sq[3]++; if (s == 5 || s == 6 || s == 16 || s == 19) sq[4]++; if (s == 6 || s == 7 || s == 17 || s == 20) sq[5]++; if (s == 8 || s == 9 || s == 18 || s == 21) sq[6]++; if (s == 9 || s == 10 || s == 19 || s == 22) sq[7]++; if (s == 10 || s == 11 || s == 20 || s == 23) sq[8]++; } bool winlose(int *c){ int i; bool q[9]; calq(c, q); int sen=0, kou=0; for (i = 0; i < 9; i++){ if (q[i] == 0) sen++; else kou++; } if (sen>kou) return 0; else return 1; } void printc(int *c){ int i; for (i = 0; i < 24; i++){ printf("%d,", c[i]); } printf("\n"); }