[C++]Program do rozwiązywania sudoku-błąd logiczny.

diego_maradona
Użytkownik
Użytkownik
Posty: 184
Rejestracja: 16 cze 2010, o 00:59
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 80 razy

[C++]Program do rozwiązywania sudoku-błąd logiczny.

Post autor: diego_maradona »

Od dłuższego czasu nie mogę znaleźć błędu w programie(C++) , który w przyszłości ma rozwiązywać sudoku. Jest on obsługiwany przez konsolę systemu Windows, długość to ok. 500 linijek, ale większość to mało istotne elementy typu obsługa menu, wczytywanie plansz itp.(nie zaszkodzi chyba wklejenie tutaj całego kodu :wink: ). Obecnie z powodu niezidentyfikowanego błędu, proces rozwiązywania "wykłada się" na pierwszym etapie - przeiterowaniu planszy i wypełnieniu pól, w których "na pierwszy rzut oka" jest tylko jedna możliwa wartość (min. za to odpowiedzialna jest funkcja sudokuBoard::resolve()). Niestety, wypełniane są pola gdzie tej możliwości nie ma, np. dokłada się drugą liczbę o tej samej wartości do tej samej kolumny itp.

main.cpp

Kod: Zaznacz cały

#include <iostream>
#include "sudokuBoard.h"

using namespace std;
using namespace sudoku;

int MainMenu();
int ResolvingMenu();

int main(void)
{
	
	sudokuBoard currentBoard;
	

	switch(MainMenu())
	{	
		case 1:
			currentBoard.load();
			break;
		case 2:
			currentBoard.createCustom();
			break;
	}

	currentBoard.print();

	switch(ResolvingMenu())
	{
	case 1:
		currentBoard.resolve();
		break;
	case 2:
		currentBoard.resolveManually();
			
	}
	
	cout<<endl;
	currentBoard.print();

	cout<<endl;
	system("PAUSE");
	return 0;
}

int MainMenu()
{
	int choice;
	
	cout<<"Sudoku Wizard (Console version)\n"
		<<"1.Load board\n"
		<<"2.Create a new board\n";
	
	cin>>choice;

	return choice;
}

int ResolvingMenu()
{
	int choice;

	cout<<"1.\nResolve automatically\n";
	cout<<"2.Resolve manually\n";
	
	cin>>choice;

	return choice;

}
sudokuBoard.h

Kod: Zaznacz cały

#ifndef H_sudokuBoard
#define H_sudokuBoard

#include <Windows.h>


namespace sudoku
{
struct slotType
{	
	

	slotType()
	{
		possibilitiesCounter=0;
		confirmed = false;
	}

	int value;
	int possibilitiesCounter;
	bool fixed;
	bool confirmed;
	int possibleValues[9]; 

};

struct number
{
	number()
	{
		present = false;
	}
	
	int value;
	bool present;
};

class sudokuBoard
{
public:	
	sudokuBoard operator=(sudokuBoard ); 


	sudokuBoard();
	void switchSlotValue(int , int , int);
	//column, row, value

	void print() const;

	void createCustom();

	void load();

	bool check(int column,int row,int value) const; 

	void resolve();

	void resolveManually();

	bool isFull() const; 

	void finishOff();

private:
	 slotType slot[9][9];
	 int possibilities;
};
}
void MakeFilesList(const TCHAR* rPath,const TCHAR* oDPath,const TCHAR* repFileName);
#endif
sudokuBoard_df.cpp

Kod: Zaznacz cały

#include "sudokuBoard.h"
#include <iostream>
#include <fstream>
#include <Windows.h>
#include <ctime>
#include <cstring>
#include <cstdio>
#include <stack>

using namespace std;



TCHAR SAVEDIR[]="Saves";


using namespace sudoku;

sudokuBoard sudokuBoard::operator=(sudokuBoard actualCheckBoard)
{
	for(int i=0; i < 9 ; i++)
		for(int j=0; j< 9 ; j++)
		slot[j][i] = actualCheckBoard.slot[j][i];
	
	return *this;
}

sudokuBoard::sudokuBoard()
{
	for(int i=0; i<9 ; i++)
		for(int j=0; j<9 ; j++)
		slot[j][i].value = 0;

}

void sudokuBoard::print() const
{
	for(int i=0; i<9 ; i++)
	{	
		for(int j=0; j<9 ; j++)
		{
			
			if(slot[j][i].fixed && (slot[j][i].value != 0))
			{
				SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 15);
				cout<<slot[j][i].value<<' ';

				
			}
			else
			{	
				if(slot[j][i].value == 0)
				{
					SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),8);
					cout<<slot[j][i].value<<' ';
					
				}
				else
				{	
					SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 12);
					cout<<slot[j][i].value<<' ';
				}
			}
		}
	cout<<endl;
	}
	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);	
}

void sudokuBoard::switchSlotValue(int column, int row , int newValue){	slot[column][row].value = newValue; }



