４っの部屋プログラムの改良詳細


１．基本形
　　MonoBas.java　は以下の通り

import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.util.*;

public class MonoBas{
　int N=66;

　class Stat{
　　byte[][] rm=new byte[4][68];
　　public Stat(){}
　　public Stat(Stat bs){
　　　for(int i=0;i<=N;i++){
　　　　for(int r=0;r<4;r++){
　　　　　this.rm[r][i]=bs.rm[r][i];
　　　　}
　　　}
　　}
　　boolean check(int no,int num){
　　　return checkR(no,num)
　　　　&& checkM(no,num)
　　　　&& checkL(no,num);
　　}

　　boolean checkR(int no,int num ){ //大きい順に　num n m　としたとき　
　　　for(int n=num-1;n>0;n--){
　　　　if(rm[no][n]==0) continue;
　　　　for(int m=n-1;m>0;m--){
　　　　　if(rm[no][m]==0) continue;
　　　　　if(n+m==num) return false;
　　　　　if(n+m　　　　}
　　　}
　　　return true;
　　}

　　boolean checkM(int no,int num){　//大きい順に　n num m　としたとき　
　　　for(int n=num+1;n<68;n++){
　　　　if(rm[no][n]==0) continue;
　　　　for(int m=num-1;m>0;m--){
　　　　　if(rm[no][m]==0) continue;
　　　　　if(m+num==n) return false;
　　　　　if(m+num　　　　}
　　　}
　　　return true;
　　}

　　boolean checkL(int no,int num){ //大きい順に　m n num　としたとき　
　　　for(int n=num+1;n<68;n++){
　　　　if(rm[no][n]==0) continue;
　　　　for(int m=n+1;m<68;m++){
　　　　　if(rm[no][m]==0) continue;
　　　　　if(num+n==m) return false;
　　　　　if(num+n　　　　}
　　　}
　　　return true;
　　}
　}

　void solv(){
　　Stat stat=new Stat();
　　stat.rm[0][1]=1;
　　stat.rm[0][2]=2;
　　place(stat);
　}

　boolean place( Stat stat){
　　int p,r;
　　int[] rt={0,0,0,0,0};
　　for(p=1;p<=N;p++){
　　　if( stat.rm[0][p]+stat.rm[1][p]+stat.rm[2][p]+stat.rm[3][p]>0 ) 　
　　　　　　continue; //すでに配分が完了した数
　　　break;
　　}
　　if(p==N+1){　//全ての数の配分が完了
　　　printAns(stat);
　　　return true;
　　}
　　/*　else{ //高速化１の工夫
　　for(int i=p;i<=N;i++){
　　　int rtw=0;
　　　for(r=0;r<4;r++) if(stat.check(r,i)) rtw++;
　　　　if(rtw==0) return false;
　　　}
　　}*/
　　for(r=0;r<4;r++) if(stat.check(r,p)){　//置ける部屋を探す
　　　rt[0]++;rt[r+1]=p;
　　}
　　if(rt[0]==0) return false;　//どこにも置けない
　　for(r=0;r<4;r++){
　　　int pn=rt[r+1];
　　　if(pn==0) continue;
　　　Stat stw=new Stat(stat);
　　　stw.rm[r][pn]=(byte)pn;
　　　if(place(stw)) return true;
　　}
　　return false;
　}
　void printAns(Stat stat){
　　long w=0;
　　System.out.println("Mono"+N );
　　for(int r=0;r<4;r++){
　　　System.out.print("rm="+r+":");
　　　for(int i=1;i<=N;i++){
　　　　int n=stat.rm[r][i];
　　　　if(n==0) continue;
　　　　System.out.print(" "+n);
　　　}
　　　System.out.println();
　　}
　}

　public static void main(String[] args){
　　MonoBas mp=new MonoBas();
　　mp.solv();
　}
}

４っの部屋プログラムの改良部分


Mono66.java で　改善した部分を以下に示す。

　boolean place( Stat stat){
　　node_N++;
　　int p,r;
　　int[] rt={5,0,0,0,0};
　　boolean flg=true;
　　printSts(stat);
　　for(p=stat.rm[0][0];p<=N;p++){//初期値１->stat.rm[0][0]効果小
　　　if( stat.rm[0][p]+stat.rm[1][p]+stat.rm[2][p]+stat.rm[3][p]
>0 ) continue;
　　　int[] rtw=new int[5];
　　　if(flg){　　　//完了してない最初の数設定するフラグ
　　　　flg=false; stat.rm[0][0]=(byte)p;
　　　}
　　　for(r=0;r<4;r++) if(stat.check(r,p)){
　　　　rtw[0]++;rtw[r+1]=p;
　　　}
　　　if(rtw[0]==0) return false;
　　　if(rtw[0]　　　　rt=rtw;
　　　}
　　　if(rt[0]==1) break;//１の工夫を一部失うが効果は勝る
　　}
　　if(rt[0]==5){　//全ての数の配分が完了
　　　printAns(stat);
　　　return true;　　//答えを一つ見つけるとき
　　　//return false;　　//全ての答えを見つけるとき
　　}
　　for(r=0;r<4;r++){
　　　int pn=rt[r+1];
　　　if(pn==0) continue;
　　　Stat stw=new Stat(stat);
　　　stw.rm[r][pn]=(byte)pn;
　　　if(place(stw)) return true;
　　}
　　return false;
　}