井字棋博弈问题

伪代码如下：

//1表示胜利 -1表示失败 0表示平局func(局面){tag = -1;for(所有可能要走的情况){试走 -> 新局面 s;t = func(s); if(t == -1) return 1;if(t == 0) tag = 0;}return tag;}

流程分析如下：

实现代码如下：

package com.rjxy.test;public class _TicTacToe {//判断是否赢下的方法public static int judge(int[][] arr) {{if(arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2] && arr[0][0] == arr[2][2]) {return 1;}if(arr[0][2] == arr[1][1] && arr[1][1] == arr[0][2] && arr[3][0] == arr[0][2]) {return 1;}for(int i=0;i<arr.length;i++) {if(arr[i][0] == arr[i][1] && arr[i][0] == arr[i][2] && arr[i][1] == arr[i][2]) {return 1;}if(arr[0][i] == arr[1][i] && arr[0][i] == arr[2][i] && arr[1][i] == arr[2][i]) {return 1;}}}return 0;}public static int func(int[][] arr,boolean b) {int tag = -1; //int t ;boolean key = b;//遍历每种要走的局面for(int i = 0; i<3; i++) {for(int j = 0; j<3; j++) {//试走之前看看能不能走 发现不能就结束本次递归调用 返回信息{if(arr[0][0] == arr[1][1] && arr[1][1] == arr[2][2] && arr[0][0] == arr[2][2] && arr[0][0]!=0) {return -1;}if(arr[0][2] == arr[1][1] && arr[1][1] == arr[0][2] && arr[2][0] == arr[0][2] && arr[0][2]!=0) {return -1;}for(int m=0;m<arr.length;m++) {if(arr[m][0] == arr[m][1] && arr[m][0] == arr[m][2] && arr[m][1] == arr[m][2] && arr[m][0]!=0) {return -1;}if(arr[0][m] == arr[1][m] && arr[0][m] == arr[2][m] && arr[1][m] == arr[2][m] && arr[0][m]!=0) {return -1;}}}//int t;//如果为能走 也就是第一个 if 则返回 1if(arr[i][j] == 0) {//试走 根据走的不同传递不同的值及局面 而后根据返回结果判断if(!key) {arr[i][j] = 1;int t = func(arr,!key);//key = true;arr[i][j] = 0;if(t == -1) {//System.out.println("走"+i+j);return 1;}if(t == 0) tag = 0;}else {arr[i][j] = 2;int t = func(arr,!key);//key = false;arr[i][j] = 0;if(t == -1) {//System.out.println("走"+i+j);return 1;}if(t == 0) tag = 0;}//tag = func(arr,key);}else if(i == 2 && j ==2 && arr[i][j] != 0 && arr[j][j] != 0){if(tag == -1 && judge_0(arr) || tag == 0 ) {//数组没有零返回true//System.out.println("走"+i+j);return 0;}else if(tag == -1 && !judge_0(arr)) {return -1;}else return -1;}else {continue;}//if(tag == -1) {////System.out.println("走"+i+j);//return 1;//}//if(tag == 0) tag = 0;}}return tag;}public static boolean judge_0(int[][] arr) {// TODO Auto-generated method stubfor(int i=0;i<3;i++) {for(int j=0;j<3;j++) {if(arr[i][j]==0) {return false;}}}return true;}public static void main(String[] args) {int[][] situation0 = new int[][]{{1,2,0},{0,1,0},{0,0,2}};int[][] situation1 = new int[][]{{1,1,2},{0,2,0},{1,0,0}};int[][] situation2 = new int[][]{{1,0,2},{0,0,0},{2,1,2}};int[][] situation3 = new int[][]{{1,0,1},{2,1,0},{0,0,2}};int[][] situation4 = new int[][]{{1,2,0},{0,0,0},{0,0,0}};//System.out.println(situation.length);System.out.println(func(situation0,false)); //在情况1下，X是必赢的//System.out.println();System.out.println(func(situation1,true)); //在情况2下，O顶多走平//System.out.println();System.out.println(func(situation2,false));//在情况3下，O是必赢的 X必输//System.out.println();System.out.println(func(situation3,true)); //在情况4下，O必输//System.out.println();System.out.println(func(situation4,false)); //在情况5下 （1，0）是必胜的招}}

运行结果：