void sudokuBoard::createCustom()
{
	
	int tempCol,tempRow,tempValue;
	char choice='y';

	SetCurrentDirectory(SAVEDIR);

	while(choice=='y')
	{
		cout<<"\nEnter the coordinates (column and row)\n";
	
		tempColPrompt:
		cin>>tempCol;
		
		if(tempCol > 9 || tempCol < 1)
		{
			cout<<"Incorrect column selected!Please re-enter(1-9)\n";
			goto tempColPrompt;
		}
		
		tempRowPrompt:
		cin>>tempRow;
		
		if(tempRow > 9 || tempRow < 1)
		{
			cout<<"Incorrect row selected!Please re-enter(1-9)\n";
			goto tempRowPrompt;
		}

		cout<<"Enter the new value of "<<tempCol<<":"<<tempRow<<endl;

		tempValuePrompt:
		cin>>tempValue;

		if(tempValue > 9 || tempValue < 1)
		{
			cout<<"Incorrect  value(1-9)!Please re-enter\n";
			goto tempValuePrompt;
		}


		tempCol--;
		tempRow--;



		slot[tempCol][tempRow].value = tempValue;
		slot[tempCol][tempRow].fixed = true;
		print();
		cout<<"\nPress \"y\" if you want to continue\n";
		cin>>choice;
	}

	cout<<"Press s to save, and q to quit\n";

	cin>>choice;

	if(choice=='s')
	{
		
		char label[_MAX_FNAME];
		char fileShortPath[255];

		

		ofstream oFile;
		
		

		cout<<"Enter the label of your file(max 100 characters)\n";
		cin>>label;

		
		
			
		oFile.open(label);

		for(int i=0; i<9 ; i++)
		{	
			for(int j=0; j<9 ; j++)
			oFile << slot[j][i].value<<' ';

		oFile<<endl;
		}

		oFile.close();

		cout<<"file"<<"\""<<label<<"\" saved!\n";
	}
}


void sudokuBoard::load()
{
	TCHAR buffer[MAX_PATH];
	FILE* boardListFile;
	TCHAR openFileShortPath[MAX_PATH+_MAX_FNAME];
	TCHAR selection[_MAX_FNAME];
	FILE* selectionFile;
	int tmp;

	SetCurrentDirectory(SAVEDIR);
	MakeFilesList(NULL,NULL,"boards");
	
	cout<<"Select from the list of files:\n";

	boardListFile = fopen("boards","r");
	if (boardListFile==NULL) 
	{
		perror ("Error opening file");
		system("pause");
		exit(1);
	}
	while(!feof(boardListFile))
	{	
		fscanf(boardListFile,"%s",buffer);
		if(buffer!="boards")
		printf("%s\n",buffer);
	}

	printf("Enter the file's name\n");
	scanf("%s",&selection);
	printf("You've selected %s file\n",selection);

	selectionFile=fopen(selection,"r"); 

	if(selectionFile==NULL)
	{		
		printf("Can not open the file!\n");
		//MessageBox(0,"File doesn't exist!","Error!",0);	
		return;
	}

	
	for(int i=0;i<9; i++)
		for(int j=0; j<9; j++)
		{
			fscanf_s(selectionFile,"%d",&tmp);
			switchSlotValue(j,i,tmp);

			if(tmp != 0)
			{	
				slot[j][i].fixed = true;
				slot[j][i].confirmed = true;
			}
			else
			{
				slot[j][i].fixed = false;
				slot[j][i].confirmed = false;
			}
		}
	printf("File %s loaded\n",selection);
}

bool sudokuBoard::check(int column  ,int row,int checkedValue) const// 5,0,1
{
	int miniBoxFirstColumn;//0v3v6
	int miniBoxFirstRow;//0v3v6
	
	slotType miniBox[3][3];

	
	//column check
	for(int i=0; i<9; i++) 
	{		
		if(i==row)continue;
					
		if(checkedValue==slot[column][i].value) return false;
	}	

	//row check

	for(int i=0; i<9; i++) 
	{	
		if(i==column) continue;
		if(checkedValue==slot[i][row].value) return false;
	}

	//3x3 box

	miniBoxFirstColumn=(column/3)*3;
	miniBoxFirstRow=(row/3)*3;

	for(int m=0;m<3;m++)
		for(int n=0;n<3;n++)
		{
			if(n==column && m==row) continue; 

			if(checkedValue == slot[miniBoxFirstColumn+n][miniBoxFirstRow+m].value) return false;			

		}
						
		return true;
}	

