#include <cmath>
#include <cstdio>

#include <cuda_runtime.h>

#include "Sudoku.cuh"


/**
* Takes array and resets all values to false.
*/
__device__
void clearArray(bool *arr, int size) {
	for (int i = 0; i < size; i++) {
		arr[i] = false;
	}
}


/**
* Checks if the state of board is valid.
* board is one-dimensional array which stores the sudoku board.
*/
__device__
bool isBoardValid(const int *board) {
	bool visited[N]; // indicates already visited values in row or column or sub-board
	clearArray(visited, N);

	// rows
	for (int row = 0; row < N; row++) {
		clearArray(visited, N);
		for (int col = 0; row < N; col++) {
			int value = board[row * N + col];

			if (value != 0) {
				if (visited[value - 1]) {
					return false;
				}
				else {
					visited[value - 1] = true;
				}
			}
		}
	}

	// columns
	for (int row = 0; row < N; row++) {
		clearArray(visited, N);
		for (int col = 0; col < N; col++) {
			int val = board[col * N + row];

			if (val != 0) {
				if (visited[val - 1]) {
					return false;
				}
				else {
					visited[val - 1] = true;
				}
			}
		}
	}

	// sub-boards
	for (int subr = 0; subr < n; subr++) {
		for (int subc = 0; subc < n; subc++) {
			clearArray(visited, N);
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					int value = board[(subr * n + i) * N + (subc * n + j)];

					if (value != 0) {
						if (visited[value - 1]) {
							return false;
						}
						else {
							visited[value - 1] = true;
						}
					}
				}
			}
		}
	}
	//the board is valid
	return true;
}


/**
* Takes a board and an index between 0 and N * N - 1. This function assumes the board
* without the value at index is valid and checks for validity given the new change.
*
* index: index of the changed value
*/
__device__
bool isBoardValid(const int *board, int index) {

	int r = index / 9;
	int c = index % 9;

	if (index < 0) {
		return isBoardValid(board);
	}

	if ((board[index] < 1) || (board[index] > 9)) { //not the values from sudoku
		return false;
	}

	bool visited[N];// from 0 to 8
	clearArray(visited, N);
	// row (with the value at index)
	for (int i = 0; i < N; i++) {
		int value = board[r * N + i];

		if (value != 0) {
			if (visited[value - 1]) {
				return false;
			}
			else {
				visited[value - 1] = true;
			}
		}
	}

	clearArray(visited, N);
	// column (with the value at index)
	for (int j = 0; j < N; j++) {
		int value = board[j * N + c];

		if (value != 0) {
			if (visited[value - 1]) {
				return false;
			}
			else {
				visited[value - 1] = true;
			}
		}
	}

	// sub-board
	int subr = r / n;
	int subc = c / n;

	clearArray(visited, N);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int value = board[(subr * n + i) * N + (subc * n + j)];

			if (value != 0) {
				if (visited[value - 1]) {
					return false;
				}
				else {
					visited[value - 1] = true;
				}
			}
		}
	}
	//valid
	return true;
}


/**
* Each thread solves the different board using backtracking algorithm.
*
* boards:      The array of boards N*N , where the number of boards is numBoards,
*				boards[x*N*N + r*N + c] - specific value in board x.
*
* numBoards:   The total number of boards in the boards array.
*
* emptySpaces: The array which stores indices of empty spaces, the size of array is numBoards * N * N
*
* numEmptySpaces:  The array which stores number of empty spaces in each board of boards.
*
* finished:    The flag indicating to stop the kernel when solution is found.
*
* solved:      Output array with solution N*N.
*/
__global__
void sudokuBacktrack(int *boards,
	const int numBoards,
	int *emptySpaces,
	int *numEmptySpaces,
	int *finished,
	int *solved) {

	int index = blockDim.x * blockIdx.x + threadIdx.x; // the number of board

	int *currentBoard;
	int *currentEmptySpaces;
	int currentNumEmptySpaces;


	while ((*finished == 0) && (index < numBoards)) { // not finished, not all boards done

		int emptyIndex = 0;// empty spaces index

		currentBoard = boards + index * N * N;// select board
		currentEmptySpaces = emptySpaces + index * N * N;// the empty spaces indices
		currentNumEmptySpaces = numEmptySpaces[index];// the number of empty spaces

		while ((emptyIndex >= 0) && (emptyIndex < currentNumEmptySpaces)) {
			//walk through empty spaces
			currentBoard[currentEmptySpaces[emptyIndex]]++;

			if (!isBoardValid(currentBoard, currentEmptySpaces[emptyIndex])) {

				// all numbers were tried, backtrack
				if (currentBoard[currentEmptySpaces[emptyIndex]] >= 9) {
					currentBoard[currentEmptySpaces[emptyIndex]] = 0;
					emptyIndex--;
				}
			}
			// move forward
			else {
				emptyIndex++;
			}

		}

		if (emptyIndex == currentNumEmptySpaces) { //all spaces filled
			// we found the solution
			*finished = 1;

			// copy board to output
			for (int i = 0; i < N * N; i++) {
				solved[i] = currentBoard[i];
			}
		}

		index += gridDim.x * blockDim.x; // move to next board
	}
}


