Sudoku Çözüm Algoritması
Sudoku, standart olarak 9x9 boyutlarında bir diyagramda çözülen ve her satır, her sütun ve her 3x3'lük karede 1'den 9'a rakamların birer kez yer alması gereken bir zeka oyunu türüdür.
Oyunun amacı dokuzar hücreden oluşan 9 eşit kutuya bölünmüş bir alan üzerinde sayıları tekrar etmeyecek şekilde dizmeyi başarmak. Her satır ve sütunda 1'den 9'a kadar olan sayıları sadece bir kez kullanarak dizmeniz gerekiyor. Aynı şekilde çizgilerle ayrılmış her kutu içerisinde de 1'den 9'a kadar olan sayılar 1 kez kullanılmak zorundadır.
Sudoku çözümü ile onlarca farklı teknik bulunmaktadır. İnsan eliyle çözümünde, tahmine dayalı sayı yerleştirmeleri oyunun bitiş süresini etkili oranda kısaltmaktadır. Bilgisayarın çözdüğü bulmacalara tahmin ölçütünü katarak yapay zeka algoritmaları da geliştirebiliriz. Fakat aşağıdaki kod, boş bulunan yerelre sayıları yerleştirmeye çalışmakta, ilerleme işlemi devam ederken eğer sayılar çakışırsa 1 adım geri dönmektedir. Böylece doğru yolu bulana dek "Queue Data Structure" algoritmasıyla haritayı çözümlemektedir.
**Not : Yazılımı çalıştırmadan önce, kodda ismini belirttiğiniz input dosyasını oluşturunuz. Sudokuda verilmeyen sayılar için 0 giriniz.
Oyunun amacı dokuzar hücreden oluşan 9 eşit kutuya bölünmüş bir alan üzerinde sayıları tekrar etmeyecek şekilde dizmeyi başarmak. Her satır ve sütunda 1'den 9'a kadar olan sayıları sadece bir kez kullanarak dizmeniz gerekiyor. Aynı şekilde çizgilerle ayrılmış her kutu içerisinde de 1'den 9'a kadar olan sayılar 1 kez kullanılmak zorundadır.
Sudoku çözümü ile onlarca farklı teknik bulunmaktadır. İnsan eliyle çözümünde, tahmine dayalı sayı yerleştirmeleri oyunun bitiş süresini etkili oranda kısaltmaktadır. Bilgisayarın çözdüğü bulmacalara tahmin ölçütünü katarak yapay zeka algoritmaları da geliştirebiliriz. Fakat aşağıdaki kod, boş bulunan yerelre sayıları yerleştirmeye çalışmakta, ilerleme işlemi devam ederken eğer sayılar çakışırsa 1 adım geri dönmektedir. Böylece doğru yolu bulana dek "Queue Data Structure" algoritmasıyla haritayı çözümlemektedir.
**Not : Yazılımı çalıştırmadan önce, kodda ismini belirttiğiniz input dosyasını oluşturunuz. Sudokuda verilmeyen sayılar için 0 giriniz.
Ekran Görüntüsü
Kaynak Kodu :
//C++ Programming Language
// zafercavdar
#include <cstdio>
#include <cstdlib>
FILE *inputf = fopen("input.in","r");
FILE *outputf = fopen("output.txt","w");
int sudoku1[100][100];
int changed[100][100];
void map_read()
{
for (int y = 1 ; y < 10 ; y++)
for (int x = 1 ; x < 10 ; x++)
fscanf(inputf,"%1d",&sudoku1[x][y]);
}
int checkColRow(int x, int y)
{
for (int val = 1 ; val < 10 ; val++)
{
int temp1 = 1;
int temp2 = 1;
for (int ax = 1 ; ax < 10 ; ax++)
if (sudoku1[ax][y] == val )
{
temp1 = 0;
break;
}
for (int ay = 1 ; ay < 10 ; ay++)
if (sudoku1[x][ay] == val )
{
temp2 = 0;
break;
}
if (temp1 == 1 && temp2 == 1 )
{
return val;
break;
}
}
return 0;
}
void map_solve()
{
int prevX = 0;
for (int y = 1 ; y < 10 ; y++)
for (int x = 1 ; x < 10 ; x++)
{
if (sudoku1[x][y] == 0 || changed[x][y] == 1)
{
sudoku1[x][y] = checkColRow(x,y);
if ( sudoku1[x][y] != 0 )
{
changed[x][y] = 1;
}
if (sudoku1[x][y] == 0 )
x = prevX - 1;
printf("%d %d %d",x,y,sudoku1[x][y]);
prevX = x;
getchar();
}
}
}
int main()
{
map_read();
map_solve();
fclose(inputf);
fclose(outputf);
}
// zafercavdar
#include <cstdio>
#include <cstdlib>
FILE *inputf = fopen("input.in","r");
FILE *outputf = fopen("output.txt","w");
int sudoku1[100][100];
int changed[100][100];
void map_read()
{
for (int y = 1 ; y < 10 ; y++)
for (int x = 1 ; x < 10 ; x++)
fscanf(inputf,"%1d",&sudoku1[x][y]);
}
int checkColRow(int x, int y)
{
for (int val = 1 ; val < 10 ; val++)
{
int temp1 = 1;
int temp2 = 1;
for (int ax = 1 ; ax < 10 ; ax++)
if (sudoku1[ax][y] == val )
{
temp1 = 0;
break;
}
for (int ay = 1 ; ay < 10 ; ay++)
if (sudoku1[x][ay] == val )
{
temp2 = 0;
break;
}
if (temp1 == 1 && temp2 == 1 )
{
return val;
break;
}
}
return 0;
}
void map_solve()
{
int prevX = 0;
for (int y = 1 ; y < 10 ; y++)
for (int x = 1 ; x < 10 ; x++)
{
if (sudoku1[x][y] == 0 || changed[x][y] == 1)
{
sudoku1[x][y] = checkColRow(x,y);
if ( sudoku1[x][y] != 0 )
{
changed[x][y] = 1;
}
if (sudoku1[x][y] == 0 )
x = prevX - 1;
printf("%d %d %d",x,y,sudoku1[x][y]);
prevX = x;
getchar();
}
}
}
int main()
{
map_read();
map_solve();
fclose(inputf);
fclose(outputf);
}