void sudokuBoard::resolve()
{
	/*int randRow;
	int randCol;
	int randVal;*/
	
	bool prephaseFinished;

	cout<<"\nResolving...\n";

	while(!isFull())
	{
	prephaseFinished = true;

	for(int i=0; i<9; i++)
		for(int j=0; j<9; j++)
		{
	 			if(slot[j][i].value == 0)
				for(int k=1; k<=9; k++) 
				{
						if(check(j,i,k)) 
						{	
							slot[j][i].possibleValues[slot[j][i].possibilitiesCounter] = k;
							slot[j][i].possibilitiesCounter++;
							
						}
				}				
		}

	//Fulfill fields with the only one possible number
	for(int i=0; i<9; i++)
		for(int j=0; j<9; j++)
			for(int k=1; k<=9; k++)
			{
				if(slot[j][i].possibilitiesCounter == 1 )
				{
					slot[j][i].value = k;
					slot[j][i].confirmed = true;
					slot[j][i].fixed = false;
					
					prephaseFinished=false;

					cout<<endl;
					print();
				}	
			}

	if(prephaseFinished) return;

	
	}	
}

void sudokuBoard::resolveManually()
{
	int tempCol,tempRow,tempValue;
	
	while(1)
	{	
		cout<<endl;
		print();
		cout<<endl;

		cout<<"Enter coordinates(column and row, respectively)\n";
		cin>>tempCol>>tempRow;

		cout<<"\nEnter the value of "<<tempCol<<"x"<<tempRow<<endl;
		cin>>tempValue;

		cout<<endl;
		cout<<check(tempCol,tempRow,tempValue)<<endl;
	}


}

bool sudokuBoard::isFull() const
{
	for(int i=0; i<9 ; i++)
		for(int j=0; j<9; j++)
			if(!slot[j][i].value) return false;
	return true;
} 

void MakeFilesList(const TCHAR* rPath,const TCHAR* oDPath, const TCHAR* repFileName)
{
	TCHAR command[MAX_PATH+30];
	

	strcpy(command,"dir /b \"");

	if(rPath!=NULL)
	{	strcat(command,rPath);
	
		strcat(command,"\" > \"");
	}
	else
	strcat(command," > \"");

	if(oDPath!=NULL) 
	strcat(command,oDPath);
	
	strcat(command,repFileName);

	strcat(command,"\"");

	system(command);

}

void sudokuBoard::finishOff()
{
	number possibleValues[9];
	int columnWithZero;
	bool isFinishable = true;

	for(int i=0; i<9; i++)
	{	
		for(int j=0; j<9; j++)
		{		
			if(slot[j][i].value != 0 )
			{
				possibleValues[j].value = slot[j][i].value;
				possibleValues[j].present = true;				
			}
			else
				columnWithZero = j;
		
		}
		
		for(int k=0; k<9; k++)
			if( possibleValues[k].present == false) switchSlotValue(columnWithZero,i,possibleValues[k].value); /*slot[columnWithZero][i] = possibleValues[k].value; - you must overload operator in order to implement that*/
				
				
	}

}
witekkq
Użytkownik
Użytkownik
Posty: 145
Rejestracja: 16 lis 2007, o 09:06
Płeć: Mężczyzna
Lokalizacja: Gniezno
Podziękował: 2 razy
Pomógł: 27 razy

[C++]Program do rozwiązywania sudoku-błąd logiczny.

Post autor: witekkq »

Jakbyś dodał jakiś plik z planszami byłoby łatwiej to sprawdzić w domu i może komuś by się chciało
diego_maradona
Użytkownik
Użytkownik
Posty: 184
Rejestracja: 16 cze 2010, o 00:59
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 80 razy

[C++]Program do rozwiązywania sudoku-błąd logiczny.

Post autor: diego_maradona »

Słuszna uwaga

Kod: Zaznacz cały

2 0 0 0 6 9 0 4 8
0 0 0 3 0 0 2 7 0
0 7 0 0 2 1 6 9 0
4 0 0 6 0 0 5 0 0
8 0 3 0 1 7 0 0 0
5 0 0 0 0 2 0 0 6
7 9 0 1 0 3 0 0 2
0 4 0 9 0 6 7 0 0
6 0 8 2 0 0 1 0 0

Kod: Zaznacz cały

0 0 6 0 0 4 1 0 5
0 4 0 7 0 6 0 3 9
2 0 0 9 3 0 6 0 0
7 0 0 1 8 0 5 0 4
0 0 4 0 6 0 9 0 0
1 0 9 0 5 2 0 0 3
0 0 1 0 9 3 0 0 7
6 7 0 5 0 8 0 9 0
9 0 8 0 0 0 4 0 0

Kod: Zaznacz cały

7 0 0 0 3 6 9 0 1
4 6 0 0 0 0 0 5 0
0 0 0 0 1 5 0 7 0
0 5 0 0 0 0 6 0 0
0 0 0 7 0 9 0 0 0
0 0 2 0 0 0 0 8 0
0 3 0 6 2 0 0 0 0
0 1 0 0 0 0 0 4 8
8 0 7 1 9 0 0 0 5
Proszę bez komentarzy na temat obsługi plików, wiem że system jest zrobiony na odwal się, ale chodziło mi głównie o algorytm rozwiązywania w którym to właśnie tkwi jakiś szkopuł.
ODPOWIEDZ