またしても解けない問題が出てきたので質問しに来ました。
現在、基本テクニック(ルールによるもの)と単独候補数字、そしてn国同盟まで作りました。
ですが現在、このn国同盟は数字が2つならでき、3つ以上となるとできません。
temporaryFlag()がn国同盟のつもりです。当然ですがtemporaryFlag()の中の2を3や4にしてもできません。
完全にn国同盟ができるようご指摘ください。
おそらく、コードを読んだだけでは何をしているのかすらわからないかと思います。
遠慮なく質問なさってください。
またshow(true,任意の値)で呼び出すと任意の値の現在のフラグの状態を表示できます。
#include "stdafx.h"
#include "stdio.h"
#include <time.h>
#include <iostream>
using namespace std;
#define Size 9
#define dataSize 82
int ban[Size][Size];
int checkedTarget = 0;
bool flagban[Size][Size][Size + 1];//0は使わない
bool IsFill = false;//1箇所でも埋めたか
void resetBan(){
for (int Line = 0; Line < Size; Line++){
for (int Column = 0; Column < Size; Column++){
ban[Line][Column] = 0;
}
}
}
void resetFlag(){
for (int Line = 0; Line < Size; Line++){
for (int Column = 0; Column < Size; Column++){
for (int Number = 1; Number <= Size; Number++)
flagban[Line][Column][Number] = true;//すべての数字の入る可能性をありにする
flagban[Line][Column][0] = false;//0は使わない
}
}
}
void show(bool IsFlagType, int Num){//IsFlagTypeはデバッグ用
cout << endl;
cout << " 1 2 3 4 5 6 7 8 9" << endl;
for (int Line = 0; Line < Size; Line++){
cout << Line + 1 << "0";
for (int Column = 0; Column < Size; Column++){
if (Column == 3 || Column == 6)
cout << " |";//マスの区切り表示
if(IsFlagType && flagban[Line][Column][Num])
cout << " o";
else if(IsFlagType)
cout << " x";
else
cout << " " << ban[Line][Column];//数字の表示
}
if (Line == 2 || Line == 5){
cout << endl;
cout << " ------+-------+------";//マスの区切り表示
}
cout << endl;
}
cout << endl;
}
void showPlace(int Line, int Column, int Num){
cout << "X:" << Column + 1 << " Y:" << Line + 1 << " <=" << Num << endl;//埋めた座標と数字を表示
IsFill = true;
}
//input関連はいずれGUIを使うようものに変更する
void input(){
int add = 0, data = 0;
cout << "データを以下のように入力してください" << endl << "行:5 列:7 数値:8 => 857" << endl << "1000を入力すると終了" << endl;
while (add != 1000){
show(false,0);
cout << "1000を入力すると終了" << endl << "データ:";
cin >> add; //入力
if (add < 10 || add >Size * 100 + Size * 10 + Size){
if (add != 1000)
cout << "入力失敗しました" << endl << "正しく入力してください" << endl;
continue;
}
data = add / 100;
add = add % 100;
ban[add / 10 - 1][add % 10 - 1] = data; //マスに反映
}
}
void input2(){
char c_data[10];
int data[10], ans;
for (int i = 0; i < Size; i++){
cout << i + 1 << "行目のデータを一括で入力してください" << endl << "空白は0を入力してください" << endl;
cin >> c_data;
for (int j = 0; j < Size; j++){
data[j] = c_data[j] - '0'; //数字を数値に変換
ban[i][j] = data[j];
}
show(false,0);
cout << i + 1 << "行目のデータはこれで合っていますか?" << endl << "はい:0を入力, いいえ:0以外を入力" << endl << "Ans: ";
cin >> ans;
if (ans != 0)i--;
else if (i == 8)continue;
}
}
void readData(){
FILE *fp;
char c_data[dataSize];
int Line = 0, Column = 0;
fp = fopen("data.txt", "r");
if (fp == NULL)
cout << "FILE OPEN ERROR1" << endl;
else{
if (fgets(c_data, dataSize, fp) != NULL){
for (int i = 0; i < dataSize - 1; i++){
if (i != 0){
if (i % Size == 0){
Line++;
Column = 0;
}
else
Column++;
}
ban[Line][Column] = c_data[i] - '0'; //数字を数値に変換
}
}
else
cout << "FILE OPEN ERROR2" << endl;
fclose(fp);
}
cout << "読み込んだファイルは以下のようになります" << endl;
show(false,0);
}
void deleteNumFlag(int Line, int Column){
int startLine = Line / 3 * 3;
int startColumn = Column / 3 * 3;
for (int Number = 1; Number <= Size; Number++){
if (flagban[Line][Column][Number]){//チェックする必要がなければチェックしない
for (int x = 0; x < Size; x++){//横方向のチェック
if (Number == ban[Line][x])
flagban[Line][Column][Number] = false;//そのマスのNumberの可能性をなくす
}
for (int y = 0; y < Size; y++){//縦方向のチェック
if (Number == ban[y][Column])
flagban[Line][Column][Number] = false;
}
for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
for (int j = startColumn; j < startColumn + 3; j++){
if (Number == ban[i][j])
flagban[Line][Column][Number] = false;
}
}
}
}
}
int retLineColumn(int Line, int Column, int Num){
int CountX = 0, CountY = 0, CountBox = 0, possibleLine = 10, possibleColumn = 10;
for (int x = 0; x < Size; x++){//横方向のチェック
if (flagban[Line][x][Num]){
possibleColumn = x;//一時的に記憶
CountX++;
}
}
if (CountX == 1){
checkedTarget = 1;//横
return possibleColumn;
}
else if (CountX == 0)
return 99;
for (int y = 0; y < Size; y++){//縦方向のチェック
if (flagban[y][Column][Num]){
possibleLine = y;//一時的に記憶
CountY++;
}
}
if (CountY == 1){
checkedTarget = 2;//縦
return possibleLine;
}
else if (CountY == 0)
return 99;
int startLine = Line / 3 * 3;
int startColumn = Column / 3 * 3;
for (int i = startLine; i < startLine + 3; i++){//ボックス内のチェック
for (int j = startColumn; j < startColumn + 3; j++){
if (flagban[i][j][Num]){
possibleColumn = j;
possibleLine = i;
CountBox++;
}
}
}
if (CountBox == 1){
checkedTarget = 3;//ボックス
return possibleLine * 10 + possibleColumn;
}
else if (CountBox == 0)
return 99;
return 99;
}
void filledGrid(int Line, int Column, int Num, bool IsStart){//埋めたマスのx,yと埋めた数字を引数とする
if (ban[Line][Column] != 0){//改めて空白でないか確認
if(!IsStart)
showPlace(Line, Column, Num);//埋めたマスについて表示
for (int Number = 1; Number <= Size; Number++)//既に埋められたマスのすべての可能性をなくす
flagban[Line][Column][Number] = false;
for (int x = 0; x < Size; x++)//横方向のチェック
flagban[Line][x][Num] = false;//埋めた数字の可能性をなくす
for (int y = 0; y < Size; y++)//縦方向のチェック
flagban[y][Column][Num] = false;//埋めた数字の可能性をなくす
int startLine = Line / 3 * 3;
int startColumn = Column / 3 * 3;
for (int i = startLine; i < startLine + 3; i++)//ボックス内のチェック
for (int j = startColumn; j < startColumn + 3; j++)
flagban[i][j][Num] = false;//埋めた数字の可能性をなくす
}
}
void startFlag(){
for (int Line = 0; Line < Size; Line++){
for (int Column = 0; Column < Size; Column++){
if (ban[Line][Column] != 0)
filledGrid(Line, Column, ban[Line][Column], true);
}
}
}
//このtemporaryFlagがn国同盟のつもりです。
void temporaryFlag(int Line, int Column){//一時的にフラグを折る
int flagCount[Size + 1] = {0,0,0,0,0,0,0,0,0,0};
int startLine = Line / 3 * 3;
int startColumn = Column / 3 * 3;
int ngPosX[Size + 1][2];
int ngPosY[Size + 1][2];
for (int num = 1; num <= Size; num++){
for (int i = startLine; i < startLine + 3; i++){
for (int j = startColumn; j < startColumn + 3; j++){
if (flagban[i][j][num]){
flagCount[num]++;
if (flagCount[num] <= 2){
ngPosX[num][flagCount[num] - 1] = j;
ngPosY[num][flagCount[num] - 1] = i;
}
}
}
}
}
for (int first = 1; first <= Size; first++){
for (int second = 1; second <= Size; second++){
if (first != second && flagCount[first] == 2 && flagCount[second] == 2){
if (flagban[ngPosY[first][0]][ngPosX[first][0]][second] && flagban[ngPosY[first][1]][ngPosX[first][1]][second]){
for (int k = 1; k <= Size; k++){
if(k != first && k != second){
flagban[ngPosY[first][0]][ngPosX[first][0]][k] = false;
flagban[ngPosY[first][1]][ngPosX[first][1]][k] = false;
}
}
}
}
}
}
}
void solve() {
int Num, possibleNumCount = 0;
for (int Line = 0; Line < Size; Line++){
for (int Column = 0; Column < Size; Column++){
if (ban[Line][Column] == 0){//空白である
resetFlag();
startFlag();
deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
temporaryFlag(Line, Column);
deleteNumFlag(Line, Column);//入る可能性のある数字を減らす
possibleNumCount = 0;//マスごとに初期化
for (Num = 1; Num <= Size; Num++){
if (flagban[Line][Column][Num])//入る可能性を発見
possibleNumCount++;//カウントする
}
if (possibleNumCount == 1){//そのマスにおいて入る可能性のある数字が一つならば
for (Num = 1; Num <= Size; Num++){
if (flagban[Line][Column][Num]){//その唯一可能性のある数字を
cout << "outPut-onlyNum" << endl;
ban[Line][Column] = Num;//代入
filledGrid(Line, Column, Num, false);
}
}
}
for (Num = 1; Num <= Size; Num++){
int pos = retLineColumn(Line, Column, Num);
if (pos != 99){//99は発見できなかったとき
if (checkedTarget == 3){//対象がボックス
cout << "outPut-Box" << endl;
ban[pos / 10][pos % 10] = Num;
filledGrid(pos / 10, pos % 10, Num, false);
}
else if (checkedTarget == 2){//縦
cout << "outPut-Column" << endl;
ban[pos][Column] = Num;
filledGrid(pos, Column, Num, false);
}
else if (checkedTarget == 1){//横
cout << "outPut-Line" << endl;
ban[Line][pos] = Num;
filledGrid(Line, pos, Num, false);
}
}
}
}
}
}
}
bool IsEnd(){
for (int Line = 0; Line < Size; Line++){
for (int Column = 0; Column < Size; Column++){
if (ban[Line][Column] == 0)//空白を発見
return false;//続行
}
}
return true;
}
void setStart(){
char mode;
bool isOK = false;
cout << "| ナンプレ・数独解読プログラム |" << endl;
cout << "入力の仕方を選択してください" << endl;
do{
cout << "aを入力: 番地・数値入力モード(空白の多いとき推奨)" << endl;
cout << "bを入力: 行一括入力モード(空白の少ないとき推奨)" << endl;
cout << "fを入力: ファイルから読み込み" << endl << "入力モード :";
cin >> mode;
if (mode == 'a'){
input();
isOK = true;
}
else if (mode == 'b'){
input2();
isOK = true;
}
else if (mode == 'f'){
readData();
isOK = true;
}
else
cout << "正しく入力してください" << endl;
} while (!isOK);
}
int _tmain(int argc, const char * argv[]) {
resetBan();
resetFlag();
setStart();
do{//解く
IsFill = false;
solve();
if (!IsFill)
cout << "結果:盤への代入はありませんでした" << endl;
show(false,0);
cin.sync();//syncとgetで入力待ち
cin.get();//getが1回だとバグが起こることがある
cin.get();
} while (!IsEnd());
cout << "---------答え----------" << endl;
show(false,0);
return 0;
}