AtCoder Regular Contest #001 C - パズルのお手伝い

http://arc001.contest.atcoder.jp/tasks/arc001_3

#概要
8クイーン問題
8*8のチェス盤に、縦横斜めにクイーンがないように8個置くことが目標
あらかじめいくつか置いた状態が与えられるので、それに追加して置いて上記目標を満たすパターンのうち1個を出力
どうやっても満たせない場合はその旨を表示
#解いた方針
全パターン試す
盤面のクイーンを置ける場所をビット列にして「000000000001」「000000000010」「000000000011」と順番に列挙、目標を満たしているかチェック（再起呼び出しでこの構想を実現）
その過程で満たしてるものを検出したら即表示
最後まで満たさなかったら、満たしえないと表示

```php:自分の回答.php

<?php
 
//require_once('./debug.php');
 
define('MAP_MAX', 8);
 
// 入力
for($i = 0; $i < 8; $i++){
	fscanf(STDIN, "%s", $input);
	//$input = debug_getInput();
 
	$input = str_replace(array("\r\n","\n","\r"), '', $input);
	$tempArray = str_split($input);
	$map[$i] = $tempArray;
}
// いきなり違反してたらアウト
if(!checkMap($map)) exit("No Answer\n");
 
 
 
// とりあえず、置けるとこに全部置きゃあいいんじゃねえのか？
$result = putQueen($map);
 
if($result === false){
	exit("No Answer\n");
}
else {
	printMap($result);
}
 
exit();
 
 
function printMap($map){
	foreach($map as $line){
		foreach($line as $point){
			echo $point;
		}
		echo "\n";
	}
	echo "\n";
}
 
/****************************
 *
 * 指定した場所に置いていく
 *
 ****************************/
function putQueen($map, $x = 0, $y = 0){
	// (x, y)...(x, MAP_MAX), (x+1, 0)...という風に調べるための工夫
	// 盤面の途中から調べる
	$yIni = $y;
	for($i = 0; $i < MAP_MAX; $i++){
		for($j = $yIni; $j < MAP_MAX; $j++){
			// ある行の途中から調べたら、次の行は先頭から調べる
			$yIni = 0;
			// 置けるなら
			if(checkPoint($map, $i, $j) == 'C'){
				// 仮のマップ
				$mapTemp = $map;
 
				// 置く
				$mapTemp[$i][$j] = 'Q';
				// 次にも置く
				$nextXY = xyPlus1($i, $j);
				if($nextXY !== false){
					list($nextX, $nextY) = $nextXY;
					$mapTemp = putQueen($mapTemp, $nextX, $nextY);
 
					$result = checkAnswer($mapTemp);
					if($result === false){
						continue;
					} else {
						return $result;
					}
				}
			}
		}
	}
 
	return checkAnswer($map);
}
 
 
 
 
/****************************
 *
 * 次の座標を求める
 *
 ****************************/
function xyPlus1($x, $y){
	$y++;
	// y座標を加えてはみ出したら
	if($y >= MAP_MAX){
		// 次の行の最初へ
		$x++;
		$y = 0;
		// それでx座標もはみ出たら、次のマスはもうない
		if($x >= MAP_MAX) return false;
	}
 
	return array($x, $y);
}
 
/****************************
*
* 正解かどうかを調べる
*
****************************/
function checkAnswer($map){
	if(!is_array($map)) return false;
 
	if(checkQueenAmount($map) >= MAP_MAX && checkMap($map)) return $map;
	return false;
}
 
/****************************
*
* クイーンが何個か調べる
*
****************************/
function checkQueenAmount($map){
	if(!is_Array($map)) return 0;
 
	$count = 0;
	for($i = 0; $i < MAP_MAX; $i++){
		for($j = 0; $j < MAP_MAX; $j++){
			if($map[$i][$j] == 'Q') $count++;
		}
	}
 
	return $count;
}
 
 
/***************************
*
* ゲーム盤が8クイーン問題に違反していないかチェック
*
* return true:違反していない。
* return false:違反している。
*
***************************/
 
function checkMap($map){
	for($i = 0; $i < MAP_MAX; $i++){
		for($j = 0; $j < MAP_MAX; $j++){
			$checkPointResult = checkPoint($map, $i, $j);
			if($checkPointResult === 'B'){
				return false;
			}
		}
	}
 
	return true;
}
 
/***************************
 *
 * ゲームボードの特定の座標の状態を返す
 *
 * return C:何もない。置ける。
 * return E:何もない。置けない。
 * return Q:クイーンがある。違反していない。
 * return B:クイーンがある。違反している。
 *
 ***************************/
function checkPoint($map, $x, $y){
	$patterns = array(
		array(1,1),
		array(1,-1),
		array(-1,1),
		array(-1,-1),
	);
 
	// クイーンがあるパターン
	if($map[$x][$y] === 'Q'){
		for($i = 0; $i < MAP_MAX; $i++){
			// 横
			if($i != $y && $map[$x][$i] == 'Q'){
				return 'B';
			}
			// 縦
			if($i != $x && $map[$i][$y] == 'Q'){
				return 'B';
			}
			// 斜め
			foreach($patterns as $pattern){
				$xNew = $x+$i*$pattern[0];
				$yNew = $y+$i*$pattern[1];
				if($xNew != $x && $yNew != $y &&
					0 <= $xNew && $xNew < MAP_MAX &&
					0 <= $yNew && $yNew < MAP_MAX &&
					$map[$xNew][$yNew] == 'Q'){
					return 'B';
				}
			}
 
		}
		return 'Q';
	}
	// ないパターン
	else{
		for($i = 0; $i < MAP_MAX; $i++){
			// 横
			if($i != $y && $map[$x][$i] == 'Q'){
				return 'E';
			}
			// 縦
			if($i != $x && $map[$i][$y] == 'Q'){
				return 'E';
			}
			// 斜め
			foreach($patterns as $pattern){
				$xNew = $x+$i*$pattern[0];
				$yNew = $y+$i*$pattern[1];
				if($xNew != $x && $yNew != $y &&
					0 <= $xNew && $xNew < MAP_MAX &&
					0 <= $yNew && $yNew < MAP_MAX &&
					$map[$xNew][$yNew] == 'Q'){
					return 'E';
				}
			}
		}
		return 'C';
	}
}
 
?>

```