#include <stdlib.h>
#include <unistd.h>

int	checkRow(int *puzzle, int row, int numb)
{
	for (int col = 0; col < 4; col++)
	{
		if (puzzle[row * 4 + col] == numb)
		{
			return (0);
		}
	}
	return (1);
}

int	checkColumn(int *puzzle, int col, int numb)
{
	for (int row = 0; row < 4; row++)
	{
		if (puzzle[row * 4 + col] == numb)
		{
			return (0);
		}
	}
	return (1);
}

int	isValid(int *puzzle, int row, int col, int numb)
{
	return (checkRow(puzzle, row, numb) && checkColumn(puzzle, col, numb));
}

int	isSolved(int *puzzle)
{
	for (int i = 0; i < 4 * 4; i++)
	{
		if (puzzle[i] == 0)
		{
			return (0);
		}
	}
	return (1);
}

void	printPuzzle(int *puzzle)
{
	char	buffer[2];

	for (int row = 0; row < 4; row++)
	{
		for (int col = 0; col < 4; col++)
		{
			buffer[0] = puzzle[row * 4 + col] + '0';
			buffer[1] = ' ';
			write(1, buffer, 2);
		}
		write(1, "\n", 1);
	}
}

int	solvePuzzle(int *puzzle, int row, int col)
{
	if (isSolved(puzzle))
	{
		return (1);
	}
	if (puzzle[row * 4 + col] != 0)
	{
		if (col < 4 - 1)
		{
			return (solvePuzzle(puzzle, row, col + 1));
		}
		else if (row < 4 - 1)
		{
			return (solvePuzzle(puzzle, row + 1, 0));
		}
		else
		{
			return (1);
		}
	}
	for (int numb = 1; numb <= 4; numb++)
	{
		if (isValid(puzzle, row, col, numb))
		{
			puzzle[row * 4 + col] = numb;
		if (col < 4 - 1)
		{
			if (solvePuzzle(puzzle, row, col + 1))
			{
				return (1);
			}
		}
		else if (row < 4 - 1)
		{
			if (solvePuzzle(puzzle, row + 1, 0))
			{
				return (1);
			}
		}
		else
		{
			return (1);
		}
		puzzle [row * 4 + col] = 0;
		}
	}
	return (0);
}

int main (int argc, char *argv[])
{
	if (argc != 2)
	{
	write (1, "Invalid number of argumnents.\n", 29);
	return (1);
	}

	char *input = argv[1];
	int input_length = 0;
	while (input[input_length] != '\0')
	{
		input_length++;
	}
	if (input_length != 4 * 4 * 2 - 1)
	{
		write (1, "Invalid input length.\n", 22);
		return (1);
	}


	int *puzzle = malloc(4 * 4 * sizeof(int));
	if (puzzle == NULL)
	{
		write(1, "Memory allocation failed.\n", 26);
		return (1);
	}

	int idx = 0;
	for (int i = 0; i < 4 * 4; i++)
	{
		if (input[idx] == ' ')
		{
			idx++;
		}
		if (input[idx] >= '0' && input[idx] <= '9')
		{
			puzzle[i] = input[idx] - '0';
		}
		else
		{
			write (1, "Invalid input.\n", 15);
		}
		idx++;
	}
	if (solvePuzzle(puzzle, 0, 0))
	{
		write (1, "Puzzle solved:\n", 15);
		printPuzzle(puzzle);
	}
	else
	{
		write (1, "No solution found.\n", 19);
	}
	free (puzzle);
	return (0);
}