void cudaSudokuBacktrack(const unsigned int blocks,
	const unsigned int threadsPerBlock,
	int *boards,
	const int numBoards,
	int *emptySpaces,
	int *numEmptySpaces,
	int *finished,
	int *solved) {

	sudokuBacktrack << <blocks, threadsPerBlock >> >
		(boards, numBoards, emptySpaces, numEmptySpaces, finished, solved);
}


/**
* This is generating kernel, which genearates next boards from old one.
* Uses breadth first search to find new boards.
*
* old_boards:      Each N * N section is another board. This array stores the previous set of boards.
*
* new_boards:      This array stores the next set of boards.
*
* total_boards:    Number of old boards.
*
* board_index:     Index specifying the index of the next frontier in new_boards.
*
* empty_spaces:    Each N * N section is another board, storing the
*                  indices of empty spaces in new_boards.
*
* empty_space_count:   empty spaces number in corresponding board.
*/
__global__
void
cudaBFSKernel(int *old_boards,
	int *new_boards,
	int total_boards,
	int *board_index,
	int *empty_spaces,
	int *empty_space_count) {

	unsigned int index = blockIdx.x * blockDim.x + threadIdx.x;// index of board

	while (index < total_boards) {
		// empty space index
		int found = 0;

		for (int i = (index * N * N); (i < (index * N * N) + N * N) && (found == 0); i++) {// search in each board
			// found an empty space
			if (old_boards[i] == 0) {
				found = 1;
				int temp = i - N * N * index;
				int row = temp / N;
				int col = temp % N;

				// try numbers
				for (int attempt = 1; attempt <= N; attempt++) {
					int correct = 1;
					// row constraint, test columns
					for (int c = 0; c < N; c++) {
						if (old_boards[row * N + c + N * N * index] == attempt) {// found equal in column
							correct = 0;
						}
					}
					// column contraint, test rows
					for (int r = 0; r < N; r++) {
						if (old_boards[r * N + col + N * N * index] == attempt) {// found equal in row
							correct = 0;
						}
					}
					// sub-board
					for (int r = n * (row / n); r < n; r++) {
						for (int c = n * (col / n); c < n; c++) {
							if (old_boards[r * N + c + N * N * index] == attempt) {// equal in sub-board
								correct = 0;
							}
						}
					}
					if (correct == 1) {
						// copy the whole board to new boards

						int next_board_index = atomicAdd(board_index, 1);// stores result back at same address
						int empty_index = 0;
						for (int r = 0; r < N; r++) {
							for (int c = 0; c < N; c++) {
								new_boards[next_board_index * N * N + r * N + c] = old_boards[index * N * N + r * N + c];
								if (old_boards[index * N * N + r * N + c] == 0 && (r != row || c != col)) {
									empty_spaces[empty_index + N * N * next_board_index] = r * N + c;// the index of empty space
									empty_index++;// count empty spaces
								}
							}
						}
						empty_space_count[next_board_index] = empty_index;
						new_boards[next_board_index * N * N + row * N + col] = attempt;// put the correct number
					}
				}
			}
		}

		index += blockDim.x * gridDim.x; // move forward
	}
}


void callBFSKernel(const unsigned int blocks,
	const unsigned int threadsPerBlock,
	int *old_boards,
	int *new_boards,
	int total_boards,
	int *board_index,
	int *empty_spaces,
	int *empty_space_count) {
	cudaBFSKernel << <blocks, threadsPerBlock >> >
		(old_boards, new_boards, total_boards, board_index, empty_spaces, empty_space_count);
}

	.file	"tmpxft_00352141_00000000-6_Sudoku.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2034:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2034:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z10clearArrayPbi
	.type	_Z10clearArrayPbi, @function
_Z10clearArrayPbi:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2027:
	.size	_Z10clearArrayPbi, .-_Z10clearArrayPbi
	.globl	_Z12isBoardValidPKi
	.type	_Z12isBoardValidPKi, @function
_Z12isBoardValidPKi:
.LFB2028:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2028:
	.size	_Z12isBoardValidPKi, .-_Z12isBoardValidPKi
	.globl	_Z12isBoardValidPKii
	.type	_Z12isBoardValidPKii, @function
_Z12isBoardValidPKii:
.LFB2029:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2029:
	.size	_Z12isBoardValidPKii, .-_Z12isBoardValidPKii
	.globl	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.type	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_, @function
