Kali ini saya akan membagikan script kode program sudoku dengan penyelesaian menggunakan metode backtracking disertai user input baris dan kolom. Script ini saya modifikasi sedemikian rupa agar user bisa input nilai baris dan kolom sesuai keinginan masing-masing. Tapi masih ada beberapa kendala disini yaitu user harus input semua nilai agar program ini berjalan dengan baik.
/*
* C++ Program to Solve Sudoku Problem using BackTracking
*/
#include
#include
#include
#include
using namespace std;
#define UNASSIGNED 0
#define N 9
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
bool isSafe(int grid[N][N], int row, int col, int num);
/* assign values to all unassigned locations for Sudoku solution
*/
bool SolveSudoku(int grid[N][N])
{
int row, col;
if (!FindUnassignedLocation(grid, row, col))
return true;
for (int num = 1; num <= 9; num++)
{
if (isSafe(grid, row, col, num))
{
grid[row][col] = num;
if (SolveSudoku(grid))
return true;
grid[row][col] = UNASSIGNED;
}
}
return false;
}
/* Searches the grid to find an entry that is still unassigned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
for (row = 0; row < N; row++)
for (col = 0; col < N; col++)
if (grid[row][col] == UNASSIGNED)
return true;
return false;
}
/* Returns whether any assigned entry n the specified row matches
the given number. */
bool UsedInRow(int grid[N][N], int row, int num)
{
for (int col = 0; col < N; col++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry in the specified column matches
the given number. */
bool UsedInCol(int grid[N][N], int col, int num)
{
for (int row = 0; row < N; row++)
if (grid[row][col] == num)
return true;
return false;
}
/* Returns whether any assigned entry within the specified 3x3 box matches
the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row+boxStartRow][col+boxStartCol] == num)
return true;
return false;
}
/* Returns whether it will be legal to assign num to the given row,col location.
*/
bool isSafe(int grid[N][N], int row, int col, int num)
{
return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) &&
!UsedInBox(grid, row - row % 3 , col - col % 3, num);
}
/* print grid */
void printGrid(int grid[N][N])
{
for (int row = 0; row < N; row++)
{
for (int col = 0; col < N; col++)
cout<
cout<
}
}
/* Main */
int main()
{
int inputA [9][9];
//input matrix A
cout << "Masukkan Nilai Batasan : "< cout << "------------------"< for (int bar = 0; bar <= 8; bar++)
{
for (int kol = 0; kol <= 8; kol++)
{
cout << "A ["< cin >> inputA[bar][kol];
}
}
cout << "\nHasil Inputan "< cout << "----------------------------"<
for (int bar = 0; bar <= 8; bar++)
{
for (int kolA = 0; kolA <= 8; kolA++)
{
cout << " "< }
cout << " "< }
cout << "----------------------------"<
if (SolveSudoku(inputA) == true)
printGrid(inputA);
else
cout<<"No solution exists"<
return 0;
}
Semoga bermanfaat dan menjadi lebih tambah pengalaman, jika ada tambahan atau saran yang membangun bisa ditambahkan di komentar.
Terima kasih :D