I need help writing a sudoku solver in ARM assembly language! Please help, any h
ID: 3556882 • Letter: I
Question
I need help writing a sudoku solver in ARM assembly language! Please help, any help would be appreciated. Here is the outline of the program in C.
Solve sudoku using brute force (exhaustive)
C-code is given for a simple recursive solution that solves all sudoku puzzles.
Translate it into an assembly program that reads a board from the file board.txt with the following format:
704006390
000701500
000090027
002610053
400207008
610039400
930060000
006308000
048900206
Output should be the solved board in the same format printed to the stdout output.
C Code:
int rowOK(int board[9][9], int row) {
int index;
int count[10];
for (index=0; index<10; index++)
count[index] = 0;
for (index=0; index<9; index++)
count[board[row][index]]++;
for (index=1; index<10; index++)
if (count[index] > 1)
return 0;
return 1;
}
int colOK(int board[9][9], int col) {
int index;
int seen[10];
for (index=0; index<10; index++)
seen[index] = 0;
for (index=0; index<9; index++)
if ((board[index][col] != 0) &&
(count[board[index][col]] == 1))
return 0;
else
count[board[index][col]] = 1;
return 1;
}
int boxOK(int board[9][9], int row, int col) {
int roff;
int coff;
int seen = 0x0;
for (roff=0; roff<3; roff++)
for (coff=0; coff<3; coff++)
if ((board[row+roff][col+coff] != 0) &&
((seen & (0x1 << board[row+roff][col+coff]])) != 0))
return 0;
else
seen = seen | (0x1 << board[row+roff][col+coff]]);
return 1;
}
int status(int board[9][9]) {
int index;
int row;
int col;
for (index=0; index<9; index++)
if ((rowOK(board,index) == 0) ||
(colOK(board,index) == 0))
return 0;
for (row=0; row<9; row=row+3)
for (col=0; col<9; col=col+3)
if (boxOK(board,row,col) == 0)
return 0;
return 1;
}
int solve(int board[9][9]) {
int guess;
int row;
int col;
int emptyrow = -1;
int emptycol = -1;
for (row=0; row<9; row++)
for (col=0; col<9; col++)
if (board[row][col] ==0) {
emptyrow = row;
emptycol = col;
}
if (emptyrow < 0)
return 1;
for (guess = 1; guess<10; guess++) {
board[emptyrow][emptycol] = guess;
if (status(board) == 1)
if (solve(board) == 1)
return 1;
}
return 0;
}
Explanation / Answer
extern printf, exit global main ; Single-line macros ----------------------------------------------------------- %define SIZE 9 ; Width of the Sudoku board %define BOX_W 3 ; Width of the inner boxes %define BOX_H 3 ; Height of the inner boxes %define EMPTY 0 ; Empty cells marker %define RET_OK 0 ; Return code upon success %define RET_FAIL 1 ; Return code upon failure ; Macros ----------------------------------------------------------------------- %macro print_separator 0 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; push dword separator ; call printf ; Print a separator between board lines add esp, 4 ; %endmacro ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; %macro setup_stack_frame 0 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; push ebp ; mov ebp, esp ; Set up the stack frame according to the push ebx ; C calling convention, preserving the push esi ; ebp, ebx, esi and edi registers. push edi ; %endmacro ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; %macro destroy_stack_frame 0 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; pop edi ; pop esi ; Destroy the stack frame restoring the pop ebx ; edi, esi, ebx and ebp registers to mov esp, ebp ; their original values. pop ebp ; %endmacro ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;------------------------------------------------------------------------------- ; main - Call the guess() function and print the resulting board. If no solution ; exists, the board will be printed as it is (with zeroes) ; ; Last update : 06/09/2005 ; Args : None ; Action : Call guess(), print the board and exit cleanly. ;------------------------------------------------------------------------------- main: setup_stack_frame ; Set up stack frame push dword 0 ; Offset of first cell to guess call guess ; Start brute forcing the solution add esp, 4 ; Clean up the stack mov ebx, eax ; Save return code call print_board ; Print resulting board push ebx ; Exit with guess() return code call exit ; Exit cleanly add esp, 4 ; Clean up the stack destroy_stack_frame ; Destroy stack frame ret ; Return ;------------------------------------------------------------------------------- ; guess - Test all candidate numbers for the current cell until the board is ; complete ; ; Last update : 06/09/2005 ; Args : offset (at [ebp + 8]) - Offset of the cell to guess ; Action : Loop on numbers from 9 to 1 to find candidates for the current ; cell. If none is found, return RET_FAIL. Otherwise go on to the ; next cell. ;------------------------------------------------------------------------------- guess: setup_stack_frame ; Set up stack frame mov esi, [ebp + 8] ; Store offset in esi cmp esi, SIZE * SIZE ; Is offset outside the board bounds? je .return_ok ; If it is, return TRUE xor edx, edx ; Clean edx mov eax, esi ; eax = offset mov ecx, SIZE ; Set divisor to find cell's column div cx ; edx = column index of cell mov ebx, eax ; ebx = row index of cell cmp byte [board + esi], EMPTY ; Check if cell is empty je .loop ; If it is, jump to the loop inc esi ; Otherwise increment offset push esi ; push it on the stack call guess ; and go on to the next cell add esp, 4 ; Clean up the stack jmp .return ; Return the value returned by guess() .loop: push edx ; Push cell column index push ebx ; Push cell row index push ecx ; Push number to check call check ; Check if number is a legal candidate pop ecx ; Restore ecx (number to check) pop ebx ; Restore ebx (row index) pop edx ; Restore edx (column index) cmp eax, RET_OK ; Examine check() return value jne .next ; If RET_FAIL, try next number mov byte [board + esi], cl ; If RET_OK, assign number to cell push ecx ; Save ecx push edx ; Save edx inc esi ; Increment offset of number to guess push esi ; Push guess() argument call guess ; Call guess() on next cell add esp, 4 ; Clean up the stack pop edx ; Restore edx pop ecx ; Restore ecx cmp eax, RET_OK ; Examine guess() return value je .return ; If RET_OK, return RET_OK dec esi ; Else, restore esi to current offset .next: loop .loop ; Loop on every number form 9 to 1 mov byte [board + esi], EMPTY ; If no number worked, empty the cell mov eax, RET_FAIL ; Set return value to RET_FAIL jmp .return ; Jump to Return instructions .return_ok: xor eax, eax ; Set return value to RET_OK .return: destroy_stack_frame ; Destroy the stack frame ret ; Return ;------------------------------------------------------------------------------- ; check - Check if a number is, according to Sudoku rules, a legal candidate for ; the given cell ; ; Last update : 06/09/2005 ; Args : num (at [ebp + 8]) - Number to check ; row (at [ebp + 12]) - Cell's row index ; col (at [ebp + 16]) - Cell's column index ; Action : Return RET_FAIL if the number already appears in the row, column ; or 3x3 box the cell belongs to. Otherwise return RET_OK. ;------------------------------------------------------------------------------- check: setup_stack_frame ; Set up stack frame mov ebx, [ebp + 8] ; Store number in ebx cld ; Clear DF ;;; Row check - Point to the beginning of the row ([board] + row * SIZE) and ;;; parse it looking for the number we're checking mov esi, board ; Load board address in esi mov eax, [ebp + 0Ch] ; Load row in eax mov ecx, SIZE ; Set column counter mul cl ; eax = row offset from board add esi, eax ; esi = address of row's first cell .row_check: lodsb ; eax = number in current cell cmp al, bl ; Does the cell contain our number? je .return_fail ; If it does, return RET_FAIL loop .row_check ; Otherwise, go on to the next cell ;;; Column check - Point to the beginning of the column ([board] + col) and ;;; parse it looking for the number we're checking mov esi, board ; Store board address in esi mov eax, [ebp + 010h] ; Load col in eax add esi, eax ; esi = Column offset from board mov ecx, SIZE ; Set row counter .col_check: cmp byte [esi], bl ; Does the cell contain our number? je .return_fail ; If it does, return RET_FAIL add esi, SIZE ; Otherwise, point to the next cell loop .col_check ; and loop on each column cell ;;; Box check - Point to the top-left corner of the box the cell belongs to ;;; ([board] + (col - (col % BOX_H)) + ((row - (row % BOX_W)) * SIZE)) and ;;; parse it looking for the number we're checking mov esi, board ; Store board address in esi mov edx, eax ; edx = col mov ecx, BOX_H ; Set divisor div cl ; ah = col % BOX_H sub dl, ah ; dl = (col - (col % 3)) add esi, edx ; esi = [board] + (col - (col % 3)) mov eax, [ebp + 0Ch] ; eax = row mov edx, eax ; edx = row div cl ; ah = row % BOX_W sub dl, ah ; dl = (row - (row % 3)) mov eax, SIZE ; Set multiplicator mul dl ; eax = ((row - (row % 3)) * 9) add esi, eax ; esi = address of box's top-left corner .box_check: mov edx, ecx ; Save row counter mov ecx, BOX_W ; Set column counter .box_row_check: lodsb ; eax = number in current cell cmp al, bl ; Does the cell contain our number? je .return_fail ; If it does, return RET_FAIL loop .box_row_check ; Otherwise go on to the next row cell add esi, SIZE - BOX_W ; Point to the beginning of next row mov ecx, edx ; Restore row counter loop .box_check ; Loop on each box row xor eax, eax ; eax = RET_OK (0) jmp .return ; Number is a legal candidate for this cell .return_fail: mov eax, RET_FAIL ; Store return value in eax .return: destroy_stack_frame ; Destroy stack frame ret ; Return ;------------------------------------------------------------------------------- ; print_board - Print the Sudoku board ; ; Last update : 06/09/2005 ; Args : None ; Action : Read board rows pushing each number on the stack and print them. ; Rows are read from right to left to push printf arguments in ; reverse order ;------------------------------------------------------------------------------- print_board: setup_stack_frame ; Set up stack frame print_separator ; Print top border mov esi, board + (SIZE - 1) ; Point to the end of the first row mov ecx, SIZE ; Set rows counter .loop: std ; Set DF to load data in reverse order mov ebx, ecx ; Save the outer loop counter mov ecx, SIZE ; Set the columns counter .inloop: lodsb ; Store cell content in eax push eax ; and push it on the stack for printf loop .inloop ; Loop on each row cell push board_row ; Push format string call printf ; Print row add esp, 028h ; Clean stack print_separator ; Print separator between rows add esi, SIZE * 2 ; Point to the end of the next row mov ecx, ebx ; Restore the outer loop counter loop .loop ; Loop on each row destroy_stack_frame ; Destroy stack frame ret ; Return