_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_:
.LFB2056:
	.cfi_startproc
	endbr64
	subq	$184, %rsp
	.cfi_def_cfa_offset 192
	movq	%rdi, 40(%rsp)
	leaq	72(%rsp), %rdi
	movl	%esi, 36(%rsp)
	leaq	84(%rsp), %rsi
	movq	%rdx, 24(%rsp)
	leaq	56(%rsp), %rdx
	movq	%rcx, 16(%rsp)
	leaq	64(%rsp), %rcx
	movq	%r8, 8(%rsp)
	movq	%r9, (%rsp)
	movq	%fs:40, %rax
	movq	%rax, 168(%rsp)
	xorl	%eax, %eax
	leaq	40(%rsp), %rax
	movl	$1, 80(%rsp)
	movq	%rax, 120(%rsp)
	leaq	36(%rsp), %rax
	movq	%rax, 128(%rsp)
	leaq	24(%rsp), %rax
	movq	%rax, 136(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 144(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 152(%rsp)
	movq	%rsp, %rax
	movq	%rax, 160(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 72(%rsp)
	movq	%rax, 84(%rsp)
	movl	$1, 92(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L8
	pushq	64(%rsp)
	.cfi_def_cfa_offset 200
	leaq	_Z15sudokuBacktrackPiiS_S_S_S_(%rip), %rdi
	pushq	64(%rsp)
	.cfi_def_cfa_offset 208
	movq	100(%rsp), %rcx
	movl	108(%rsp), %r8d
	movq	88(%rsp), %rsi
	movl	96(%rsp), %edx
	leaq	136(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 200
	popq	%rdx
	.cfi_def_cfa_offset 192
.L8:
	movq	168(%rsp), %rax
	subq	%fs:40, %rax
	je	.L10
	call	__stack_chk_fail@PLT
.L10:
	addq	$184, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2056:
	.size	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_, .-_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.globl	_Z15sudokuBacktrackPiiS_S_S_S_
	.type	_Z15sudokuBacktrackPiiS_S_S_S_, @function
_Z15sudokuBacktrackPiiS_S_S_S_:
.LFB2057:
	.cfi_startproc
	endbr64
	jmp	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
	.cfi_endproc
.LFE2057:
	.size	_Z15sudokuBacktrackPiiS_S_S_S_, .-_Z15sudokuBacktrackPiiS_S_S_S_
	.globl	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_
	.type	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_, @function
_Z19cudaSudokuBacktrackjjPiiS_S_S_S_:
.LFB2030:
	.cfi_startproc
	endbr64
	movabsq	$4294967297, %rax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%r9, %r13
	xorl	%r9d, %r9d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movq	%r8, %r12
	xorl	%r8d, %r8d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	movl	%ecx, %ebp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdx, %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	%esi, 20(%rsp)
	movq	96(%rsp), %r14
	movq	%rax, 24(%rsp)
	movl	28(%rsp), %ecx
	movq	20(%rsp), %rdx
	movq	104(%rsp), %r15
	movq	%rax, 12(%rsp)
	movl	%edi, 8(%rsp)
	movl	16(%rsp), %esi
	movq	8(%rsp), %rdi
	call	__cudaPushCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L14
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r15, %r9
	movq	%r14, %r8
	movq	%r13, %rcx
	movq	%r12, %rdx
	movl	%ebp, %esi
	movq	%rbx, %rdi
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	_Z44__device_stub__Z15sudokuBacktrackPiiS_S_S_S_PiiS_S_S_S_
.L14:
	.cfi_restore_state
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2030:
	.size	_Z19cudaSudokuBacktrackjjPiiS_S_S_S_, .-_Z19cudaSudokuBacktrackjjPiiS_S_S_S_
	.globl	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.type	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_, @function
_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_:
.LFB2058:
	.cfi_startproc
	endbr64
	subq	$184, %rsp
	.cfi_def_cfa_offset 192
	movq	%rdi, 40(%rsp)
	leaq	72(%rsp), %rdi
	movq	%rsi, 32(%rsp)
	leaq	84(%rsp), %rsi
	movl	%edx, 28(%rsp)
	leaq	56(%rsp), %rdx
	movq	%rcx, 16(%rsp)
	leaq	64(%rsp), %rcx
	movq	%r8, 8(%rsp)
	movq	%r9, (%rsp)
	movq	%fs:40, %rax
	movq	%rax, 168(%rsp)
	xorl	%eax, %eax
	leaq	40(%rsp), %rax
	movl	$1, 80(%rsp)
	movq	%rax, 120(%rsp)
	leaq	32(%rsp), %rax
	movq	%rax, 128(%rsp)
	leaq	28(%rsp), %rax
	movq	%rax, 136(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 144(%rsp)
	leaq	8(%rsp), %rax
	movq	%rax, 152(%rsp)
	movq	%rsp, %rax
	movq	%rax, 160(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 72(%rsp)
	movq	%rax, 84(%rsp)
	movl	$1, 92(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L17
	pushq	64(%rsp)
	.cfi_def_cfa_offset 200
	leaq	_Z13cudaBFSKernelPiS_iS_S_S_(%rip), %rdi
	pushq	64(%rsp)
	.cfi_def_cfa_offset 208
	movq	100(%rsp), %rcx
	movl	108(%rsp), %r8d
	movq	88(%rsp), %rsi
	movl	96(%rsp), %edx
	leaq	136(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 200
	popq	%rdx
	.cfi_def_cfa_offset 192
.L17:
	movq	168(%rsp), %rax
	subq	%fs:40, %rax
	je	.L19
	call	__stack_chk_fail@PLT
.L19:
	addq	$184, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2058:
	.size	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_, .-_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.globl	_Z13cudaBFSKernelPiS_iS_S_S_
	.type	_Z13cudaBFSKernelPiS_iS_S_S_, @function
_Z13cudaBFSKernelPiS_iS_S_S_:
.LFB2059:
	.cfi_startproc
	endbr64
	jmp	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
	.cfi_endproc
.LFE2059:
	.size	_Z13cudaBFSKernelPiS_iS_S_S_, .-_Z13cudaBFSKernelPiS_iS_S_S_
	.globl	_Z13callBFSKerneljjPiS_iS_S_S_
	.type	_Z13callBFSKerneljjPiS_iS_S_S_, @function
_Z13callBFSKerneljjPiS_iS_S_S_:
.LFB2031:
	.cfi_startproc
	endbr64
	movabsq	$4294967297, %rax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movq	%r9, %r13
	xorl	%r9d, %r9d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	movl	%r8d, %r12d
	xorl	%r8d, %r8d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	movq	%rcx, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rdx, %rbx
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	%esi, 20(%rsp)
	movq	96(%rsp), %r14
	movq	%rax, 24(%rsp)
	movl	28(%rsp), %ecx
	movq	20(%rsp), %rdx
	movq	104(%rsp), %r15
	movq	%rax, 12(%rsp)
	movl	%edi, 8(%rsp)
	movl	16(%rsp), %esi
	movq	8(%rsp), %rdi
	call	__cudaPushCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L22
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movq	%r15, %r9
	movq	%r14, %r8
	movq	%r13, %rcx
	movl	%r12d, %edx
	movq	%rbp, %rsi
	movq	%rbx, %rdi
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	_Z42__device_stub__Z13cudaBFSKernelPiS_iS_S_S_PiS_iS_S_S_
.L22:
	.cfi_restore_state
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2031:
	.size	_Z13callBFSKerneljjPiS_iS_S_S_, .-_Z13callBFSKerneljjPiS_iS_S_S_
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"_Z13cudaBFSKernelPiS_iS_S_S_"
.LC1:
	.string	"_Z15sudokuBacktrackPiiS_S_S_S_"
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2061:
	.cfi_startproc
	endbr64
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	pushq	$0
	.cfi_def_cfa_offset 24
	xorl	%r9d, %r9d
	orl	$-1, %r8d
	pushq	$0
	.cfi_def_cfa_offset 32
	leaq	.LC0(%rip), %rdx
	movq	%rax, %rdi
	movq	%rax, %rbx
	pushq	$0
	.cfi_def_cfa_offset 40
	movq	%rdx, %rcx
	leaq	_Z13cudaBFSKernelPiS_iS_S_S_(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 48
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFunction@PLT
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	movq	%rbx, %rdi
	xorl	%r9d, %r9d
	pushq	$0
	.cfi_def_cfa_offset 24
	leaq	.LC1(%rip), %rdx
	orl	$-1, %r8d
	leaq	_Z15sudokuBacktrackPiiS_S_S_S_(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 32
	movq	%rdx, %rcx
	pushq	$0
	.cfi_def_cfa_offset 40
	pushq	$0
	.cfi_def_cfa_offset 48
	call	__cudaRegisterFunction@PLT
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rbx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2061:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

#ifndef SUDOKU_CUH
#define SUDOKU_CUH


#define N 9 // board size
#define n 3 // sub-board size

void cudaSudokuBacktrack(const unsigned int blocks,
	const unsigned int threadsPerBlock,
	int *boards,
	const int numBoards,
	int *emptySpaces,
	int *numEmptySpaces,
	int *finished,
	int *solved);

void callBFSKernel(const unsigned int blocks,
	const unsigned int threadsPerBlock,
	int *old_boards,
	int *new_boards,
	int total_boards,
	int *board_index,
	int *empty_spaces,
	int *empty_space_count);
#endif // SUDOKU_CUH
	.text
	.file	"Sudoku.hip"
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
